Algoritma Genetika (genetic algorithm) dan TSP problem

Algoritma genetik adalah suatu metode yang baru ditemukan pada abad ke 20. Algoritma genetika ditemukan oleh john holland prinsip dari algoritma genetika terinspirasi dari proses seleksi alam seperti teori yang di kemukakan oleh Darwin. Dalam algoritma genetika juga dapat disebut sebagai metode pencarian yang pararel. konsep dari algoritma genetika adalah penyeleksi individu - individu dimana tiap-tiap individu mewakili sebuah solusi dari permasalahan yang diberikan. Dalam algoritma genetika terdapat dua operator utama yaitu, crossover dan  mutasi. 

Salah satu permasalahan yang dapat diselesaikan oleh algoritma genetika adalah masalah travelling salesmen problem (TSP problem). Inti dari masalah TSP ini adalah untuk menemukan rute tercepat untuk menelusuri beberapa kota dimana satu kota hanya dikunjungi satu kali.

Gambar diatas digambarkan ada 4 kota yang saling terhubung, maka akan dicari susunan kota yang akan dikunjungi dengan harapan dapat meminimumkan jarak yang ditempuh.

Pada gambar 2 akan dicari jarak terpendek dari 8 kota. kita akan generate individu-individu yang akan jadi kandidat solusi dimana tiap2 kormosom berisi gen dengan susunan kota yang akan dikunjungi, misal didifinisikan funsi fetness adalah jumlah jarak yang ditempuh dari kunjungan 8 kota. salah satu conoh kromosom adalah sebaai berikut (1,2,4,3,5,6,8,7). kita akan melakukan crossover dan mutasi namun kalau melakukan crossover biasa kita akan kesulitan karena dapat menghilangkan kunjungan kesalah satu kota dan ada kota yang di kunjungi lebih dari sekali. Solusinya kita akan melakukan order crossover. langkahnya sebagai berikut.

parent 1 : (1 2 | 3 5 4 7| 6 8)

parent 2 : (2 3 | 1 4 5 6 |7 8)

kemudian O1 nya : (- - | 3547|--)

dan O2 nya (--|1456|--)

kemudian susunan q nya 78231456 kemudian eliminasi 3 5 4 7 sehingga tersisa 8216 sehingga :

O1 : (16354782 )

dengan cara serupa untuk O2 didapat : ( 37145682)  

sehingga dengan melakukan crossover dan mutasi selama beberapa generasi akan dihasilkan solusi terbaik misalnya setelah generasi ke tujuh didapat susunan 61253478 misalnya dengan jarak minimum 20 km.