Mengapa individu dengan kebugaran rendah memiliki kesempatan untuk bertahan hidup ke generasi berikutnya?

Saat ini saya membaca dan menonton tentang algoritma genetika dan saya merasa sangat menarik (saya belum memiliki kesempatan untuk mempelajarinya ketika saya masih di universitas).

Saya mengerti bahwa mutasi didasarkan pada probabilitas (keacakan adalah akar dari evolusi) tetapi saya tidak mengerti mengapa bertahan hidup.

Dari apa yang saya pahami, seorang individu $I$ memiliki kebugaran $F(i)$ seperti untuk individu lain $J$ memiliki kebugaran $F(j)$ kita memiliki $F(i) > F(j)$ , maka $I$ memiliki probabilitas yang lebih baik daripada $J$ untuk bertahan hidup ke generasi berikutnya.

Probabilitas menyiratkan bahwa $J$ dapat bertahan dan $I$ mungkin tidak (dengan "nasib buruk"). Saya tidak mengerti mengapa ini bagus sama sekali? Jika $I$ akan selalu bertahan seleksi, apa yang akan salah dalam algoritma? Dugaan saya adalah bahwa algoritme akan serupa dengan algoritme serakah tetapi saya tidak yakin.

Gagasan utamanya adalah bahwa dengan membiarkan individu suboptimal bertahan hidup, Anda dapat beralih dari satu "puncak" dalam lanskap evolusi ke yang lain melalui serangkaian mutasi bertahap kecil. Di sisi lain, jika Anda hanya diizinkan untuk menanjak maka diperlukan mutasi raksasa dan tidak mungkin untuk beralih dari puncak.

Berikut adalah diagram yang menunjukkan perbedaan:

Praktis, properti globalisasi ini adalah titik sellling utama dari algoritma evolusioner - jika Anda hanya ingin mencari maxima lokal, ada teknik khusus yang lebih efisien. (mis., L-BFGS dengan gradien perbedaan terbatas dan pencarian garis)

Di dunia nyata evolusi biologis, membiarkan individu suboptimal untuk bertahan hidup menciptakan ketahanan ketika lanskap evolusi berubah. Jika setiap orang terkonsentrasi di puncak, maka jika puncak itu menjadi lembah, seluruh populasi mati (mis., Dinosaurus adalah spesies yang paling cocok sampai terjadi pemogokan asteroid dan lanskap evolusi berubah). Di sisi lain, jika ada keragaman dalam populasi maka ketika lanskap berubah sebagian akan bertahan.

Jawaban Nick Alger sangat bagus, tetapi saya akan membuatnya sedikit lebih matematis dengan satu contoh metode, metode Metropolis-Hastings.

$i$$j$$Q(i,j)$$Q(i,j) = Q(j,i)$$F(i)>0$$i$ ; jika Anda tidak memiliki kebugaran dalam model Anda, Anda dapat memperbaikinya dengan menambahkan epsilon kecil di mana-mana.

$i$$j$

Dengan kata lain, jika lebih pas, kami selalu mengambilnya, tetapi jika kurang pas, kami bawa dengan probabilitas , kalau tidak kita coba lagi sampai kita menerima mutasi.$j$$j$$\frac{F(j)}{F(i)}$

Sekarang kami ingin menjelajahi , probabilitas aktual bahwa kami beralih dari ke .$P(i,j)$$i$$j$

Jelas itu:

Anggap saja . Kemudian = 1, dan karenanya:$F(j) \ge F(i)$$\min\left(1, \frac{F(j)}{F(i)}\right)$

Menjalankan argumen ke belakang, dan juga memeriksa kasus sepele di mana , Anda dapat melihat bahwa untuk semua dan :$i=j$$i$$j$

Ini luar biasa karena beberapa alasan.

Probabilitas transisi independen dari . Tentu saja, mungkin perlu beberapa saat bagi kita untuk menjadi penarik, dan mungkin perlu waktu bagi kita untuk menerima mutasi. Setelah kita lakukan, probabilitas transisi sepenuhnya tergantung pada , dan bukan pada .$Q$$F$$Q$

Menyimpulkan semua yang berikan:$i$

