Permutation Crossover (PMX)

Bagi yang sering berkecimpung di dunia Artificial Intelligent, Genetic Algorithm (GA) adalah hal yang sudah tidak asing lagi. Dengan GA kita bisa melakukan optimasi berbagai macam hal. Bagaimana menyelesaikan persamaan kuadrat sampai dengan melakukan optimasi titik. TSP, Travelling Salesman Problem, yaitu mencari jarak terpendek antar beberapa titik, adalah hal yang paling sering dikerjakan dengan menggunakan Genetic Algorithm.

Ada banyak istilah dan step yang ada dalam Genetic Algorithm. Dari mulai istilah populasi, gen, kromosom, perhitungan fitness, cross-over sampai kepada mutasi gen. Pada tulisan kali ini akan dibahas bagaimana melakukan crossover untuk TSP dan sejenisnya. Crossover pada prinsipnya adalah melakukan pertukaran, dimana dalam GA pertukaran yang dimaksud adalalah pertukaran gen dalam kromosom. Karena gen yang mewakili sebuah titik dalam sebuah kromosom tidak boleh sama, maka teknik crossover yang digunakan adalah teknik permutaion crossover.

Prinsip utama dari crossover yang dibahas disini adalah melakukan pertukaran dimulai dari setelah gen cutpoint. Perhatikan contoh di bawah.

Semisal titik cutpoint adalah 3. Sedangkan yang mau dicross adalah Kromosom 1 dan Kromosom 2.

posisi gen

cutpoint 3 berarti proses pertukaran dimulai dari gen 4 seterusnya. Sehingga menjadi :

setelah di tukar

Sekarang terlihat kombinasi gen ada yang sama. Hal ini tidak tepat untuk masalah TSP atau penyelesaian titik-titik yang tidak bisa double. Untuk itu kita harus melakukan mapping masing-masing gen yang tidak mengalami pertukaran, dengan pola pertukaran tadi (warna kuning).

Pola yang didapat adalah : 1 ditukar 4 dan 3 ditukar 5. Artinya, jika isi gennya adakah angka 1 maka isi nya diubah menjadi angka 4. Hasilnya :

Setelah dimapping

Sekarang, kombinasi gen sudah tidak ada yang kembar.

Teknik ini dikenal dengan permutaion crossover atau Partition-Mapping Crossover (PMX). Berikut adalah contoh prosedur yang dibuat dengna Borland Delphi 7 :

Prosedur PMX Delphi