Bagaimana kita tahu bahwa generasi selanjutnya akan lebih baik?

Saya diperkenalkan dengan algoritma genetika baru-baru ini oleh artikel MSDN ini , di mana ia menyebut mereka evolusi kombinatorial, tetapi tampaknya hal yang sama, dan saya berjuang untuk memahami bagaimana menggabungkan dua solusi potensial akan selalu menghasilkan solusi baru yang setidaknya sama baik seperti orang tuanya.

Kenapa begitu? Tentunya menggabungkan bisa menghasilkan sesuatu yang lebih buruk.

Sejauh yang saya mengerti, algoritma didasarkan pada konsep bahwa ketika seorang jantan dan betina dari suatu spesies menghasilkan keturunan, keturunan tersebut akan memiliki karakteristik dari kedua orang tua. Beberapa kombinasi akan lebih baik, beberapa lebih buruk dan beberapa sama baiknya. Orang-orang yang lebih baik (untuk apa pun definisi "lebih baik" adalah tepat) memiliki peluang lebih besar untuk bertahan dan menghasilkan keturunan yang memiliki karakteristik yang lebih baik. Namun, akan ada kombinasi yang lebih lemah. Mengapa ini tidak menjadi masalah dengan GA?

Algoritma genetika mencoba untuk meningkatkan pada setiap generasi dengan memusnahkan populasi. Setiap anggota dievaluasi sesuai dengan fungsi kebugaran, dan hanya sebagian dari mereka yang mendapat skor tinggi diperbolehkan untuk bereproduksi.

Anda benar, meskipun: tidak ada jaminan bahwa generasi berikutnya akan meningkat pada skor pendahulunya.

Pertimbangkan program musang Dawkins : "mengembangkan" string "Methinks it is like a weasel". Mulai dari populasi string acak, fungsi kebugaran mengevaluasi kecocokan tekstual terdekat, yang terganggu untuk menghasilkan generasi berikutnya. Dengan reproduksi crossover sederhana, dua string skor tinggi yang digabungkan dapat dengan mudah menghasilkan keturunan dengan skor lebih rendah. Bahkan mutasi acak "aseksual" dari string kebugaran tinggi tunggal dapat menurunkan kebugaran anak.

Perlu dicatat, saya pikir, ini belum tentu cacat. Dengan pencarian seperti ini, ada ide tentang maxima lokal . Seorang anggota populasi mungkin mewakili solusi yang bukan hasil optimal, tetapi merupakan yang terbaik yang dapat dicapai tanpa menjadi lebih buruk di jalan.

Bayangkan bahwa fungsi kebugaran untuk program musang tidak hanya menemukan jarak sunting, tetapi memiliki beberapa gagasan "kata", dan menguji apakah kata terakhir dari string adalah nama binatang. Setiap nama hewan mendapat skor bagus, tetapi "weasel"mendapat bonus besar.

Sekarang apa yang terjadi jika "Methinks it is like a walrus"berevolusi? Skornya bagus. Tidak sebaik string target akhir, tetapi lebih baik daripada "Methinks it is like a walrut"atau variasi dekat lainnya yang dapat dicapai dengan satu langkah mutasi.

String walrus adalah maksimum lokal, dan pencarian bisa macet di sana kecuali jika program memungkinkan skor generasi berikutnya menjadi lebih buruk.

Kami tidak tahu itu akan menjadi lebih baik, kami tahu bahwa itu tidak akan menjadi lebih buruk.

Dalam setiap generasi, tidak hanya terdiri dari jumlah elemen terbaik, tetapi juga termasuk elemen terbaik itu sendiri - klon jika Anda mau. Karena mereka masih ada, mereka akan mencetak skor yang sama seperti sebelumnya. Artinya, jika tidak ada keturunan yang lebih baik, pemenang generasi sebelumnya akan menang lagi - dan dimutasi kembali / berkembang biak.

