Pengarang: Chinmay Bhalerao
Awalnya diterbitkan di Towards AI the World’s Leading AI and Technology News and Media Company. Jika Anda sedang membangun produk atau layanan terkait AI, kami mengundang Anda untuk mempertimbangkan untuk menjadi sponsor AI. Di Towards AI, kami membantu menskalakan AI dan startup teknologi. Biarkan kami membantu Anda melepaskan teknologi Anda kepada massa.
Penjelasan terperinci tentang algoritme pengoptimalan yang terinspirasi dari evolusi dan alam
“Lingkungan memilih beberapa mutasi yang meningkatkan kelangsungan hidup, menghasilkan serangkaian transformasi lambat dari satu bentuk kehidupan ke bentuk kehidupan lainnya, asal usul spesies baru.” – CARL SAGAN, 1934–1996
Evolusi
Konsep seleksi alam dan evolusi biologis mengubah cara pandang berpikir tentang teori evolusi. Evolusi selalu merupakan proses yang lambat dan bertahap yang membutuhkan waktu berabad-abad untuk bekerja. Jutaan spesies yang ada di bumi saat ini muncul dari satu bentuk kehidupan asli melalui proses percabangan yang disebut spesiasi. makhluk kompleks berevolusi dari nenek moyang yang lebih sederhana secara alami dari waktu ke waktu. Singkatnya, karena mutasi genetik acak terjadi dalam kode genetik suatu organisme, mutasi yang menguntungkan dipertahankan karena membantu kelangsungan hidup – sebuah proses yang dikenal sebagai “seleksi alam.”
DNA berubah seiring waktu dengan mutasi yang berbeda dan kombinasi pewarisan acak, yang merupakan rekombinasi DNA induk dan perilaku mutasi. Ini mudah dijelaskan menggunakan alat dari teori probabilitas dan proses stokastik.
“Evolusi adalah kumpulan ribuan peristiwa semi-acak dan tekanan alami untuk bereproduksi atau mati” -Evolusi Darwin
https://medium.com/media/232b8f2e71b1022f8628652aaa260398/href
Untuk memahami evolusi, ada contoh yang bagus tentang sistem mangsa dan pemangsa. Rubah memakan kelinci, dan kelinci yang lebih cepat cenderung menyelamatkan hidup mereka, sedangkan yang lebih lambat memiliki kemungkinan lebih besar untuk ditangkap. Mengingat populasi, individu yang lebih pintar dan lebih cepat cenderung tidak dikonsumsi oleh rubah. Akibatnya, mereka dapat terus bereproduksi, itulah yang paling baik dilakukan kelinci. Beberapa kelinci yang kurang cerdas dan lebih lambat juga berhasil melakukannya secara kebetulan. Saat populasi yang tersisa mulai bereproduksi, kombinasi yang baik dari materi genetik kelinci dihasilkan.
Rubah dan kelinci berevolusi seiring waktu [image by author created by Dall. E]
beberapa kelinci lambat berkembang biak dengan kelinci cepat, beberapa kelinci cepat berkembang biak dengan kelinci cepat, Dan di atas itu, alam melempar kelinci liar sesekali dengan memutasikan beberapa materi genetik kelinci. Karena lebih banyak orang tua yang lebih cepat dan lebih pintar yang selamat dari rubah, kelinci yang dihasilkan (rata-rata) lebih cepat dan lebih pintar daripada yang ada di kelompok aslinya. Hal baiknya adalah rubah juga menjalani prosedur serupa. Jika tidak, kelinci akan berkembang menjadi makhluk yang terlalu cepat dan cerdas untuk ditangkap oleh rubah.
Optimasi Algoritma Genetika
GAs pertama kali diusulkan oleh John Holland pada tahun 1960-an. GA menggabungkan metode yang diusulkan oleh dan terinspirasi oleh proses seleksi alam. Seperti yang saya sebutkan dalam contoh di atas, individu yang paling kuat memiliki lebih banyak peluang atau kemungkinan untuk bertahan hidup. Hal yang sama di GA. Dari kumpulan solusi, orang yang memiliki lebih banyak kebugaran memiliki lebih banyak kesempatan untuk bertahan hidup. Mari kita mulai pemahaman sebenarnya tentang Algoritma Genetika. Mari kita memahami terminologi dasar.
Terminologi Algoritma Genetika
Induk: Orang yang menghasilkan keturunan. anggota generasi sekarang.
Keturunan: Juga dikenal sebagai seorang anak. keturunannya adalah anggota dari generasi berikutnya
Populasi: Populasi adalah kumpulan semua solusi yang mungkin atau kromosom yang menunjukkan struktur gen yang serupa
Kebugaran: Kebugaran adalah angka yang diberikan kepada seorang individu yang mewakili ukuran kebaikan. Semakin bugar, semakin besar peluang untuk bertahan hidup dan bereproduksi.
Kromosom: Kromosom adalah bentuk kode dari kemungkinan set solusi yang terdiri dari gen yang terbuat dari salah satu dari dua atau lebih versi urutan DNA (alel).
Crossover: Crossover adalah fenomena di mana umumnya dua orang tua menghasilkan dua keturunan melalui pertukaran gen.
Mutasi: Mutasi adalah perubahan acak dari nilai gen yang kita ubah sedikit dan ubah 0 menjadi 1 dan 1 menjadi nol.
Generasi: Generasi adalah populasi yang dibuat secara berurutan. Dalam Algoritma Genetika, ini juga disebut sebagai “iterasi”.
Garis besar algoritma genetika
Algoritma genetika dimulai dengan mendefinisikan pernyataan masalah yang tepat dan menciptakan satu set populasi awal yang mungkin dari solusi. Populasi adalah kromosom yang dihasilkan secara acak. seperti prosedur evolusi, prosedur seleksi alam dimulai. Selama generasi berturut-turut, kromosom dalam populasi dinilai untuk kebugaran mereka atau dinilai untuk kesempatan mereka untuk menjadi solusi. Sekarang, berdasarkan evaluasi nilai fitnessnya, set kromosom baru terbentuk menggunakan operasi seleksi diikuti dengan crossover dan mutasi.
Alur dasar prosedur Algoritma Genetika [Image by Author]
Pilihan
Langkah penting pertama dalam operasi algoritma genetika adalah seleksi. Anda mungkin memiliki pertanyaan di sini! apa yang kita pilih? Saya akan menjawab pertanyaan ini. Solusi yang paling cocok atau keturunan/Anak yang paling cocok adalah tujuan kami. untuk itu tentunya kita harus memilih parent tergantung fitness nya. Jika kita memiliki populasi “X”, maka seleksi menciptakan populasi antara “X’ ” [X_hash] dengan salinan kromosom X. Kromosom yang lebih bugar akan memiliki lebih banyak salinannya !!! Setelah ini, mekanisme pemilihan dimulai.
Operasi seleksi dilakukan dengan dua cara:
Pemilihan roda roulette
Anda tahu kata roda Roulette dari kasino atau perjudian, bukan? Ini adalah konsep yang sangat mirip. Dalam perjudian, kami memiliki roda, dan kami memprediksi angka. Artinya, dadu akan mendarat di angka prediksi tersebut atau tidak! Dalam pemilihan roda roulette GA, rodanya sama. hanya titik berhenti diperkenalkan pada titik tetap. Kromosom mengambil nilai pada pai atau roda roulette persis sama dengan fitness yang dimilikinya.
Kromosom dan nilai kebugarannya [Image by author]
Jelas bahwa individu yang lebih bugar secara fisik memiliki pai yang lebih besar di roda dan peluang lebih tinggi untuk mendarat di depan titik tetap saat roda diputar. Akibatnya, kemungkinan seleksi individu berkorelasi langsung dengan kebugaran mereka.
Prosedur pemilihan roda roulette. Kromosom yang memiliki nilai fitness tertinggi cenderung menempati lebih banyak ruang pada pie dan memiliki kemungkinan lebih besar untuk terpilih [Image by author]Hitung jumlah totalnya [S]kebugaran. Hasilkan angka acak antara 0 dan jumlah total[S]. Hitung jumlah parsial P. Kromosom yang P melebihi S adalah individu yang dipilih.
Jumlah = F1 + F2 +F3+F4 + F5
Pilihan = (F1+F2+F3+F4+ F5)/Jumlah
2. Pemilihan turnamen
Dalam turnamen N-Way, kami secara acak memilih N orang dari populasi, dan kami memilih yang terbaik untuk menjadi orang tua. Induk berikut dipilih menggunakan prosedur yang sama seperti sebelumnya. Karena kemampuannya untuk berfungsi bahkan ketika nilai kebugaran negatif, pemilihan turnamen adalah perangkat sastra yang sangat umum.
Prosedur pemilihan turnamen [Image credit here ]
pindah silang
Crossover adalah operasi di mana kami menggabungkan properti dari kedua orang tua. Ciri-ciri dari dua kromosom induk dicampur sedemikian rupa sehingga ada kemungkinan kromosom yang baik menghasilkan keturunan.
Operator crossover berperan dalam keseimbangan antara eksploitasi dan eksplorasi, yang memungkinkan ekstraksi karakteristik dari kedua tetua, dan berharap keturunan yang dihasilkan memiliki karakteristik yang baik dari tetua (Gallard & Esquivel, 2001).
Crossover biasanya diterapkan dalam GA dengan probabilitas tinggi [pc]. Menurut posisi crossover, crossover dibagi menjadi beberapa jenis:
dan untuk jenis crossover lainnya, lihat INI.
Jika Anda memiliki pertanyaan tentang cara memilih jenis dan probabilitas crossover, maka Anda dapat merujuk ke makalah komprehensif tautan ini tentang Probabilitas Crossover.
Mutasi
Menurut National Geographic, Mutasi adalah perubahan struktur gen, unit hereditas. Gen terbuat dari asam deoksiribonukleat (DNA), molekul panjang yang terdiri dari blok bangunan yang disebut nukleotida. Setiap nukleotida dibangun di sekitar salah satu dari empat subunit berbeda yang disebut basa. Basa ini dikenal sebagai guanin, sitosin, adenin, dan timin. Sebuah gen membawa informasi dalam urutan nukleotidanya, seperti sebuah kalimat membawa informasi dalam urutan huruf-hurufnya.
Di GA, mutasi adalah langkah di mana kami memastikan bahwa ruang pencarian tidak akan pernah menjadi nol. Kita tahu bahwa dalam algoritme optimasi tradisional seperti penurunan gradien, selalu ada kemungkinan bahwa itu akan macet di maxima/minima lokal dan menganggapnya sebagai solusi akhir. Untuk mengatasi skenario semacam ini, upaya mutasi ekstra ini diambil, dan ini membantu untuk menghindari menempel pada tonjolan lokal.
Mutasi dan mutasi DNA [images by author created by Dall. E]
Intinya, probabilitas mutasi mengukur kemungkinan bahwa fragmen kromosom acak yang tidak terkait dapat terbalik dan menjadi sesuatu yang berbeda. Jika kromosom Anda dikodekan sebagai string biner dengan panjang 100, misalnya, dan risiko mutasi Anda adalah 1%, ini menunjukkan bahwa, rata-rata, 1 dari setiap 100 bit yang dipilih secara acak akan dibalik. Crossover biasanya dilakukan di GA dalam berbagai cara, pada dasarnya mensimulasikan rekombinasi genetik seksual yang mirip dengan reproduksi manusia.
Penghentian
Proses iterasi GA diulang sampai kondisi terminasi tercapai, seperti,
Kriteria ambang batas yang ditentukan pengguna tercapai Jumlah iterasi tetap yang tercapai habis dengan jumlah maksimum solusi yang mungkin Kesesuaian maksimum tercapai Kriteria penghentian daya komputasi
Ini hanya ikhtisar teoretis dari GA, tetapi saya berencana untuk mengambil studi kasus untuk mengimplementasikan GA di atasnya jika Anda masih ingin mengerjakan solusi matematika sederhana dari masalah dengan GA dengan kode, maka lihat blog informatif INI di GA oleh Niranjan Pramanik, Ph.D.
Anda dapat mensimulasikan proses evolusi di SINI.
Anylogic mensimulasikan masalah perutean distribusi rantai pasokan [ vehicle routing problem] dan diselesaikan dengan menggunakan algoritma Genetika.
simulasi masalah perutean distribusi rantai pasokan [ vehicle routing problem] solusi menggunakan algoritma Genetika.[credits: HERE]
Anda bisa mendapatkan simulasi ini DI SINI.
Anylogic cloud memiliki banyak simulasi berbeda dan menarik berdasarkan skenario kehidupan nyata, Anda dapat memeriksanya DI SINI.
Jika Anda telah menemukan artikel ini berwawasan
Jika Anda menemukan artikel ini berwawasan luas, ikuti saya di Linkedin dan medium. Anda juga dapat berlangganan untuk mendapatkan pemberitahuan ketika saya menerbitkan artikel. Ayo buat komunitas! Terima kasih atas dukunganmu!
Jika Anda ingin mendukung saya:
Karena follow dan tepuk tangan Anda adalah hal yang paling penting, tetapi Anda juga dapat mendukung saya dengan membeli kopi. KOPI.
Anda juga dapat membaca blog saya yang terkait dengan
Referensi :
1]Algoritma Genetika Real-Coded
2]Tentang Meningkatkan Algoritma Genetika Menggunakan Crossover Baru
3]Algoritma genetika crossover yang dioptimalkan untuk masalah perutean kendaraan berkapasitas
[image by author created by Dall. E]
Optimasi Algoritma Genetika awalnya diterbitkan di Towards AI on Medium, di mana orang-orang melanjutkan percakapan dengan menyoroti dan menanggapi cerita ini.
Diterbitkan melalui Menuju AI
