Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę

Stygmergia, doświadczenie z podwójnym mostem, system mrówkowy Doriga, rola parametrów α, β i ρ oraz ulepszone warianty — na trasie przez czeskie miasta wojewódzkie i na 60 miastach, w porównaniu z wyżarzaniem.

13 minut Matěj Žalmánek 2026-10-15

Seria Podstawy AI Część 29 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Pojedyncza mrówka nie ma mapy, nie umie liczyć i widzi ledwie kilka centymetrów przed sobą. Kolonia mimo to niezawodnie znajduje najkrótszą drogę z mrowiska do pożywienia. Żadna mrówka jej nie zna — powstaje z tego, jak wszystkie razem znakują teren. Na początku lat dziewięćdziesiątych Marco Dorigo z Politechniki Mediolańskiej zauważył, że tę samą sztuczkę można zastosować do problemu komiwojażera. Tak powstała optymalizacja kolonią mrówek, a wraz z nią cała dziedzina inteligencji roju.

Artykuł nawiązuje do części Przeszukiwanie lokalne i symulowane wyżarzanie. Rozwiązujemy to samo zadanie — trasę przez czeskie miasta wojewódzkie z optimum 1 060,4 km —, więc zobaczymy, jak mrówki radzą sobie w porównaniu z wyżarzaniem.

1. Komunikacja przez ślad

Definicja — stygmergia

Stygmergia to pośrednia komunikacja przez środowisko: osobnik zmienia środowisko, a ta zmiana wpływa na to, co później zrobią inni (albo on sam). Pojęcie wprowadził Pierre-Paul Grassé w 1959 roku, badając budowę termitier.

2. Doświadczenie z podwójnym mostem

W 1989 roku Goss, Deneubourg i ich współpracownicy zbudowali mrówkom argentyńskim między mrowiskiem a pożywieniem dwa mosty — jeden dwa razy dłuższy od drugiego. Po chwili większość kolonii chodziła po krótszym. Dlaczego? Mrówka, która wybrała krótką gałąź, dociera do pożywienia wcześniej, a gdy wraca, krótka gałąź jest przy pożywieniu już oznakowana. Krótka droga znakuje się szybciej i zaczyna wygrywać.

Definicja — model wyboru gałęzi (Deneubourg i in.)

Jeśli na początku na krótkiej i długiej gałęzi są ilości feromonu A i B, mrówka wybiera krótką gałąź z prawdopodobieństwem

P = (k + A)^h / ((k + A)^h + (k + B)^h),

gdzie k określa, jak silnie mrówka reaguje na słaby ślad, a h > 1 wzmacnia różnice. Mrówka składa feromon na początku wybranej gałęzi i na jej końcu, gdy dotrze.

P = (k + A)^h / ((k + A)^h + (k + B)^h)

P

prawdopodobieństwo, że następna mrówka pójdzie krótką gałęzią — mrówka nie decyduje na pewno, tylko z wagą; długa gałąź dostaje resztę 1 − P

A

feromon na krótkiej gałęzi — jedyne, co mrówka „wie“ o drodze; im więcej go tam jest, tym mocniej krótka gałąź przyciąga

B

feromon na długiej gałęzi — w mianowniku rywalizuje z krótką, więc decyduje stosunek śladów, a nie ich bezwzględna ilość

k

„próg uwagi“ — dodaje się do obu gałęzi tak samo, więc kilka pierwszych cząsteczek feromonu prawie nie zmienia stosunku; bez niego o całej kolonii zdecydowałaby pierwsza mrówka

h

wzmacniacz — potęga większa od 1 wyolbrzymia różnicę; to właśnie ona robi z małej przypadkowej przewagi dodatnie sprzężenie zwrotne

Przykład — jak decydują k = 30 i h = 2

Na krótkiej gałęzi jest A = 20, na długiej B = 10 jednostek feromonu:

P = (30 + 20)² / ((30 + 20)² + (30 + 10)²) = 2 500 / (2 500 + 1 600) = 2 500 / 4 100 ≈ 0,610.

• Jednakowe ślady (A = B, na przykład oba zerowe): P = 0,500 — czysty przypadek.
• Pięć jednostek przeciw zeru: P = 35² / (35² + 30²) ≈ 0,576 — mały ślad prawie o niczym nie decyduje, to robota k.
• A = 60, B = 10: P = 8 100 / (8 100 + 1 600) ≈ 0,835 — już wyraźna przewaga.
• Bez wzmocnienia (h = 1) przy A = 20, B = 10 wyszłoby tylko 50 / 90 ≈ 0,556 zamiast 0,610.

