Algoritma Koloni Semut (ACO)

Ant Colony Optimization ACO atau Algoritma Koloni Semut adalah sebuah probabilistik komputasi teknik untuk memecahkan masalah yang dapat dikurangi untuk menemukan jalur yang baik melalui grafik.

Algoritma ini adalah anggota dari keluarga algoritma koloni semut, pada intelijen segerombolan metode, dan hal itu merupakan beberapa metaheuristic optimasi. Awalnya diusulkan oleh Marco Dorigo tahun 1992 di gelar PhD tesis [1] [2], algoritma pertama yang bertujuan untuk mencari jalan yang optimal dalam grafik; berdasarkan perilaku semut mencari jalan antara koloni dan sumber makanan . Aslivvz ide ini telah diversifikasi untuk menyelesaikan kelas yang lebih luas dari masalah numerik, dan sebagai hasilnya, beberapa masalah telah muncul, menggambar tentang berbagai aspek perilaku semut.

Ringkasan

Di dunia nyata, semut (awalnya) berjalan secara acak, dan ketika menemukan makanan kembali ke koloni mereka sambil meletakkan feromon jejak. Jika semut lain menemukan jalur tersebut, mereka tidak cenderung untuk menjaga bepergian secara acak, tapi malah mengikuti jejak, kembali dan menguatkannya jika pada akhirnya mereka menemukan makanan.

Seiring waktu, Namun, jejak feromon mulai menguap, sehingga mengurangi kekuatan yang menarik. Semakin banyak waktu yang diperlukan untuk seekor semut melakukan perjalanan menyusuri jalan setapak dan kembali lagi, semakin banyak waktu yang harus feromon menguap.
Jalan pendek, dengan perbandingan, akan berjalan lebih cepat, dan dengan demikian kerapatan feromon akan tetap tinggi seperti yang diletakkan di jalan secepat dapat menguap. Penguapan feromon juga mempunyai keuntungan untuk menghindari konvergensi solusi optimal secara lokal. Jika tidak ada penguapan sama sekali, jalur yang dipilih oleh semut pertama akan cenderung menarik secara berlebihan yang berikut. Dalam hal ini, eksplorasi ruang solusi akan dibatasi.

Jadi, ketika seekor semut menemukan yang baik (yakni, pendek) jalur dari koloni ke sumber makanan, semut lain lebih cenderung mengikuti jalan, dan umpan balik yang positif pada akhirnya menyebabkan semua semut berikut satu jalan. Ide dari algoritma koloni semut adalah untuk meniru perilaku ini dengan "simulasi semut" berjalan di sekitar grafik yang menunjukkan masalah yang harus diselesaikan.

Detail
Gagasan awalnya berasal dari mengamati makanan eksploitasi sumber daya di antara semut, di mana semut 'secara individual memiliki kemampuan kognitif terbatas secara kolektif mampu menemukan jalur terpendek antara sumber makanan dan sarang.

..........................
..........................

1. Semut pertama menemukan sumber makanan (F), melalui cara apapun (a), kemudian kembali ke sarang (N), meninggalkan jejak feromon (b)
2. Semut tanpa pandang bulu cara mengikuti empat kemungkinan, tapi penguatan landasan membuatnya lebih menarik sebagai rute terpendek.
3. Semut mengambil rute terpendek, panjang bagian-bagian dari cara-cara lain kehilangan jejak feromon.

Dalam serangkaian percobaan pada koloni semut dengan pilihan antara dua tidak sama panjang jalan yang mengarah ke sumber makanan, ahli biologi telah mengamati bahwa semut cenderung menggunakan rute terpendek. [3] [4] Sebuah model yang menjelaskan perilaku ini adalah sebagai berikut

1. Semut (disebut "kilat") berjalan lebih atau kurang secara acak di sekitar koloni;
2. Jika menemukan sumber makanan, itu kembali lebih atau kurang langsung ke sarang, meninggalkan dalam jalur jejak feromon;
3. Feromon ini yang menarik, di dekatnya semut akan cenderung mengikuti, lebih atau kurang langsung, trek;
4. Kembali ke koloni, semut ini akan memperkuat rute;
5. Jika dua rute yang mungkin untuk mencapai sumber makanan yang sama, yang lebih pendek akan, dalam waktu yang sama, yang ditempuh oleh lebih banyak semut daripada rute yang panjang akan
6. Rute pendek akan semakin ditingkatkan, dan karena itu menjadi lebih menarik;
7. Rute yang panjang akhirnya akan menghilang, feromon yang mudah menguap;
8. Akhirnya, semua semut telah ditentukan dan karena itu "dipilih" rute terpendek.
   

