Ilmu Komputer Evolusi: Pengantar Algoritma Genetika

Foto oleh Hal Gatewood di Unsplash

Menjadi seorang ilmuwan komputer dengan minat pada evolusi dan proses biologis, topik algoritma genetika, dan yang lebih luas, perhitungan evolusi bagi saya adalah seperti toko permen bagi anak berusia 5 tahun: Surga. Kemungkinan hanya untuk dapat menggabungkan dua minat saya dengan cara yang begitu mulus telah sangat menggembirakan, dan akan salah bagi saya untuk menyimpan pengetahuan dan kegembiraan ini untuk diri saya sendiri.

Jadi dalam upaya untuk menguji beberapa pembelajaran saya sejauh ini, dan berbagi temuan saya dengan seluruh dunia, saya telah memutuskan untuk mengumpulkan serangkaian artikel tentang topik ini.

Dalam posting ini, saya akan memberikan pengantar singkat untuk algoritma genetika dan menjelaskan bagaimana mereka meniru proses alami yang sama yang telah terjadi di Bumi selama miliaran tahun.

Hidup di bumi

Selama 3,5 miliar tahun terakhir, alam ibu, waktu ayah, evolusi dan seleksi alam telah berkolaborasi bersama untuk menghasilkan semua bentuk kehidupan khusus yang kita lihat di bumi hari ini: seperti tanaman Penangkap Lalat Venus karnivora; Ikan Terbang Atlantik yang hidup di lautan; kelelawar yang menggunakan ekolokasi; jerapah berleher panjang; cheetah super cepat, menari Lebah Madu; dan tentu saja, milikmu yang sesungguhnya, Homo sapiens yang pintar di jalanan.

Venus Flytrap adalah tanaman karnivora yang terutama menyantap serangga dan arakhnida.Beberapa kelelawar menggunakan echolokasi untuk menavigasi dan berburu mangsa dan bertentangan dengan kepercayaan populer, kelelawar sebenarnya tidak buta; spesies kelelawar yang dikenal sebagai The Flying Foxes sebenarnya memiliki penglihatan yang lebih baik daripada manusia.Ikan Terbang tidak dapat terbang dengan cara yang sama seperti burung, namun, ikan ini dapat membuat lompatan yang kuat dan mandiri keluar dari air di mana sirip panjangnya yang seperti sayap memungkinkan mereka meluncur untuk jarak yang cukup jauh di atas permukaan air.

Tak perlu dikatakan, kehidupan di Bumi adalah salah satu, jika bukan eksperimen paling sukses yang pernah dijalankan di alam semesta kita; dan menilai dari hasil yang mengesankan dari percobaan ini, jelaslah bahwa evolusi jelas menuju sesuatu.

Baru-baru ini, kita manusia - hanya salah satu dari banyak produk akhir dari proses ini - menyadari bahwa kita juga dapat mengambil keuntungan dari pendekatan yang cerdik ini untuk penyelesaian masalah yang progresif, dan sejak tahun 1950-an, ilmuwan komputer, ahli genetika, ahli matematika, dan ahli biologi, telah berusaha untuk meniru proses biologis ini melalui penerapan simulasi komputer. Dengan tujuan menghasilkan solusi optimal untuk masalah yang sulit dan tidak sepele, secara efisien.

Pembuat jam yang buta

Salah satu buku pertama yang saya temui yang memicu minat saya pada bidang biologi evolusi adalah The Blind Watchmaker, karya Richard Dawkins. Dalam buku ini, Richard Dawkins menjelaskan bagaimana mekanisme rumit seperti ekolokasi (suatu proses yang digunakan kelelawar untuk bernavigasi, berburu dan mencari makan, juga dikenal sebagai bio-sonar), struktur rumit seperti sarang laba-laba (yang digunakan laba-laba untuk menarik dan menangkap mangsa mereka), dan instrumen kompleks seperti mata manusia (dua benda berbentuk bola yang saat ini Anda gunakan untuk membaca artikel ini) hanyalah hasil dari ribuan, jika bukan jutaan tahun evolusi dan adaptasi.

