Penerapan Algoritme Genetik Pada Travellino Salesman Problem Naviansony Tandriarto

Abstract

Trm'elling salesman problem (TSP) mcrupakan permasalahan klasik yang sering kita temui. TSP mencari rute terpendck dari scbuah graph lcngkap tak berarah dcngan N titik. Dengan scmakin besar nilai N, diperlukan adanya algoritma aproksimasi yang mampu mencmukan nilai mendckati optimal dengan waktn komputasi yang wajar. . Algoritmc genetik mcrupakan algoritme yang dikembangkan dengan ide yang berasal dari teori evolusi. Segugus soIusi yang memungkinkan untuk suatu pennasalahan, atau disebutjuga dengan populasi masuk ke dalam proses evolusi tcrsimulasi. Pada setiap generasi, solusi yang relatif buruk akan mati, scmentara solusi yang relatifbaik akan bereproduksi dengan operator rckombinasi dan mutasi ke generasi bcrikutnya. Algoritmc gcnctik klnsik dcngan rcprcscntasi biner gagal dalam mcrcprcscntasikan TSP, karena akan menghasilkan tur yang tidak benar. Bentuk represcntasi gcnetik yang coeok untuk TSP adalah rcpresentasi path. Beberapa operator yang dikembangkan untuk representasi path adalal! operator partia/(v-mapped, operator ordered, dan operator cyclic. Penelitian ini meneoba memberi soIusi mendekati optimal bagi TSP dengan mengaplikasikan algoritme genetik. Karena telah ada beberapa algoritme aproksimasi untuk TSP, maka penelitian ini meliputi juga penggunaan algoritme aproksimasi lainnya untuk melihat pengaruh yang ditimbulkan. Algoritme aproksimasi yang digllnakan adalah algoritmc hil/climhing 2-opt. Algoritme genctik !l1urni dan algorilme genctik hibrid dilljieoba sebanyak 10 kali untuk masing-masing operator pada 9 data kota yaitu pr76, kroAIOO, pr124, kroAl50, u159, kroA200, pr226, pr264, dan a280. Hasil yang dieapai oleh algoritme genetik dengan menggunakan operator ordered merupakan yang terbaik dibanding kedua operator lainnya. Nilai persentase keoptimalan tertinggi pada pr76 dengan 62%. Hasil yang dieapai algoritme genetik hibrid menunjukkan tingkat persentase kenaikan keoptimalan yang ckstrim, meneapai 50% lebih. Operator ordered tetap lebih unggul dibanding kedua operator lainnya, dengan tingkat keberhasilan 100%.