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

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.