Algoritma genetika dijelaskan
Evolusi telah menghasilkan mata, sayap, dan otak tanpa perancang, hanya dengan mempertahankan apa yang berhasil dan memvariasikannya. Algoritma genetika meminjam gagasan itu untuk memecahkan masalah di komputer. Ia tidak perlu memahami masalahnya, cukup bisa membedakan jawaban yang lebih baik dari yang lebih buruk, dan inilah yang menjadikannya alat yang ampuh ketika ruang jawaban yang mungkin terlalu besar dan terlalu aneh untuk ditelusuri dengan cara lain.
Gagasannya
Pada tahun 1960-an dan 1970-an, John Holland dari University of Michigan mengubah teori Darwin menjadi sebuah algoritma, yang ia uraikan dalam bukunya tahun 1975, Adaptation in Natural and Artificial Systems. Sekitar waktu yang sama, Ingo Rechenberg dan Hans-Paul Schwefel di Jerman mengembangkan strategi evolusi untuk desain rekayasa. Resep umumnya: pertahankan populasi kandidat solusi, beri skor, biarkan yang lebih baik bereproduksi dengan variasi, dan ulangi selama banyak generasi.
Gen dan populasi
Setiap kandidat dijelaskan oleh sebuah kromosom, yaitu daftar gen. Di simulator, gen sebuah roket adalah dorongan-dorongannya, satu untuk setiap saat penerbangannya; dalam masalah lain, gen bisa berupa bit-bit sebuah bilangan, urutan kota pada sebuah rute, atau ukuran komponen dalam sebuah desain. Generasi pertama bersifat acak, artinya ia menjelajahi ruang jawaban secara luas tetapi hampir tidak memiliki jawaban yang baik.
Fungsi kebugaran
Kebugaran adalah satu angka yang menyatakan seberapa baik sebuah kandidat, dan itulah satu-satunya hal yang diketahui algoritma tentang masalahnya. Untuk roket, kebugaran paling menghargai kedatangan awal, lalu berakhir dekat target, dan menghukum tabrakan. Fungsi kebugaran yang dipilih dengan baik menuntun pencarian dengan mulus menuju jawaban yang baik; fungsi yang dibuat sembarangan menghargai hal yang salah, dan algoritma akan memanfaatkan setiap celah yang dibiarkannya terbuka.
Seleksi
Induk dipilih sedemikian rupa sehingga kandidat yang lebih bugar memiliki lebih banyak anak, tetapi yang lebih lemah tetap mendapat kesempatan, karena gen mereka mungkin menyimpan bagian yang berguna. Seleksi roda rolet memberi setiap kandidat sepotong roda yang sebanding dengan kebugarannya; seleksi turnamen memilih beberapa kandidat secara acak dan mengambil yang terbaik di antaranya. Seleksi yang lebih kuat mempercepat kemajuan, tetapi juga membuat populasi lebih seragam, yang dapat mengakhiri pencarian terlalu dini.
Pindah silang dan mutasi
Pindah silang menggabungkan dua induk: di sini setiap anak mengambil bagian pertama gennya dari satu induk dan sisanya dari induk lain, sehingga manuver awal satu roket dapat bertemu dengan manuver akhir roket lain. Mutasi mengganti beberapa gen secara acak. Pindah silang menggabungkan ulang apa yang sudah dimiliki populasi; mutasi membawa apa yang belum pernah dimilikinya. Teorema skema Holland menjelaskan bagaimana blok pembangun pendek dari gen-gen yang baik menyebar ke seluruh populasi di bawah perpaduan seleksi dan rekombinasi ini.
Elitisme, eksplorasi, dan eksploitasi
Menyalin beberapa kandidat terbaik tanpa perubahan ke generasi berikutnya, yaitu elitisme, menjamin bahwa jawaban terbaik tidak pernah hilang. Setiap algoritma genetika harus menyeimbangkan eksplorasi, yaitu mencoba wilayah baru ruang pencarian, dengan eksploitasi, yaitu menyempurnakan apa yang sudah baik. Terlalu sedikit variasi membuat populasi mengerucut pada satu jawaban yang biasa-biasa saja; terlalu banyak membuatnya tidak pernah stabil. Ukuran populasi, laju mutasi, dan tekanan seleksi adalah tombol pengatur keseimbangan itu.
Optimum lokal
Algoritma genetika hanya mengikuti kebugaran, sehingga ia bisa tertipu. Ketika jalan menuju jawaban terbaik mula-mula melewati jawaban yang lebih buruk, populasi mendaki bukit terdekat dan tetap di sana: sebuah optimum lokal. Di balik dinding berselang-seling di simulator, roket yang menabrak di bawah target mendapat skor lebih baik daripada roket yang berbelok menjauh untuk mencari celah, sehingga populasi menumpuk di dinding. Cara mengatasinya antara lain populasi yang lebih besar, mutasi yang lebih tinggi, menjaga keragaman populasi, dan terutama fungsi kebugaran yang lebih baik.
Jelajahi sendiri
Buka simulator algoritma genetika untuk mengevolusikan roket memutari satu dinding, sebuah celah, pilar-pilar, dinding berselang-seling, atau dinding yang Anda gambar sendiri. Ubah populasi, laju mutasi, masa hidup, dan metode seleksi, nyalakan dan matikan elitisme, lalu ikuti di grafik seberapa cepat proporsi roket yang mencapai target bertambah, atau mengapa tidak bertambah.
Pertanyaan yang sering diajukan
Apakah algoritma genetika termasuk kecerdasan buatan?
Algoritma genetika termasuk dalam bidang AI dan machine learning yang lebih luas, sebagai metode pencarian dan optimisasi. Ia tidak belajar dari contoh seperti jaringan saraf; ia memperbaiki kandidat solusi melalui percobaan dan seleksi. Keduanya sering digabungkan, misalnya dengan mengevolusikan struktur atau bobot jaringan saraf, pendekatan yang disebut neuroevolusi.
Apakah algoritma genetika selalu menemukan jawaban terbaik?
Tidak. Ia adalah heuristik: biasanya menemukan jawaban yang baik untuk masalah yang sulit, tetapi tidak menjamin jawaban terbaik dan tidak membuktikan seberapa dekat jawabannya dengan yang terbaik. Untuk masalah yang dapat diselesaikan cukup cepat dengan metode eksak, metode itu lebih baik.
Apa perbedaan antara algoritma genetika dan strategi evolusi?
Keduanya adalah algoritma evolusioner. Algoritma genetika klasik menekankan pindah silang pada kromosom berbentuk untaian; strategi evolusi terutama bekerja dengan mutasi pada bilangan real dan sering menyesuaikan sendiri ukuran mutasinya seiring berjalannya proses. Metode modern memadukan gagasan dari keduanya.
Mengapa roket begitu canggung pada awalnya?
Gen pertama mereka adalah dorongan yang sepenuhnya acak, sehingga rata-rata saling meniadakan dan roket hanya melayang tak tentu arah. Penerbangan yang terkoordinasi baru muncul setelah seleksi mempertahankan roket langka yang kebetulan mendorong kira-kira ke arah yang benar, dan pindah silang menggabungkan bagian-bagian baiknya.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Buka simulator algoritma genetika