REPRESENTASI JALUR (PATH) PADA TRAVELING SALESMAN PROBLEM UNTUK MENENTUKAN JARAK TERPENDEK MENGGUNAKAN ALGORITMA GENETIKA

Yurika Permanasari (Universitas Islam Bandung)
Ravi A. Salim (Universitas Islam Bandung)

Matematika: Jurnal Teori dan Terapan
Vol 6, No 1 (2007): Jurnal Matematika

Algoritma Genetika merupakan algoritma pencarian yang berdasarkan kepada mekanisme seleksi alam dan genetika alam. Algoritma ini merupakan salah satu alat bantu untuk memudahkan pekerjaan atau menyelesaikan suatu kasus yang dihadapi dengan tidak melibatkan seluruh populasi. Pada kasus Traveling Salesman Problem, Algoritma Genetika merepresentasikan jalur kota yang dilalui sebagai kromosom yang terdiri dari gen-gen yang merupakan kota-kota yang harus dilalui. Dengan menentukan peluang crossover dan mutasi setiap kromosom mengalami regenerasi dengan harapan sebagian besar kromosom yang baik dapat diperiksa sebagai calon jalur terbaik. Dengan menggunakan Order Crossover(OX) pada Representasi Path, kasus Traveling Salesman Problem menghasilkan nilai pendekatan optimum yang sama baik untuk data 50% maupun 100% dari total populasi. Ini menunjukkan bahwa dengan menggunakan Algoritma Genetika, sebagian sampel sudah mewakili dari seluruh solusi yang ada.Kata Kunci : Algoritma Genetika; Travelling Salesman Problem; Order Crossover