Ślady Feromonowe Mrówek: Stigmergia, Najkrótsze Drogi i Algorytm Kolonii Mrówek

Brak przywódca, brak mapy, tylko chemia

Kolonia mrówek znajduje krótkie ścieżki między gniazdem a pożywieniem bez udziału jakiegokolwiek indywidualnego mrówka, który zna układ. Mechanizm to stigmergia: mrówki modyfikują swój współdzielone środowisko poprzez depozyt substancji feromonowej, a to zmodyfikowane środowisko kieruje decyzje kolejnej mrówki, bez żadnej bezpośredniej komunikacji między nimi. Klasyczny feromon to substancja śladowa kładzona przez pysk jako mrówka idzie, która ulega zniszczeniu w ciągu kilku minut do kilku godzin w zależności od gatunku i pogody.

Samotna mrówka opuszczająca gniazdo wędruje losowo, kładąc feromony w miarę postępu. Jeśli znajdzie pokarm, wraca drogą obciążoną silniejszymi istniejącymi śladami, ponownie kładąc feromony w drodze powrotnej — więc udany pojedynczy cykl zostaje oznaczony dwa razy. Zasada, którą podąża każda jednostka, jest prosta: na rozwidleniu skręć w kierunku gałęzi z wyższą koncentracją feromonów, ważoną prawdopodobieństwem zamiast deterministycznie, aby zapewnić ciągłe eksplorowanie.

Pozytywna informacja wywiera wpływ na wybór najkrótszej ścieżki

Eksperymenty podwójnego mostu prowadzona przez Deneuborga i współpracowników (1990) sprawdziły to: dwa drogi o różnej długości łączą gniazdo z pożywieniem, a mrówki są wolne wyboru pomiędzy nimi w punkcie rozwidlenia. Na początku wybór jest zbliżony do 50/50, ale droga, która przypadkowo uzyskuje nieco więcej ruchu na początku, szybciej kumuluje feromony, wpływając na późniejsze mrówki, które kierują się ku niej, wzmacniając to dalej — autocataliza. Ponieważ krótsza droga jest kończona (i tym samym ponownie oznaczana) częściej na jednostkę czasu, jej stężenie feromonów kumuluje się szybciej, a kolonia koncentruje się na krótszym szlaku, nawet jeśli żadna mrówka nigdy nie porównywała długości obu dróg.

P(wybór gałęzi i) = (k + feromony_i)^n / Σ_j (k + feromony_j)^n k, n: stałe kontrolujące, jak silnie wpływ feromonów przekłada się na wybór, (oryginalny model Deneuborga użył n ≈ 2, dając stosunkowo ostre, zwycięski-zajmuje-wszystko zbieżność, gdy jedna gałąź wyprzedza), Erozja jest niezbędna, a nie przypadkowa: bez zaniku, wczesny wypadek (dłuższa droga oznaczona najpierw przez przypadek) mógłby zostać trwale zablokowany. Ponieważ ścieżka feromonowa stale ulega zanikowi, droga przestaje być wzmacniana i kolonia może ją porzucić, jeśli jedzenie wyczerpie się lub zostanie później odkryta krótsza trasa — ta sama erozja, która pozwala jej zapomnieć o błędach, pozwala jej je skorygować.

p(choose branch i) = (k + pheromone_i)^n / Σ_j (k + pheromone_j)^n

k, n: constants controlling how strongly pheromone bias translates into choice
      (Deneubourg's original model used n ≈ 2, giving a fairly sharp,
      winner-take-most convergence once one branch pulls ahead)

Optymalizacja Kolonii Młódźca

Marco Dorigo zformalizował to jako Optymalizację Kolonii Młódźca (OKM), metaheurystykę dla problemów kombinatorycznych, takich jak problem komiwojażera. Wirtualne mrówki budują trasy krok po kroku, kierując się wirtualną macierzą feromonów; po każdej generacji trasy z dobrych (krótkich) tras wzmacniane są, a wszystkie feromony lekko parują. Przez wiele iteracji macierz feromonów koncentruje się na krawędziach występujących w krótkich trasach, a populacja zbliża się do optymalnych rozwiązań bez konieczności obliczania ich dokładnie.

dla każdej generacji: każde wirtualne mrówki buduje pełną trasę, wybierając następne miasto z prawdopodobieństwem ∝ feromun(krawędź)^α · (1/odległość)^β parowanie: feromun *= (1 − ρ) dla wszystkich krawędzi wzmocnienie: feromun(krawędź) += Δ / długość_trasy dla każdej użytej krawędzi (największy wzrost dla krawędzi występujących w najlepszych znalezionych trasach) OKM i jej powiązane metody są wykorzystywane do optymalizacji trasowania pojazdów, routingu sieci oraz harmonogramowania zleceń roboczych, generalnie tam, gdzie przestrzeń poszukiwań jest zbyt duża, aby ją przeliczyć, ale ma wystarczającą strukturę, aby wzmacnianie częściowo dobrych decyzji wypłacało się. Dzieli ona podstawowe składniki systemu biologicznego: współdzieloną, rozkładającą się pamięć, którą wiele niezależnych, krótkowzrocznych agentów czyta i zapisuje.

for each generation:
  each virtual ant builds a full tour, choosing next city
      with probability ∝ pheromone(edge)^α · (1/distance)^β
  evaporate: pheromone *= (1 − ρ)   for all edges
  reinforce: pheromone(edge) += Δ / tour_length   for every edge used
             (biggest boost to edges on the best tours found so far)

Dlaczego jest to odporne

Mechanizm ten nie posiada pojedynczego punktu awarii: zabicie dowolnej pojedynczej muchówki nie wpływa na jej żerowanie, ponieważ ścieżka – a nie pamięć żadnej muchówki – zawiera rozwiązanie. Ponadto adaptuje się on stale; zablokowanie obecnej trasy powoduje, że kolonia ponownie eksploruje i tworzy świeżą ścieżkę wokół przeszkody w ciągu kilku minut, co nie byłoby możliwe dla kolonii korzystającej z ustalonych, zapamiętanych tras. Koszt stanowi to jednak fakt, że poszukiwanie stigmeryczne może utknąć na gorszej ścieżce, jeśli zbyt szybko zbiegnie się z lepszą alternatywą – ten sam autocataliz mechanizm, który szybko znajduje krótkie trasy, może również zablokować jedynie dobrą.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Ant Pheromone Trails i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.