Optimalizace mravenčí kolonií: jak feromonová stopa najde krátkou cestu

Stigmergie, pokus s dvojitým mostem, Dorigův mravenčí systém, role parametrů α, β a ρ a vylepšené varianty — na okruhu přes krajská města a na 60 městech, ve srovnání se žíháním.

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

Série Základy AI Díl 29 z 83

1. Mapa umělé inteligence: co je co a jak to do sebe zapadá
2. Stručná historie umělé inteligence: od Turinga po jazykové modely
3. Data, model, trénink, inference: základní pojmy na jednom příkladu
4. Jak číst matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relace: stavebnice, ze které se skládají definice v AI
6. Funkce a zobrazení: proč je každý model v AI funkce
7. Logika a důkazy: pravidla, podle kterých se v AI uvažuje
8. Grafy a stromy: struktura, na které stojí hledání i neuronové sítě
9. Lineární algebra pro strojové učení: vektory, matice a proč AI hlavně násobí
10. Derivace, gradient a řetízkové pravidlo: jak model zjistí, kterým směrem se učit
11. Gradientní sestup: jak se model učí
12. Co je pravděpodobnost: od hodu kostkou ke Kolmogorovovým axiomům
13. Podmíněná pravděpodobnost a Bayesova věta: jak změnit odhad, když se dozvíte něco nového
14. Náhodná veličina a distribuční funkce: jedna funkce, která o rozdělení řekne všechno
15. Funkce hustoty a pravděpodobnostní funkce: proč má spojitá veličina v bodě pravděpodobnost nula
16. Střední hodnota, rozptyl a kovariance: kde rozdělení leží, jak je široké a co s čím souvisí
17. Přehled pravděpodobnostních rozdělení: Bernoulli, binomické, Poisson, rovnoměrné, normální a exponenciální
18. Zákon velkých čísel a centrální limitní věta: proč se průměry chovají tak předvídatelně
19. Statistika a odhady parametrů: maximální věrohodnost, MAP a intervaly spolehlivosti
20. Teorie informace: entropie, křížová entropie a KL divergence — odkud se berou ztrátové funkce
21. Prohledávání stavového prostoru: BFS, DFS, UCS a A* s animacemi
22. Hry a protivník: minimax, alfa-beta ořezávání a Monte Carlo tree search
23. Splňování omezujících podmínek: backtracking, propagace omezení a AC-3 na sudoku a mapě krajů
24. Logika a znalostní systémy: dopředné a zpětné řetězení, rezoluce a expertní systémy
25. Plánování: STRIPS, svět kostek, heuristiky z relaxace a plánování v AI agentech
26. Lokální hledání a simulované žíhání: obchodní cestující přes krajská města
27. Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet
28. Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon
29. Optimalizace mravenčí kolonií: jak feromonová stopa najde krátkou cestu
30. Optimalizace hejnem částic: setrvačnost, vlastní zkušenost a zkušenost hejna
31. Neuroevoluce: evoluce vah i tvaru neuronových sítí a algoritmus NEAT
32. Fuzzy množiny a funkce příslušnosti: jak zapsat „trochu teplo“
33. Fuzzy logika a pravděpodobnost: proč „trochu teplo“ neznamená „pravděpodobně teplo“
34. Fuzzy logika: t-normy, implikace a pravidla KDYŽ–PAK
35. Fuzzy řízení: Mamdani a Sugeno od ventilátoru po kyvadlo na vozíku
36. Fuzzy shlukování: algoritmus fuzzy c-means a body mezi shluky
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidla, která se učí z dat
38. Markovovy řetězce: přechodová matice, stacionární rozdělení a PageRank
39. Skryté Markovovy modely: Viterbiho algoritmus a nepoctivé kasino
40. Bayesovské sítě: proč je tráva mokrá a co z toho plyne pro postřikovač
41. Kalmanův filtr: jak z nepřesných měření odhadnout, kde auto je a jak rychle jede
42. Druhy strojového učení: s učitelem, bez učitele, s částečným učitelem a další
43. Přeučení a regularizace: proč model, který zná data nazpaměť, selže
44. Vyhodnocení modelu: křížová validace, F1 a křivka ROC
45. Shlukování a snížení dimenze: k-means, PCA a t-SNE
46. Klasifikace a regrese: dvě úlohy učení s učitelem
47. Lineární regrese: nejmenší čtverce geometricky i maticově
48. Polynomiální a nelineární regrese: jak přímku ohnout
49. Logistická regrese: sigmoida, šance a křížová entropie
50. Vícetřídní klasifikace a softmax: od dvou tříd k mnoha
51. Naivní Bayesův klasifikátor: spamový filtr, který funguje lépe, než by měl
52. Ztrátové funkce: co přesně model minimalizuje
53. Rozhodovací stromy a k nejbližších sousedů: modely bez vzorců
54. Ansámbly: náhodný les a gradient boosting
55. SVM a jádrový trik: nejširší hranice a jak ji ohnout
56. Signál a vzorkování: proč platí Nyquistův teorém
57. Fourierova transformace: rozklad signálu na frekvence
58. Filtry a konvoluce: vyhlazení, hrany a odstranění šumu
59. Zvuk a řeč: spektrogram, melová škála a MFCC
60. Obraz jako signál: pixely, barvy, konvoluce a hrany
61. Perceptron a umělý neuron: nejjednodušší neuronová síť a co neumí
62. Neuronová síť od nuly: zpětné šíření chyby krok za krokem
63. Aktivace, inicializace a normalizace: drobnosti, na kterých hluboká síť stojí
64. Konvoluční sítě: jak síť poznává obrázky
65. Rekurentní sítě: paměť pro posloupnosti a mizející gradient
66. LSTM a GRU: brány, které rozhodují, co si síť zapamatuje
67. Autoenkodéry: síť, která se učí data stlačit a zase rozbalit
68. Embeddingy a word2vec: jak se slovo stane vektorem
69. Mechanismus pozornosti: jak se model naučí, kam se dívat
70. Transformery a velké jazykové modely: architektura krok za krokem
71. Tokenizace: jak se text rozseká na kousky pro model
72. Předtrénování a škálování: proč větší model a víc dat funguje
73. Doladění a RLHF: jak se z doplňovače textu stane asistent
74. Prompty, kontext a RAG: jak modelu dát správné informace
75. Variační autoenkodéry (VAE): nové obrázky ze spojitého latentního prostoru
76. Generativní adversariální sítě (GAN): padělatel proti detektivovi
77. Difúzní modely: jak se z čistého šumu stane obrázek
78. Markovovy rozhodovací procesy: stavy, akce, odměny a Bellmanovy rovnice
79. Q-learning a DQN: učení hodnoty akcí od tabulky po neuronovou síť
80. Policy gradient a PPO: učení přímo strategie
81. Jak funguje AI agent: jazykový model ve smyčce s nástroji
82. Programování s AI agenty: zadání, testy a kontrola
83. Vyhodnocení a bezpečnost AI systémů: jak měřit a jak hlídat

