Artificial Ants and Minimum Cost Paths

.

.
.
Secara khusus, semut buatan mengingat bentuk memori yang terbatas di mana mereka dapat menyimpan jalur parsial yang mereka miliki mengikuti sejauh ini, serta biaya tautan yang mereka lalui. Melalui penggunaan Dalam memori, semut dapat menerapkan sejumlah perilaku bermanfaat yang memungkinkannya secara efisien membangun solusi untuk masalah jalur biaya minimum. Perilaku-perilaku ini adalah 

(1)konstruksi solusi probabilistik yang bias oleh jalur feromon, tanpa maju pembaruan feromon; 

(2) jalur mundur deterministik dengan eliminasi loop dan dengan pembaruan feromon; 

(3) evaluasi kualitas solusi yang dihasilkan dan penggunaan kualitas solusi dalam menentukan jumlah deposit feromon 

Probabilistic forward ants and solution construction. 

Semut S-ACO memiliki dua mode kerja: maju dan mundur. Mereka berada dalam mode maju ketika mereka bergerak dari sarang menuju makanan, dan mereka berada di mode mundur ketika mereka pindah dari makanan kembali ke sarang mereka. Setelah semut mode maju mencapai tujuannya, ia beralih ke mode mundur dan memulai perjalanannya kembali ke sumbernya. Dalam S-ACO, semut maju membangun solusi dengan memilih secara probabilistik simpul berikutnya untuk pindah ke antara mereka yang ada di sekitar simpul grafik dimana mereka berada. 

Pilihan probabilistik dapat dibiaskan oleh jalur feromon yang sebelumnya disimpan pada grafik oleh semut lain. Saat mode maju, semut tidak menyetor feromon saat bergerak. Maupun saat gerakan mundur deterministik, membantu dalam menghindari pembentukan loop.

Deterministic backward ants and pheromone update.

Semut S-ACO meningkatkan kinerja sistem dengan mengimplementasikan eliminasi loop. Dalam praktiknya, sebelum mulai bergerak mundur di jalur, mereka hafal saat mencari node tujuan (mis., jalur maju), semut S-ACO menghilangkan loop dari itu. Saat bergerak mundur, semut S-ACO meninggalkan feromon pada lintasan yang mereka lintasi.

Pheromone updates based on solution quality.

Membuat pembaruan feromon dapat membantu mengarahkan semut di masa depan ke arah solusi yang lebih baik. Semisal dengan membiarkan semut menyetor jumlah feromon yang lebih tinggi di jalur pendek, pencarian jalur semut lebih cepat condong ke arah solusi terbaik. Ketergantungan pada jumlah deposit jejak feromon pada solusi kualitas juga ada pada beberapa spesies semut: Beckers et al. (1993) menemukan bahwa pada semut spesies Lasius niger semut yang kembali dari sumber makanan yang baik cenderung lebih banyak menjatuhkan feromon daripada yang kembali dari sumber makanan yang lebih buruk.

Pheromone evaporation.

Pada koloni semut nyata, intensitas feromon menurun berangsur-angsur karena penguapan. Dalam penguapan S-ACO disimulasikan dengan menerapkan aturan penguapan feromon yang didefinisikan secara khusus. 

Ants’ Path-Searching Behavior

Setiap semut membangun, dimulai dari node sumber, solusi untuk masalah dengan menerapkan kebijakan keputusan langkah demi langkah. Di setiap node, informasi lokal disimpan di node sendiri atau pada lintasan keluarnya dibaca (dirasakan) oleh semut dan digunakan dengan cara stokastik untuk memutuskan simpul mana yang akan dipindahkan ke berikutnya.

Di awal proses pencarian, jumlah feromon yang konstan dijatuhkan untuk semua lintasan. Ketika terletak di sebuah simpul, semut k menggunakan jalur feromon τij untuk menghitung probabilitas memilih j sebagai simpul berikutnya:

N adalah lingkungan semut k ketika dalam simpul i. Dalam S-ACO tudung tetangga simpul i berisi semua simpul yang terhubung langsung ke simpul i dalam grafik G, kecuali untuk pendahulu simpul I (mis., Simpul terakhir yang dikunjungi oleh semut sebelum pindah ke i). Dengan cara ini semut menghindari kembali ke simpul yang sama dengan mereka kunjungi sebelum simpul i. Hanya dalam kasus N kosong, yang sesuai dengan kebuntuan pada grafik, prekursor dari simpul i dimasukkan ke dalam N. 

