ANALISIS PERBANDINGAN ALGORITMA GENETIK DAN ALGORITMA ANT COLONY SYSTEM DALAM PENYELESAIAN TRAVELLING SALESMAN PROBLEM

Travelling Salesman Problem (TSP) yaitu sebuah masalah dimana seorang

pedagang harus membuat suatu sirkuit atau rute melalui beberapa kota, dimana

setiap kota hanya dikunjungi sekali dan dengan meminimalkan total jarak yang

dilalui. Batasannya adalah bahwa setiap kota yang dilalui hanya sekali dikunjungi,

dan pedagang tersebut harus kembali ke kota asal pada akhir perjalanannya.

Algoritma genetik adalah algoritma yang bekerja berdasarkan mekanisme

seleksi alam dan genetika alam. Ide utama dibalik algoritma ini adalah memilih

individu-individu terbaik dari sebuah populasi individu dan melakukan

rekombinasi antar individu untuk membangkitkan individu baru yang diharapkan

lebih baik dari individu sebelumnya.

Ant Colony System adalah algoritma yang menggunakan cara kerja koloni

semut untuk memecahkan masalah TSP. Pada ACS ini terdapat sekumpulan

semut yang bekerja sama untuk menentukan solusi TSP yang paling baik, semutsemut

bekerja sama melalui komunikasi tidak langsung dengan menggunakan

jejak pheromone yang disimpan pada sisi-sisi dari graph TSP.

Dari perbedaan pendekatan ini, akan dipelajari dan diperbandingkan

kemampuan masing-masing pendekatan dalam menyelesaikan travelling salesman

problem.