Pengenalan kepada algoritma genetik

Algoritma genetik adalah program yang mencari penyelesaian terbaik untuk masalah ini dengan mensimulasikan proses evolusi semulajadi seperti "survival of the fittest", lintasan kromosom dan mutasi. Artikel ini akan memperkenalkan kaedah penulisan algoritma genetik, membincangkan beberapa faktor penting yang perlu dipertimbangkan ketika menulis algoritma anda sendiri, dan memberikan beberapa contoh aplikasi praktikal algoritma genetik.

mata utama

Algoritma genetik mensimulasikan proses evolusi seperti "survival of the fittest", dan menggunakan mekanisme seperti pemilihan, crossover dan mutasi untuk mencari penyelesaian yang optimum untuk masalah kompleks.
Dalam algoritma genetik, penyelesaian yang berpotensi dinyatakan sebagai kromosom, dan kebolehgunaannya dinilai oleh fungsi kecergasan yang menentukan kebarangkalian ia dipilih untuk pembiakan.
Proses crossover menggabungkan ciri -ciri dari sepasang penyelesaian ibu bapa untuk mewujudkan anak -anak baru, sementara variasi memperkenalkan perubahan rawak dalam keturunan, dengan itu mengekalkan kepelbagaian genetik dan berpotensi menemui penyelesaian baru.
Kerana algoritma genetik dapat meneroka ruang penyelesaian yang besar dan kompleks, mereka sangat berkesan untuk masalah yang sukar untuk diselesaikan dalam kaedah carian dan pengoptimuman tradisional.
Aplikasi praktikal algoritma genetik terdiri daripada merekabentuk antena dengan ciri -ciri prestasi yang dipertingkatkan untuk mengoptimumkan reka bentuk web, yang menggambarkan kepelbagaian dan kuasa mereka dalam menyelesaikan masalah praktikal.

Retak Maklumat Tidak Diketahui

Masa adalah 2369 tahun, dan manusia telah tersebar di seluruh Laut Bintang. Anda seorang doktor muda dan pintar yang ditempatkan di pangkalan bintang yang sibuk, sibuk dengan pelancong, pedagang, dan pelanggar sekali-sekala. Tidak lama selepas anda tiba, penjaga kedai di pangkalan menjadi berminat dengan anda. Dia mendakwa dia hanya tukang jahit yang mudah, tetapi khabar angin mengatakan bahawa dia adalah ejen rahsia yang bekerja untuk rejim yang sangat jahat.

Anda mula makan tengah hari bersama -sama setiap minggu, membincangkan topik dari politik ke puisi. Walaupun selepas beberapa bulan, anda masih tidak pasti sama ada dia menyatakan perasaan romantis atau mengambil rahsia (anda pasti tidak mempunyai rahsia). Mungkin kedua -duanya.

suatu hari semasa makan tengah hari, dia mencabar anda: "Saya mempunyai mesej untuk memberitahu anda, Doktor yang dikasihi! Saya pasti tidak dapat memberitahu anda apa itu. Tetapi saya memberitahu anda, itu 12 watak panjang. Watak -watak ini boleh menjadi apa -apa Surat, ruang tulis

Anda kembali ke pejabat di kabin perubatan, masih memikirkan apa yang baru saja dia katakan. Tiba -tiba, eksperimen simulasi penjujukan gen yang pernah anda jalankan di komputer berdekatan memberi anda idea. Anda bukan pakar penyahsulitan kata laluan, tetapi mungkin anda boleh menggunakan kepakaran anda dalam genetik untuk menguraikan maklumatnya!

Beberapa teori

Seperti yang saya nyatakan pada mulanya, algoritma genetik adalah program yang menggunakan operasi yang mendorong evolusi untuk mencari penyelesaian. Selepas banyak lelaran, algoritma memilih calon terbaik (meneka) dari satu set penyelesaian yang mungkin, rekombinasi mereka, dan cek yang kombinasi menjadikannya lebih dekat dengan penyelesaiannya. Calon yang lemah akan dibuang.