Celá osnova série 83 z 83 témat hotovo

Jeden mravenec nemá mapu, neumí počítat a vidí sotva pár centimetrů před sebe. Kolonie přesto spolehlivě najde nejkratší cestu z mraveniště k potravě. Žádný mravenec ji nezná — vznikne z toho, jak všichni dohromady značkují terén. Na začátku devadesátých let si Marco Dorigo z milánské polytechniky všiml, že stejný trik se dá použít na problém obchodního cestujícího. Tak vznikla optimalizace mravenčí kolonií a s ní celý obor inteligence hejna.

Navazuje na díl Lokální hledání a simulované žíhání. Řešíme stejnou úlohu — okruh přes krajská města s optimem 1 060,4 km —, takže uvidíme, jak si mravenci vedou proti žíhání.

1. Komunikace stopou

Definice — stigmergie

Nechť skupina jedinců (např. mravenců jedné kolonie) sdílí společné prostředí, jehož stav se může měnit. Stigmergie je způsob koordinace těchto jedinců, při kterém platí všechny tři podmínky:

1. jedinec svou činností změní stav prostředí — zanechá v něm stopu (např. feromon);
2. změněný stav prostředí ovlivní, co později udělají ostatní jedinci nebo on sám;
3. jedinci si informaci nepředávají přímo (signálem od jedince k jedinci), ale jen prostřednictvím stavu prostředí.