Evolusi progresif mata manusia. Apa yang dimulai sebagai sel-sel fotosensitif sederhana, berevolusi menjadi instrumen kompleks yang sering kita anggap remeh. Hewan pertama dengan apa pun yang menyerupai mata hidup sekitar 550 juta tahun yang lalu. Dan, menurut perhitungan seorang ilmuwan, hanya butuh 364.000 tahun bagi mata yang mirip kamera untuk berevolusi dari tambalan yang peka terhadap cahaya.

Meskipun keajaiban alam ini memberi kesan bahwa mereka dibangun dengan tujuan dari perjalanan (yaitu oleh 'pembuat' yang sadar), mereka sebenarnya hanya hasil dari iterasi pada iterasi trial and error, digabungkan dengan Perubahan tekanan seleksi (yaitu perubahan iklim, habitat, atau perilaku dan kemampuan predator atau mangsa). Jadi sementara mereka mungkin terlihat dan berperilaku seperti hasil dari rekayasa yang tepat dan berpikiran maju, mereka sebenarnya adalah hasil dari proses yang benar-benar buta, sebuah proses yang tidak tahu sebelumnya apa 'solusi' sempurna itu.

Apa itu algoritma genetika dan mengapa kita membutuhkannya?

Algoritma genetika adalah teknik yang digunakan untuk menghasilkan solusi berkualitas tinggi untuk masalah optimasi dan pencarian, yang didasarkan pada proses biologis mendasar. Algoritme ini digunakan dalam situasi di mana kisaran solusi yang mungkin sangat besar, dan di mana pendekatan yang lebih mendasar untuk pemecahan masalah seperti pencarian menyeluruh / brute force akan menghabiskan terlalu banyak waktu dan upaya.

Masalah salesman keliling mengajukan pertanyaan berikut: "Diberikan daftar kota dan jarak antara masing-masing pasangan kota, apa rute terpendek yang mungkin mengunjungi setiap kota dan kembali ke kota asal?" optimisasi kombinatorial.

Kami dapat menggunakan algoritma genetika untuk memberikan solusi berkualitas tinggi untuk masalah ini, dengan biaya yang jauh lebih rendah daripada teknik pemecahan masalah yang lebih primitif, seperti pencarian lengkap, yang akan mengharuskan Anda untuk mengubah-ubah semua solusi yang mungkin.

Bagaimana cara kerja algoritma genetika?

Algoritma bekerja dengan melakukan iterasi melalui sejumlah langkah, hingga mencapai titik terminasi yang telah ditentukan. Setiap iterasi dari algoritma genetika menghasilkan generasi baru dari solusi yang mungkin, yang, secara teori, harus merupakan peningkatan pada generasi sebelumnya.

Langkah-langkahnya adalah sebagai berikut:

1. Buat populasi awal N solusi yang memungkinkan (sup primordial)

Langkah pertama dari algoritma ini adalah untuk membuat kelompok awal solusi yang berfungsi sebagai solusi dasar pada generasi 0. Setiap solusi dalam populasi awal ini akan membawa seperangkat kromosom, yang terdiri dari kumpulan gen, di mana setiap gen ditugaskan ke salah satu variabel kemungkinan masalah. Penting bahwa solusi dalam populasi awal dibuat dengan gen yang ditugaskan secara acak, untuk memiliki tingkat variasi genetik yang tinggi.

2. Beri peringkat solusi populasi berdasarkan kesesuaian (survival of the fittest, bagian 1).

Pada langkah ini, algoritme harus dapat menentukan apa yang membuat satu solusi lebih 'pas' daripada solusi lain. Ini ditentukan oleh fungsi kebugaran. Tujuan dari fungsi kebugaran adalah untuk mengevaluasi kelayakan genetik dari solusi-solusi dalam populasi, menempatkan mereka dengan sifat-sifat genetik yang paling layak, menguntungkan & unggul di bagian atas daftar.

Dalam masalah salesman keliling, fungsi kebugaran bisa menjadi penghitungan total jarak yang ditempuh oleh solusi. Dimana jarak yang lebih pendek berarti kebugaran yang lebih tinggi.

3. Cull solusi yang lebih lemah (survival of the fittest, bagian 2)

Pada langkah ini, algoritma menghilangkan solusi yang kurang pas dari populasi. Yang 'paling cocok' tidak selalu berarti yang terkuat, tercepat, atau sengit, seperti yang biasanya diasumsikan oleh manusia. Kelangsungan hidup yang terkuat berarti bahwa semakin baik suatu organisme diperlengkapi untuk bertahan hidup di lingkungannya, semakin besar kemungkinannya hidup cukup lama untuk bereproduksi dan menyebarkan gennya ke generasi berikutnya.

