Algorytm mrówkowy
Algorytm mrówkowy to technika stworzona przez Marco Dorigo, która wykorzystuje probabilistyczne podejście do rozwiązywania problemów, skupiając się na poszukiwaniu optymalnych ścieżek w grafach. Inspiracją dla tego algorytmu jest zachowanie mrówek, które poszukują jedzenia dla swojej kolonii.
W naturze mrówki poruszają się w sposób przypadkowy, jednak gdy znajdą pożywienie, wracają do kolonii, zostawiając za sobą ślad z feromonów. Kiedy inna mrówka natrafi na ten ślad, przestaje poruszać się losowo i podąża za nim w kierunku źródła pożywienia.
W miarę upływu czasu feromony ulegają wyparowaniu, co sprawia, że ich skuteczność maleje. Dłuższe trasy od pożywienia do kolonii mają więcej czasu na wyparowanie feromonów, co oznacza słabszy sygnał. Z kolei krótsze trasy charakteryzują się silniejszymi feromonami. Proces wyparowania feromonów jest korzystny, ponieważ pozwala na identyfikowanie najefektywniejszej drogi do pożywienia. Gdyby feromony nie znikały, każda nowa trasa miałaby taką samą moc jak poprzednia, co uniemożliwiłoby znalezienie optymalnego rozwiązania.
W sytuacji, gdy jedna mrówka odkryje skuteczną (krótką) trasę, inne mrówki również zaczną nią podążać, zostawiając kolejne feromony i tym samym wzmacniając ich obecność. W końcu wszystkie mrówki zaczną poruszać się tą samą, najlepszą drogą, podczas gdy inne trasy zostaną zapomniane (wyparują).
Przypisy
Bibliografia
E. Bonabeau, M. Dorigo i G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
Marco M. Dorigo, Ant Colony Optimization, Thomas T. Stützle, Cambridge, Mass.: MIT Press, 2004, ISBN 0-262-04219-3, OCLC 57182707. Brak numerów stron w książce.
M. Dorigo, G. Di Caro i L. M. Gambardella, 1999. „Ant Algorithms for Discrete Optimization”. Artificial Life, 5 (2): 137–172.