Stigmergie je tedy nepřímá komunikace přes prostředí. Pojem zavedl Pierre-Paul Grassé v roce 1959 při studiu stavby termitišť.

2. Pokus s dvojitým mostem

V roce 1989 postavili Goss, Deneubourg a jejich kolegové mravencům argentinským mezi mraveniště a potravu dva mosty — jeden dvakrát delší než druhý. Po chvíli chodila většina kolonií po kratším. Proč? Mravenec, který zvolil krátkou větev, dorazí k potravě dřív, a když se vrací, u potravy už je krátká větev označená. Krátká cesta se značí rychleji a začne vyhrávat.

Definice — model volby větve (Deneubourg a kol.)

Nechť mezi mraveništěm a potravou vedou dvě větve, krátká a dlouhá. Nechť A ≥ 0 a B ≥ 0 jsou množství feromonu na začátku krátké a dlouhé větve v okamžiku, kdy mravenec přichází k rozcestí, a nechť k > 0 a h > 0 jsou parametry modelu. Mravenec zvolí krátkou větev s pravděpodobností

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

a dlouhou větev s pravděpodobností 1 − P(A, B). Mravenec položí jednotku feromonu na začátek zvolené větve a další na její konec, když tam dorazí.

Parametr k tedy určuje, jak silně mravenec reaguje na slabou stopu (čím větší k, tím méně), a h > 1 zesiluje rozdíly mezi větvemi; při A = B je P = 1/2.

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

P

pravděpodobnost, že další mravenec půjde krátkou větví — mravenec se nerozhoduje jistě, jen s vahou; dlouhá větev dostane zbytek 1 − P

A

feromon na krátké větvi — to jediné, co mravenec o cestě „ví“; čím víc ho tam je, tím víc to krátkou větev táhne

B

feromon na dlouhé větvi — ve jmenovateli soupeří s krátkou, takže rozhoduje poměr stop, ne jejich absolutní množství

k

„práh pozornosti“ — přičte se k oběma větvím stejně, takže pár prvních molekul feromonu poměr skoro nezmění; bez něj by o celé kolonii rozhodl první mravenec

h

zesilovač — mocnina větší než 1 zveličí rozdíl; právě ona dělá z malé náhodné výhody pozitivní zpětnou vazbu

Příklad — jak rozhoduje k = 30 a h = 2

Na krátké větvi je A = 20, na dlouhé B = 10 jednotek feromonu:

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

(Barvy podle vzorce výše.)

• Stejné stopy (A = B, třeba obě nulové): P = 0,500 — čistá náhoda.
• Pět jednotek proti nule: P = (30 + 5)²/(30 + 5)² + (30 + 0)² = 35²/35² + 30² ≈ 0,576 — malá stopa skoro nerozhoduje, to je práce k.
• A = 60, B = 10: P = 8 100/8 100 + 1 600 ≈ 0,835 — už jasná převaha.
• Bez zesílení (h = 1) by u A = 20, B = 10 vyšlo jen 50/90 ≈ 0,556 místo 0,610.

Simulace modelu (k = 30, h = 2, deset mravenců za krok, krátká větev 5 kroků, dlouhá 10) ukazuje podíl feromonu na krátké větvi u osmi kolonií:

Sedm kolonií se ustálilo na krátké větvi, jedna na dlouhé: několik prvních mravenců náhodou zvolilo dlouhou větev a pozitivní zpětná vazba ji „zamkla“. Ze sta kolonií skončilo 85 na krátké větvi a 9 na dlouhé. Když jsou obě větve stejně dlouhé, rozdělí se kolonie zhruba napůl (46 a 42) — symetrii rozbije náhoda. Délka cesty tedy výsledek posunuje, ale nezaručuje. Stejnou slabost uvidíme u algoritmu.

3. Mravenčí systém

Dorigův mravenčí systém (Ant System, 1992) posílá virtuální mravence po grafu měst. Každý postaví celý okruh, a podle toho, jak krátký je, položí feromon na jeho hrany.

Definice — okruh a jeho délka

Nechť n ∈ ℕ, n ≥ 3, je počet měst, města označíme čísly 1, …, n, a nechť pro všechna i, j ∈ {1, …, n}, i ≠ j, je dána vzdálenost d_ij ∈ ℝ taková, že d_ij = d_ji > 0.

1. Okruh je uspořádaná n-tice π = (π₁, …, π_n), ve které je každé město právě jednou, tj. {π₁, …, π_n} = {1, …, n} (π je permutace měst). Kvůli kratšímu zápisu klademe π_n+1 = π₁.
2. Délka okruhu π je číslo L(π) = ∑_k=1ⁿ d_πkπk+1 = d_π1π2 + d_π2π3 + … + d_πnπ1; poslední člen vrací cestovatele domů.
3. Hrana (i, j) patří do okruhu π, právě když existuje k ∈ {1, …, n} takové, že {π_k, π_k+1} = {i, j}.
4. Problém obchodního cestujícího je úloha najít okruh π^* takový, že L(π^*) ≤ L(π) pro každý okruh π.

Okruh tedy projde každé město právě jednou a vrátí se do výchozího; hrana do něj patří, právě když v něm jdou její dvě města hned po sobě.

Definice — pravidlo přechodu

Nechť jsou dána města 1, …, n se vzdálenostmi d_ij > 0 (viz definici okruhu výše), na každé hraně (i, j) feromon τ_ij > 0 a parametry α ≥ 0, β ≥ 0. Viditelnost hrany (i, j) je číslo

η_ij = 1/d_ij.

Nechť mravenec stojí ve městě i a N_i ⊆ {1, …, n} je neprázdná množina měst, která na svém okruhu dosud nenavštívil. Mravenec přejde do města j s pravděpodobností

p_ij = τ_ij^α · η_ij^β/∑_{l ∈ Ni} τ_il^α · η_il^β   pro j ∈ N_i,   p_ij = 0   pro j ∉ N_i.

Mravenec tedy volí jen mezi nenavštívenými městy, a to s vahou úměrnou součinu stopy τ_ij^α a viditelnosti η_ij^β (blízká města jsou lákavější); parametry α a β váží stopu proti vzdálenosti. Pravděpodobnosti p_ij přes j ∈ N_i mají součet 1.

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

p_ij

pravděpodobnost kroku z i do j — losujeme, ne vybíráme nejlepší, aby kolonie pořád zkoušela i jiné okruhy

τ_ij^α

paměť kolonie — feromon nese zkušenost předchozích mravenců; exponent α říká, jak moc jí věřit (α = 0 ji úplně vypne)

η_ij^β

chamtivost — η = 1/d zvýhodní blízká města; je to rada, kterou máme zadarmo hned od první iterace, kdy feromon ještě nic neví

∑ … přes N_i

součet vah všech dosud nenavštívených měst — dělením se z vah stanou pravděpodobnosti se součtem 1; navštívená města v něm nejsou, takže se do nich mravenec nevrátí

Příklad — jedno rozhodnutí mravence

Mravenec stojí ve městě i a zbývají mu tři města: ve vzdálenosti 50, 100 a 150 km, s feromonem τ = 1, 3 a 2. Konstanta ve viditelnosti se ve zlomku zkrátí, počítejme proto s η = 100/d, tedy 2, 1 a 2/3. S α = 1 a β = 3 (barvy podle vzorce výše):

