Optimalizácia mravčou kolóniou: ako feromónová stopa nájde krátku cestu

Stigmergia, pokus s dvojitým mostom, Dorigov mravčí systém, úloha parametrov α, β a ρ a vylepšené varianty — na okruhu cez krajské mestá a na 60 mestách, v porovnaní so žíhaním.

13 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 29 z 52

1. Mapa umelej inteligencie: čo je čo a ako to do seba zapadá
2. Stručná história umelej inteligencie: od Turinga po jazykové modely
3. Dáta, model, tréning, inferencia: základné pojmy na jednom príklade
4. Ako čítať matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relácie: stavebnica, z ktorej sa skladajú definície v AI
6. Funkcie a zobrazenia: prečo je každý model v AI funkcia
7. Logika a dôkazy: pravidlá, podľa ktorých sa v AI uvažuje
8. Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete
9. Lineárna algebra pre strojové učenie: vektory, matice a prečo AI hlavne násobí
10. Derivácie, gradient a reťazové pravidlo: ako model zistí, ktorým smerom sa učiť
11. Gradientný zostup: ako sa model učí
12. Čo je pravdepodobnosť: od hodu kockou ku Kolmogorovovým axiómam
13. Podmienená pravdepodobnosť a Bayesova veta: ako zmeniť odhad, keď sa dozviete niečo nové
14. Náhodná premenná a distribučná funkcia: jedna funkcia, ktorá o rozdelení povie všetko
15. Funkcia hustoty a pravdepodobnostná funkcia: prečo má spojitá premenná v bode pravdepodobnosť nula
16. Stredná hodnota, rozptyl a kovariancia: kde rozdelenie leží, aké je široké a čo s čím súvisí
17. Prehľad pravdepodobnostných rozdelení: Bernoulliho, binomické, Poissonovo, rovnomerné, normálne a exponenciálne
18. Zákon veľkých čísel a centrálna limitná veta: prečo sa priemery správajú tak predvídateľne
19. Štatistika a odhady parametrov: maximálna vierohodnosť, MAP a intervaly spoľahlivosti
20. Teória informácie: entropia, krížová entropia a KL divergencia — odkiaľ sa berú stratové funkcie
21. Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami
22. Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search
23. Splňovanie obmedzujúcich podmienok: backtracking, propagácia obmedzení a AC-3 na sudoku a mape krajov
24. Logika a znalostné systémy: dopredné a spätné reťazenie, rezolúcia a expertné systémy
25. Plánovanie: STRIPS, svet kociek, heuristiky z relaxácie a plánovanie v AI agentoch
26. Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá
27. Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet
28. Evolučné stratégie a genetické programovanie: od pravidla jednej pätiny po Keplerov zákon
29. Optimalizácia mravčou kolóniou: ako feromónová stopa nájde krátku cestu
30. Optimalizácia rojom častíc: zotrvačnosť, vlastná skúsenosť a skúsenosť roja
31. Neuroevolúcia: evolúcia váh aj tvaru neurónových sietí a algoritmus NEAT
32. Fuzzy množiny a funkcie príslušnosti: ako zapísať „trochu teplo“
33. Fuzzy logika a pravdepodobnosť: prečo „trochu teplo“ neznamená „pravdepodobne teplo“
34. Fuzzy logika: t-normy, implikácie a pravidlá AK–TAK
35. Fuzzy riadenie: Mamdani a Sugeno od ventilátora po kyvadlo na vozíku
36. Fuzzy zhlukovanie: algoritmus fuzzy c-means a body medzi zhlukmi
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidlá, ktoré sa učia z dát
38. Markovove reťazce: prechodová matica, stacionárne rozdelenie a PageRank
39. Skryté Markovove modely: Viterbiho algoritmus a nepoctivé kasíno
40. Bayesovské siete: prečo je tráva mokrá a čo z toho vyplýva pre postrekovač
41. Kalmanov filter: ako z nepresných meraní odhadnúť, kde auto je a ako rýchlo ide
42. Druhy strojového učenia: s učiteľom, bez učiteľa, s čiastočným učiteľom a ďalšie
43. Prompty, kontext a RAG: ako modelu dať správne informácie
44. Variačné autoenkodéry (VAE): nové obrázky zo spojitého latentného priestoru
45. Generatívne adversariálne siete (GAN): falšovateľ proti detektívovi
46. Difúzne modely: ako sa z čistého šumu stane obrázok
47. Markovove rozhodovacie procesy: stavy, akcie, odmeny a Bellmanove rovnice
48. Q-learning a DQN: učenie hodnoty akcií od tabuľky po neurónovú sieť
49. Policy gradient a PPO: učenie priamo stratégie
50. Ako funguje AI agent: jazykový model v slučke s nástrojmi
51. Programovanie s AI agentmi: zadanie, testy a kontrola
52. Vyhodnocovanie a bezpečnosť AI systémov: ako merať a ako strážiť