Symulacja modelu (k = 30, h = 2, dziesięć mrówek na krok, krótka gałąź 5 kroków, długa 10) pokazuje udział feromonu na krótkiej gałęzi w ośmiu koloniach:

Siedem kolonii ustabilizowało się na krótkiej gałęzi, jedna na długiej: kilka pierwszych mrówek przypadkiem wybrało długą gałąź, a dodatnie sprzężenie zwrotne ją „zablokowało“. Ze stu kolonii 85 skończyło na krótkiej gałęzi, a 9 na długiej. Gdy obie gałęzie są jednakowo długie, kolonie dzielą się mniej więcej po połowie (46 i 42) — symetrię łamie przypadek. Długość drogi przesuwa więc wynik, ale go nie gwarantuje. Tę samą słabość zobaczymy w algorytmie.

3. System mrówkowy

System mrówkowy Doriga (Ant System, 1992) wysyła wirtualne mrówki po grafie miast. Każda buduje cały cykl i w zależności od tego, jak jest krótki, składa feromon na jego krawędziach.

Definicja — cykl i jego długość

Dane jest n miast i odległości d_ij = d_ji > 0. Cykl to kolejność miast π = (π₁, …, π_n), w której każde miasto występuje dokładnie raz; jego długość to

L(π) = d_π1π2 + d_π2π3 + … + d_πnπ1

— ostatni składnik sprowadza podróżnika do domu. Krawędź (i, j) należy do cyklu, jeśli i i j występują w nim bezpośrednio po sobie. Problem komiwojażera szuka cyklu o najmniejszej długości.

Definicja — reguła przejścia

Mrówka w mieście i idzie do jeszcze nieodwiedzonego miasta j z prawdopodobieństwem

p_ij = τ_ij^α · η_ij^β / ∑_l τ_il^α · η_il^β,

gdzie τ_ij to feromon na krawędzi, η_ij = 1 / d_ij to widoczność (bliskie miasta są bardziej kuszące), a suma biegnie po wszystkich nieodwiedzonych miastach l. Parametry α i β ważą ślad względem odległości.

p_ij = τ_ij^α · η_ij^β / ∑_{l ∈ Ni} τ_il^α · η_il^β

p_ij

prawdopodobieństwo kroku z i do j — losujemy, a nie wybieramy najlepszego, żeby kolonia wciąż próbowała też innych cykli

τ_ij^α

pamięć kolonii — feromon niesie doświadczenie wcześniejszych mrówek; wykładnik α mówi, jak bardzo mu ufać (α = 0 całkiem go wyłącza)

η_ij^β

zachłanność — η = 1 / d faworyzuje bliskie miasta; to rada, którą mamy za darmo od pierwszej iteracji, gdy feromon jeszcze nic nie wie

∑ … po N_i

suma wag wszystkich jeszcze nieodwiedzonych miast — dzielenie zamienia wagi w prawdopodobieństwa o sumie 1; odwiedzonych miast w niej nie ma, więc mrówka do nich nie wraca

Przykład — jedna decyzja mrówki

Mrówka stoi w mieście i i zostały jej trzy miasta: w odległości 50, 100 i 150 km, z feromonem τ = 1, 3 i 2. Stała w widoczności skraca się w ułamku, liczmy więc z η = 100 / d, czyli 2, 1 i 2/3. Przy α = 1 i β = 3:

• wagi: 1 · 2³ = 8,000, 3 · 1³ = 3,000, 2 · (2/3)³ ≈ 0,593;
• ich suma 11,593;
• prawdopodobieństwa 0,690, 0,259 i 0,051.

Wygrywa najbliższe miasto, choć ma najmniej feromonu. Przy β = 1 wyszłoby 0,316, 0,474 i 0,211 — prowadzi feromon. A przy β = 0 decyduje tylko ślad: 0,167, 0,500 i 0,333 (proporcje 1 : 3 : 2).

Definicja — aktualizacja feromonu

Po każdej iteracji feromon wszędzie paruje, a każda mrówka m dodaje na krawędzie swojego cyklu o długości L_m ilość proporcjonalną do 1 / L_m:

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ cykl m} Q / L_m,

gdzie ρ ∈ (0, 1) to szybkość parowania.

τ_ij ← (1 − ρ) · τ_ij + ∑_{m : (i, j) ∈ cykl m} Q / L_m

