PERBANDINGAN ALGORITMA GENETIKA FIX DENGAN ALGORITMA GENETIKA ADAPTIF PADA TRAVELLING SALESMAN PROBLEM

Abstract

Travelling salesman problem(TSP) adalah permasalahan seorang salesman yang harus mengunjungi beberapa kota tepat satu kali dan harus kembali ke kota asalnya. Salah satu algoritma yang biasa digunakan adalah metode heuristik, seperti algoritma genetika. Algoritma genetika bekerja dengan membangkitkan beberapa solusi secara random kemudian melakukan crossover dan mutasi untuk mencari solusi yang lebih baik pada setiap generasinya. Pada algoritma genetika biasa, jumlah populasi, probabilitas crossover dan probabilitas mutasi yang digunakan tidak berubah (fix) sepanjang waktu. Pengembangan algoritma genetika yaitu algoritma genetika adaptif, dimana jumlah populasi, probabilitas crossover dan probabilitas mutasi yang digunakan bisa berubah secara adaptif sesuai dengan perubahan ratarata fitness seluruh populasi. Tujuan dari penelitian ini adalah membandingkan penerapan algoritma genetika fix dan adaptif pada kasus TSP. Dari 30 kali percobaan yang dilakukan, algoritma genetika adaptif memberikan solusi yang lebih baik daripada algoritma genetika fix. Fitness terbaik yang diperoleh pada algoritma genetika adaptif adalah 1,07 x 10^-5 dan fitness rata-rata 7,58 x 10^-6. Sedangkan fitness terbaik yang diperoleh pada algoritma genetika fix adalah 1,01 x 10^-5 dan fitness rata-rata 7,66 x 10^-6. Waktu rata-rata algoritma genetika adaptif adalah 207 milidetik, sedangkan algoritma genetika fix 99 milidetik.