Jelas harus berjumlah jika Anda menjumlahkan semua (yaitu, probabilitas transisi dari satu negara harus berjumlah ), sehingga Anda mendapatkan:$P(j,i)$$1$$i$$1$

Yaitu, adalah fungsi kepadatan probabilitas (tidak normal) yang menyatakan metode yang dipilih. Anda tidak hanya dijamin untuk menjelajahi seluruh lanskap, Anda melakukannya sesuai dengan seberapa "pas" masing-masing negara.$F$

Tentu saja, ini hanya satu contoh dari banyak; seperti yang saya catat di bawah ini, kebetulan merupakan metode yang sangat mudah dijelaskan. Anda biasanya menggunakan GA bukan untuk menjelajahi pdf, tetapi untuk menemukan ekstrem, dan Anda dapat bersantai beberapa kondisi dalam kasus itu dan masih menjamin konvergensi akhirnya dengan probabilitas tinggi.

Keuntungan menggunakan GA adalah bahwa Anda dapat menjelajahi ruang pencarian yang lebih luas dengan mengikuti jalur yang berasal dari kandidat yang berpotensi lebih buruk. Seharusnya ada kandidat yang lebih buruk yang berhasil untuk mengeksplorasi berbagai bidang pencarian ini, tidak banyak tetapi pasti beberapa. Jika Anda mulai mengambil hanya yang terbaik setiap kali Anda menghapus aspek eksplorasi dari algoritma ini dan itu menjadi lebih dari seorang pendaki bukit. Juga hanya memilih yang terbaik secara konstan dapat mengarah pada konvergensi dini.

Sebenarnya, algoritma pemilihan mengambil kedua pendekatan. Satu cara adalah apa yang Anda sarankan dan yang lainnya adalah bahwa individu dengan kebugaran tinggi dipilih dan mereka yang lebih rendah tidak.

Pendekatan yang Anda pilih untuk pemilihan juga disesuaikan dengan masalah yang Anda coba modelkan. Dalam percobaan di sekolah, kami mencoba mengembangkan pemain kartu dengan membuat mereka bermain satu sama lain (yaitu pemilihan turnamen ). Dalam skenario seperti itu, kita bisa saja selalu lebih menyukai daripada (dari contoh Anda) karena aspek 'keberuntungan' sudah ada dalam permainan itu sendiri. Bahkan jika untuk setiap dua dan , dalam setiap babak tertentu, murni dengan cara tangan diberikan dan bagaimana orang lain bermain, bisa memenangkan putaran dan dengan demikian kita bisa berakhir dengan$I$$J$$F(i) > F(j)$$I$$J$$J$$F(j) > F(i)$. Perlu diingat bahwa suatu populasi seringkali cukup besar sehingga seseorang dapat kehilangan beberapa individu yang baik dan secara keseluruhan, itu tidak masalah.

Karena GAS dimodelkan di sekitar evolusi dunia nyata, ketika distribusi probabilistik digunakan, mereka terutama dimodelkan di sekitar bagaimana komunitas nyata berevolusi di mana kadang-kadang individu dengan kebugaran lebih rendah dapat bertahan hidup sedangkan individu dengan kebugaran lebih tinggi mungkin tidak (analogi kasar: kecelakaan mobil, alami bencana dll :-)).

itu sangat sederhana, dari satu pov: kadang-kadang solusi "anak" yang lebih tinggi kebugaran dapat lahir dari solusi "orang tua" yang lebih rendah kebugaran baik melalui crossover atau mutasi (yang sebenarnya banyak teori tentang algoritma genetika). jadi secara umum orang ingin mencari / membawa solusi kebugaran yang lebih tinggi tetapi terlalu menekankan pada pemeliharaan / pemeliharaan hanya solusi kebugaran tinggi yang dapat menyebabkan terjebak dalam minimum lokal dan tidak mencari "lanskap evolusi" yang besar. sebenarnya seseorang dapat membuat "batas kebugaran yang lebih tinggi" untuk bertahan hidup seketat atau longgar seperti yang diinginkan & bereksperimen dengan bagaimana hal itu memengaruhi kualitas solusi akhir. baik strategi cutoff yang terlalu ketat atau terlalu longgar akan mengarah pada solusi akhir yang lebih rendah. tentu saja semua ini memiliki beberapa hubungan dengan evolusi biologis nyata. ada lagi "