Di tempat kejadian di atas, mana-mana watak dalam mesej rahsia boleh menjadi A-Z, ruang atau tanda baca asas. Katakan ini memberi kita 32 aksara "abjad" berikut: abcdefghijklmnopqrstuvwxyz -.,!? mereka betul. Ia mengambil masa terlalu lama untuk memeriksa setiap kemungkinan. Sebaliknya, algoritma genetik akan secara rawak memilih 12 aksara dan meminta tukang jahit/mata -mata untuk menilai sejauh mana hasilnya adalah maklumatnya. Ini lebih berkesan daripada carian kekerasan, kerana skor membolehkan kita menyempurnakan calon masa depan. Maklum balas membolehkan kita mengukur kecergasan setiap tekaan dan diharapkan mengelakkan masa membuang -buang waktu mati. Katakan kami membuat tiga teka -teki: HOMLK? WSRZDJ, BGK KA! QTPXC dan XELPOCV.XLF!. Calon pertama menjaringkan 248.2, yang kedua ialah 632.5, dan yang ketiga ialah 219.5. Skor cara dikira bergantung kepada keadaan, yang akan kita bincangkan kemudian, tetapi sekarang mari kita anggap ia berdasarkan sisihan antara calon dan maklumat sasaran: skor sempurna adalah 0 (iaitu tidak ada sisihan; calon dan sasarannya adalah sama), skor yang lebih tinggi bermakna sisihan yang lebih besar. Teka -teki dengan skor 248.2 dan 219.5 lebih dekat dengan kandungan maklumat rahsia daripada tekaan dengan skor 635.5. Tebakan masa depan dibuat melalui gabungan percubaan terbaik. Terdapat banyak cara untuk menggabungkan calon, tetapi sekarang kita menganggap pendekatan crossover mudah: setiap watak dalam tekaan baru mempunyai kebarangkalian 50-50 yang disalin dari calon induk pertama atau kedua. Sekiranya kita mengambil dua teka -teki HOMLK? WSRZDJ dan XELPOCV.XLF!, Maka watak pertama calon keturunan kita mempunyai kebarangkalian 50% H, kebarangkalian 50% X, dan watak kedua akan O atau E, dan, dan E, Jadi pada. Anak mungkin hello? W.RLD!.

Menjana calon baru dengan crossover

Walau bagaimanapun, jika kita hanya menggunakan nilai calon induk, mungkin ada masalah dalam pelbagai lelaran: kekurangan kepelbagaian. Jika kita mempunyai satu calon terdiri daripada semua A dan yang lain terdiri daripada semua B, maka mana -mana keturunan yang dihasilkan oleh crossover hanya terdiri daripada A dan B. Jika penyelesaiannya termasuk C, kita akan menjadi malang.

Untuk mengurangkan risiko ini dan mengekalkan kepelbagaian sementara masih menyempitkan skop penyelesaian, kita dapat memperkenalkan sedikit perubahan. Daripada melakukan segmentasi 50-50 secara langsung, kami membenarkan kebarangkalian kecil untuk menggantikan sebarang nilai dalam abjad. Melalui mutasi ini, keturunan mungkin menjadi Hello World!.

Mutasi menyimpan perkara -perkara yang segar!

Menurut jangkaan, algoritma genetik meminjam sejumlah besar perbendaharaan kata sains genetik. Oleh itu, sebelum kita membincangkan lebih lanjut, mari kita memperbaiki beberapa istilah:

• Alleles: ahli abjad genetik. Takrif alel bergantung kepada algoritma. Sebagai contoh, 0 dan 1 mungkin alel algoritma genetik yang digunakan untuk memproses data binari, dan algoritma yang digunakan untuk memproses kod boleh menggunakan penunjuk fungsi, dll. Dalam senario maklumat rahsia kami, alel adalah huruf, ruang, dan pelbagai tanda baca dalam abjad.
• Kromosom: urutan alel yang diberikan; Dalam senario kami, HOMLK? WSRZDJ, XELPOCV.XLF!
• gen: alel di lokasi tertentu dalam kromosom. Untuk kromosom homlk? Wsrzdj, gen pertama adalah h, gen kedua adalah O, gen ketiga adalah m, dan sebagainya.
• Penduduk: Koleksi satu atau lebih kromosom calon yang dicadangkan sebagai penyelesaian kepada masalah.
• Generasi: Penduduk semasa algoritma lelaran khusus. Calon dalam satu generasi menyediakan gen untuk menghasilkan generasi populasi yang akan datang.
• Kecergasan: Ukuran sejauh mana calon adalah penyelesaian yang dikehendaki. Kromosom penyesuaian lebih cenderung untuk lulus gen mereka kepada calon masa depan, sementara kromosom yang kurang menyesuaikan diri lebih cenderung dibuang.
• Pilih: Proses memilih beberapa calon untuk pembiakan (digunakan untuk membuat kromosom calon baru) dan membuang calon lain. Terdapat pelbagai strategi pemilihan yang berbeza dalam toleransi untuk memilih calon yang lebih lemah.
• Pengeluaran semula: Proses menggabungkan gen satu atau lebih calon untuk menghasilkan calon baru. Kromosom penderma dipanggil Bapa, dan kromosom yang dihasilkan dipanggil keturunan.
• Mutasi: Gen yang tidak normal secara rawak dalam keturunan untuk mencegah kehilangan kepelbagaian genetik dalam banyak generasi.