τ_ij po lewej

nowy feromon na krawędzi — to, czym będą się kierować mrówki następnej iteracji

(1 − ρ)

parowanie — każda iteracja zabiera z każdego śladu ten sam ułamek ρ; stare doświadczenie słabnie więc geometrycznie i kolonia może się przeuczyć

τ_ij po prawej

dotychczasowy feromon — pamięć jest tylko poprawiana, nie zaczyna się od zera

∑_m

suma po mrówkach, które przeszły krawędzią — każda mrówka dodaje tylko na krawędzie swojego cyklu; krawędź, której użyje więcej mrówek, dostaje więcej — tu liczy się „głosowanie“ kolonii

Q / L_m

nagroda odwrotnie proporcjonalna do długości cyklu — krótszy cykl = silniejszy ślad; stała Q ustala tylko skalę

Przykład — jedna aktualizacja

Krawędź ma τ = 1, ρ = 0,3, Q = 1 000, a przeszły nią dwie mrówki z cyklami o długości 1 100 i 1 300 km:

τ ← 0,7 · 1 + 1 000 / 1 100 + 1 000 / 1 300 ≈ 0,700 + 0,909 + 0,769 = 2,378.

Krawędź, którą nikt nie przeszedł, ma po tej samej iteracji tylko 0,7. Mrówka z krótszym cyklem dodała więcej (0,909 wobec 0,769).

import random

def postav_okruh(start, n, tau, d, alfa=1, beta=3):
    okruh, volna = [start], set(range(n)) - {start}
    while volna:
        i = okruh[-1]
        kandidati = list(volna)
        vahy = [tau[i][j] ** alfa * (1 / d[i][j]) ** beta for j in kandidati]
        j = random.choices(kandidati, weights=vahy)[0]
        okruh.append(j)
        volna.remove(j)
    return okruh

def aktualizuj(tau, okruhy, delka, rho=0.3, Q=1.0):
    for radek in tau:
        for j in range(len(radek)):
            radek[j] *= 1 - rho                 # parowanie
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # krótszy cykl, silniejszy ślad
            tau[b][a] += Q / L

Cały system mrówkowy potem tylko przeplata budowę cykli i aktualizację i pamięta najlepszy cykl, jaki ktokolwiek kiedykolwiek zbudował:

def mravenci_system(n, d, mravencu, iteraci, tau0):
    tau = [[tau0] * n for _ in range(n)]      # na początku wszędzie tak samo
    nejlepsi = None
    for it in range(iteraci):
        okruhy = [postav_okruh(m % n, n, tau, d) for m in range(mravencu)]
        aktualizuj(tau, okruhy, delka)        # parowanie + nowy ślad
        kandidat = min(okruhy, key=delka)
        if nejlepsi is None or delka(kandidat) < delka(nejlepsi):
            nejlepsi = kandidat
    return nejlepsi

4. Mrówki na czeskich miastach wojewódzkich

Wypuśćmy 13 mrówek (z każdego miasta jedną) na 100 iteracji z α = 1, β = 3 i ρ = 0,3. Mapa pokazuje feromon na krawędziach po 1., 5., 20. i 100. iteracji — im grubsza linia, tym więcej feromonu:

W pierwszej iteracji ślad jest rozłożony prawie wszędzie, a najlepszy cykl mierzy 1 292,6 km. Już w piątej iteracji jedna z mrówek znajduje optimum 1 060,4 km. Feromon skupia się potem na krawędziach dobrych cykli — słabe linie znikają, silne zostają — a przeciętna mrówka buduje cykl długi mniej więcej na 1 250 km. Kolonia nie zbiega się całkowicie, wciąż trochę próbuje.

Przebieg działania po iteracjach — najlepszy dotąd znaleziony cykl i przeciętny cykl trzynastu mrówek w danej iteracji:

Najlepszy cykl poprawia się skokowo (trzecia iteracja nie przyniosła nic nowego, czwarta urwała 111 km), średnia spada wolniej i nierówno: mrówki losują, więc nawet w dobrej iteracji niektóre budują słabe cykle. Różnica między średnią a najlepszym to właśnie ta eksploracja, która chroni kolonię przed całkowitym zamarznięciem.