Langkah 3 dan 4 secara kolektif dikenal sebagai seleksi.

4. Kembang biakkan solusi yang lebih kuat (survival of the fittest, bagian 3)

Solusi yang tersisa kemudian dipasangkan satu sama lain untuk kawin dan bereproduksi. Selama proses ini, dalam bentuknya yang paling dasar, setiap orangtua akan berkontribusi satu% dari gen mereka (di alam itu adalah 50/50 split) untuk masing-masing keturunan mereka, di mana P1 (G)% + P2 (G)% = 100 %. Proses penentuan gen orang tua mana yang akan diwarisi oleh keturunannya dikenal sebagai crossover.

5. Mutasi gen keturunannya (mutasi)

Keturunannya akan mengandung persentase gen 'ibu', dan persentase gen 'ayah' dan kadang-kadang akan ada 'mutasi' dari satu atau lebih gen ini. Mutasi pada dasarnya adalah kelainan genetik, kesalahan penyalinan yang menyebabkan satu atau lebih gen keturunan berbeda dari gen yang diwarisi dari orang tuanya. Dalam algoritma genetika, dalam beberapa kasus mutasi akan meningkatkan kebugaran keturunan, dalam kasus lain, itu akan menguranginya.

Penting untuk dicatat bahwa tidak perlu ada mutasi dengan setiap keturunan, frekuensi mutasi yang diperlukan juga dapat menjadi parameter dari algoritma.

Dalam algoritma genetika, seleksi, crossover, dan mutasi dikenal sebagai operator genetik.

6. Pengakhiran

Langkah 2 hingga 5 akan diulangi hingga titik terminasi yang telah ditentukan. Titik terminasi ini dapat berupa salah satu dari yang berikut:

  1. Alokasi waktu / sumber daya maksimum tercapai.
  2. Jumlah generasi yang tetap telah berlalu.
  3. Kesesuaian solusi dominan tidak dapat dilampaui oleh generasi mendatang.

Konvergensi solusi

1. Global optimal

Dalam situasi ideal, solusi terkuat akan memiliki nilai kebugaran setinggi mungkin, yaitu solusi optimal, artinya tidak perlu melanjutkan dengan algoritma dan menghasilkan generasi selanjutnya.

2. Optimal lokal

Dalam beberapa kasus, jika parameter algoritma tidak masuk akal, populasi mungkin cenderung menuju konvergensi prematur pada solusi yang kurang optimal, yang bukan optimum global yang kita kejar, tetapi lebih pada yang lokal. Begitu tiba di sini, melanjutkan algoritma dan menghasilkan generasi selanjutnya mungkin sia-sia.

Optimal global vs optimal lokal

Apa yang akan terjadi jika tidak ada mutasi?

Pada pandangan pertama, mutasi mungkin tampak seperti bagian proses yang tidak perlu dan tidak relevan. Tetapi tanpa aspek fundamental dari keacakan ini, evolusi melalui seleksi alam akan sepenuhnya terbatas pada varietas genetik yang ditetapkan oleh populasi awal, dan tidak akan ada sifat-sifat baru yang dimasukkan ke dalam populasi setelah itu. Ini akan sangat menghambat kemampuan pemecahan masalah alam, dan kehidupan di bumi tidak akan dapat 'beradaptasi' dengan lingkungannya, setidaknya tidak secara fisik.

Jika ini adalah kasus dalam algoritma genetika kita, pada suatu titik dalam simulasi kita, generasi populasi masa depan tidak akan dapat mengeksplorasi bagian dari ruang solusi yang tidak dieksplorasi oleh pendahulu mereka. Simulasi tanpa mutasi akan sangat membatasi variasi genetik dalam populasi, dan dalam kebanyakan kasus - tergantung pada populasi awal - mencegah kita dari pernah mencapai optimal global.

Tanpa mutasi, kami tidak akan memiliki mutan, dan tanpa mutan, kami tidak akan memiliki franchise X-men.

Apa yang akan terjadi jika ukuran populasi tidak cukup besar?

