Algoritma Genetika - Persilangan
Dalam bab ini, kita akan membahas tentang apa itu Crossover Operator bersama dengan modul lainnya, kegunaan dan manfaatnya.
Pengantar Crossover
Operator crossover dianalogikan dengan reproduksi dan crossover biologis. Dalam hal ini lebih dari satu induk dipilih dan satu atau lebih mata air diproduksi dengan menggunakan materi genetik dari induk. Crossover biasanya diterapkan di GA dengan probabilitas tinggi -pc .
Operator Crossover
Pada bagian ini kita akan membahas beberapa operator crossover yang paling populer digunakan. Perlu dicatat bahwa operator crossover ini sangat umum dan GA Designer mungkin memilih untuk menerapkan operator crossover khusus masalah juga.
Satu Titik Crossover
Dalam perpotongan satu titik ini, titik perpotongan acak dipilih dan ekor kedua orangtuanya ditukar untuk mendapatkan pegas baru.
Crossover Multi Titik
Perpotongan multi titik adalah generalisasi dari persilangan satu titik dimana segmen bolak-balik ditukar untuk mendapatkan pegas baru.
Seragam Crossover
Dalam persilangan seragam, kami tidak membagi kromosom menjadi beberapa segmen, melainkan kami memperlakukan setiap gen secara terpisah. Dalam hal ini, kita pada dasarnya melempar koin untuk setiap kromosom untuk memutuskan apakah akan dimasukkan atau tidak pada musim semi. Kita juga bisa membiaskan koin ke satu orang tua, untuk memiliki lebih banyak materi genetik pada anak dari orang tua itu.
Rekombinasi Aritmatika Utuh
Ini biasanya digunakan untuk representasi bilangan bulat dan bekerja dengan mengambil rata-rata tertimbang dari dua orang tua dengan menggunakan rumus berikut -
- Anak1 = α.x + (1-α) .y
- Anak2 = α.x + (1-α) .y
Tentunya jika α = 0,5, maka kedua anak tersebut akan sama seperti yang ditunjukkan pada gambar berikut.
Crossover Pesanan Davis (OX1)
OX1 digunakan untuk persilangan berbasis permutasi dengan maksud untuk mentransmisikan informasi tentang pengurutan relatif ke pegas. Ini bekerja sebagai berikut -
Buat dua titik persilangan acak di induk dan salin segmen di antara keduanya dari induk pertama ke keturunan pertama.
Sekarang, mulai dari titik persilangan kedua di orang tua kedua, salin nomor yang tidak digunakan yang tersisa dari orang tua kedua ke anak pertama, melingkari daftar.
Ulangi untuk anak kedua dengan peran orang tua dibalik.
Ada banyak crossover lain seperti Partially Mapped Crossover (PMX), Order based crossover (OX2), Shuffle Crossover, Ring Crossover, dll.