Nie zawsze kończy się to tak dobrze. Z dwudziestu przebiegów z różnymi ziarnami optimum znalazło tylko 7, średnia wyniosła 1 073,9 km, a najgorszy wynik 1 083,0 km. Wyżarzanie było na tym samym zadaniu z wynikiem 98 na 100 bardziej niezawodne. Dla porównania: zachłanny „najbliższy sąsiad“, który zawsze idzie do najbliższego nieodwiedzonego miasta, daje zależnie od startu od 1 120 do 1 336 km. Mrówki są wyraźnie lepsze, ale podstawowy system mrówkowy sam w sobie nie jest mistrzem — dlatego powstały jego ulepszone warianty.

5. Do czego służą α, β i ρ

Na trzynastu miastach wiele da się rozwiązać nawet bez feromonu. Różnicę pokaże dopiero większe zadanie — te same 60 losowych miast co w części o wyżarzaniu, 30 mrówek, 150 iteracji, średnia z trzech przebiegów:

• Bez feromonu (α = 0) mrówki są tylko losowymi zachłannymi podróżnikami i niczego się nie uczą — cykle o jedną trzecią dłuższe.
• Bez odległości (β = 0) kolonia nie ma się od czego odbić: pierwsze cykle są całkowicie losowe, a feromon z nich prowadzi do kolejnych losowych.
• Wolne parowanie trzyma ślady pierwszych, złych cykli zbyt długo i kolonia uczy się powoli. Szybkie parowanie z kolei zapomina także to, co dobre.

Jak długo kolonia pamięta, da się obliczyć dokładnie. Wystarczy śledzić jedną krawędź.

Twierdzenie — ustalony feromon i okres połowicznego zaniku

Jeśli krawędź dostaje w każdej iteracji ten sam przyrost Δ ≥ 0, czyli τ_t+1 = (1 − ρ) τ_t + Δ, to

τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ) → Δ/ρ dla t → ∞.

Bez przyrostu (Δ = 0) ślad spada do połowy po t_½ = ln 2 / (−ln(1 − ρ)) iteracjach.

Dowód. Odejmując Δ/ρ od obu stron rekurencji, dostajemy τ_t+1 − Δ/ρ = (1 − ρ)(τ_t − Δ/ρ), ponieważ (1 − ρ)Δ/ρ + Δ = Δ/ρ. Odchylenie od Δ/ρ mnoży się więc w każdej iteracji przez liczbę 1 − ρ ∈ (0, 1) i maleje geometrycznie do zera. Okres połowicznego zaniku to rozwiązanie (1 − ρ)^t = ½. ∎

τ^* = Δ / ρ

τ^*

poziom, na którym ustala się feromon krawędzi — dodawanie i parowanie są w równowadze

Δ

ile krawędź dostaje na iterację — krawędzie z częstych i krótkich cykli mają duże Δ, a więc i wysoki poziom

ρ

w mianowniku: wolne parowanie pozwala śladom urosnąć wysoko, a różnice między krawędziami długo się wyrównują; szybkie trzyma je nisko i zależne tylko od kilku ostatnich iteracji

Krawędź z τ₀ = 1 i ρ = 0,3: jedna dostaje w każdej iteracji Δ = 1, drugiej nikt nie używa.

Używana krawędź zbliża się do 1/0,3 ≈ 3,33, nieużywana po dziesięciu iteracjach spada poniżej trzech setnych. Okres połowicznego zaniku dla wierszy tabeli wyżej: przy ρ = 0,3 to 1,94 iteracji, przy ρ = 0,02 całe 34,31 iteracji — ślady pierwszych losowych cykli rządzą więc jeszcze przez dziesiątki iteracji — a przy ρ = 0,9 tylko 0,30 iteracji, więc kolonia pamięta praktycznie tylko ostatnią rundę.

Najlepsze ustawienie dało od 2 194 do 2 314 km — porównywalnie z wyżarzaniem z poprzedniej części, które na tych samych miastach skończyło między 2 210 a 2 270 km.

6. Lepsze mrówki

• Strategia elitarna dodaje dodatkowy feromon na dotąd najlepszy cykl, żeby się nie zgubił.
• MAX–MIN Ant System (Stützle i Hoos, 2000) pozwala składać feromon tylko najlepszej mrówce i trzyma τ między dolną a górną granicą. Dolna granica gwarantuje, że żadna krawędź całkiem nie zniknie, więc kolonia nie zamarza przedwcześnie — jak ta, która w doświadczeniu z mostem skończyła na długiej gałęzi.
• Ant Colony System (Dorigo i Gambardella, 1997) z pewnym prawdopodobieństwem wybiera od razu najlepszą krawędź i zabiera feromon już w trakcie budowy cyklu, żeby pozostałe mrówki próbowały gdzie indziej.
• Przeszukiwanie lokalne. W praktyce każdy cykl zbudowany przez mrówkę dopracowuje się jeszcze ruchami 2-opt z części o wyżarzaniu. Mrówki znajdują dobry obszar, algorytm wspinaczkowy go dopieszcza — ta kombinacja należała w latach dziewięćdziesiątych do najlepszych metod na komiwojażera.