Tunjukkan beberapa kod!

Saya mengesyaki bahawa diberikan gambaran keseluruhan dan senarai istilah, anda mungkin tergoda untuk melihat beberapa kod sekarang. Oleh itu, mari kita lihat beberapa kod JavaScript yang menyelesaikan masalah maklumat rahsia kami. Semasa proses bacaan, saya menjemput anda untuk memikirkan kaedah mana yang boleh dianggap sebagai "kod boilerplate" dan pelaksanaan mana yang lebih dekat dengan masalah yang kita cuba selesaikan:

// ... (Candidate class and GeneticAlgorithm class code as provided in the original text) ...

Kami mula -mula menentukan objek data calon, hanya untuk memasangkan kromosom dengan skor kecergasan mereka. Untuk kemudahan, kaedah penyortiran statik juga dilampirkan;

Seterusnya, kami mempunyai kelas genetikalgoritma yang melaksanakan algoritma genetik itu sendiri.

Pembina menggunakan objek yang menyelesaikan pelbagai parameter yang diperlukan untuk simulasi. Ia menyediakan cara untuk menentukan abjad genetik, mesej sasaran, dan parameter lain yang menentukan kekangan di mana simulasi akan dijalankan. Dalam contoh di atas, kami menjangkakan populasi 100 calon setiap generasi. Dari ini, hanya 40 kromosom yang akan dipilih untuk pembiakan. Kami mempunyai peluang 3% untuk memperkenalkan mutasi, dan apabila ia berlaku, kami akan menukar sehingga dua gen. Nilai maxgenerations digunakan sebagai langkah perlindungan;

Perlu dinyatakan bahawa populasi, saiz pemilihan dan jumlah maksimum umur yang disediakan semasa menjalankan algoritma agak kecil. Masalah yang lebih kompleks mungkin memerlukan ruang carian yang lebih besar, yang seterusnya meningkatkan penggunaan memori algoritma dan masa yang diperlukan untuk dijalankan. Walau bagaimanapun, sangat disyorkan untuk menggunakan parameter varian yang lebih kecil. Sekiranya mereka terlalu besar, kami kehilangan apa -apa manfaat calon pembiakan berdasarkan kecergasan, dan simulasi mula menjadi carian rawak.

Kaedah seperti rawak (), init (), dan run () boleh dianggap boilerplate. Tetapi hanya kerana terdapat boilerplate tidak bermakna ia tidak akan memberi kesan praktikal terhadap simulasi. Sebagai contoh, algoritma genetik menggunakan rawak berat. Walaupun fungsi matematik terbina dalam () sesuai untuk tujuan kami, untuk isu-isu lain, anda memerlukan penjana rawak yang lebih tepat. Crypto.GetRandomValues ​​() menyediakan nilai rawak kriptografi yang lebih kuat.

Prestasi juga merupakan pertimbangan. Saya berusaha untuk menjadi jelas dan mudah difahami dalam artikel ini, tetapi ingat bahawa operasi akan diulang. Anda mungkin mendapati diri anda perlu mengoptimumkan kod mikro dalam gelung, menggunakan struktur data memori yang lebih efisien, dan menyamakan kod dan bukannya memisahkannya ke dalam fungsi/kaedah, semuanya tanpa mengambil kira bahasa pelaksanaan anda.

pelaksanaan calcfitness (), pilih (), menghasilkan semula () dan juga berhenti () adalah khusus untuk masalah yang kita cuba selesaikan.