• váhy τ^α · η^β: 1 · 2³ = 8,000, 3 · 1³ = 3,000, 2 · (2/3)³ ≈ 0,593;
• jejich součet 11,593;
• pravděpodobnosti p = 8,000/11,593 ≈ 0,690, 3,000/11,593 ≈ 0,259 a 0,593/11,593 ≈ 0,051.

Nejbližší město vyhrává, ačkoli má nejméně feromonu. S β = 1 by vyšlo 0,316, 0,474 a 0,211 — vede feromon. A s β = 0 rozhoduje jen stopa: 0,167, 0,500 a 0,333 (podíly 1 : 3 : 2).

Definice — aktualizace feromonu

Nechť ρ ∈ (0, 1) je rychlost vyprchání a Q > 0 konstanta. Nechť v jedné iteraci postavilo M ≥ 1 mravenců okruhy π⁽¹⁾, …, π^(M) (okruh m je π^(m)) s délkami L_m = L(π^(m)), m = 1, …, M. Po iteraci se feromon na každé hraně (i, j) nahradí hodnotou

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

kde se sčítá přes všechna m ∈ {1, …, M}, pro která hrana (i, j) patří do okruhu π^(m) (prázdný součet je 0). Feromon tedy všude vyprchá o podíl ρ a každý mravenec m přidá na hrany svého okruhu množství Q/L_m, nepřímo úměrné délce okruhu.

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

τ_ij vlevo

nový feromon na hraně — to, podle čeho se budou rozhodovat mravenci příští iterace

(1 − ρ)

vyprchání — každá iterace z každé stopy ubere stejný podíl ρ; stará zkušenost tak slábne geometricky a kolonie se může přeučit

τ_ij vpravo

dosavadní feromon — paměť se jen opravuje, nezačíná se od nuly

∑_m

součet přes mravence, kteří hranou prošli — každý mravenec přidává jen na hrany svého okruhu; hrana, kterou použije víc mravenců, dostane víc — tady se sčítá „hlasování“ kolonie

Q/L_m

odměna nepřímo úměrná délce okruhu — kratší okruh = silnější stopa; konstanta Q jen nastavuje měřítko

Příklad — jedna aktualizace

Hrana má τ = 1, ρ = 0,3, Q = 1 000 a prošli jí dva mravenci s okruhy dlouhými 1 100 a 1 300 km (barvy podle vzorce výše):

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