Semut menggunakan lingkungan sebagai media komunikasi. Mereka bertukar informasi secara tidak langsung dengan mendepositokan feromon, semua rincian status mereka "bekerja". Bertukar informasi memiliki lingkup lokal, hanya seekor semut yang terletak di mana feromon dibiarkan mempunyai pengertian dari mereka. Sistem ini disebut "Stigmergy" dan terjadi di banyak hewan sosial masyarakat (hal itu telah dipelajari dalam kasus pembangunan pilar dalam sarang rayap).

Mekanisme untuk menyelesaikan masalah terlalu kompleks untuk ditangani oleh satu semut adalah contoh yang baik dari diri-sistem terorganisir. Sistem ini didasarkan pada umpan balik positif (yang deposit menarik feromon semut lain yang akan memperkuat sendiri) dan negatif (disipasi dari rute oleh sistem mencegah penguapan dari labrakan). Secara teoritis, jika jumlah feromon tetap sama dari waktu ke waktu pada semua sisi, tidak ada rute yang akan dipilih. Namun, karena umpan balik, sedikit variasi pada pinggir akan diperkuat dan dengan demikian memungkinkan pilihan dari tepi. Algoritma akan bergerak dari keadaan yang tidak stabil di mana tidak ada ujung lebih kuat daripada yang lain, untuk negara yang stabil di mana rute terdiri dari tepi paling kuat.

Aplikasi
Algoritma optimisasi koloni semut telah diterapkan ke banyak permasalahan optimasi kombinatorial, mulai dari penugasan kuadrat melipat protein atau routing kendaraan dan banyak metode yang diturunkan telah disesuaikan untuk masalah dinamis dalam variabel-variabel riil, masalah-masalah stokastik, multi-target dan implementasi paralel.

Ini juga telah digunakan untuk menghasilkan solusi optimal mendekati ke masalah salesman keliling. Mereka memiliki kelebihan simulasi annealing dan algoritma genetika pendekatan masalah serupa saat grafik mungkin berubah secara dinamis; algoritma koloni semut dapat dijalankan terus menerus dan beradaptasi dengan perubahan secara real time. This is of interest in network routing and urban transportation systems. Hal ini menarik dalam routing jaringan dan sistem transportasi perkotaan.
Sebagai contoh yang sangat bagus, Algoritma optimisasi koloni semut telah digunakan untuk menghasilkan solusi optimal mendekati ke masalah salesman keliling. Pada setiap tahap, semut memilih untuk berpindah dari satu kota ke yang lain menurut beberapa aturan:

1. Harus mengunjungi setiap kota tepat satu kali;
2. Sebuah kota yang jauh memiliki lebih sedikit kesempatan untuk dipilih (visibilitas);
3. Semakin kuat jejak feromon diletakkan pada tepi antara dua kota, semakin besar kemungkinan bahwa tepi akan dipilih;
4. Setelah menyelesaikan perjalanannya, deposit semut lebih feromon pada semua sisi itu dilalui, jika perjalanan pendek;
5. Setelah setiap iterasi, jejak feromon menguap.
   

Aco_TSP.svg (Berkas SVG, nominal 1.000 × 375 piksel, besar berkas: 85 KB)
Salah satu contoh's Pseudo-kode dan formula
procedure ACO_MetaHeuristic
while(not_termination)
generateSolutions()
daemonActions()
pheromoneUpdate()
end while
end procedure

Edge Selection:
Semut akan bergerak dari node i ke node j dengan probabilitas





di mana

τ _{i , j} is the amount of pheromone on edge i , j τ _{i, j} adalah jumlah feromon di tepi i, j

α is a parameter to control the influence of τ _{i , j} α adalah parameter untuk mengontrol pengaruh τ _{i, j}

η _{i , j} is the desirability of edge i , j (a priori knowledge, typically 1 / d _{i , j} , where d is the distance) η _{i, j} adalah keinginan tepi i, j (a priori pengetahuan, biasanya 1 / d _{i, j,} di mana d adalah jarak)

β is a parameter to control the influence of η _{i , j} β adalah parameter untuk mengontrol pengaruh η _{i, j}

Pheromone Update Feromon Update

τ _{i , j} = (1 − ρ)τ _{i , j} + Δτ _{i , j} τ _{i, j} = (1 - ρ) τ _{i, j} + Δτ _{i, j}

where di mana

τ _{i, j} adalah jumlah feromon pada sisi tertentu i, j