Semut berulang kali melompat dari satu simpul ke simpul lainnya menggunakan kebijakan keputusan ini hingga akhirnya mencapai titik tujuan. Karena perbedaan antara jalur semut, maka langkah waktu di mana semut mencapai simpul tujuan mungkin berbeda dari semut ke semut lain (semut yang melalui jalur lebih pendek akan mencapai tujuan mereka lebih cepat).

Path Retracing and Pheromone Update

Saat mencapai node tujuan, semut beralih dari mode maju ke mode mundur dan kemudian menelusuri kembali langkah demi langkah jalur yang sama mundur ke sumber simpul, sebelum memulai perjalanan kembali, semut menghilangkan loop yang telah dibangun saat mencari node tujuannya. Masalah loop adalah bahwa mereka mungkin menerima feromon beberapa kali ketika seekor semut menelusuri kembali jalannya untuk menyimpan jejak feromon.

Penghapusan loop dapat dilakukan dengan memindai posisi pengidentifikasi simpul secara iteratifposisi mulai dari node sumber: untuk node di posisi ke-i, pathnya adalah dipindai mulai dari node tujuan hingga kemunculan pertama node tersebut ditemui, katakanlah, pada posisi j (selalu berpendapat bahwa i  j karena proses pemindaian berhenti pada posisi i terakhir). Proses pemindaian adalah divisualisasikan dalam gambar berikut:

Contoh juga menunjukkan bahwa prosedur eliminasi loop kami tidak selalu menghilangkan loop terbesar. Dalam contoh, loop 3 - 4 - 5 - 3 dari panjang 3 dihilangkan. Namun, loop terpanjang dalam contoh ini, loop 5 - 3 - 2 - 8 - 5 dari panjang 4, tidak dihilangkan karena tidak muncul kembali setelah menghilangkan loop yang pertama. Secara umum, jika jalur berisi loop bersarang, jalur bebas loop akhir akan tergantung pada urutan di mana loop dihilangkan.

Selama perjalanan kembali ke rumah, semut k menyetorkan sejumlah feromon pada lintasan yang telah dikunjungi. Khususnya, jika semut k berada dalam mode mundur dan melintasi maka akan mengubah nilai feromon τij sebagai berikut:

Dengan aturan ini, semut yang menggunakan lintasan yang menghubungkan simpul i ke simpul j meningkatkan probabilitas bahwa semut yang akan datang akan menggunakan lintasan yang sama di masa depan. Semakin pendek jalan semakin banyak feromon disimpan oleh semut. 

Pheromone Trail Evaporation

Dalam koloni semut nyata, jejak feromon juga menguap, tetapi, seperti yang telah kita lihat, penguapan tidak memainkan peran penting dalam penemuan jalur terpendek semut sungguhan. Itu fakta bahwa, sebaliknya, penguapan feromon tampaknya penting dalam Semut buatan mungkin karena fakta bahwa masalah optimasi ditangani oleh semut buatan jauh lebih kompleks daripada yang bisa dipecahkan semut nyata. Selain itu, penguapan feromon buatan juga memainkan fungsi penting untuk mengikat nilai maksimum yang dapat dicapai oleh jalur feromon. Penguapan mengurangi jejak feromon dengan kecepatan eksponensial. Di S-ACO, penguapan feromon disisipkan dengan deposit feromon semut. Setelah setiap semut k pindah ke simpul berikutnya sesuai dengan perilaku pencarian semut dijelaskan sebelumnya, jalur feromon diuapkan dengan menerapkan persamaan berikut untuk semua lintasan:

Setelah penguapan feromon telah diterapkan semua lintasan, jumlah feromon semut k ditambahkan ke lintasan. 

Secara khusus, hasil eksperimen yang disajikan di atas mendukung kesimpulan berikut: 

(1) efek panjang jalur berbeda, meskipun penting, tidak cukup untuk memungkinkan solusi efektif dari masalah optimasi besar; 

(2) feromon pembaruan berdasarkan kualitas solusi penting untuk konvergensi cepat; 

(3) nilai besar untuk parameter mengarah pada penekanan kuat pada fluktuasi awal, acak, dan burukperilaku algoritma; 

(4) semakin besar jumlah semut, semakin baik konvergensi dari algoritma, meskipun ini datang pada biaya waktu simulasi yang lebih lama;

(5) penguapan feromon penting ketika mencoba memecahkan yang lebih kompleks

tulisan ini adalah hasil terjemahan dari buku "Ant colony optimization" karya M Dorigo, T Stützle

yang diterbitkan oleh MIT Press tahun 2004