Algoritma semut
Diperkenalkan oleh Moyson dan Manderick dan dikembangkan secara ekstensif oleh Marco Dorigo, algoritma Ant adalah teknik probabilistik untuk memecahkan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Algoritme ini terinspirasi oleh perilaku semut saat mereka mencari jalan dari koloni menuju makanan.
Di dunia nyata, semut berkeliaran secara acak dan ketika menemukan makanan, mereka kembali ke koloninya, mengirimkan sinyal melalui jejak feromon. Ketika semut lain menemukan jejaknya, mereka tidak lagi berkeliaran secara acak tetapi mengikuti jejak tersebut dan kembali serta memperkuatnya ketika mereka akhirnya menemukan makanan.
Namun, seiring berjalannya waktu, jejak feromon akan hilang dan kekuatan tarik-menariknya akan berkurang. Semakin lama semut bergerak bolak-balik sepanjang jalur ini, semakin lama pula feromonnya menguap. Sebagai perbandingan, jalur pendek akan lebih cepat sejajar dan oleh karena itu kepadatan feromon tetap tinggi karena ia bergerak secepat penguapannya.Penguapan feromon juga mempunyai keuntungan dalam menghindari konvergensi menuju solusi optimal lokal. Jika tidak terjadi penguapan, jalur yang dipilih semut pertama akan cenderung terlalu menarik bagi semut berikutnya. Dalam kasus seperti ini, eksplorasi ruang solusi menjadi terbatas.
Jadi jika seekor semut menemukan jalur yang baik (jalur pendek) dari koloni menuju sumber makanan, semut lain akan mengikuti jalur tersebut, dan pada akhirnya semua semut akan mengikuti satu jalur. Ide dari algoritma koloni semut adalah untuk meniru perilaku ini melalui “semut buatan” yang berjalan mengelilingi grafik yang mewakili masalah yang harus dipecahkan
.Algoritma optimisasi koloni semut telah digunakan untuk menghasilkan penyelesaian yang mendekati optimal pada masalah salesman yang melakukan perjalanan. Algoritme semut lebih menguntungkan daripada pendekatan penguatan tiruan (simulaten annealing) dan algoritme genetik saat grafik mungkin berubah secara dinamis; algoritme koloni semut dapat berjalan secara kontinu dan menyesuaikan dengan perubahan secara waktu nyata (real time). Hal ini menarik dalam routing jaringan dan sistem transportasiurban.
Algoritma dan Rumus
Dalam algoritma optimasi koloni semut, semut buatan bertindak sebagai agen komputasi sederhana yang tujuannya adalah menemukan solusi optimal untuk masalah optimasi yang diberikan. Untuk menerapkan algoritma ini, masalah optimasi harus diubah menjadi masalah pencarian jalur terpendek dalam graf berbobot. Pada langkah pertama setiap iterasi, setiap semut secara stokastik membangun solusi dengan menyusun rangkaian sisi dalam grafik. Langkah kedua adalah membandingkan jalur yang ditemukan oleh semut yang berbeda. Langkah terakhir adalah memperbarui nilai feromon pada setiap sisi grafik.Dengan pendekatan ini, setiap semut berkontribusi dalam pencarian solusi optimal, menciptakan kolaborasi dan kemampuan beradaptasi untuk menemukan jalur terpendek menuju masalah optimasi tertentu.
Aplikasi
Algoritme optimasi koloni semut telah diterapkan pada banyak masalah optimasi kombinatorial mulai dari penugasan kuadrat hingga pelipatan protein atau perutean kendaraan, dan banyak metode turunan telah disesuaikan dengan masalah dinamis dalam variabel nyata, masalah stokastik, tujuan ganda, dan implementasi paralel. Ini juga telah digunakan untuk menemukan solusi yang mendekati optimal terhadap masalah penjual. Mereka memiliki keunggulan dibandingkan pendekatan simulasi anildan algoritma genetika untuk masalah serupa ketika grafik dapat berubah secara dinamis; Algoritma koloni semut dapat berjalan terus menerus dan beradaptasi terhadap perubahan secara real time. Hal ini menarik untuk perutean jaringan dan sistem transportasi perkotaan.
Algoritma ACO, seperti Ant System, mengimplementasikan seperangkat aturan yang terinspirasi oleh perilaku semut biologis. Setiap semut dalam algoritma ini memiliki tujuan untuk mengunjungi setiap kota tepat satu kali dalam perjalanan yang dipilih. Konsep visibilitas diterapkan, dengan kota-kota yang lebih jauh mempunyai kemungkinan yang lebih kecil untuk dipilih, hal ini mencerminkan kecenderungan semut untuk memilih jalur yang lebih dekat. Selain itu, keberhasilan suatu tepi dalam melakukan perjalanan dipengaruhi oleh kekuatan jejak feromon yang ada pada tepi tersebut. Semakin kuat jejak feromon, semakin besar kemungkinan semut memilih tepian tersebut.
Setelah menyelesaikan perjalanannya, semut menyimpan feromon tambahan di semua sisi jalurnya, terutama jika perjalanannya singkat.Hal ini mencerminkan cara semut biologis meninggalkan jejak feromon untuk memandu temannya menuju sumber daya yang mereka temukan. Namun, untuk menghindari konvergensi menuju solusi optimal lokal, jejak feromon menghilang setelah setiap iterasi. Pendekatan ini menciptakan dinamika yang mirip dengan siklus alami semut biologis, di mana feromon yang ditinggalkan semut sebelumnya secara bertahap berkurang seiring berjalannya waktu. Dengan menerapkan aturan-aturan ini, algoritma ACO menghasilkan totalsolusi optimal atau mendekati optimal terhadap masalah penjual yang kompleks.
Masalah Penjadwalan
Permasalahan perencanaan produksi meliputi Sequential Order Problem (SOP), Job Shop Scheduling Problem (JSP), Open Shop Scheduling Problem (OSP), Permutation Flow Shop Problem (PFSP), Single Machine Total Lateness Problem (SMTTP) dan masalah penundaan. Single Machine Weighted Total (SMTWTP), Resource Constrained Project Scheduling Problem (RCPSP), Group Shop Scheduling Problem (GSP), Single Machine Total Delay Problem dengan Time Sequence Dependent Configuration(SMTTPDST), Multistage Flow Shop Scheduling Problem (MFSP) dengan Sequence Waktu Pengaturan/perubahan yang bergantung dan masalah Perencanaan Urutan Perakitan (ASP).
Masalah perutean kendaraan
Permasalahan pada domain routing kendaraan mencakup berbagai aspek seperti capacity vehicle routing problem (CVRP), multi-depot vehicle routing problem (MDVRP), periodic vehicle routing problem (PVRP), split delivery vehicle routing problem (SDVRP) dan permasalahan berkendara. kendaraan. Masalah Stokastik (SVRP), Masalah Perutean Kendaraan dengan Penjemputan dan Pengantaran (VRPPD), Masalah Perutean Kendaraan dengan Jendela Waktu (VRPTW), Masalah Perutean KendaraanBergantung Waktu dengan Waktu Jendela Waktu (TDVRPTW) dan Masalah Perutean Kendaraan dengan Waktu dan Waktu Pekerja Layanan Multi-Jendela (VRPTWMS).
Sumber: id.wikipedia.org