ρ adalah feromon tingkat penguapan

dan Δτ _{i, j} adalah jumlah feromon diendapkan, biasanya diberikan oleh

di mana L _k adalah biaya dari th k tur semut (biasanya panjang).

Common ekstensi

Berikut adalah beberapa variasi paling populer Algoritma ACO

1. Elitis Sistem Ant

• Solusi terbaik global deposito feromon pada setiap iterasi bersama dengan semua semut lain
  

1. Max-Min Ant System (MMAS) [6]

• Ditambahkan Maksimum dan Minimum jumlah feromon [τ _max, τ _min]
• Hanya global iterasi terbaik atau disetor wisata terbaik feromon
• Semua tepi-tepi yang telah siap untuk melakukan τ _max dan reinitialized untuk τ _max ketika mendekati stagnasi.

1. pseudo-acak proporsional aturan. telah disajikan di atas [7]

1. Rank Berbasis Ant System (ASrank)

• Semua solusi yang peringkat menurut kebugaran mereka. Jumlah feromon disimpan kemudian bobot untuk setiap solusi, sehingga solusi yang lebih baik deposito kebugaran lebih feromon daripada solusi dengan kebugaran lebih buruk

Untuk beberapa versi algoritma, adalah mungkin untuk membuktikan bahwa itu konvergen (mis. itu mampu menemukan global optimum dalam waktu tertentu). Bukti pertama konvergensi algoritma koloni semut dibuat pada tahun 2000, grafik berbasis algoritma sistem semut, dan kemudian algoritma untuk ACS dan MMAS. Seperti kebanyakan metaheuristics, sangat sulit untuk memperkirakan kecepatan teoritis konvergensi. Pada tahun 2004, Zlochin dan koleganya [8] telah menunjukkan tipe COA dapat diasimilasikan algoritma metode stokastik gradient descent, pada salib-entropi dan algoritma Estimasi distribusi. Mereka mengusulkan bahwa metaheuristics sebagai "model berbasis penelitian"

Contoh-contoh lainnya
Algoritma koloni semut ini awalnya digunakan terutama untuk menghasilkan solusi optimal mendekati ke masalah salesman keliling dan, lebih umum, masalah-masalah optimasi kombinatorial. Hal ini diamati bahwa sejak itu mulai penggunaannya telah menyebar ke daerah klasifikasi [9] dan image processing.

Sebuah kesulitan dalam definisi
Dengan algoritma ACO, jalan terpendek dalam grafik, antara dua titik A dan B, dibangun dari kombinasi beberapa jalan. Tidaklah mudah untuk memberikan definisi yang tepat tentang apa algoritma atau tidak sebuah koloni semut, karena definisi dapat bervariasi menurut para penulis dan penggunaannya. Secara umum, algoritma koloni semut dianggap sebagai dihuni metaheuristics solusi dengan masing-masing diwakili oleh semut bergerak dalam ruang pencarian. Semut menandai solusi terbaik dan memperhatikan tanda-tanda sebelumnya untuk mengoptimalkan pencarian mereka. Mereka dapat dilihat sebagai probabilistik multi-agen algoritma menggunakan distribusi probabilitas untuk melakukan transisi antara setiap iterasi. Dalam versi untuk masalah kombinatorial, mereka menggunakan konstruksi berulang-ulang solusi. Menurut beberapa penulis, hal yang membedakan algoritma ACO dari sanak keluarga lainnya (seperti algoritma untuk memperkirakan distribusi atau partikel kawanan optimasi) adalah justru mereka aspek konstruktif. Dalam masalah kombinatorial, adalah mungkin bahwa solusi terbaik pada akhirnya akan ditemukan, meskipun tidak ada semut akan terbukti efektif. Jadi, dalam contoh dari penjual Travelling masalah, tidak perlu bahwa semut benar-benar perjalanan rute terpendek: rute terpendek dapat dibangun dari segmen terkuat solusi yang terbaik. Namun, definisi ini bisa menimbulkan masalah dalam kasus masalah dalam variabel-variabel riil, di mana tidak ada struktur 'tetangga' ada. Perilaku kolektif serangga sosial tetap menjadi sumber inspirasi bagi peneliti. Berbagai macam algoritma (untuk pengoptimalan atau tidak) mencari diri-organisasi dalam sistem biologis telah menyebabkan konsep "kecerdasan berkerumun", yang merupakan kerangka kerja yang sangat umum di mana algoritma koloni semut cocok.

