Wejdź do lasu
Mrówcze ścieżki
Podpatrzone u natury

Mrówcze ścieżki

Owady bez mapy, które uczą komputery szukać drogi

✦ Potwierdzone

Żadna mrówka nie zna mapy. Mimo to cała kolonia znajduje najkrótszą drogę do jedzenia. Młody Włoch zamienił ten trik w program komputerowy.

Kto: Jean-Louis Deneubourg, Marco Dorigo · Kiedy: 1989–1992 · Gdzie: Bruksela, Belgia i Mediolan, Włochy

Zobacz ilustrowaną historięzdjęcia, animacje i doświadczenia do zrobienia samemu

Natura i wynalazek

Mrówki znaczą drogę zapachem, feromonem. Na krótszej ścieżce mrówki szybciej wracają, więc zapach gęstnieje i przyciąga kolejne. Dłuższa droga powoli wietrzeje.

Algorytmy mrówkowe, czyli programy, w których wirtualne mrówki szukają dobrych tras dla ciężarówek, planów produkcji i ruchu w sieciach komputerowych.

Opowieść

Pod koniec lat 80. belgijski zespół Jean-Louisa Deneubourga postawił mrówkom argentyńskim zadanie: od gniazda do pożywienia prowadziły dwa mostki, krótki i długi. Na początku mrówki szły obiema drogami po równo.

Po kilku minutach prawie cała kolonia wybrała krótszy mostek. Nikt tym nie dowodził. Wystarczyło, że mrówki na krótszej drodze szybciej wracały i częściej ją znaczyły.

Marco Dorigo, doktorant z Politechniki Mediolańskiej, uznał, że to gotowy przepis na trudne zadania matematyczne. W 1992 roku w swoim doktoracie opisał pierwszy algorytm mrówkowy: wirtualne mrówki chodzą po mapie miast, zostawiają cyfrowy zapach, a zapach paruje.

Dziś algorytmy mrówkowe są jedną z rodzin metod optymalizacji. Używa się ich do planowania tras dostaw, przydziału zadań i badań nad trasowaniem w sieciach komputerowych.

Jak to działa

  1. Zapach: Każda mrówka wracająca z jedzeniem znaczy drogę. Następne mrówki wolą ścieżki, które pachną mocniej.
  2. Wzmocnienie: Krótka droga jest szybciej przebywana, więc dostaje więcej zapachu w tym samym czasie. Dobra trasa sama się wzmacnia.
  3. Parowanie: W programie zapach powoli znika. Dzięki temu wirtualne mrówki nie utkną na pierwszej, przypadkowej trasie i dalej szukają lepszej.

Sprawdź sam

  1. Dwie drogi do cukru: Latem połóż kroplę miodu w dwóch odległościach od mrówczej ścieżki, z dwoma patyczkami jako mostkami: krótkim i długim. Po kwadransie policz mrówki na każdym mostku.
  2. Zmaż ślad: Przetrzyj palcem w poprzek mrówczej ścieżki na płytce chodnikowej. Patrz, jak mrówki gubią się w tym miejscu i szukają zapachu.
  3. Mrówki na papierze: Narysuj pięć miast na kartce i szukaj najkrótszej trasy przez wszystkie. Policz, ile jest możliwych tras. Przy dwudziestu miastach jest ich więcej niż ziaren piasku na plaży.

Co wiadomo na pewno

Doświadczenia z mostkami opisali Goss, Aron, Deneubourg i Pasteels w 1989 roku. Algorytm mrówkowy zaproponował Marco Dorigo w 1992 roku i od tego czasu jest szeroko stosowaną metodą przybliżonego rozwiązywania zadań o trasach. Nie zawsze daje najlepszy wynik, ale zwykle dobry i szybko.

Źródła