ACO: Jak Żymy Rozwiązują Trudne Problemy

Stigmergia: koordynacja bez dowódcy

W 1959 roku entomolog Pierre-Paul Grassé ukuł termin stigmergia – to koordynacja zachodząca w całości poprzez środowisko wspólne, a nie bezpośrednie sygnalizowanie. Prawdziwe mrówki nigdy nie wydają instrukcji sobie nawzajem. Każda mrówka odkładając ślad feromonowy podczas poruszania się, każda kolejna reaguje jedynie na zgromadzony ślad pozostawiony przez całą kolonię. Umieszczając przeszkodę między gniazdem a źródłem pokarmu z krótkim obok i długim odcinkiem, mrówki początkowo rozkładają równomiernie się na obu trasach. Mrówki, które podążały krótszą drogą, wracały wcześniej i odkładając feromon wcześniej, więc krótka droga szybciej gromadziła zapach – pozytywna pętla sprzężenia zwrotnego, która w ciągu kilku minut skierowała niemal cały ruch na optymalną trasę, a żadna mrówka nigdy nie widziała całego obrazu.

Od stigmergii do algorytmu

Optymalizacja Kolonii Żądów (ACO), wprowadzona przez Marco Dorigo w 1992 roku, przekształca to zachowanie w ogólne rozwiązanie problemów kombinatorycznych, a najczęściej problem podróży sprzedawcy: znaleźć najkrótszy cykl Hamiltona przez n miast. Liczba możliwych tras wynosi (n−1)!/2 – dla 20 miast jest to już około ~6×10¹⁶, więc metoda przeszukiwania wszechstronnego (brute force) jest niemożliwa. Każdy odcinek (i, j) między dwoma miastami przenosi dwie liczby: stałą długość d[i][j] i zmienną zawartość feromonową τ[i][j], oraz wyprowadzona widzialność η[i][j] = 1/d[i][j], która faworyzuje krótkie odcinki.

Jedna iteracja składa się z trzech faz: każda żuka niezależnie konstruuje pełną trasę, długość każdej trasy jest oceniana, a mapa feromonowa jest aktualizowana na podstawie tych wyników. Powtórz to kilkaset razy i mapa feromonowa zbliża się do najkrótszych tras znalezionych.

Prawdopodobieczny wybór krawędzi i aktualizacja feromonów

Stojąc w mieście i, mrówka wybiera swoje następne nieodwiedzone miasto j z prawdopodobieństwem proporcjonalnym do mieszanki feromonów i widzialności, ważonej przez wykładniki α i β:

p[i][j] = ( τ[i][j]^α · η[i][j]^β ) / Σ_l∈dozwolone ( τ[i][l]^α · η[i][l]^β ) α — waga przypisana zgromadzonym feromonom (zwykle: 1) β — waga przypisana surowej odległości (zwykle: 2–5) dozwolone — zbiór miast, które jeszcze nie zostały odwiedzone przez tę mrówkę Po zakończeniu pracy przez wszystkie mrówki feromony są aktualizowane w dwóch etapach – odparowywanie, a następnie depozycja:

τ[i][j] ← (1 − ρ) · τ[i][j] // odparowywanie, ρ ≈ 0.1 τ[i][j] ← τ[i][j] + Σ_k Δτ_k[i][j] // depozycja Δτ_k[i][j] = Q / L_k jeśli mrówka k użyła krawędzi (i,j), w przeciwnym razie 0 Q — stała, L_k — długość wycieczki mrówki k Odparowywanie to nie drobiazg – bez tego pierwsza, średnia trasa, która kiedykolwiek została znaleziona, stale gromadziłaby coraz więcej feromonów, a kolonia nigdy by się jej nie zastanawiała. Mrówki znajdujące krótsze trasy depozycji feromonów w proporcji większej (Q/L jest większe, gdy L jest mniejsze), co najszybciej wzmacnia dobre krawędzie.

p[i][j] = ( τ[i][j]^α · η[i][j]^β ) / Σ_l∈allowed ( τ[i][l]^α · η[i][l]^β )
  α — weight given to accumulated pheromone (typical: 1)
  β — weight given to raw distance (typical: 2–5)
  allowed — the set of cities not yet visited by this ant

Min-Max ACO: eliminacja wczesnej konwergencji

Prosty System Młodych Żądli posiada znaną słabość, zwaną stagnacją: po kilkudziesięciu iteracjach dosłownie wszystkie żądły podążają za tą samą ścieżką, a eksploracja całkowicie się zatrzymuje. MAX-MIN Ant System (Stützle & Hoos, 2000) narzuca każdą wartość feromonu w zakresie τ_min ≤ τ[i][j] ≤ τ_max i pozwala tylko jednemu najlepszemu żądłowi z danej rundy na depozyt. Dzięki temu każdy krawędź pozostaje wystarczająco prawdopodobny, aby została ponownie odwiedzona później, co przekłada się na wyniki o 15–35% lepsze niż w przypadku klasycznego Ant System na dużych instancjach.

Gdzie faktycznie wykorzystywane jest ACO

Poza demonstracjami TSP, warianty ACO rozwiązują problem trasowania pojazdów dla dostaw towarów, planowanie harmonogramu pracy na procesorach grupujących (algorytm Job-Shop Scheduling) oraz adaptacyjne trasowanie pakietów sieciowych (protokół AntNet). Jego prawdziwa siła objawia się w dynamicznych środowiskach – gdy krawędzie grafu pojawiają się lub znikają w czasie, kolonia mrówek może nieustannie dostosowywać się w czasie rzeczywistym, ponieważ mapa feromonów jest, w zasadzie, żywą, rozkładającą się pamięcią niedawnych, udanych rozwiązań, zamiast odpowiedzi obliczonej raz dla grafu, który już nie istnieje.

Często zadawane pytania

Wypróbuj na żywo

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