Hrana, kterou neprošel nikdo, má po téže iteraci jen 0,7. Mravenec s kratším okruhem přidal víc (0,909 proti 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                 # vyprchání
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # kratší okruh, silnější stopa
            tau[b][a] += Q / L

Celý mravenčí systém pak jen střídá stavbu okruhů a aktualizaci a pamatuje si nejlepší okruh, jaký kdy kdo postavil:

def mravenci_system(n, d, mravencu, iteraci, tau0):
    tau = [[tau0] * n for _ in range(n)]      # na začátku všude stejně
    nejlepsi = None
    for it in range(iteraci):
        okruhy = [postav_okruh(m % n, n, tau, d) for m in range(mravencu)]
        aktualizuj(tau, okruhy, delka)        # vyprchání + nová stopa
        kandidat = min(okruhy, key=delka)
        if nejlepsi is None or delka(kandidat) < delka(nejlepsi):
            nejlepsi = kandidat
    return nejlepsi

4. Mravenci na krajských městech

Pusťme 13 mravenců (z každého města jeden) na 100 iterací s α = 1, β = 3 a ρ = 0,3. Mapa ukazuje feromon na hranách po 1., 5., 20. a 100. iteraci — čím silnější čára, tím víc feromonu:

V první iteraci je stopa rozprostřená skoro všude a nejlepší okruh měří 1 292,6 km. Už v páté iteraci najde jeden z mravenců optimum 1 060,4 km. Feromon se pak soustředí na hrany dobrých okruhů — slabé čáry mizí, silné zůstávají — a průměrný mravenec postaví okruh dlouhý zhruba 1 250 km. Kolonie nekonverguje úplně, pořád trochu zkouší.

Trasování běhu po iteracích — nejlepší okruh nalezený dosud a průměrný okruh třinácti mravenců v dané iteraci:

Nejlepší okruh se zlepšuje skokem (třetí iterace nepřinesla nic nového, čtvrtá ubrala 111 km), průměr klesá pomaleji a nerovnoměrně: mravenci losují, takže i v dobré iteraci někteří postaví slabé okruhy. Rozdíl mezi průměrem a nejlepším je přesně ten průzkum, který kolonii brání úplně zamrznout.

Ne vždy to dopadne tak dobře. Ze dvaceti běhů s různými semínky našlo optimum jen 7, průměr byl 1 073,9 km a nejhorší výsledek 1 083,0 km. Žíhání bylo na téže úloze s 98 ze 100 spolehlivější. Pro představu: hladový „nejbližší soused“, který jde vždycky do nejbližšího nenavštíveného města, dá podle startu 1 120 až 1 336 km. Mravenci jsou výrazně lepší, ale základní mravenčí systém sám o sobě není šampion — proto vznikly jeho vylepšené varianty.

5. K čemu jsou α, β a ρ

Na třinácti městech se dá hodně vyřešit i bez feromonu. Rozdíl ukáže až větší úloha — stejných 60 náhodných měst jako v dílu o žíhání, 30 mravenců, 150 iterací, průměr ze tří běhů:

• Bez feromonu (α = 0) jsou mravenci jen náhodní hladoví cestovatelé a nic se nenaučí — okruhy o třetinu delší.
• Bez vzdáleností (β = 0) nemá kolonie od čeho se odrazit: první okruhy jsou úplně náhodné a feromon z nich vede k dalším náhodným.
• Pomalé vyprchání drží stopy z prvních, špatných okruhů příliš dlouho a kolonie se učí pomalu. Rychlé vyprchání naopak zapomíná i to dobré.

Jak dlouho si kolonie pamatuje, se dá spočítat přesně. Stačí sledovat jednu hranu.

Věta — ustálený feromon a poločas vyprchání

Nechť ρ ∈ (0, 1), Δ ≥ 0 a τ₀ ∈ ℝ. Nechť posloupnost (τ_t)_{t = 0, 1, 2, …} (feromon jedné hrany po t iteracích, která v každé iteraci dostane stejný přírůstek Δ) splňuje pro každé t ≥ 0

τ_t+1 = (1 − ρ) τ_t + Δ.

Pak

1. pro každé t ≥ 0 platí τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ),
2. lim_{t → ∞} τ_t = Δ/ρ,
3. je-li Δ = 0 a τ₀ > 0, je τ_t = (1 − ρ)^t τ₀ a pro reálné t ≥ 0 platí (1 − ρ)^t τ₀ = τ₀/2, právě když t = t_½, kde t_½ = ln 2/−ln(1 − ρ) je poločas vyprchání (obecně není celé číslo).

Důkaz. Označme e_t = τ_t − Δ/ρ odchylku od Δ/ρ. Protože (1 − ρ) · Δ/ρ + Δ = Δ/ρ, dostaneme odečtením Δ/ρ od obou stran rekurence e_t+1 = (1 − ρ) e_t, a indukcí e_t = (1 − ρ)^t e₀; to je bod 1. Protože 1 − ρ ∈ (0, 1), je (1 − ρ)^t → 0, a tedy e_t → 0; to je bod 2. Pro Δ = 0 je τ_t = (1 − ρ)^t τ₀, takže τ_t = τ₀/2, právě když (1 − ρ)^t = 1/2, tj. t · ln(1 − ρ) = −ln 2; protože ln(1 − ρ) < 0, je jediným řešením t = ln 2/−ln(1 − ρ). ∎