Stigmergy algoritma
Ada dalam prakteknya sejumlah besar algoritma yang mengaku sebagai "koloni semut", tanpa selalu berbagi kerangka umum optimasi oleh koloni semut kanonik (COA). Dalam prakteknya, penggunaan pertukaran informasi antara semut melalui lingkungan (sebuah prinsip yang disebut "Stigmergy") adalah dianggap cukup untuk sebuah algoritma untuk termasuk dalam kelas dari algoritma koloni semut. Prinsip ini telah mendorong beberapa penulis untuk menciptakan istilah "nilai" untuk mengatur metode dan perilaku yang didasarkan pada makanan pencarian, pengurutan larva, pembagian kerja dan kooperatif transportasi. [10].

Related metode

• Algoritma genetik (GA) mempertahankan genangan solusi daripada hanya satu. Proses pencarian solusi unggul meniru bahwa evolusi, dengan solusi yang sedang digabungkan atau bermutasi untuk mengubah kolam solusi, dengan solusi berkualitas rendah yang dibuang.
• Simulated annealing (SA) adalah berkaitan dengan teknik pengoptimalan global yang melintasi ruang pencarian dengan menghasilkan solusi tetangga solusi saat ini. Tetangga yang lebih rendah diterima probabilistically didasarkan pada perbedaan kualitas dan parameter suhu. Parameter suhu ini dimodifikasi sebagai kemajuan algoritma untuk mengubah sifat pencarian.
• Tabu search (TS) mirip dengan simulasi anil dalam kedua melintasi ruang solusi dengan menguji mutasi dari solusi individu. Sementara simulasi anil hanya satu bermutasi menghasilkan solusi, tabu cari solusi menghasilkan banyak bermutasi dan bergerak ke solusi dengan kesesuaian terendah yang dihasilkan. ntuk mencegah bersepeda dan mendorong gerakan yang lebih besar melalui ruang solusi, sebuah daftar tabu dipertahankan parsial atau solusi lengkap. Hal ini dilarang untuk pindah ke sebuah solusi yang berisi elemen dari daftar tabu, yang diperbarui sebagai solusi solusi melintasi ruang.
• Buatan sistem kekebalan (AIS) adalah algoritma yang meniru sistem kekebalan tubuh vertebrata.
• Particle swarm optimization (PSO) lain yang sangat sukses intelijen Swarm metode
  
• Koloni semut metode clustering (ACCM) Salah satu metode yang efisien menggunakan pendekatan clustering, memperluas ACO.
  

Sejarah

• 1959, Pierre-Paul Grass menemukan teori Stigmergy untuk menjelaskan perilaku bangunan sarang rayap [11];
• 1983, Deneubourg dan rekan-rekannya mempelajari perilaku kolektif dari semut [12];
• 1988, dan Moyson Manderick memiliki artikel tentang organisasi diri di antara semut [13];
• 1989, karya Goss, Aron, Pasteels di Deneubourg dan perilaku kolektif semut Argentina, yang akan memberikan ide Algoritma optimisasi koloni semut [3];
• 1989, pelaksanaan model perilaku untuk makanan oleh Ebling dan rekan-rekannya [14];
• 1991, M. Dorigo mengusulkan Sistem Ant tesis doktoralnya (yang diterbitkan pada tahun 1992 [2] dengan V. Maniezzo dan A. Colorni). a technical report [ 15 ] was published five years later [ 5 ] ; laporan teknis [15] diterbitkan lima tahun kemudian [5];
• 1995, Bilchev dan mempublikasikan Parmee usaha pertama untuk beradaptasi dengan masalah-masalah yang berkelanjutan [16];
• 1996, penerbitan artikel di Ant [5];
• 1996, Hoos dan menciptakan Stützle MAX-MIN Ant System [6];
• 1997, Dorigo dan menerbitkan Gambardella Ant Colony [7];
• 1997, Martinoli dan rekan-rekannya menggunakan Algoritma ACO untuk mengendalikan robot [18]
• 1998, Dorigo meluncurkan konferensi pertama yang didedikasikan untuk algoritma ACO [19];
• 1998, mengusulkan Stützle awal implementasi paralel [20];
• 1999, Bonabeau dan koleganya telah menerbitkan sebuah buku berurusan terutama buatan semut [21]
• 1999, aplikasi pertama untuk kendaraan routing, maka kuadrat penugasan, multi-dimensi masalah ransel;
• 2000, edisi khusus jurnal tentang algoritma ACO [22]
• 2000, aplikasi pertama ke penjadwalan, penjadwalan urutan dan kepuasan kendala;
• 2000, Gutjahr memberikan bukti pertama konvergensi untuk algoritma koloni semut [23]
• 2001, penggunaan pertama COA Algoritma oleh perusahaan (Eurobios dan AntOptima);
• 2001, Ireda dan rekan-rekannya menerbitkan multi-objektif pertama algoritma [24]
• 2002, aplikasi pertama dalam merancang jadwal, Bayesian jaringan;
• 2002, Bianchi dan rekan-rekannya menyarankan algoritma pertama untuk stokastik masalah [25];
• 2004, Zlochin dan Dorigo menunjukkan bahwa beberapa algoritma yang setara dengan gradien stokastik keturunan, yang lintas-entropi dan algoritma untuk memperkirakan distribusi [8]
• 2005, aplikasi pertama untuk lipat protein.

