Algorytm mrówkowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Algorytm mrówkowy został zainspirowany zachowaniem mrówek poszukujących pożywienia

Algorytm mrówkowy, zaproponowany przez Marco Dorigo[1], jest probabilistyczną techniką rozwiązywania problemów poprzez szukanie dobrych dróg w grafach. Jest on zainspirowany zachowaniem mrówek szukających pożywienia dla swojej kolonii.

W prawdziwym świecie, mrówki poruszają się w sposób losowy; gdy znajdują pożywienie, wracają do swojej kolonii pozostawiając ślad składający się z feromonów[2]. Gdy inna mrówka natknie się na ten ślad, przestaje poruszać się w sposób losowy i podąża za śladem w kierunku pożywienia.

Jednak po pewnym czasie feromony wyparowują, a więc siła ich działania maleje. Im dłuższa jest trasa od pożywienia do kolonii, tym więcej mają czasu feromony, aby wyparować. Krótsze trasy jednak zapewniają, iż siła działania feromonów będzie większa. Parowanie feromonów jest efektem pozytywnym, bowiem pozwala to na odnajdywanie optymalnej trasy do pożywienia. Gdyby feromony nie wyparowywały, każda kolejna trasa miałaby taką samą siłę jak poprzednia, przez co nie dochodziłoby do odnalezienia optymalnego rozwiązania problemu.

Zatem, gdy jedna mrówka odnajdzie dobrą (krótką) drogę, inne mrówki będą podążać tą właśnie drogą również zostawiając feromony, a więc zwiększając ich natężenie. Ostatecznie wszystkie mrówki będą poruszać się tą samą, najlepszą drogą, a pozostałe drogi zostaną zapomniane (wyparują).

Bibliografia[edytuj | edytuj kod]

  • E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
  • M. Dorigo & T. Stützle, 2004. Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3
  • M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Artificial Life, 5 (2): 137–172.

Przypisy

  1. Dorigo, M., 1992. Optimization, Learning and Natural Algorithms, rozprawa doktorska (PhD thesis), Politecnico di Milano, Włochy.
  2. Stanisław Ignatowicz: Mrówki. Murator, 2010-02-23.