calcfitness () mengembalikan nilai yang mengukur kecergasan kromosom berdasarkan kriteria yang diharapkan -dalam kes kami, seberapa baik ia sepadan dengan mesej rahsia. Pengiraan kecergasan hampir selalu menjadi spesifik keadaan; Sebagai contoh, saya boleh mengira jarak Hamming atau jarak levinstein antara dua nilai, dan juga menggabungkan pelbagai ukuran. Akhirnya, adalah penting bahawa fungsi kecergasan mengembalikan pengukuran yang berguna berdasarkan masalah di tangan, bukan hanya boolean "sesuai"/"tidak sesuai".

Pilih () Kaedah Menunjukkan strategi pemilihan elit -hanya calon yang paling sesuai di seluruh penduduk dipilih untuk pembiakan. Seperti yang saya nyatakan sebelum ini, terdapat strategi lain, seperti pemilihan kejohanan, yang memilih calon yang paling sesuai dari set calon individu dalam populasi, dan pemilihan Boltzmann, yang mengenakan calon yang semakin besar dan lebih besar mengenai pemilihan tekanan calon. Tujuan kaedah yang berbeza ini adalah untuk memastikan bahawa kromosom mempunyai peluang untuk menyampaikan gen yang boleh membuktikan bermanfaat kemudian, walaupun ia tidak dapat dilihat dengan segera. Penerangan mendalam tentang strategi pemilihan ini dan lain-lain, serta pelaksanaan contoh, mudah dijumpai dalam talian.

Menggambarkan pelbagai strategi pemilihan

Terdapat banyak kaedah untuk menggabungkan gen. Kod kami mencipta keturunan menggunakan crossover seragam di mana setiap gen mempunyai kebarangkalian yang sama untuk memilih dari ibu bapa. Strategi lain mungkin cenderung ke arah satu gen ibu bapa dan bukannya yang lain. Satu lagi strategi popular ialah penyeberangan K-Point, di mana kromosom dibahagikan pada titik k , menghasilkan serpihan 1 yang menggabungkan untuk menghasilkan keturunan. Persimpangan boleh diperbaiki atau dipilih secara rawak.

Keterangan Strategi Crossing K-Point

Kami tidak terhad kepada dua kromosom induk; Pertimbangkan algoritma yang mengubah imej dengan menarik poligon rawak. Dalam kes ini, kromosom kami dilaksanakan sebagai data imej. Dalam setiap generasi, imej yang paling sesuai dipilih dari penduduk sebagai ibu bapa, dan semua calon kanak -kanak dihasilkan dengan menarik poligon mereka sendiri ke salinan induk. Kromosom ibu bapa/imej adalah variasi/lukisan yang unik dari ibu bapa.

Aplikasi praktikal algoritma genetik

Algoritma genetik boleh digunakan untuk hiburan dan keuntungan. Mungkin dua contoh yang paling popular mengenai aplikasi praktikal algoritma genetik adalah antena X-band yang berkembang oleh Boxcar 2D dan NASA.

Boxcar 2D adalah simulasi yang menggunakan algoritma genetik untuk mengembangkan "kereta" terbaik yang boleh bergerak melalui medan simulasi. Kereta ini terdiri daripada lapan vektor rawak, dan menghubungkan roda ke titik rawak. Laman web projek ini boleh didapati di boxcar2d.com, yang secara ringkas memperkenalkan algoritma pada halaman tentangnya dan menyediakan senarai ranking yang menunjukkan beberapa reka bentuk terbaik. Malangnya, laman web ini menggunakan flash dan kini mungkin tidak dapat diakses oleh ramai orang - dalam kes ini, pelbagai rakaman skrin boleh didapati di YouTube jika anda ingin tahu. Anda juga mungkin ingin menyemak simulasi yang sama (cemerlang) yang ditulis oleh Rafael Matsunaga menggunakan teknologi HTML5, yang boleh didapati di rednuht.org/genetic_cars_2.

Kereta berkembang dalam Boxcar 2D, gambar dari Ranking Boxcar 2D