Saya baru-baru ini di Suaka Margasatwa Jukani di Plettenberg, di mana saya mendapat hak istimewa untuk bertemu harimau putih. Dia benar-benar binatang yang agung. Dia besar, dia tampak ganas, dan, dia juga 80% buta dan semakin parah seiring dengan berlalunya waktu.

Kenapa dia buta? Karena dia adalah produk generasi inbreeding. Harimau putih ini hanya diproduksi ketika dua harimau yang membawa gen resesif yang mengendalikan warna bulu disatukan. Jadi, untuk memastikan kelanjutan harimau-harimau ini di penangkaran, orang-orang telah membiakkan harimau-harimau ini dalam populasi yang sangat terbatas untuk memamerkan mereka di sirkus, memamerkannya di kebun binatang, atau menjadikannya sebagai hewan peliharaan rumah tangga.

Tetapi salah satu efek negatif dari perkawinan sedarah adalah Anda sangat membatasi variasi genetik dalam spesies, yang semakin meningkatkan kemungkinan bahwa sifat resesif yang berbahaya akan ditularkan ke keturunannya.

Harimau putih yang saya temui di Suaka Margasatwa Jukani pada April 2019. Dia terlihat agung, tetapi dia menderita.

Bahkan di alam liar, kawin sedarah masih bisa menjadi masalah besar. Selama beberapa dekade terakhir, populasi badak di Afrika Selatan telah terkena dampak yang signifikan karena perburuan, dan jika ukuran populasi mencapai jumlah yang cukup rendah itu berarti bahwa mempertahankan keragaman genetik spesies badak yang terancam ini akan sangat sulit. Jadi, bahkan jika perburuan liar tidak sepenuhnya menyebabkan mereka punah, kawin sedarah bisa.

Foto oleh redcharlie di Unsplash.

Tentu saja, manusia tidak asing dengan perkawinan sedarah. Salah satu hasil perkawinan sedarah yang berkelanjutan dalam spesies kita adalah Charles (Carlos) II dari Spanyol.

“Raja Habsburg, Carlos II dari Spanyol dengan sedih merosot dengan kepala yang cacat besar. Mulut Habsburg-nya sangat menonjol sehingga dua baris giginya tidak bisa bertemu; dia tidak bisa mengunyah. Lidahnya begitu besar sehingga dia hampir tidak bisa berbicara. Kecerdasannya juga cacat. ”

Habsburg King Charles II dari Spanyol. Ayahnya adalah paman ibunya, menjadikan Charles putra mereka, cicit perempuan dan sepupu pertama.

'Inbreeding' dalam algoritme genetik kami, pada dasarnya berarti pengembangbiakan solusi yang memiliki susunan genetika yang sangat mirip, yang, untungnya, dalam hal ini, tidak akan menghasilkan keturunan dengan kecenderungan terhadap kelainan fisik apa pun. Tetapi jika populasinya sangat kecil dan jika semua solusinya memiliki susunan genetik yang sangat mirip, maka kesesuaian generasi mendatang dari populasi akan sangat dibatasi. Berarti butuh waktu lebih lama untuk menyatu pada solusi optimal global jika kita sampai di sana sama sekali.

Perkawinan sedarah tidak selalu merupakan hal yang buruk, itu hanya tergantung pada tahap simulasi Anda. Dalam tahap simulasi yang sangat maju, ketika populasi menyatu ke arah global / lokal, jelas sangat sulit untuk menghindari perkawinan sedarah, karena , dalam beberapa kasus, banyak solusi dominan akan sangat mirip satu sama lain, dan dengan demikian, akan memiliki banyak sifat genetik yang sama.

Membungkus

Baiklah, itu harus mencakup dasar-dasar. Jika Anda memiliki pertanyaan, permintaan, atau mutasi genetik untuk berkontribusi, silakan tinggalkan komentar di bawah ini.

Pada posting berikutnya, kita akan mempelajari beberapa kode ketika kita melihat bagaimana masing-masing operator genetik yang dijelaskan di atas bermain di dunia pemrograman. Saya menggunakan bahasa pemrograman Ruby untuk simulasi perangkat lunak yang saya kerjakan, dan di dalamnya, saya menunjukkan bagaimana hanya dalam beberapa generasi, suatu algoritma genetika dapat menghasilkan kata atau frasa yang telah ditentukan dari kumpulan awal omong kosong yang lengkap dan sepenuhnya. Semua kode akan di-host di Github.