τ^* = Δ/ρ

τ^*

hladina, na které se feromon hrany ustálí — přidávání a vyprchání jsou v rovnováze

Δ

kolik hrana dostává za iteraci — hrany z častých a krátkých okruhů mají Δ velké, a proto i vysokou hladinu

ρ

ve jmenovateli: pomalé vyprchání nechá stopy narůst vysoko a rozdíly mezi hranami se vyrovnávají dlouho; rychlé je drží nízko a závislé jen na posledních pár iteracích

Dvě hrany s τ₀ = 1 a ρ = 0,3: jedna dostává v každé iteraci Δ = 1, druhou nikdo nepoužívá.

Používaná hrana se blíží k τ^* = 1/0,3 ≈ 3,33 (barvy podle vzorce výše), nepoužívaná za deset iterací spadne pod tři setiny. Poločas vyprchání pro řádky tabulky výše: s ρ = 0,3 je 1,94 iterace, s ρ = 0,02 celých 34,31 iterace — stopy z prvních náhodných okruhů tedy vládnou ještě desítky iterací — a s ρ = 0,9 jen 0,30 iterace, takže kolonie si pamatuje prakticky jen poslední kolo.

Nejlepší nastavení dalo 2 194 až 2 314 km — srovnatelně se žíháním z minulého dílu, které na stejných městech skončilo mezi 2 210 a 2 270 km.

6. Lepší mravenci

• Elitní strategie přidává feromon navíc na dosud nejlepší okruh, aby se neztratil.
• MAX–MIN Ant System (Stützle a Hoos, 2000) dovolí klást feromon jen nejlepšímu mravenci a drží τ mezi dolní a horní mezí. Dolní mez zaručí, že žádná hrana úplně nezmizí, a kolonie tak předčasně nezamrzne — jako ta, která v pokusu s mostem skončila na dlouhé větvi.
• Ant Colony System (Dorigo a Gambardella, 1997) s pravděpodobností volí rovnou nejlepší hranu a feromon ubírá už během stavby okruhu, aby ostatní mravenci zkoušeli jinde.
• Lokální hledání. V praxi se každý okruh postavený mravencem ještě dopiluje tahy 2-opt z dílu o žíhání. Mravenci najdou dobrou oblast, horolezec ji doladí — tahle kombinace patřila v devadesátých letech k nejlepším metodám na obchodního cestujícího.

Definice — elitní strategie a MAX–MIN Ant System

Nechť ρ ∈ (0, 1) a Q > 0 jsou jako v aktualizaci feromonu mravenčího systému a nechť π^best je nejlepší okruh nalezený od začátku běhu, s délkou L^best = L(π^best).

1. Elitní strategie s parametrem e ∈ ℕ (počet „elitních mravenců“) provede běžnou aktualizaci mravenčího systému a pak na každou hranu (i, j), která patří do okruhu π^best, přidá ještě e · Q/L^best; ostatních hran se tento krok netýká.
2. MAX–MIN Ant System s mezemi 0 < τ_min < τ_max klade feromon jen podle jednoho nejlepšího okruhu π^best (podle varianty nejlepšího v dané iteraci, nebo nejlepšího od začátku běhu) a výsledek ořízne do intervalu [τ_min, τ_max]: pro každou hranu (i, j) τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), kde Δ_ij = 1/L^best, patří-li (i, j) do π^best, a Δ_ij = 0 jinak.

Elitní strategie tedy dosud nejlepší okruh posiluje navíc, MAX–MIN Ant System naopak dovolí posilovat jen jej a žádné hraně nedovolí klesnout pod τ_min ani vystoupat nad τ_max.

Horní mez Stützle a Hoos volí τ_max = 1/ρ L^best — přesně ustálená hodnota Δ/ρ z věty výše pro hranu, která leží v nejlepším okruhu pokaždé. Dolní mez je malý zlomek horní; feromon se navíc na začátku nastaví na τ_max, aby první iterace zkoumaly co nejšíř.