Celá osnova série Hotovo: 52 z 83 tém

Jeden mravec nemá mapu, nevie počítať a vidí sotva pár centimetrov pred seba. Kolónia napriek tomu spoľahlivo nájde najkratšiu cestu z mraveniska k potrave. Žiadny mravec ju nepozná — vznikne z toho, ako všetci spoločne značkujú terén. Začiatkom deväťdesiatych rokov si Marco Dorigo z milánskej polytechniky všimol, že ten istý trik sa dá použiť na problém obchodného cestujúceho. Tak vznikla optimalizácia mravčou kolóniou a s ňou celý odbor inteligencie roja.

Nadväzuje na diel Lokálne hľadanie a simulované žíhanie. Riešime tú istú úlohu — okruh cez krajské mestá s optimom 1 060,4 km —, takže uvidíme, ako si mravce vedú proti žíhaniu.

1. Komunikácia stopou

Definícia — stigmergia

Nech skupina jedincov (napr. mravcov jednej kolónie) zdieľa spoločné prostredie, ktorého stav sa môže meniť. Stigmergia je spôsob koordinácie týchto jedincov, pri ktorom platia všetky tri podmienky:

1. jedinec svojou činnosťou zmení stav prostredia — zanechá v ňom stopu (napr. feromón);
2. zmenený stav prostredia ovplyvní, čo neskôr urobia ostatní jedinci alebo on sám;
3. jedinci si informáciu neodovzdávajú priamo (signálom od jedinca k jedincovi), ale len prostredníctvom stavu prostredia.

Stigmergia je teda nepriama komunikácia cez prostredie. Pojem zaviedol Pierre-Paul Grassé v roku 1959 pri štúdiu stavby termitísk.

2. Pokus s dvojitým mostom

V roku 1989 postavili Goss, Deneubourg a ich kolegovia argentínskym mravcom medzi mravenisko a potravu dva mosty — jeden dvakrát dlhší ako druhý. Po chvíli chodila väčšina kolónie po kratšom. Prečo? Mravec, ktorý zvolil krátku vetvu, dorazí k potrave skôr, a keď sa vracia, pri potrave je krátka vetva už označená. Krátka cesta sa značí rýchlejšie a začne vyhrávať.

Definícia — model voľby vetvy (Deneubourg a kol.)

Nech medzi mraveniskom a potravou vedú dve vetvy, krátka a dlhá. Nech A ≥ 0 a B ≥ 0 sú množstvá feromónu na začiatku krátkej a dlhej vetvy v okamihu, keď mravec prichádza k rázcestiu, a nech k > 0 a h > 0 sú parametre modelu. Mravec zvolí krátku vetvu s pravdepodobnosťou

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

a dlhú vetvu s pravdepodobnosťou 1 − P(A, B). Mravec položí jednotku feromónu na začiatok zvolenej vetvy a ďalšiu na jej koniec, keď tam dorazí.

Parameter k teda určuje, ako silno mravec reaguje na slabú stopu (čím väčšie k, tým menej), a h > 1 zosilňuje rozdiely medzi vetvami; pri A = B je P = 1/2.

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

P

pravdepodobnosť, že ďalší mravec pôjde krátkou vetvou — mravec sa nerozhoduje isto, len s váhou; dlhá vetva dostane zvyšok 1 − P

A

feromón na krátkej vetve — to jediné, čo mravec o ceste „vie“; čím viac ho tam je, tým viac to krátku vetvu ťahá

B

feromón na dlhej vetve — v menovateli súperí s krátkou, takže rozhoduje pomer stôp, nie ich absolútne množstvo

k

