Obserwuj, jak prawdziwa metaheurystyka optymalizacji kolonii mrówek rozwija na żywo trasy dronów dostawczych, z rzeczywistym wzmacnianiem śladów feromonowych, zbiegając ku krótszym trasom wieloprzystankowym w kolejnych koloniach.
Ta symulacja wykorzystuje prawdziwy algorytm optymalizacji kolonii mrówek (ACO) do rozwiązania problemu trasowania dronów dostawczych z wieloma przystankami — dron musi odwiedzić każdy punkt dostawy dokładnie raz i wrócić do bazy, czyli klasyczny problem komiwojażera. Zamiast skryptować trasę, strona utrzymuje prawdziwą macierz feromonów τ nad każdą parą punktów dostawy. W każdej kolonii każda symulowana mrówka buduje pełną trasę, wielokrotnie wybierając swój następny nieodwiedzony przystanek z prawdopodobieństwem proporcjonalnym do τ(i,j)α · η(i,j)β, gdzie η(i,j) = 1/odległość(i,j) to heurystyczna atrakcyjność krótkiego skoku. Gdy każda mrówka w kolonii zakończy swoją trasę, feromon paruje o współczynnik (1 − ρ), a każda mrówka deponuje nowy feromon proporcjonalny do Q / L na krawędziach zbudowanej przez siebie trasy — więc krótsze trasy wzmacniają swoje krawędzie znacznie silniej niż długie.
Uruchom to na wystarczającą liczbę kolonii, a mapa śladów widocznie się wyostrza: słabe, rzadko używane krawędzie zanikają do zera, podczas gdy garstka krawędzi — tych, które wciąż pojawiają się w najkrótszych trasach — jaśnieje coraz bardziej, a najlepsza znana długość trasy (śledzona na wykresie na żywo) wciąż spada. Możesz na żywo dostosować liczbę punktów dostawy, liczbę mrówek na kolonię i współczynnik parowania ρ, wraz z wykładnikami wagi feromonu α i wagi odległości β, które kontrolują, jak silnie mrówki ufają doświadczeniu kolonii w porównaniu z surową odległością. Nic tutaj nie jest skryptowane ani z góry przygotowane — każda kolonia naprawdę wyprowadza na nowo swoje trasy z bieżącego stanu feromonu i losowych decyzji mrówek, więc restart z nową mapą lub innymi parametrami za każdym razem daje inną krzywą zbieżności.
Czym jest optymalizacja kolonii mrówek i jaki problem tutaj rozwiązuje?
Optymalizacja kolonii mrówek (ACO) to metaheurystyka inspirowana tym, jak prawdziwe mrówki znajdują krótkie ścieżki między gniazdem a pożywieniem za pomocą śladów feromonowych. W tej symulacji rozwiązuje problem trasowania dostaw z wieloma przystankami: dron musi odwiedzić każdy punkt dostawy dokładnie raz i wrócić do bazy, co jest klasycznym problemem komiwojażera (TSP). TSP jest NP-trudny, więc dla czegokolwiek powyżej garstki przystanków sprawdzenie każdej możliwej kolejności jest niepraktyczne. ACO zamiast tego uruchamia wiele symulowanych mrówek, które budują kandydujące trasy probabilistycznie, wzmacniając krawędzie, które mają tendencję do pojawiania się w krótkich trasach, dzięki czemu populacja tras poprawia się w kolejnych koloniach, nigdy jednak nie udowadniając optymalności.
Jak reguła prawdopodobieństwa przejścia ACO decyduje, dokąd pójdzie każda mrówka?
Na każdym kroku mrówka stojąca w punkcie dostawy i wybiera swój następny nieodwiedzony przystanek j z prawdopodobieństwem proporcjonalnym do [τ(i,j)]^α × [η(i,j)]^β, gdzie τ(i,j) to poziom feromonu na krawędzi (i,j), a η(i,j) = 1/odległość(i,j) to atrakcyjność heurystyczna — bliższe punkty wyglądają bardziej atrakcyjnie. α kontroluje, jak silnie mrówka podąża za zgromadzonym doświadczeniem kolonii (feromonem), podczas gdy β kontroluje, jak silnie podąża za czystą zachłanną odległością. Mrówka następnie dokonuje ważonego losowego (na zasadzie koła ruletki) wyboru spośród wszystkich nieodwiedzonych kandydatów, używając tych połączonych wyników, więc zazwyczaj — ale nie zawsze — wybiera obiecującą krawędź, co utrzymuje eksplorację kolonii.
Dlaczego feromon paruje i co kontroluje współczynnik parowania ρ?
Po zakończeniu tras przez każdą kolonię wszystkie wartości feromonu są mnożone przez (1 − ρ), zanim dodane zostaną nowe depozyty. Bez parowania feromon tylko by się kumulował, a którekolwiek krawędzie miały szczęście na początku, dominowałyby na zawsze — uwięziając wyszukiwanie w przeciętnym rozwiązaniu. Parowanie pozwala słabym lub nieaktualnym śladom zanikać, dzięki czemu kolonia może dalej eksplorować alternatywne trasy. Wysokie ρ szybko zapomina historię i eksploruje więcej, ale zbiega wolniej i z większym szumem; niskie ρ pamięta dłużej i zbiega szybciej, ale ryzykuje utknięcie na wczesnej, nieoptymalnej trasie (przedwczesna zbieżność).
Po parowaniu każda mrówka w kolonii deponuje feromon o wielkości Q / L na każdej krawędzi zbudowanej przez siebie trasy, gdzie L to całkowita długość trasy tej mrówki, a Q to stała. Ponieważ depozyt jest odwrotnie proporcjonalny do długości, mrówka, która znalazła krótką trasę, wzmacnia jej krawędzie znacznie silniej niż mrówka, która znalazła długą, nieefektywną trasę. W wielu koloniach to zróżnicowane wzmacnianie zamienia czysto losowe wyszukiwanie w takie, które koncentruje feromon — a tym samym przyszły ruch mrówek — na krawędziach, które wielokrotnie pojawiają się w krótkich trasach.
Ustawienie α = 0 sprawia, że mrówki całkowicie ignorują feromon i zachowują się jak zachłanna heurystyka w stylu najbliższego sąsiada, kierowana wyłącznie przez η (odległość), więc nie powstaje żadna pamięć kolonii i z czasem następuje niewielka poprawa. Ustawienie β = 0 sprawia, że mrówki całkowicie ignorują odległość i podążają wyłącznie za feromonem, co może spowodować, że cała kolonia bardzo szybko wzmocni jedną wczesną, być może słabą, trasę (stagnacja). Klasyczna równowaga wykorzystuje umiarkowane α (około 1) z silniejszym β (około 2–5), dzięki czemu wczesna eksploracja uwzględnia odległość, a feromon nadal pozwala dobrej strukturze kumulować się w kolejnych koloniach.
Wykres śledzi najlepszą dotychczas znalezioną długość trasy, która z definicji nigdy nie może się pogorszyć — jest to bieżące minimum. Zatrzymuje się, gdy żadna mrówka w ostatnich koloniach nie zdołała pokonać obecnej rekordowej trasy, co jest oczekiwane: w miarę jak feromon koncentruje się na dobrych krawędziach, większość mrówek zbiega ku podobnym trasom, a naprawdę nowe usprawnienia stają się rzadsze. Długie plateau zwykle oznacza, że kolonia osiadła w pobliżu optimum lokalnego dla bieżących parametrów; zwiększenie współczynnika parowania, liczby mrówek lub wykładnika eksploracji β może czasem ją uwolnić, aby znaleźć krótszą trasę.
Dokładny solver (branch-and-bound, programowanie dynamiczne lub programowanie całkowitoliczbowe) może zagwarantować prawdziwie najkrótszą możliwą trasę, ale jego czas działania rośnie eksplozywnie wraz z liczbą przystanków — programowanie dynamiczne wymaga już około n²·2ⁿ operacji, co staje się niewykonalne na długo przed n = 30. ACO rezygnuje z gwarancji optymalności w zamian za skalowalność: tworzy dobre, często niemal optymalne trasy dla znacznie większych przypadków przy stałej ilości obliczeń, co jest dokładnie kompromisem, jaki przyjmują rzeczywiste systemy dostaw i logistyki przy trasowaniu dziesiątek lub setek przystanków.