Pada tahun 2006, Teknologi Angkasa NASA 5 Misi menguji pelbagai teknologi baru di angkasa. Salah satu daripada teknologi ini adalah jenis antena baru yang direka menggunakan algoritma genetik. Merancang antena baru boleh menjadi proses yang sangat mahal dan memakan masa. Ia memerlukan kepakaran khas dan sering berlaku apabila perubahan permintaan atau prototaip gagal dilakukan seperti yang diharapkan. Masa penciptaan antena berkembang adalah lebih pendek, dengan keuntungan yang lebih tinggi dan penggunaan kuasa yang lebih rendah. Teks penuh kertas yang membincangkan proses reka bentuk tersedia secara percuma dalam talian (reka bentuk antena automatik menggunakan algoritma evolusi). Algoritma genetik juga telah digunakan untuk mengoptimumkan reka bentuk antena sedia ada untuk prestasi yang lebih tinggi.

Antena evolusi terbaik dalam kategori mereka, gambar adalah dari kertas reka bentuk antena automatik

algoritma genetik telah digunakan dalam reka bentuk web! Projek lanjutan oleh Elijah Mensch (mengoptimumkan reka bentuk laman web dengan menggunakan algoritma genetik interaktif) menggunakannya untuk mengoptimumkan karusel artikel berita dengan memanipulasi peraturan CSS dan kecergasan penarafan menggunakan ujian A/B.

susun atur terbaik untuk generasi pertama dan kesembilan, gambar itu berasal dari kertas pada reka bentuk laman web yang dioptimumkan

Kesimpulan

Setakat ini, anda harus mempunyai pemahaman asas tentang apa algoritma genetik dan cukup akrab dengan perbendaharaan kata mereka untuk mentafsir apa -apa sumber yang mungkin anda hadapi dalam penyelidikan anda sendiri. Walau bagaimanapun, memahami teori dan istilah hanya separuh kerja. Jika anda merancang untuk menulis algoritma genetik anda sendiri, anda juga mesti memahami masalah khusus anda. Sebelum anda memulakan, berikut adalah beberapa soalan penting untuk bertanya kepada diri sendiri:

• bagaimana saya mewakili masalah saya sebagai kromosom? Apakah alel saya yang sah?
• Adakah saya tahu apa matlamatnya? Itulah, apa yang saya cari? Adakah nilai tertentu atau sebarang penyelesaian dengan kecergasan melebihi ambang tertentu?
• Bagaimana saya mengukur kecergasan calon?
• Bagaimana saya menggabungkan dan bermutasi calon untuk menjana penyelesaian calon baru?

Saya harap saya juga membantu anda memahami bagaimana program menarik inspirasi dari alam semula jadi -bukan hanya dalam bentuk, tetapi juga dalam proses dan fungsi. Jangan ragu untuk berkongsi pemikiran anda sendiri di forum.

soalan yang sering ditanya mengenai algoritma genetik

• Apakah algoritma genetik (GA)? Algoritma genetik adalah teknik carian dan pengoptimuman heuristik yang diilhamkan oleh proses pemilihan semulajadi. Ia digunakan untuk mencari penyelesaian anggaran untuk mengoptimumkan dan masalah carian melalui prinsip -prinsip evolusi simulasi.
• Bagaimana algoritma genetik berfungsi? Algoritma genetik berfungsi dengan mengubah populasi penyelesaian calon berbanding generasi berturut -turut. Proses ini termasuk pemilihan, crossover (rekombinasi), mutasi dan menilai individu dalam populasi, yang bertujuan untuk meningkatkan kualiti penyelesaiannya.
• Apakah jenis masalah yang sesuai dengan algoritma genetik? Algoritma genetik digunakan secara meluas dan boleh digunakan untuk pelbagai masalah pengoptimuman dan carian, termasuk tetapi tidak terhad kepada penjadualan, penghalaan, pembelajaran mesin, dan pengoptimuman fungsi.
• Bagaimana untuk memilih parameter untuk algoritma genetik? Parameter seperti saiz populasi, kebolehubahan dan kadar crossover bergantung kepada ciri -ciri masalah tertentu dan ruang penyelesaian. Eksperimen dan penalaan adalah amalan biasa untuk mencari nilai parameter terbaik untuk masalah yang diberikan.
• Apakah peranan fungsi kecergasan dalam algoritma genetik? Fungsi kecergasan mengukur bagaimana penyelesaian individu dilakukan dalam masalah tertentu. Ia membimbing proses pemilihan dan memudahkan penyelesaian yang menyumbang secara positif kepada matlamat pengoptimuman.

Atas ialah kandungan terperinci Pengenalan kepada algoritma genetik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!