Proses Rekombinasi pada algoritma genetika

Proses rekombinasi atau yang lebih dikenal dengan nama proses crossover adalah menyilangkan dua kromosom sehingga membentuk kromosom baru yang harapannya lebih baik dari pada induknya. Tidak semua kromosom pada suatu populasi akan mengalami proses rekombinasi. Kemungkinan suatu kromosom mengalami proses rekombinasi  didasarkan pada probabilitas crossover yang telah ditentukan terlebih dahulu. Probabilitas crossover menyatakan peluang suatu cromosom akan mengalami crossover. Ada beberapa teknik rekombinasi yang dapat digunakan untuk menyelesaikan Traveling Salesman Problem, antara lain adalah partially mapped crossover (PMX), order crossover dan cycle crossover. Teknik rekombinasi yang digunakan adalah teknik order crossover. Order crossover (OX) diperkenalkan oleh Davis [3]. Teknik ini diawali dengan membangkitkan dua bilangan acak. Kemudian gen yang berada diantara kedua bilangan acak akan disalin ke offspring dengan posisi yang sama. Langkah berikutnya untuk mendapatkan offspring pertama adalah mengurutkan gen yang berada pada parent kedua dengan urutan gen yang berada pada posisi setelah bilangan acak kedua diikuti dengan gen yang berada pada posisi sebelum bilangan acak pertama dan diakhiri dengan gen yang berada pada posisi diantara kedua bilangan acak. Kemudian gen yang telah diurutkan tersebut dibandingkan dengan offspring pertama. Apabila gen tersebut ada pada offspring kedua maka abaikan gen tersebut dari urutan itu. Kemudian masukkan urutan yang baru saja didapat pada offspring dengan cara memasukkan urutan gen pada posisi setelah bilangan acak kedua terlebih dahulu dan sisanya dimasukkan pada posisi sebelum bilangan acak pertama. Begitu juga untuk menghasikan offspring kedua. Contoh order crossover adalah sebagai berikut
p1 = (1 2 3 | 4 5 6 7 | 8 9)
p2 = (4 5 2 | 1 8 7 6 | 9 3)
=> copy the selected segments
o1 = (x x x | 4 5 6 7 | x x)
o2 = (x x x | 1 8 7 6 | x x)
=> the seq of p2 : 9-3-4-5-2-1-8-7-6
remove 4, 5, 6, 7 in the seq and put it in o1 the
remaining seq : 9-3-2-1-8
o1 = (x x x | 4 5 6 7 | x x) = (2 1 8 | 4 5 6 7 | 9 3)
construct o2 in the same way:
o2 = (3 4 5 | 1 8 7 6 | 9 2)

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s