Analisis Pengaruh Operator Genetik pada Algoritma Genetika dan Penerapannya pada Traveling Salesman Problem (TSP)

Main Article Content

Nuzulul Khairu Nissa
Farikhin Farikhin
Bayu Surarso

Abstract

Algoritma genetika merupakan suatu algoritma pencarian metaheuristik yang berdasar pada mekanisme seleksi alam dan operasi genetika guna diperolehnya suatu solusi. Solusi yang dihasilkan, ditentukan berdasarkan nilai parameter dan operator yang digunakan. Penentuan cara kerja dari masing-masing operator yaitu operator seleksi, crossover dan mutasi, dapat diketahui dengan menggunakan teori Schemata. Selain itu, jika diasumsikan bahwa operator crossover diabaikan, dengan maksud akan lebih ditekankan pada operator mutasi maka probabilitas dihasilkannya suatu solusi, akan meningkat. Salah satu permasalahan yang dapat diselesaikan dengan menggunakan algoritma genetika yaitu Traveling Salesman Problem (TSP). TSP merupakan suatu permasalahan optimasi, guna ditemukannya sikel Hamilton yang memiliki bobot minimum pada sebuah graf terhubung. Penelitian ini membahas penerapan algoritma genetika untuk menyelesaikan TSP pada kasus data ulysses16.tsp. Berdasarkan perhitungan dan pengujian, diperoleh nilai parameter yang menghasilkan total jarak tempuh minimal sebesar 65.169, dengan:  jumlah generasi sebesar 300, jumlah populasi sebesar 120, probabilitas crossover sebesar 0,7 dan probabilitas mutasi sebesar 0,3.

Article Details

How to Cite
Nissa, N., Farikhin, F., & Surarso, B. (2020). Analisis Pengaruh Operator Genetik pada Algoritma Genetika dan Penerapannya pada Traveling Salesman Problem (TSP). PRISMA, Prosiding Seminar Nasional Matematika, 3, 1-7. Retrieved from https://journal.unnes.ac.id/sju/index.php/prisma/article/view/37546
Section
Articles

References

Arkeman, Y., Seminar, K. B., & Gunawan, H. (2012). Algoritma Genetika, Teori dan Aplikasinya untuk Bisnis dan Industri. Bogor: PT Penerbit IPB Press.
David L. Applegate, Robert E. Bixby, Vasek Chvatal, & William J. Cook. (2006). The Traveling Salesman Problem - A Computational Study. New Jersey: Princeton University Press.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Massachusett: Addison-Wesley.
Sharapov, R.R., & Laphshin, A.V. (2006). Convergence of Genetic Algorithm. Pattern Recognition and Image Analysis, 16, 392-397.
Sutojo, T. (2011). Kecerdasan Buatan. Yogyakarta: ANDI.
Suyanto. (2005). Algoritma Genetika dalam MATLAB. Yogyakarta: Andi Offset.