„prah pozornosti“ — pripočíta sa k obom vetvám rovnako, takže pár prvých molekúl feromónu pomer takmer nezmení; bez neho by o celej kolónii rozhodol prvý mravec

h

zosilňovač — mocnina väčšia ako 1 zveličí rozdiel; práve ona robí z malej náhodnej výhody kladnú spätnú väzbu

Príklad — ako rozhoduje k = 30 a h = 2

Na krátkej vetve je A = 20, na dlhej B = 10 jednotiek feromónu:

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

(Farby podľa vzorca vyššie.)

• Rovnaké stopy (A = B, napríklad obe nulové): P = 0,500 — čistá náhoda.
• Päť jednotiek proti nule: P = (30 + 5)²/(30 + 5)² + (30 + 0)² = 35²/35² + 30² ≈ 0,576 — malá stopa takmer nerozhoduje, to je práca k.
• A = 60, B = 10: P = 8 100/8 100 + 1 600 ≈ 0,835 — už jasná prevaha.
• Bez zosilnenia (h = 1) by pri A = 20, B = 10 vyšlo len 50/90 ≈ 0,556 namiesto 0,610.

Simulácia modelu (k = 30, h = 2, desať mravcov za krok, krátka vetva 5 krokov, dlhá 10) ukazuje podiel feromónu na krátkej vetve pri ôsmich kolóniách:

Sedem kolónií sa ustálilo na krátkej vetve, jedna na dlhej: niekoľko prvých mravcov náhodou zvolilo dlhú vetvu a kladná spätná väzba ju „zamkla“. Zo sto kolónií skončilo 85 na krátkej vetve a 9 na dlhej. Keď sú obe vetvy rovnako dlhé, rozdelia sa kolónie zhruba napoly (46 a 42) — symetriu rozbije náhoda. Dĺžka cesty teda výsledok posúva, ale nezaručuje. Rovnakú slabinu uvidíme pri algoritme.

3. Mravčí systém

Dorigov mravčí systém (Ant System, 1992) posiela virtuálne mravce po grafe miest. Každý postaví celý okruh a podľa toho, aký je krátky, položí feromón na jeho hrany.

Definícia — okruh a jeho dĺžka

Nech n ∈ ℕ, n ≥ 3, je počet miest, mestá označíme číslami 1, …, n, a nech pre všetky i, j ∈ {1, …, n}, i ≠ j, je daná vzdialenosť d_ij ∈ ℝ taká, že d_ij = d_ji > 0.

1. Okruh je usporiadaná n-tica π = (π₁, …, π_n), v ktorej je každé mesto práve raz, t. j. {π₁, …, π_n} = {1, …, n} (π je permutácia miest). Kvôli kratšiemu zápisu kladieme π_n+1 = π₁.
2. Dĺžka okruhu π je číslo L(π) = ∑_k=1ⁿ d_πkπk+1 = d_π1π2 + d_π2π3 + … + d_πnπ1; posledný člen vracia cestovateľa domov.
3. Hrana (i, j) patrí do okruhu π práve vtedy, keď existuje k ∈ {1, …, n} také, že {π_k, π_k+1} = {i, j}.
4. Problém obchodného cestujúceho je úloha nájsť okruh π^* taký, že L(π^*) ≤ L(π) pre každý okruh π.

Okruh teda prejde každé mesto práve raz a vráti sa do východiskového; hrana doň patrí práve vtedy, keď v ňom idú jej dve mestá hneď po sebe.

Definícia — pravidlo prechodu

Nech sú dané mestá 1, …, n so vzdialenosťami d_ij > 0 (pozri definíciu okruhu vyššie), na každej hrane (i, j) feromón τ_ij > 0 a parametre α ≥ 0, β ≥ 0. Viditeľnosť hrany (i, j) je číslo

η_ij = 1/d_ij.

Nech mravec stojí v meste i a N_i ⊆ {1, …, n} je neprázdna množina miest, ktoré na svojom okruhu doteraz nenavštívil. Mravec prejde do mesta j s pravdepodobnosťou

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

Mravec teda volí len medzi nenavštívenými mestami, a to s váhou úmernou súčinu stopy τ_ij^α a viditeľnosti η_ij^β (blízke mestá sú lákavejšie); parametre α a β vážia stopu proti vzdialenosti. Pravdepodobnosti p_ij cez j ∈ N_i majú súčet 1.

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