Definice — pravidla Ant Colony System

Nechť jsou dána města, vzdálenosti, feromon τ_ij > 0 a viditelnost η_ij = 1/d_ij jako v pravidle přechodu výše, a parametry q₀ ∈ [0, 1], β ≥ 0, ρ ∈ (0, 1), ξ ∈ (0, 1) a počáteční hodnota feromonu τ₀ > 0. Ant Colony System se od mravenčího systému liší třemi pravidly:

1. Pseudonáhodné proporcionální pravidlo. Mravenec ve městě i s neprázdnou množinou nenavštívených měst N_i vylosuje q rovnoměrně z [0, 1), nezávisle na předchozích losováních. Je-li q ≤ q₀, přejde do města j = arg max_{l ∈ Ni} τ_il · η_il^β; je-li q > q₀, zvolí j ∈ N_i losem podle pravidla přechodu mravenčího systému s α = 1.
2. Lokální aktualizace. Hned poté, co mravenec přejde po hraně (i, j), se τ_ij ← (1 − ξ) τ_ij + ξ τ₀.
3. Globální aktualizace. Nechť π^best je nejlepší dosud nalezený okruh a L^best jeho délka. Po každé iteraci se jen pro hrany (i, j) patřící do π^best provede τ_ij ← (1 − ρ) τ_ij + ρ/L^best; feromon ostatních hran se nemění.

S pravděpodobností q₀ tedy mravenec bere rovnou nejlepší hranu; použitá hrana podle pravidla 2 trochu zeslábne směrem k počáteční hodnotě τ₀, takže další mravenci zkoušejí jinde, a vyprchání i posílení se týká jen nejlepšího okruhu.

Dorigo a Gambardella (1997) v původním článku používají q₀ = 0,9, β = 2 a ρ = ξ = 0,1 — v devíti krocích z deseti tedy mravenec bere nejlepší hranu a jen v desátém zkouší.

7. Kde mravenci pracují

• Směrování v sítích. Algoritmus AntNet (Di Caro a Dorigo, 1998) posílá sítí malé pakety-mravence, které měří zpoždění a aktualizují směrovací tabulky. Síť se tak průběžně přizpůsobuje zahlcení.
• Trasy vozidel a rozvrhy. Rozvoz zboží, svoz odpadu nebo pořadí zakázek ve výrobě — úlohy příbuzné obchodnímu cestujícímu, kde se mravenčí algoritmy používají spolu s lokálním hledáním.
• Inteligence hejna. Mravenčí kolonie je jeden z příkladů, jak z jednoduchých jedinců a místních pravidel vznikne chytré chování celku. Další, hejno částic, je námětem příštího dílu.

8. Shrnutí

• Mravenci komunikují stopou v prostředí (stigmergie): kratší cesta se značí rychleji a pozitivní zpětná vazba ji zesílí.
• V modelu dvojitého mostu se 85 ze 100 kolonií ustálí na krátké větvi — náhoda ale může zamknout i tu dlouhou.
• Mravenčí systém volí další město podle feromonu τ^α a vzdálenosti η^β; feromon vyprchává rychlostí ρ a krátké okruhy ho přidávají víc.
• Na krajských městech našel optimum, ale jen v 7 z 20 běhů; na 60 městech dopadl srovnatelně se žíháním. Bez feromonu i bez vzdáleností výrazně hůř.
• Prakticky používané varianty (MAX–MIN, ACS) brání předčasnému zamrznutí a kombinují mravence s lokálním hledáním.

Chcete si to osahat? Nechte AI agenta napsat simulaci dvojitého mostu a zkuste, co se stane, když krátkou větev v polovině pokusu „zavřete“ — dokáže kolonie přejít zpátky na dlouhou?

Máte na to jiný názor? Napište na support@coden-app.com.