Definicja — strategia elitarna i MAX–MIN Ant System

Strategia elitarna dodaje do zwykłej aktualizacji jeszcze e · Q / L^best na każdą krawędź dotąd najlepszego cyklu o długości L^best; e to liczba „mrówek elitarnych“.

MAX–MIN Ant System składa feromon tylko według jednego najlepszego cyklu i przycina wynik do przedziału [τ_min, τ_max]:

τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), gdzie Δ_ij = 1 / L^best dla krawędzi najlepszego cyklu, w przeciwnym razie 0.

Górną granicę Stützle i Hoos wybierają jako τ_max = 1 / (ρ L^best) — dokładnie ustaloną wartość Δ/ρ z twierdzenia wyżej dla krawędzi, która za każdym razem leży w najlepszym cyklu. Dolna granica to mały ułamek górnej; feromon ustawia się ponadto na początku na τ_max, żeby pierwsze iteracje eksplorowały jak najszerzej.

Definicja — reguły Ant Colony System

Pseudolosowa reguła proporcjonalna: mrówka w mieście i losuje q z [0, 1). Jeśli q ≤ q₀, idzie od razu do miasta o największej wadze, j = arg max_{l ∈ Ni} τ_il · η_il^β; w przeciwnym razie wybiera losowo według reguły przejścia systemu mrówkowego.

Aktualizacja lokalna: zaraz po przejściu krawędzią (i, j) τ_ij ← (1 − ξ) τ_ij + ξ τ₀, więc użyta krawędź nieco słabnie w kierunku wartości początkowej τ₀.

Aktualizacja globalna po iteracji tylko na krawędziach najlepszego cyklu: τ_ij ← (1 − ρ) τ_ij + ρ / L^best.

Dorigo i Gambardella (1997) w oryginalnym artykule używają q₀ = 0,9, β = 2 i ρ = ξ = 0,1 — w dziewięciu krokach na dziesięć mrówka bierze więc najlepszą krawędź i tylko w dziesiątym próbuje.

7. Gdzie pracują mrówki

• Routing w sieciach. Algorytm AntNet (Di Caro i Dorigo, 1998) wysyła przez sieć małe pakiety-mrówki, które mierzą opóźnienia i aktualizują tablice routingu. Sieć na bieżąco dostosowuje się w ten sposób do przeciążenia.
• Trasy pojazdów i harmonogramy. Rozwóz towarów, wywóz odpadów albo kolejność zleceń w produkcji — zadania pokrewne problemowi komiwojażera, w których algorytmy mrówkowe stosuje się razem z przeszukiwaniem lokalnym.
• Inteligencja roju. Kolonia mrówek to jeden z przykładów, jak z prostych osobników i lokalnych reguł powstaje mądre zachowanie całości. Inny, rój cząstek, jest tematem następnej części.

8. Podsumowanie

• Mrówki komunikują się śladem w środowisku (stygmergia): krótsza droga znakuje się szybciej, a dodatnie sprzężenie zwrotne ją wzmacnia.
• W modelu podwójnego mostu 85 ze 100 kolonii ustala się na krótkiej gałęzi — przypadek może jednak zablokować i tę długą.
• System mrówkowy wybiera następne miasto według feromonu τ^α i odległości η^β; feromon paruje z szybkością ρ, a krótkie cykle dodają go więcej.
• Na czeskich miastach wojewódzkich znalazł optimum, ale tylko w 7 z 20 przebiegów; na 60 miastach wypadł porównywalnie z wyżarzaniem. Bez feromonu i bez odległości wyraźnie gorzej.
• Warianty stosowane w praktyce (MAX–MIN, ACS) zapobiegają przedwczesnemu zamarznięciu i łączą mrówki z przeszukiwaniem lokalnym.

Chcesz to wypróbować? Poproś agenta AI o napisanie symulacji podwójnego mostu i sprawdź, co się stanie, gdy krótką gałąź w połowie doświadczenia „zamkniesz“ — czy kolonia potrafi wrócić na długą?

Masz inne zdanie? Napisz na support@coden-app.com.