Mengapa memiliki nilai crossover yang bukan 0,5?

8

Sebagian besar literatur yang pernah saya baca tentang GA menyarankan menggunakan nilai crossover sekitar 0,7, jadi Anda mengambil 70% pertama dari satu gen kromosom, dan 30% terakhir dari yang lain untuk menghasilkan satu kromosom baru.

Jika Anda memilih kromosom induk dengan mengambil dua teratas (peringkat berdasarkan kebugaran), maka saya dapat melihat logikanya di sini, karena Anda memberi bobot lebih pada gen kromosom yang berperingkat lebih tinggi. Namun, jika Anda menggunakan metode stokastik (seperti roda roulette) untuk memilih orang tua, lalu apa gunanya menggunakan apa pun selain 0,5 sebagai nilai crossover? Mengingat Anda telah memilih kromosom A dan B sebagai orang tua, Anda juga cenderung memilih A pertama dan B kedua sebagai B pertama dan A kedua bukan?

Saya hanya benar-benar menulis satu GA sejauh ini (masih jauh di bagian bawah kurva pembelajaran, tetapi bergerak cepat berkat bantuan besar di sini!), Tetapi percobaan pada acara itu menunjukkan bahwa 0,5 memberikan konvergensi yang lebih cepat ke solusi daripada nilai lainnya.

Atau apakah saya melewatkan sesuatu?

genetic-algorithms Avrohom Yisroel
sumber
2
Most of the literature I've read about GAs suggests using a crossover value of around 0.7<- satu hal yang perlu diingat adalah banyak dari nilai-nilai ini dalam optimasi heuristik diturunkan lebih atau kurang berdasarkan pada nilai-nilai apa yang tampaknya mengarah pada hasil yang baik (daripada derivasi empiris). Saya kurang terbiasa dengan GA tetapi saya tahu dalam metode optimasi berbasis populasi lainnya konstanta ditentukan secara sewenang-wenang, dalam beberapa peneliti melakukan beberapa percobaan dasar, menemukan nilai-nilai yang bekerja lebih baik, dan kemudian nilai-nilai itu diadopsi oleh komunitas optimisasi pada umumnya .
enderland
1
Selain itu, saya tidak begitu yakin mengapa pertanyaan ini tidak dipilih - sepertinya cocok untuk topik dan ruang lingkup.
enderland
1
Saya tidak akan khawatir tentang downvote ... Saya mendapatkannya di hampir setiap posting yang saya buat di sini.
Robert Harvey
2
@enderland: akankah Anda mengatakan lebih jauh karena nilai-nilai tersebut bermutasi secara acak dan kombinasi yang paling baik bertahan? ;-)
Jörg W Mittag
2
Saya juga menambahkan bahwa nilai crossover Anda tidak harus tetap statis - karena bagian dari tujuan GA adalah untuk mendapatkan banyak varian untuk menjelajahi banyak jalur, itu bisa menjadi pilihan untuk memilih nilai crossover acak antara, katakanlah, 0,5 dan 0,8. Terutama jika Anda tidak harus menggunakan pengambilan deterministik.
Delioth

Jawaban:

5

Operasi crossover yang ideal sangat tergantung pada ruang masalah. Asumsi yang mendasari algoritma evolusi dan genetik adalah bahwa dua solusi yang baik kadang-kadang dapat digabungkan menjadi solusi yang lebih baik - solusi yang baik terlihat mirip dengan solusi yang baik lainnya. Secara intuitif ini masuk akal jika ruang masalah memiliki satu optimum yang dapat digunakan oleh setiap generasi berturut-turut.

Ketika ada beberapa optima, ruang di antara optima ini secara definisi tidak optimal. Jika kita mengambil kromosom A yang mendekati satu optimum dan menggabungkannya dengan kromosom B dari dekat optimal lain, kita akan mendarat di antaranya, dan kemungkinan akan memiliki kromosom c yang dihasilkan yang lebih buruk daripada orang tuanya. Tinggal lebih dekat dengan satu atau orang tua lain meningkatkan kemungkinan mendapatkan kromosom yang lebih baik atau setidaknya tidak jauh lebih buruk daripada orang tua.

     _                d         ^ fitness
    / \              d \        |
   /   A            B   \       |
__/     \___ccc___dd     \____  |
-----------------------------------> chromosome space
     |                |
     |     valley     |
     |     of "meh"   |
1. optimum         2. optimum

Nilai crossover hanyalah satu parameter algoritma yang dapat Anda sesuaikan dengan struktur masalah Anda. Terkadang Anda akan melihat konvergensi yang lebih cepat dengan nilai crossover yang rendah, terkadang dengan nilai crossover yang sangat tinggi. Tetapi untuk nilai yang sangat tinggi, ini akan kurang seperti crossover tetapi hanya sedikit perubahan seperti mutasi. Jadi, alih-alih menggunakan nilai dekat 1.0, Anda lebih suka mengurangi tingkat crossover dan meningkatkan tingkat mutasi.

amon
sumber
@amon Terima kasih atas penjelasannya. Saya kira seperti pada sebagian besar barang ini, ini merupakan kasus bermain-main untuk melihat apa yang berhasil dalam situasi tertentu
Avrohom Yisroel
Ini membuat saya berpikir bahwa mungkin tingkat crossover harus dipilih secara acak setiap kali.
Tanyakan Tentang Monica
2

Yang membingungkan, tingkat crossover dan tingkat mutasi, sementara diberi nama yang sama, biasanya ditafsirkan berbeda.

Tingkat mutasi x% ==> Anda melakukan operator mutasi dengan probabilitas 1.0, dan setiap aplikasi dari operator itu akan mengubah x% dari bit individu yang bermutasi.

Tingkat crossover x% ==> Anda memilih untuk melakukan crossover sama sekali dengan probabilitas x.

Jadi tingkat crossover 70% tidak berarti Anda mengambil 70% bit dari induk 1 dan 30% dari induk 2. Ini berarti bahwa Anda akan melakukan operator crossover apa pun yang telah Anda pilih 70% dari waktu. 30% sisanya, Anda akan melewati orang tua yang tidak dimodifikasi ke kolam keturunan.

deong
sumber
Terima kasih balasannya. Mungkin saya tidak menjelaskan diri saya dengan jelas, tetapi beginilah cara saya memahami keduanya. Saya tidak bertanya tentang mutasi sama sekali, hanya tentang crossover.
Avrohom Yisroel