PENERAPAN ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM

Dalam dunia yang serba praktis, diperlukan suatu algoritma cepat untuk mencari suatu solusi yang mendekati solusi optimal, tetapi tidak memerlukan waktu yang lama. Algoritma genetika adalah salah satu algoritma alternatif yang dapat digunakan sebab prosesnya cepat dan memberikan hasil yang diinginkan. Selain itu, algoritma genetika juga mampu memberikan suatu solusi pada waktu kapanpun.

Bagaimana algoritma genetika dapat menyelesaikan TSP yaitu solusi direpresentasikan ke dalam suatu kromosom yang berisi dari nomor urut kota-kota selain kota asal. Masing-masing nomor urut tidak boleh muncul lebih dari satu kali di dalam kromosom sehingga satu kromosom merepresentasikan satu rute perjalanan (satu solusi) yang valid.

Bentuk representasi dari persoalan yang akan digunakan

Berikut contoh persoalan yang diselesaikan dengan menggunakan algoritma genetika.!

Terdapat 5 buah kota yang akan dilalui oleh seorang pedangang keliling, misalnya Kota A,B,C,D,E. Perjalanan dimulai dari kota A dan berakhir di kota A. Jarak antar kota diperlihatkan pada graf di bawah ini:

Persoalan tersebut akan diselesaikan dengan menggunakan algoritma genetika. Kriteria berhenti ditentukan terlebih dahulu yaitu apabila setelah dalam beberapa generasi berturut-turut diperoleh nilai fitness yang terendah tidah berubah. Pemilihan nilai fitness yang terendah sebagai syarat karena nilai tersebut yang merepresentasikan jarak terdekat yang dicari pada persoalan ini.

Ada 4 kota yang akan menjadi gen dalam kromosom yaitu kota-kota selain kota asal.

Inisialisasi

Misalkan kita menggunakan 6 buah populasi dalam satu generasi, yaitu

Evaluasi kromosom

Kita akan menghitung nilai fitness dari tiap kromosom yang telah dibangkitkan:

Seleksi kromosom

Oleh karena pada persoalan TSP yang diinginkan yaitu kromosom dengan fitness yang lebih kecil akan mempunyai probabilitas untuk terpilih kembali lebih besar maka digunakan inverse.

Dari probabilitas di atas dapat terlihat bahwa kromosom ke-1 mempunyai fitness paling kecil mempunyai probabilitas untuk terpilih pada generasi selanjutnya lebih besar dari kromosom lainnya.

Untuk proses seleksi kita menggunakan rouletewheel, untuk itu kita terlebih dahulu menghitung persentasi dari masing-masing kromosom.

Proses roulete-wheel adalah membangkitkan nilai acak R antara 0-1. Jika R[k]<Qk[k] maka kromosom ke-k sebagai induk, selain itu pilih kromosom ke-k sebagai induk dengan syarat Qk[k-1] < R[k] < Qk[k]. Kita putar roulete-wheel sebanyak jumlah kromosom yaitu 6 kali (membangkitkan bilangan acak R).

Crros over ( Pindah Silang )

Pindah silang pada TSP dapat diimplementasikan dengan skema order crossover. Pada skema ini, satu bagian kromosom dipertukarkan dengan tetap menjaga urutan kota yang bukan bagian dari kromosom tersebut. Kromosom yang dijadikan induk dipilih secara acak dan jumlah kromosom yang dicrossover dipengaruhi oleh parameter crossover probability (ρc).

Mutasi

Pada kasus TSP ini skema mutasi yang digunakan adalah swapping mutation. yaitu teknik saling menukarkan antara satu gen dengan gen yang lain dalam satu individu. Algoritmanya adalah sebagai berikut:

Bangkitan dua bilangan random (antara 0 sampai panjang kromosom) untuk setiap individu, sebanyak jumlah individu dalam populasi. Tukarkan gen dengan lokasi kedua bilangan tersebut dengan cara:

Proses algoritma genetik untuk 1 generasi telah selesai. Maka nilai fitness setelah 1 generasi adalah:

Sebelumnya telah ditentukan kriteria berhenti yaitu bila setelah dalam beberapa generasi berturut-turut diperoleh nilai fitness yang terendah tidak berubah. Pada 1 generasi telah terlihat bahwa terdapat nilai fitness terkecil yang tidak berubah. Apabila perhitungan dilanjutkan hingga ke generasi ke-N maka diyakinkan bahwa nilai fitness yang terendah tetap tidak akan berubah. Walaupun perhitungan cukup dijabarkan hingga generasi ke-1 saja namun solusi yang mendekati optimal telah didapatkan. Oleh karena itu, terbukti bahwa algoritma genetika dapat menyelesaikan persoalan.

SEMOGA BERMANFAAT