p_ij

pravdepodobnosť kroku z i do j — losujeme, nevyberáme najlepšie, aby kolónia stále skúšala aj iné okruhy

τ_ij^α

pamäť kolónie — feromón nesie skúsenosť predchádzajúcich mravcov; exponent α hovorí, ako veľmi jej veriť (α = 0 ju úplne vypne)

η_ij^β

chamtivosť — η = 1/d zvýhodní blízke mestá; je to rada, ktorú máme zadarmo hneď od prvej iterácie, keď feromón ešte nič nevie

∑ … cez N_i

súčet váh všetkých doteraz nenavštívených miest — delením sa z váh stanú pravdepodobnosti so súčtom 1; navštívené mestá v ňom nie sú, takže sa do nich mravec nevráti

Príklad — jedno rozhodnutie mravca

Mravec stojí v meste i a zostávajú mu tri mestá: vo vzdialenosti 50, 100 a 150 km, s feromónom τ = 1, 3 a 2. Konštanta vo viditeľnosti sa v zlomku vykráti, počítajme preto s η = 100/d, teda 2, 1 a 2/3. S α = 1 a β = 3 (farby podľa vzorca vyššie):

• váhy τ^α · η^β: 1 · 2³ = 8,000, 3 · 1³ = 3,000, 2 · (2/3)³ ≈ 0,593;
• ich súčet 11,593;
• pravdepodobnosti p = 8,000/11,593 ≈ 0,690, 3,000/11,593 ≈ 0,259 a 0,593/11,593 ≈ 0,051.

Najbližšie mesto vyhráva, hoci má najmenej feromónu. S β = 1 by vyšlo 0,316, 0,474 a 0,211 — vedie feromón. A s β = 0 rozhoduje len stopa: 0,167, 0,500 a 0,333 (podiely 1 : 3 : 2).

Definícia — aktualizácia feromónu

Nech ρ ∈ (0, 1) je rýchlosť vyprchania a Q > 0 konštanta. Nech v jednej iterácii postavilo M ≥ 1 mravcov okruhy π⁽¹⁾, …, π^(M) (okruh m je π^(m)) s dĺžkami L_m = L(π^(m)), m = 1, …, M. Po iterácii sa feromón na každej hrane (i, j) nahradí hodnotou

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

kde sa sčítava cez všetky m ∈ {1, …, M}, pre ktoré hrana (i, j) patrí do okruhu π^(m) (prázdny súčet je 0). Feromón teda všade vyprchá o podiel ρ a každý mravec m pridá na hrany svojho okruhu množstvo Q/L_m, nepriamo úmerné dĺžke okruhu.

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

τ_ij vľavo

nový feromón na hrane — to, podľa čoho sa budú rozhodovať mravce budúcej iterácie

(1 − ρ)

vyprchanie — každá iterácia z každej stopy uberie rovnaký podiel ρ; stará skúsenosť tak slabne geometricky a kolónia sa môže preučiť

τ_ij vpravo

doterajší feromón — pamäť sa len opravuje, nezačína sa od nuly

∑_m

súčet cez mravce, ktoré hranou prešli — každý mravec pridáva len na hrany svojho okruhu; hrana, ktorú použije viac mravcov, dostane viac — tu sa sčítava „hlasovanie“ kolónie

Q/L_m

odmena nepriamo úmerná dĺžke okruhu — kratší okruh = silnejšia stopa; konštanta Q len nastavuje mierku

Príklad — jedna aktualizácia

Hrana má τ = 1, ρ = 0,3, Q = 1 000 a prešli ňou dva mravce s okruhmi dlhými 1 100 a 1 300 km (farby podľa vzorca vyššie):

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