Referensi

1. A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.
2. M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
3. S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, The self-organized exploratory pattern of the Argentine ant, Naturwissenschaften, volume 76, pages 579-581, 1989
4. J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, Journal of Insect Behavior, volume 3, page 159, 1990
5. M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics--Part B , volume 26, numéro 1, pages 29-41, 1996.
6. T. Stützle et H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, volume 16, pages 889-914, 2000
7. M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.
8. M. Zlochin, M. Birattari, N. Meuleau, et M. Dorigo, Model-based search for combinatorial optimization: A critical survey, Annals of Operations Research, vol. 131, pp. 373-395, 2004.
9. D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, B. Baesens, Classification with Ant Colony Optimization, IEEE Transactions on Evolutionary Computation, volume 11, number 5, pages 651—665, 2007.
10. A. Ajith; G. Crina; R. Vitorino (éditeurs), Stigmergic Optimization, Studies in Computational Intelligence , volume 31, 299 pages, 2006. ISBN 978-3-540-34689-0
11. P.-P. Grassé, La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie : Essai d’interprétation du comportement des termites constructeurs, Insectes Sociaux, numéro 6, p. 41-80, 1959.
12. J.L. Denebourg, J.M. Pasteels et J.C. Verhaeghe, Probabilistic Behaviour in Ants : a Strategy of Errors?, Journal of Theoretical Biology, numéro 105, 1983.
13. F. Moyson, B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Californie, 1988.
14. M. Ebling, M. Di Loreto, M. Presley, F. Wieland, et D. Jefferson,An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the SCS Multiconference on Distributed Simulation, 1989
15. Dorigo M., V. Maniezzo et A. Colorni, Positive feedback as a search strategy, rapport technique numéro 91-016, Dip. Elettronica, Politecnico di Milano, Italy, 1991
16. G. Bilchev et I. C. Parmee, The Ant Colony Metaphor for Searching Continuous Design Spaces, Proceedings of the AISB Workshop on Evolutionary Computation. Terence C. Fogarty (éditeurs), Evolutionary Computing Springer-Verlag, pages 25-39, avril 1995.
17. R. Schoonderwoerd, O. Holland, J. Bruten et L. Rothkrantz, Ant-based load balancing in telecommunication networks, Adaptive Behaviour, volume 5, numéro 2, pages 169-207, 1997
18. A. Martinoli, M. Yamamoto, et F. Mondada, On the modelling of bioinspired collective experiments with real robots, Fourth European Conference on Artificial Life ECAL-97, Brighton, UK, juillet 1997.
19. M. Dorigo, ANTS’ 98, From Ant Colonies to Artificial Ants : First International Workshop on Ant Colony Optimization, ANTS 98, Bruxelles, Belgique, octobre 1998.
20. T. Stützle, Parallelization Strategies for Ant Colony Optimization, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, volume 1498, pages 722-731, 1998.
21. É. Bonabeau, M. Dorigo et G. Theraulaz, Swarm intelligence, Oxford University Press, 1999.
22. M. Dorigo , G. Di Caro et T. Stützle, special issue on "Ant Algorithms", Future Generation Computer Systems, volume 16, numéro 8, 2000
23. W.J. Gutjahr, A graph-based Ant System and its convergence, Future Generation Computer Systems, volume 16, pages 873-888, 2000.
24. S. Iredi, D. Merkle et M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, Evolutionary Multi-Criterion Optimization, First International Conference (EMO’01), Zurich, Springer Verlag, pages 359-372, 2001.
25. L. Bianchi, L.M. Gambardella et M.Dorigo, An ant colony optimization approach to the probabilistic traveling salesman problem, PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, Berlin, Allemagne, 2002.
26. http://en.wikipedia.org/wiki/Ant_colony_optimization