Mengapa cross-over menjadi bagian dari algoritma genetika?

Algoritma Genetika telah menjadi perhatian saya baru-baru ini ketika mencoba untuk memperbaiki / meningkatkan lawan komputer untuk permainan komputer strategi berbasis giliran.

Saya menerapkan Algoritma Genetika sederhana yang tidak menggunakan cross-over, hanya beberapa mutasi acak. Tampaknya berhasil dalam kasus ini, jadi saya mulai berpikir:

Mengapa cross-over menjadi bagian dari algoritma genetika? Bukankah mutasi saja sudah cukup?

_{Ini dari dump data di situs AI lama. Penanya memiliki UID 7.}

Mutasi biasanya didefinisikan sebagai operator global , yaitu mutasi iterated (akhirnya) mampu mencapai setiap titik dalam ruang vektor yang ditentukan oleh genom. Dalam pengertian itu, mutasi saja sudah pasti 'cukup'.

Mengenai motivasi untuk crossover - dari Essentials of Metaheuristics , p42 :

Crossover awalnya didasarkan pada premis bahwa individu-individu yang sangat fit sering kali memiliki sifat-sifat tertentu, yang disebut building blocks . Sebagai contoh, pada individu boolean 10110101, mungkin *** 101 * 1 mungkin merupakan blok bangunan

(di mana * berarti "0 atau 1")

Jadi idenya adalah bahwa crossover bekerja dengan menyebarkan blok bangunan dengan cepat ke seluruh populasi.

Metode crossover juga mengasumsikan bahwa ada beberapa derajat keterkaitan antara gen pada kromosom: yaitu, pengaturan untuk gen tertentu dalam kelompok sangat berkorelasi dengan peningkatan kebugaran. Sebagai contoh, gen A dan B mungkin berkontribusi pada kebugaran hanya ketika keduanya diatur ke 1: jika keduanya diatur ke 0, maka fakta bahwa yang lain diatur ke 1 tidak melakukan apa-apa.

Perhatikan juga bahwa crossover bukan operator global . Jika satu-satunya operator adalah crossover maka (juga dari p42):

Akhirnya populasi akan bertemu, dan seringkali (sayangnya) bertemu secara prematur, dengan salinan dari individu yang sama. Pada tahap ini tidak ada jalan keluar: ketika seseorang menyeberang dengan dirinya sendiri, tidak ada hal baru yang dihasilkan.

Untuk alasan ini, crossover umumnya digunakan bersama dengan beberapa operator mutasi global.

Crossover memungkinkan untuk menggabungkan dua orangtua (vs. mutasi, yang hanya menggunakan satu orangtua). Dalam beberapa kasus, ini berguna (misalnya, jika Anda melatih bot FPS, jika satu orangtua pandai menembak dan orangtua lain pandai bergerak, masuk akal untuk menggabungkannya). Dalam beberapa kasus lain, tidak.

Ketika berpikir tentang crossover, penting untuk memikirkan lanskap kebugaran.

Pertimbangkan skenario hipotetis di mana kami menerapkan algoritma genetika untuk menemukan solusi yang berkinerja baik pada 2 tugas. Ini bisa dari contoh Franck (bergerak dan menembak) untuk AI, atau mungkin bisa diprediksi 2 output dalam skenario pembelajaran mesin genetika, tetapi sebenarnya sebagian besar skenario di mana GAS diterapkan adalah sama (bahkan dalam menyelesaikan satu tugas, mungkin ada menjadi aspek tugas yang berbeda untuk ditangani).

Misalkan kita memiliki seorang individu, 1, yang berkinerja cukup baik di kedua tugas, dan kami menemukan serangkaian mutasi yang menghasilkan 2 individu baru, 2 dan 3, yang berkinerja lebih baik daripada Individu 1 pada tugas 1 dan 2 masing-masing. Sekarang, meskipun keduanya merupakan peningkatan, idealnya kami ingin menemukan solusi yang umumnya baik, jadi kami ingin menggabungkan fitur-fitur yang kami temukan bermanfaat.

Di sinilah crossover masuk; dengan menggabungkan genom Individu 2 dan 3, kita dapat menemukan beberapa individu baru yang menghasilkan campuran kinerja mereka. Meskipun ada kemungkinan bahwa individu tersebut dapat dihasilkan oleh serangkaian mutasi yang diterapkan pada Individu 2 atau Individu 3, lanskap mungkin tidak cocok dengan ini (misalnya, mungkin tidak ada mutasi yang menguntungkan ke arah itu).

Anda sebagian karena itu benar; Terkadang, manfaat crossover dapat direplikasi dengan serangkaian mutasi. Kadang-kadang ini mungkin tidak terjadi dan crossover dapat memuluskan lanskap kebugaran GA Anda, mempercepat optimasi dan membantu GA Anda keluar dari optima lokal.