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.
algoritma optimasi yang terinspirasi oleh alam metaheuristik berbasis populasi
Gambar oleh penulis dibuat oleh Dalle.2
“Semut, bukan singa, yang ditakuti gajah.”
Mashona Dhliwayo
Sekelompok teknik dan pendekatan pemecahan masalah yang unik yang terinspirasi oleh proses alami dikenal sebagai “algoritma yang terinspirasi oleh alam.” Algoritma optimasi koloni semut (ACO), yang digunakan dalam ilmu komputer dan riset operasi, adalah metode probabilistik untuk menyelesaikan masalah komputasi yang dapat disederhanakan untuk menemukan jalur yang sesuai melalui grafik.
Di blog ini, kita akan membahas topik-topik berikut:
Semut di kehidupan nyata Perilaku mencari makan Inspirasi di balik algoritme pengoptimalan koloni semut Apa yang sebenarnya terjadi dengan semut dan makanan di kehidupan nyata Langkah-langkah pengoptimalan koloni semut
Semut kehidupan nyata
Bersama dengan tawon dan lebah yang berkerabat dekat, semut adalah anggota eusosial dari famili Formicidae dalam ordo Hymenoptera. Semut memiliki sekitar 22.000 spesies, dan lebih dari 13.800 telah diklasifikasikan. Semut mengalami metamorfosis sempurna, yang berarti semut memiliki empat tahap – telur, larva, kepompong, dan dewasa dalam siklus hidupnya. Umur: Semut kebun hitam: 1–2 tahun, Semut Firaun: 4–12 bulan. Semut biasanya dibagi menjadi tiga jenis: betina reproduktif, jantan reproduktif, dan betina non-reproduksi. Ini diterjemahkan menjadi ratu, pria, dan pekerja.
Koloni semut dan masyarakat serangga sosial, lebih umum, adalah sistem terdistribusi yang, Terlepas dari kesederhanaan anggota individu mereka, mereka menampilkan sistem sosial yang sangat terorganisir. Koloni semut diatur sedemikian rupa sehingga mereka dapat melakukan tugas-tugas yang rumit. bahwa, dalam beberapa situasi, secara signifikan melebihi kapasitas seekor semut individu. apa yang terjadi pada manusia dan spesies lain yang lebih tinggi yang indera utamanya adalah pendengaran atau visual. Jejak feromon sangat penting untuk perilaku sosial beberapa spesies semut. Akar dari ACO adalah aktivitas peletakan jejak dan mengikuti jejak kolektif ini, di mana seekor semut dipengaruhi oleh jalur kimia yang ditinggalkan oleh semut lain.
Semut tidak memiliki telinga. mereka dapat merasakan getaran. mereka berkomunikasi menggunakan antena dan feromon mereka.
Masalah yang melibatkan optimasi diskrit sangat cocok untuk ACO. Misalnya, rute atau jalur dikodekan sebagai solusi untuk masalah perutean. Ketika semut mengambil jalur yang berbeda, jalur yang mereka lalui ditandai dengan endapan feromon yang akhirnya menghilang. Jumlah feromon yang ada pada suatu jalur (atau dalam larutan) berkorelasi dengan kebugaran atau kualitasnya. Di persimpangan, rute dengan konsentrasi feromon yang lebih tinggi akan lebih disukai atau dipilih lebih sering.
Perilaku mencari makan
ACO terinspirasi oleh perilaku menempa semut yang mencari jalur yang cocok antara koloni dan sumber makanannya. Jika Anda ingin mencapai waktu minimum menuju makanan, maka Anda harus menemukan jalan yang paling dekat dengan sumber makanan. jalur terpendek akan memberi Anda makanan dalam waktu yang lebih singkat.
Inspirasi di balik algoritme pengoptimalan koloni semut
Bagaimana semut menemukan jalur terpendek antara sumber makanan dan sarangnya?
Semut dan rute acak yang berbeda menuju sumber makanan [Image by author]
Perhatikan gambar di atas. Saya melingkari satu semut, dan itu akan menjadi agen kami untuk mencari makanan. Sekarang ada banyak cara semut dapat mencari makanan. dari semua cara itu, saya menyoroti 4 cara tentatif acak bernama A, B, C, D. Seperti yang dapat kita lihat pada gambar, C adalah jalur terpendek dan A adalah jalur terpanjang. Saat menempuh jalan apa pun untuk mencari makanan, semut melepaskan zat kimia yang dikenal sebagai feromon. Menurut ini, saat pergi dari semua rute, semut akan melepaskan feromon.
tingkat feromon di jalan semut [Image by author]
ketika semut mencapai makanan, setiap rute memiliki sejumlah feromon yang disimpan di atasnya, seperti yang ditunjukkan pada gambar di atas. orang yang menemukan makanan atau pengembara akan menandai jejak di jalan menggunakan feromon saat akan kembali ke koloni. rute yang lebih pendek akan memiliki lebih banyak kadar feromon di atasnya. Semut lain akan mengikuti rute yang memiliki jumlah feromon lebih banyak sebagai sinyal yang mewakili rute terpendek untuk mencapai makanan. Feromon diperbarui dalam setiap pergerakan semut dari satu lokasi ke lokasi lain berdasarkan Kepadatan Semut & Jumlah Semut.
Penguapan dan pengendapan feromon [Image by author]
feromon memiliki beberapa tingkat penguapan. itu berarti feromon yang disimpan akan hilang setelah waktu tertentu. Jadi seperti yang Anda lihat pada gambar di atas, rute yang dilalui sebagian besar semut mengikuti feromon semut terdepan memiliki jumlah feromon yang paling banyak disimpan, sedangkan rute lain yang lebih panjang memiliki feromon yang sangat sedikit karena penguapan.
Ketika sumber makanan selesai, tidak ada tanda baru di jalan yang ditandai oleh semut yang kembali.
Apa yang sebenarnya terjadi dengan semut dan makanan di kehidupan nyata?
Semua semut ada di sarangnya. Tidak ada tanda feromon di tanah.
Mencari makan dimulai dan 50% SEMUT akan mengambil jalur terpendek dan 50% akan mengambil jalur yang lebih panjang.
Semut menggunakan jalur terpendek dan tiba lebih awal di sumber makanan.
Tanda feromon pada jalur yang lebih pendek memiliki sinyal feromon yang kuat. Kemungkinan jalur ini dipilih oleh semut lain meningkat.
Langkah-langkah untuk optimasi koloni semut:
1. Inisialisasi parameter ACO
Kita dapat menginisialisasi banyak parameter awal seperti Ukuran populasi, jumlah maksimum iterasi, nilai feromon awal, bobot eksponensial feromon, laju penguapan feromon, dll.
2. Konstruksi Solusi
Dengan cara yang benar, perumusan pernyataan Masalah dan iterasi dihitung.
3. Posisi setiap agen/semut pada node awal
Ini juga dikenal sebagai probabilitas transisi.
Probabilitas transisi [Image source]
Di sini, semut ke-k akan bergerak dari i ke j dengan probabilitas ini.
4. Setiap semut akan memilih node berikutnya dengan menerapkan aturan transisi.
5. Ulangi sampai semut membangun solusi terbaik
6. menghitung nilai kebugaran
7. perbarui solusi terbaik
Jika ant4(solusi) < solusi terbaik:
pertimbangkan ant4(solusi)=solusi terbaik
8. Terapkan pembaruan feromon eksternal
Peningkatan kadar percobaan feromon =Untuk solusi terbaik
Penurunan tingkat jejak feromon = Untuk solusi terburuk
persamaan pembaruan feromon [Image source]
Deposisi feromon dan perhitungan penguapan juga penting.
9. solusi terbaik
Perulangan hingga iterasi maksimum untuk menyimpulkan solusi terbaik. yang bisa menjadi hyperparameter lagi.
Eksperimen yang menarik diberikan dalam buku Ant Colony Optimization oleh Marco Dorigo dan Thomas Stützle.
Jembatan pada percobaan pertama memiliki dua cabang yang sama panjang. Semut awalnya dibiarkan berkeliaran dengan bebas di antara sarang dan persediaan makanan, dan proporsi semut yang lebih menyukai salah satu dari dua cabang di atas yang lain diukur. seiring waktu, semut diperhatikan. Hasilnya, meskipun pilihan awal dibuat secara acak, pada akhirnya setiap semut memilih untuk menggunakan cabang yang sama. Penjelasan berikut menjelaskan hasil ini. Tidak ada feromon pada dua cabang saat percobaan dimulai. Semut memilih cabang mana pun dengan probabilitas yang sama karena mereka tidak memiliki preferensi. Namun, beberapa semut lagi akan memilih satu cabang di atas yang lain karena variasi acak. Karena semut menyimpan feromon saat mereka bergerak, cabang dengan lebih banyak semut di atasnya akan memiliki lebih banyak feromon di sana.
bagaimana semut memilih rute [Image source]
Jumlah feromon yang lebih besar ini kemudian akan mendorong semut tambahan untuk memilih cabang itu lagi, dan seterusnya, sampai semut akhirnya berkumpul di salah satu dari dua cabang.
Simulasi ACO [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.
Kata-kata terakhir:
Dengan menggabungkan perilaku swarm, optimasi ACO dan Particle swarm[PSO] algoritma keduanya metode pengelompokan data. Namun, ACO lebih relevan. menangani masalah di mana sumber dan tujuan diidentifikasi dan ditetapkan dengan jelas. Selain itu, PSO adalah teknik clustering multiobjective, dynamic optimasi, dan manajemen kendala. ACO lebih tepat untuk masalah yang membutuhkan solusi tepat. Algoritma optimasi koloni semut telah diterapkan pada banyak masalah optimasi kombinatorial, mulai dari penugasan kuadratik hingga protein lipat atau kendaraan perutean, dan banyak metode turunan telah disesuaikan dengan masalah dinamis dalam variabel nyata, masalah stokastik, multi-target, dan implementasi paralel .
Ini hanya gambaran teoritis dari ACO, tapi saya berencana untuk mengambil studi kasus untuk menerapkan ACO di atasnya. Saya sudah menulis satu blog tentang algoritma yang diilhami alam tentang OPTIMASI ALGORITMA GENETIK. Anda dapat membaca itu.
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.
Tanda tangan,
Chinamay Bhalerao
Optimalisasi Koloni Semut: Ikhtisar awalnya diterbitkan di Towards AI on Medium, di mana orang-orang melanjutkan percakapan dengan menyoroti dan menanggapi cerita ini.
Diterbitkan melalui Menuju AI