Hrana, ktorou neprešiel nikto, má po tej istej iterácii len 0,7. Mravec s kratším okruhom pridal viac (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                 # vyprchanie
    for okruh in okruhy:
        L = delka(okruh)
        for a, b in zip(okruh, okruh[1:] + okruh[:1]):
            tau[a][b] += Q / L                  # kratší okruh, silnejšia stopa
            tau[b][a] += Q / L

Celý mravčí systém potom len strieda stavbu okruhov a aktualizáciu a pamätá si najlepší okruh, aký kedy niekto postavil:

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

4. Mravce na krajských mestách

Pustime 13 mravcov (z každého mesta jedného) na 100 iterácií s α = 1, β = 3 a ρ = 0,3. Mapa ukazuje feromón na hranách po 1., 5., 20. a 100. iterácii — čím silnejšia čiara, tým viac feromónu:

V prvej iterácii je stopa rozprestretá takmer všade a najlepší okruh meria 1 292,6 km. Už v piatej iterácii nájde jeden z mravcov optimum 1 060,4 km. Feromón sa potom sústredí na hrany dobrých okruhov — slabé čiary miznú, silné zostávajú — a priemerný mravec postaví okruh dlhý zhruba 1 250 km. Kolónia nekonverguje úplne, stále trochu skúša.

Trasovanie behu po iteráciách — najlepší okruh nájdený doteraz a priemerný okruh trinástich mravcov v danej iterácii:

Najlepší okruh sa zlepšuje skokom (tretia iterácia nepriniesla nič nové, štvrtá ubrala 111 km), priemer klesá pomalšie a nerovnomerne: mravce losujú, takže aj v dobrej iterácii niektoré postavia slabé okruhy. Rozdiel medzi priemerom a najlepším je presne ten prieskum, ktorý kolónii bráni úplne zamrznúť.

Nie vždy to dopadne tak dobre. Z dvadsiatich behov s rôznymi semienkami našlo optimum len 7, priemer bol 1 073,9 km a najhorší výsledok 1 083,0 km. Žíhanie bolo na tej istej úlohe s 98 zo 100 spoľahlivejšie. Pre predstavu: hladný „najbližší sused“, ktorý ide vždy do najbližšieho nenavštíveného mesta, dá podľa štartu 1 120 až 1 336 km. Mravce sú výrazne lepšie, ale základný mravčí systém sám osebe nie je šampión — preto vznikli jeho vylepšené varianty.

5. Na čo sú α, β a ρ

Na trinástich mestách sa dá veľa vyriešiť aj bez feromónu. Rozdiel ukáže až väčšia úloha — tých istých 60 náhodných miest ako v diele o žíhaní, 30 mravcov, 150 iterácií, priemer z troch behov:

• Bez feromónu (α = 0) sú mravce len náhodní hladní cestovatelia a nič sa nenaučia — okruhy o tretinu dlhšie.
• Bez vzdialeností (β = 0) nemá kolónia od čoho sa odraziť: prvé okruhy sú úplne náhodné a feromón z nich vedie k ďalším náhodným.
• Pomalé vyprchanie drží stopy z prvých, zlých okruhov príliš dlho a kolónia sa učí pomaly. Rýchle vyprchanie naopak zabúda aj to dobré.

Ako dlho si kolónia pamätá, sa dá vypočítať presne. Stačí sledovať jednu hranu.

Veta — ustálený feromón a polčas vyprchania

Nech ρ ∈ (0, 1), Δ ≥ 0 a τ₀ ∈ ℝ. Nech postupnosť (τ_t)_{t = 0, 1, 2, …} (feromón jednej hrany po t iteráciách, ktorá v každej iterácii dostane rovnaký prírastok Δ) spĺňa pre každé t ≥ 0

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

Potom

1. pre každé t ≥ 0 platí τ_t = Δ/ρ + (1 − ρ)^t (τ₀ − Δ/ρ),
2. lim_{t → ∞} τ_t = Δ/ρ,
3. ak Δ = 0 a τ₀ > 0, je τ_t = (1 − ρ)^t τ₀ a pre reálne t ≥ 0 platí (1 − ρ)^t τ₀ = τ₀/2 práve vtedy, keď t = t_½, kde t_½ = ln 2/−ln(1 − ρ) je polčas vyprchania (vo všeobecnosti nie je celé číslo).

Dôkaz. Označme e_t = τ_t − Δ/ρ odchýlku od Δ/ρ. Keďže (1 − ρ) · Δ/ρ + Δ = Δ/ρ, dostaneme odčítaním Δ/ρ od oboch strán rekurencie e_t+1 = (1 − ρ) e_t, a indukciou e_t = (1 − ρ)^t e₀; to je bod 1. Keďže 1 − ρ ∈ (0, 1), je (1 − ρ)^t → 0, a teda e_t → 0; to je bod 2. Pre Δ = 0 je τ_t = (1 − ρ)^t τ₀, takže τ_t = τ₀/2 práve vtedy, keď (1 − ρ)^t = 1/2, t. j. t · ln(1 − ρ) = −ln 2; keďže ln(1 − ρ) < 0, je jediným riešením t = ln 2/−ln(1 − ρ). ∎

τ^* = Δ/ρ

τ^*

hladina, na ktorej sa feromón hrany ustáli — pridávanie a vyprchanie sú v rovnováhe

Δ

koľko hrana dostáva za iteráciu — hrany z častých a krátkych okruhov majú Δ veľké, a preto aj vysokú hladinu

ρ

v menovateli: pomalé vyprchanie nechá stopy narásť vysoko a rozdiely medzi hranami sa vyrovnávajú dlho; rýchle ich drží nízko a závislé len od posledných pár iterácií

Dve hrany s τ₀ = 1 a ρ = 0,3: jedna dostáva v každej iterácii Δ = 1, druhú nikto nepoužíva.

Používaná hrana sa blíži k τ^* = 1/0,3 ≈ 3,33 (farby podľa vzorca vyššie), nepoužívaná za desať iterácií spadne pod tri stotiny. Polčas vyprchania pre riadky tabuľky vyššie: s ρ = 0,3 je 1,94 iterácie, s ρ = 0,02 celých 34,31 iterácie — stopy z prvých náhodných okruhov teda vládnu ešte desiatky iterácií — a s ρ = 0,9 len 0,30 iterácie, takže kolónia si pamätá prakticky len posledné kolo.

Najlepšie nastavenie dalo 2 194 až 2 314 km — porovnateľne so žíhaním z minulého dielu, ktoré na tých istých mestách skončilo medzi 2 210 a 2 270 km.

6. Lepšie mravce

• Elitná stratégia pridáva feromón navyše na doteraz najlepší okruh, aby sa nestratil.
• MAX–MIN Ant System (Stützle a Hoos, 2000) dovolí klásť feromón len najlepšiemu mravcovi a drží τ medzi dolnou a hornou hranicou. Dolná hranica zaručí, že žiadna hrana úplne nezmizne, a kolónia tak predčasne nezamrzne — ako tá, ktorá v pokuse s mostom skončila na dlhej vetve.
• Ant Colony System (Dorigo a Gambardella, 1997) s pravdepodobnosťou volí rovno najlepšiu hranu a feromón uberá už počas stavby okruhu, aby ostatné mravce skúšali inde.
• Lokálne hľadanie. V praxi sa každý okruh postavený mravcom ešte doladí ťahmi 2-opt z dielu o žíhaní. Mravce nájdu dobrú oblasť, horolezec ju doladí — táto kombinácia patrila v deväťdesiatych rokoch k najlepším metódam na obchodného cestujúceho.

Definícia — elitná stratégia a MAX–MIN Ant System

Nech ρ ∈ (0, 1) a Q > 0 sú ako v aktualizácii feromónu mravčieho systému a nech π^best je najlepší okruh nájdený od začiatku behu, s dĺžkou L^best = L(π^best).

1. Elitná stratégia s parametrom e ∈ ℕ (počet „elitných mravcov“) vykoná bežnú aktualizáciu mravčieho systému a potom na každú hranu (i, j), ktorá patrí do okruhu π^best, pridá ešte e · Q/L^best; ostatných hrán sa tento krok netýka.
2. MAX–MIN Ant System s hranicami 0 < τ_min < τ_max kladie feromón len podľa jedného najlepšieho okruhu π^best (podľa varianty najlepšieho v danej iterácii alebo najlepšieho od začiatku behu) a výsledok oreže do intervalu [τ_min, τ_max]: pre každú hranu (i, j) τ_ij ← min(τ_max, max(τ_min, (1 − ρ) τ_ij + Δ_ij)), kde Δ_ij = 1/L^best, ak (i, j) patrí do π^best, a Δ_ij = 0 inak.

Elitná stratégia teda doteraz najlepší okruh posilňuje navyše, MAX–MIN Ant System naopak dovolí posilňovať len jeho a žiadnej hrane nedovolí klesnúť pod τ_min ani vystúpiť nad τ_max.

Hornú hranicu Stützle a Hoos volia τ_max = 1/ρ L^best — presne ustálená hodnota Δ/ρ z vety vyššie pre hranu, ktorá leží v najlepšom okruhu zakaždým. Dolná hranica je malý zlomok hornej; feromón sa navyše na začiatku nastaví na τ_max, aby prvé iterácie skúmali čo najširšie.

Definícia — pravidlá Ant Colony System

Nech sú dané mestá, vzdialenosti, feromón τ_ij > 0 a viditeľnosť η_ij = 1/d_ij ako v pravidle prechodu vyššie, a parametre q₀ ∈ [0, 1], β ≥ 0, ρ ∈ (0, 1), ξ ∈ (0, 1) a počiatočná hodnota feromónu τ₀ > 0. Ant Colony System sa od mravčieho systému líši tromi pravidlami:

1. Pseudonáhodné proporcionálne pravidlo. Mravec v meste i s neprázdnou množinou nenavštívených miest N_i vylosuje q rovnomerne z [0, 1), nezávisle od predchádzajúcich losovaní. Ak je q ≤ q₀, prejde do mesta j = arg max_{l ∈ Ni} τ_il · η_il^β; ak je q > q₀, zvolí j ∈ N_i losom podľa pravidla prechodu mravčieho systému s α = 1.
2. Lokálna aktualizácia. Hneď potom, ako mravec prejde po hrane (i, j), sa τ_ij ← (1 − ξ) τ_ij + ξ τ₀.
3. Globálna aktualizácia. Nech π^best je najlepší doteraz nájdený okruh a L^best jeho dĺžka. Po každej iterácii sa len pre hrany (i, j) patriace do π^best vykoná τ_ij ← (1 − ρ) τ_ij + ρ/L^best; feromón ostatných hrán sa nemení.

S pravdepodobnosťou q₀ teda mravec berie rovno najlepšiu hranu; použitá hrana podľa pravidla 2 trochu zoslabne smerom k počiatočnej hodnote τ₀, takže ďalšie mravce skúšajú inde, a vyprchanie aj posilnenie sa týka len najlepšieho okruhu.

Dorigo a Gambardella (1997) v pôvodnom článku používajú q₀ = 0,9, β = 2 a ρ = ξ = 0,1 — v deviatich krokoch z desiatich teda mravec berie najlepšiu hranu a len v desiatom skúša.

7. Kde mravce pracujú

• Smerovanie v sieťach. Algoritmus AntNet (Di Caro a Dorigo, 1998) posiela sieťou malé pakety-mravce, ktoré merajú oneskorenie a aktualizujú smerovacie tabuľky. Sieť sa tak priebežne prispôsobuje zahlteniu.
• Trasy vozidiel a rozvrhy. Rozvoz tovaru, zvoz odpadu alebo poradie zákaziek vo výrobe — úlohy príbuzné obchodnému cestujúcemu, kde sa mravčie algoritmy používajú spolu s lokálnym hľadaním.
• Inteligencia roja. Mravčia kolónia je jeden z príkladov, ako z jednoduchých jedincov a miestnych pravidiel vznikne múdre správanie celku. Ďalší, roj častíc, je námetom budúceho dielu.

8. Zhrnutie

• Mravce komunikujú stopou v prostredí (stigmergia): kratšia cesta sa značí rýchlejšie a kladná spätná väzba ju zosilní.
• V modeli dvojitého mosta sa 85 zo 100 kolónií ustáli na krátkej vetve — náhoda však môže zamknúť aj tú dlhú.
• Mravčí systém volí ďalšie mesto podľa feromónu τ^α a vzdialenosti η^β; feromón vyprcháva rýchlosťou ρ a krátke okruhy ho pridávajú viac.
• Na krajských mestách našiel optimum, ale len v 7 z 20 behov; na 60 mestách dopadol porovnateľne so žíhaním. Bez feromónu aj bez vzdialeností výrazne horšie.
• Prakticky používané varianty (MAX–MIN, ACS) bránia predčasnému zamrznutiu a kombinujú mravce s lokálnym hľadaním.

Chcete si to vyskúšať? Nechajte AI agenta napísať simuláciu dvojitého mosta a skúste, čo sa stane, keď krátku vetvu v polovici pokusu „zatvoríte“ — dokáže kolónia prejsť späť na dlhú?

Máte na to iný názor? Napíšte na support@coden-app.com.