Pertimbangkan: Dengan seorang leluhur leluhur menjadi surat, mis. A Seorang anak yang bermutasi menjadi terdefinisi dengan menambahkan nomor misalnya A1, solusi lintas-roti ditulis dengan tanda kurung di sekitar orangtua misalnya. (A1B2) Dan inti kebugaran dari setiap tulisan individual setelahnya - semakin tinggi semakin baik[12]

Untuk demonstrasi, pertimbangkan Pool 5, tempat kami menyimpan 2. yang terbaik dan isi dengan 1 mutasi masing-masing, ditambah trah silang

Generasi 1

• A [10]
• B [5]
• C [4]
• D [3]
• E [1]

Simpan A, Bkarena mereka adalah dua yang terbaik, dan isi kembali 3 slot lainnya dengan keturunan di sana

Generasi 2

• A [10]
• B [5]
• (AB) [7]
• A1 [12]
• B1 [4]

Tetap A, dan (AB), karena mereka adalah yang terbaik 2 - Ini berarti kakek Amasih akan berada di kolam karena kebanyakan anak bekerja lebih lemah

Generasi 3

• A [10]
• (AB) [12]
• (A(AB)) [14]
• A2 [8]
• (AB)1 [13]

Simpan (AB)1dan (A(AB))- kali ini tidak ada kakek nenek yang dirawat, karena dua anak mereka memukuli mereka. Tetapi jika (AB1)telah melakukan hanya sedikit lebih buruk, kita akan tetap melakukannya (AB).

Ini berlanjut sampai skor stabil. Yang menunjukkan Anda telah mencapai beberapa jenis maxima lokal (berpotensi maxima global). Salah satu alasan untuk mendeteksi ini adalah jika individu yang sama terus "dikloning" ke generasi berikutnya. (meskipun untuk masalah dimensi tinggi yang mungkin memakan waktu terlalu lama, jadi lebih baik mungkin hanya memeriksa peningkatan <toleransi tertentu)

Secara umum, algoritma genetika bekerja dengan membuat sejumlah variasi (acak) pada orang tua di setiap generasi. Kemudian beberapa fungsi seleksi diterapkan, dan keturunan yang paling cocok menurut fungsi ini bertahan. Jadi keturunannya belum tentu lebih baik karena variasinya acak, tetapi dikombinasikan dengan seleksi Anda mendapatkan peningkatan dari waktu ke waktu.

Ketika saya mempelajari algoritma genetika di perguruan tinggi dijelaskan seperti ini:

Bayangkan sebuah solusi adalah kombinasi dari "gen", di mana masing-masing gen memengaruhi seberapa baik solusinya secara keseluruhan. Ketika dua solusi dikawinkan, gen mereka diambil secara acak dari masing-masing orangtua.

Sekarang, jika gen mengarah, pada umumnya, ke solusi yang baik, frekuensinya dalam kumpulan gen meningkat. Dalam kasus ekstrim, gen akan mendominasi populasi.

Jadi ketika Anda berpikir tentang algoritma genetika (dan evolusi secara umum), Anda seharusnya tidak memikirkan individu. Anda harus memikirkan gen dan populasi secara keseluruhan. Sekalipun satu solusi "terbaik" hilang, itu tidak berarti gen itu hilang.

Ada juga ide elitisme dalam algoritma genetika. Ini berarti, solusi terbaik selalu dijaga dari generasi ke generasi. Ini mungkin mempercepat konvergensi algoritma, tetapi lebih mudah bagi algoritma untuk terjebak dalam optima lokal.

Algoritma GA tidak deterministik, mereka tidak menjamin untuk mendapatkan peningkatan dalam setiap generasi, dan mereka juga tidak menjamin untuk menemukan total optimal. Namun, fase pemilihan GA, menggunakan fungsi kebugaran, membuatnya lebih mungkin bahwa "solusi yang baik" akan bertahan.