Mrówki w akcji

Jaki związek mają mrówki ze znajdowaniem najlepszych rozwiązań? Ano taki, że mrówki potrafią znaleźć najkrótszą drogę do pożywienia, będąc niemal ślepe. A jak to się dzieje? Dzięki współpracy i komunikacji za pomocą zapachu, który zostawiają w środowisku.

Podczas marszu od mrowiska do pożywienia i z powrotem mrówki zostawiają na podłożu substancję zwaną feromonem, formujac w ten sposób szlak feromonowy. Mrówki wyczuwają feromony i w momencie podejmowania decyzji starają sie wybrać tą drogę, na której jest większa koncentracja feromonu.

W algorytmie komputerowym naśladującym zachowanie kolonii mrówek, symulowana mrówka znajdująca się w pewnej lokalizacji wybierając kierunek marszu bierze pod uwagę dwa czynniki: nasilenie feromonu (gdzie jest największe) i odległość od pozostałych lokalizacji (gdzie jest najmniejsza). Przemieszczając się między lokalizacjami każda mrówka zostawia feromon.

Choć każda mrówka działa niezależnie, w nieświadomy sposób wpływa na postępowanie innych mrówek. W ten właśnie sposób feromon stopniowo znakuje globalnie optymalną (najkrótszą) trasę.

Poniższy program (kliknij i wybierz język) demonstruje działanie algorytmu mrówkowego. Zielonym kolorem pokazano bieżące natężenie feromonu pomiędzy lokalizacjami, a czarna linia to najkrótsza dotychczas znaleziona trasa.

Wbrew pozorom, algorytm mrówkowy można stosować do rozwiązywania najróżniejszych zadań optymalizacji, także takich, które nie przypominają zupełnie problemu komiwojażera.