Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá

Optimalizačná úloha, problém obchodného cestujúceho, horolezec s okolím 2-opt, lokálne minimá a reštarty, simulované žíhanie, teplota a rozvrh chladenia — na trase cez trinásť krajských miest so známym optimom.

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

Séria Základy AI Diel 26 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

Kováč, ktorý chce pevnú čepeľ, nenechá rozžeravený kov prudko vychladnúť — ochladzuje ho pomaly. Atómy tak majú čas nájsť pravidelné usporiadanie s najnižšou energiou. Keby kov schladil naraz, atómy by zamrzli tam, kde práve boli, a čepeľ by bola krehká. V roku 1983 si fyzici všimli, že presne toto trápi aj algoritmy, ktoré hľadajú najlepšie riešenie: keď idú len „z kopca“, zamrznú v prvej jamke. Tak vzniklo simulované žíhanie — a s ním jedna z najužitočnejších myšlienok optimalizácie.

Týmto dielom začína modul o algoritmoch inšpirovaných prírodou. Nadväzuje na diel Prehľadávanie stavového priestoru, kde sa horolezec a žíhanie objavili prvýkrát.

1. Optimalizačná úloha

Definícia — optimalizačná úloha a okolie

Nech S je neprázdna množina, ktorej prvky nazývame prípustné riešenia, a f : S → ℝ je funkcia, ktorú nazývame účelová funkcia. Optimalizačná (minimalizačná) úloha (S, f) je úloha nájsť prvok s* ∈ S, pre ktorý platí

∀ s ∈ S : f(s*) ≤ f(s),   t. j.   s* ∈ argmin_{s ∈ S} f(s) = {s ∈ S : ∀ s′ ∈ S : f(s) ≤ f(s′)}.

Taký prvok s* nazývame globálne minimum. Ak je S konečná, globálne minimum existuje (môže ich byť aj viac). Pri maximalizačnej úlohe sa nerovnosti obrátia; maximalizovať f je to isté ako minimalizovať −f.

Označme 2^S množinu všetkých podmnožín S. Okolie je zobrazenie N : S → 2^S, ktoré každému riešeniu s ∈ S priradí množinu N(s) ⊆ S jeho susedov; v praxi sú to riešenia, ktoré zo s vzniknú jednou malou zmenou predpísaného typu. Riešenie s ∈ S je lokálne minimum vzhľadom na okolie N práve vtedy, keď

∀ s′ ∈ N(s) : f(s) ≤ f(s′).

Globálne minimum je teda riešenie, ktoré nemá lepšie riešenie nikde v S, kým lokálne minimum len také, ktoré nemá lepšie riešenie medzi svojimi susedmi. Každé globálne minimum je aj lokálne, naopak to neplatí.

2. Problém obchodného cestujúceho

Obchodný cestujúci má objsť všetkých trinásť krajských miest Česka, v každom byť raz a vrátiť sa, odkiaľ vyšiel. Ktorou trasou prejde najmenej? Vzdialenosti počítame vzdušnou čiarou.

Definícia — problém obchodného cestujúceho (TSP)

Nech n ≥ 3 je počet miest, mestá sú očíslované 1, …, n, a nech d : {1, …, n} × {1, …, n} → ℝ je funkcia vzdialeností, kde d(i, j) ≥ 0 je vzdialenosť mesta i od mesta j. V tomto diele je d navyše symetrická: d(i, j) = d(j, i) pre všetky i, j.

Prípustné riešenie (okruh) je permutácia π = (π₁, …, π_n) množiny {1, …, n} — poradie, v ktorom mestá prejdeme, a z posledného sa vrátime do prvého. Účelová funkcia je dĺžka okruhu

f(π) = ∑_k=1ⁿ d(π_k, π_k+1),   kde π_n+1 = π₁.

Problém obchodného cestujúceho je optimalizačná úloha nájsť permutáciu π s najmenšou dĺžkou f(π).

Permutácie, ktoré sa líšia len tým, v ktorom meste začínajú (cyklickým posunutím), alebo smerom prejazdu, majú rovnakú dĺžku a opisujú ten istý okruh. Rôznych okruhov je preto n!/2n = (n − 1)!/2 (rozbor nižšie). Rozhodovacia verzia úlohy („existuje okruh dĺžky najviac L?“) je NP-úplná.

počet okruhov = n!/n · 2 = (n − 1)!/2

n!

všetky poradia, v ktorých možno n miest vypísať — toľko je permutácií; každý okruh je však medzi nimi započítaný viackrát

n

okruh nemá začiatok: Praha → Brno → … → Praha je tá istá cesta ako Brno → … → Praha → Brno. Každý okruh možno začať v ktoromkoľvek z n miest, preto n-krát menej

2

vzdialenosť tam je rovnaká ako späť, takže okruh prejdený opačne je tá istá cesta rovnakej dĺžky

Príklad — vzdialenosť vzdušnou čiarou z Prahy do Brna

Mestá máme dané zemepisnou šírkou φ a dĺžkou λ v stupňoch. Na území Česka stačí rovinná približná projekcia: stupeň šírky má 110,57 km, stupeň dĺžky 111,32 · cos φ₀ km, kde φ₀ = 49,8° je stred republiky (poludníky sa k pólu zbiehajú). Potom

d(i, j) = √(71,85 · Δλ)² + (110,57 · Δφ)².

Praha (50,08° s. š., 14,42° v. d.), Brno (49,20°, 16,61°)

Δλ = 2,19° → 71,85 · 2,19 = 157,35 km na východ

Δφ = −0,88° → 110,57 · 0,88 = 97,30 km na juh

d = √157,35² + 97,30² = √24 759 + 9 467 = √34 226 ≈ 185,0 km

Chyba oproti presnému výpočtu na guli je pri takých vzdialenostiach okolo 1 %; na porovnávanie trás to neprekáža.

Trinásť miest je ešte dosť málo na to, aby sme optimum vypočítali presne — Heldovým–Karpovým dynamickým programovaním cez podmnožiny miest, ktoré trvá 2ⁿ · n² krokov namiesto (n − 1)!. Najkratší okruh meria 1 060,4 km. Vďaka tomu pri každom ďalšom algoritme presne uvidíme, ako blízko sa k optimu dostal:

Algoritmus — Heldovo–Karpovo dynamické programovanie (1962)

Vstup: počet miest n ≥ 3, mestá očíslované 0, …, n − 1, a vzdialenosti d : {0, …, n − 1}² → ℝ, d ≥ 0. Výstup: dĺžka najkratšieho okruhu (problém obchodného cestujúceho vyššie); okruh sám sa zistí spätným sledovaním, v ktorom k sa minimum nadobudlo.

Okruh nemá začiatok, preto bez ujmy na všeobecnosti začína v meste 0. Pre každú množinu miest M ⊆ {0, …, n − 1} s 0 ∈ M a každé mesto j ∈ M označme D(M, j) dĺžku najkratšej cesty, ktorá vyjde z mesta 0, prejde každé mesto z M práve raz, žiadne iné, a skončí v j. Pre M ≠ {0} kladieme D(M, 0) = ∞ (cesta sa do 0 nesmie vrátiť predčasne).

1. Polož D({0}, 0) = 0.
2. Pre m = 2, …, n postupne: pre každú M ∋ 0 s |M| = m a každé j ∈ M ∖ {0} vypočítaj D(M, j) = min_{k ∈ M ∖ {j}} [ D(M ∖ {j}, k) + d(k, j) ]. Všetky hodnoty vpravo majú množinu o prvok menšiu, takže už sú vypočítané.
3. Po dokončení m = n skonči a vráť min_{j ∈ {1, …, n − 1}} [ D({0, …, n − 1}, j) + d(j, 0) ].

Algoritmus teda vždy skončí po konečnom počte krokov: hodnôt D je najviac 2ⁿ · n a každá je minimum z najviac n čísel.

n = 13:   2¹³ · 13² = 8 192 · 169 = 1 384 448 krokov

prejsť všetky poradia z pevného štartu: 12! = 479 001 600 — asi 346-krát viac

3. Horolezec a okolie 2-opt

Definícia — ťah 2-opt

Nech n ≥ 4, d je symetrická vzdialenosť z definície TSP a c = (c₀, c₁, …, c_n−1) je okruh cez n miest (po c_n−1 nasleduje znova c₀). Nech i, j sú indexy, 1 ≤ i < j ≤ n − 1. Ťah 2-opt (i, j) priradí okruhu c okruh

c′ = (c₀, …, c_i−1, c_j, c_j−1, …, c_i, c_j+1, …, c_n−1),

t. j. obráti poradie úseku c_i, …, c_j. Označme a = c_i−1, b = c_i, e = c_j a f = c_{(j+1) mod n} (tu f označuje mesto, nie účelovú funkciu). Ťah z okruhu odoberie hrany (a, b) a (e, f) a pridá hrany (a, e) a (b, f); ostatné hrany zostanú, len úsek medzi b a e sa prejde opačne. Dĺžka okruhu sa preto zmení o

Δ = dĺžka(c′) − dĺžka(c) = d(a, e) + d(b, f) − d(a, b) − d(e, f).

Okolie 2-opt N(c) je množina všetkých okruhov, ktoré z c vzniknú jedným ťahom (i, j); dvojíc (i, j) je (n − 1)(n − 2)/2.

Δ = d(a, e) + d(b, f) − (d(a, b) + d(e, f))

Δ

o koľko sa okruh predĺži; záporné Δ znamená skrátenie. Podľa znamienka sa rozhoduje horolezec aj žíhanie, preto ho potrebujeme lacno

d(a, e) + d(b, f)

dve nové hrany, ktorými prestrihnuté konce znova spojíme — pripočítavajú sa, lebo o ne trasa pribudne

d(a, b) + d(e, f)

dve hrany, ktoré sme prestrihli — odčítavajú sa, lebo z trasy zmiznú. Úsek medzi b a e len prejdeme opačne a vzdialenosti sú symetrické, takže sa jeho dĺžka nezmení a vo vzorci chýba

Algoritmus — horolezec (najstrmší zostup)

Vstup: optimalizačná úloha (S, f) s konečnou množinou S, okolie N : S → 2^S s neprázdnymi množinami N(s) a počiatočné (náhodné) riešenie s₀ ∈ S. Výstup: lokálne minimum s ∈ S vzhľadom na N.

1. Polož s ← s₀.
2. Nájdi najlepšieho suseda s′ ∈ argmin_{t ∈ N(s)} f(t) (pri zhode ľubovoľného z nich).
3. Ak je f(s′) < f(s), polož s ← s′ a pokračuj krokom 2.
4. Inak (f(s′) ≥ f(s)) skonči a vráť s.

Podmienka zastavenia je v kroku 4: žiadny sused nie je ostro lepší, teda f(s) ≤ f(t) pre všetky t ∈ N(s) a s je lokálne minimum. Keďže f(s) v každom prechode ostro klesne, žiadne riešenie sa nezopakuje, a na konečnej S preto algoritmus vždy skončí.

def delta(c, i, j):                    # ťah 2-opt: obráť c[i..j]
    a, b = c[i - 1], c[i]
    e, f = c[j], c[(j + 1) % len(c)]
    return d(a, e) + d(b, f) - d(a, b) - d(e, f)

def horolezec(c):
    n = len(c)
    while True:
        tahy = [(i, j) for i in range(1, n - 1) for j in range(i + 1, n)]
        i, j = min(tahy, key=lambda t: delta(c, *t))   # najstrmší zostup
        if delta(c, i, j) >= 0:                        # nič trasu neskráti
            return c                                    # lokálne minimum
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

Prvé mesto necháme na mieste (i ≥ 1) — okruh nemá začiatok, takže by to nič nové neprinieslo. Pre n = 13 dávajú dvojice 1 ≤ i < j ≤ 12 práve 12 · 11/2 = 66 ťahov.

Z náhodného okruhu dlhého 2 402 km dôjde horolezec za 8 krokov na 1 065,8 km — a tam sa zastaví. Do optima chýba len 5 km, ale žiadny jednotlivý ťah 2-opt už trasu neskráti. Horolezec je v lokálnom minime a nevie o tom:

4. Kde horolezec uviazne

Zo sto náhodných štartov skončil horolezec v optime 61-krát. Vo zvyšných 39 prípadoch uviazol inde, v najhoršom na 1 162,6 km — o sto kilometrov ďalej. Pasce sú tri:

• Lokálne minimum — jamka, z ktorej vedie každý krok nahor.
• Plošina — všetci susedia sú rovnako dobrí, takže horolezec nevie, kam ísť.
• Hrebeň — dobrý smer existuje, ale nevedie po žiadnom jednotlivom ťahu; ide sa k nemu len cez horšie riešenia.

Príklad — prečo horolezec z 1 065,8 km nevyjde

Horolezec z prvého štartu skončil na okruhu Zlín → Ostrava → Olomouc → Pardubice → Hradec Králové → Liberec → Ústí nad Labem → Karlovy Vary → Plzeň → Praha → České Budějovice → Jihlava → Brno → Zlín. Vypočítame Δ všetkých 66 ťahov 2-opt: jeden z nich (obrátenie všetkého okrem prvého mesta) dá ten istý okruh opačným smerom a Δ = 0, všetky ostatné trasu predĺžia. Najlacnejší z nich obráti dvojicu Pardubice – Hradec Králové:

a = Olomouc, b = Pardubice, e = Hradec Králové, f = Liberec

Δ = d(a, e) + d(b, f) − (d(a, b) + d(e, f))

  = 122,9 + 95,9 − (116,8 + 83,0) = +19,0 km

(Farby podľa rozboru ťahu 2-opt vyššie.)

Každý jednotlivý ťah teda trasu predĺži najmenej o 19,0 km — pritom optimum je o púhych 5,4 km kratšie. Cesta k nemu vedie cez horšie okruhy, a tie horolezec nikdy neprijme.

Najjednoduchší liek sú náhodné reštarty: pustiť horolezca znova z iného miesta a ponechať si najlepší výsledok. Ak uspeje jeden štart s pravdepodobnosťou 0,61, potom z piatich štartov aspoň jeden uspeje s pravdepodobnosťou P₅ = 1 − 0,39⁵ ≈ 99 % (farby podľa vzorca nižšie). Pri malej úlohe to stačí. Pri veľkej sú jamiek milióny a reštartov by bolo treba priveľa.

P_r = 1 − (1 − p)^r

P_r

pravdepodobnosť, že aspoň jeden z r štartov nájde optimum — počítame ju cez doplnok, lebo „aspoň jeden“ má mnoho podôb, kým „ani jeden“ len jednu

1 − p

pravdepodobnosť, že jeden štart zlyhá (u nás 0,39 zo sto pokusov)

r

počet štartov v exponente: štarty sú nezávislé (každý má iné náhodné semienko), takže pravdepodobnosti zlyhania sa násobia

5. Simulované žíhanie

Algoritmus — simulované žíhanie

Vstup: optimalizačná úloha (S, f), okolie N : S → 2^S s neprázdnymi konečnými množinami N(s), počiatočné (náhodné) riešenie s₀ ∈ S, počiatočná teplota T₀ > 0, koeficient chladenia α ∈ (0, 1) a počet iterácií K ∈ ℕ. Výstup: najlepšie riešenie s_naj ∈ S, ktoré algoritmus počas behu navštívil.

1. Polož s ← s₀, s_naj ← s₀, T ← T₀.
2. Pre k = 1, …, K opakuj:
   1. vyber náhodne (rovnomerne) suseda s′ ∈ N(s) a vypočítaj Δ = f(s′) − f(s);
   2. ak je Δ ≤ 0, polož s ← s′; inak vylosuj u rovnomerne z [0, 1) a ak je u < exp(−Δ/T), polož s ← s′ (Metropolisovo kritérium: horší sused sa prijme s pravdepodobnosťou exp(−Δ/T));
   3. ak je f(s) < f(s_naj), polož s_naj ← s;
   4. zníž teplotu podľa rozvrhu chladenia, tu geometrického: T ← α · T.
3. Po K iteráciách skonči a vráť s_naj.

Algoritmus sa teda zastaví vždy po vopred danom počte K iterácií; iné rozvrhy chladenia než geometrický pozri v oddiele o teplote.

P(prijať) = min(1, exp(−Δ/T))

P(prijať)

s akou pravdepodobnosťou prejdeme do navrhnutého suseda; v programe losujeme u rovnomerne z [0, 1) a ťah prijmeme, keď u < P

min(1, …)

pre zlepšenie (Δ ≤ 0) je exponenciála ≥ 1 a pravdepodobnosť nesmie presiahnuť 1 — lepší krok sa teda prijme vždy, rovnako ako pri horolezcovi

Δ

o koľko je sused horší, v km. Stojí v exponente so záporným znamienkom, takže každý ďalší kilometer zhoršenia šancu vynásobí rovnakým číslom menším než 1 — veľké zhoršenia sú exponenciálne vzácnejšie než malé

T

teplota, v rovnakých jednotkách ako Δ (km). Delí Δ, a tým určuje mierku: zhoršenie o T km prejde s pravdepodobnosťou exp(−1) = 1/e ≈ 0,37 pri akejkoľvek teplote. Vysoké T robí veľké zhoršenia „malými“, T → 0 zakáže všetky

Pravidlo na prijatie horšieho kroku pochádza z fyziky: v roku 1953 ho Nicholas Metropolis a jeho kolegovia použili na simuláciu atómov v tepelnej rovnováhe, kde pravdepodobnosť stavu s energiou E je úmerná exp(−E/kT). Na optimalizáciu ho v roku 1983 nezávisle prispôsobili Kirkpatrick, Gelatt a Vecchi z IBM — a o dva roky neskôr, takisto nezávisle, slovenský fyzik Vladimír Černý, práve na probléme obchodného cestujúceho.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # geometrické chladenie
    T, delka = T0, delka_okruhu(c)
    nej, nej_delka = c, delka
    for k in range(K):
        i, j = sorted(random.randint(1, len(c) - 1) for _ in range(2))
        if i != j:                          # i = j: žiadny ťah
            D = delta(c, i, j)
            if D <= 0 or random.random() < math.exp(-D / T):
                c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]
                delka += D
                if delka < nej_delka:
                    nej, nej_delka = c, delka
        T *= alfa
    return nej

Ako to vyzerá naozaj: prvých šesť iterácií nášho behu a šesť iterácií z jeho polovice. p je pravdepodobnosť prijatia min(1, exp(−Δ/T)), u vylosované číslo; zhoršujúci ťah prejde, keď u < p. Stĺpce T, Δ a p majú farby podľa vzorca vyššie.

Na začiatku, pri T ≈ 200, prejde aj ťah, ktorý trasu predĺži o 146,6 km — šanca je 0,48 a padlo u = 0,14. V polovici behu je T = 10 a trasa už leží v optime; ťahy, ktoré by ju predĺžili o 70 a viac kilometrov, majú šancu pod jedno promile a všetky sú zamietnuté. Niekedy sa obe náhodné čísla trafia do toho istého miesta (i = j) a iterácia nenavrhne nič — v celom behu sa to stalo 824-krát.

Veta — Boltzmannovo rozdelenie (dnešná formulácia)

Nech S je konečná množina riešení, f : S → ℝ účelová funkcia, N okolie a T > 0 pevná teplota. Nech suseda navrhujeme s pravdepodobnosťami q(s, s′) ≥ 0 (q(s, s′) > 0 len pre s′ ∈ N(s), ∑_s′ q(s, s′) = 1), ktoré sú symetrické:

∀ s, s′ ∈ S : q(s, s′) = q(s′, s)

(pri 2-opt to platí, pretože každú dvojicu (i, j) losujeme s rovnakou pravdepodobnosťou a ten istý ťah (i, j) vedie aj späť). Navrhnutý sused sa prijme s pravdepodobnosťou min(1, exp(−f(s′) − f(s)/T)). Potom je tento Metropolisov proces Markovov reťazec na S a rozdelenie

π_T(s) = exp(−f(s)/T)/Z(T),   Z(T) = ∑_{t ∈ S} exp(−f(t)/T),

π_T(s)

ako často sa po dlhom blúdení pri teplote T ocitneme v riešení s

exp(−f(s)/T)

váha riešenia: čím kratšia trasa f(s), tým väčšia. Je to presne tá váha, ktorú Metropolisovo kritérium vyvažuje — pomer váh dvoch susedov je exp(−Δ/T)

Z(T)

súčet váh cez všetky riešenia; delíme ním, aby pravdepodobnosti dávali dohromady 1

je jeho stacionárne rozdelenie: keď je reťazec v rozdelení π_T, zostane v ňom aj po ďalšom kroku. Ak sa navyše dá cez susedov dostať z každého riešenia do každého, je stacionárne rozdelenie jediné.

Dôkaz (podmienka detailnej rovnováhy). Nech s ≠ s′ a f(s′) = f(s) + Δ s Δ ≥ 0 (inak s a s′ vymeníme). Tok pravdepodobnosti zo s do s′ je π(s) · q(s, s′) · exp(−Δ/T) a tok späť π(s′) · q(s′, s) · 1. Pre π = π_T a symetrické q sa oba výrazy rovnajú q(s, s′) · exp(−f(s′)/T)/Z(T). Toky medzi každou dvojicou riešení sa vyrovnajú, takže sčítaním cez všetky s dostaneme, že pravdepodobnosť každého s′ sa krokom nezmení. ∎

optimum (1 060,4 km) oproti pasci horolezca (1 065,8 km), pomer početností:

π_T(optimum)/π_T(pasca) = exp(5,38/T)

T = 100: 1,06   T = 10: 1,71   T = 1: 217   T = 0,5: 47 089

6. Teplota a rozvrh chladenia

Akú veľkú šancu má krok, ktorý trasu predĺži o Δ = 20 km? Závisí od teploty (farby podľa vzorca pre P(prijať) v predchádzajúcom oddiele):

Pri 200 prejde takmer každý zhoršujúci krok, pri 0,5 žiadny — žíhanie sa v tej chvíli správa ako horolezec. Rozvrh chladenia určuje, ako dlho algoritmus „blúdi“ a ako dlho „zostupuje“. Najlacnejší únik z pasce horolezca (Δ = +19,0 km, pozri vyššie) by pri T = 50 prešiel s pravdepodobnosťou 0,68, pri T = 10 s 0,15 a pri T = 2 prakticky nikdy.

T_k = T₀ · α^k,   α = (T_K/T₀)^1/K

T_k

teplota v k-tej iterácii — určuje, aké veľké zhoršenia sa v tej chvíli ešte prijímajú

T₀

počiatočná teplota; volí sa tak, aby na začiatku prešla väčšina zhoršení — u nás 200 km, viac než typický ťah 2-opt na náhodnej trase

α

koeficient chladenia tesne pod 1; počítame ho z cieľovej teploty T_K a počtu iterácií K, aby beh skončil presne tam, kde chceme

k

číslo iterácie v exponente: každá iterácia teplotu vynásobí rovnakým číslom, takže za rovnaký počet iterácií klesne teplota vždy v rovnakom pomere — z 200 na 100 rovnako dlho ako z 1 na 0,5

Veta — konvergencia žíhania

Nech S je konečná množina riešení, f : S → ℝ účelová funkcia a N okolie, ktoré je symetrické (s′ ∈ N(s) ⇔ s ∈ N(s′)) a súvislé (z každého riešenia sa dá cez susedov dostať do každého). Nech S* ⊆ S je množina globálnych miním a s_k riešenie žíhania po k-tej iterácii. Pre lokálne minimum s ∉ S* definujme jeho hĺbku

h(s) = min { max_{l = 0, …, m} f(t_l) − f(s) : t₀ = s, t_l+1 ∈ N(t_l), f(t_m) < f(s) },

t. j. o koľko najmenej musí cesta po susedoch zo s stúpnuť, kým dôjde do ostro lepšieho riešenia, a nech d* = max h(s) cez všetky lokálne minimá s ∉ S* (ak nie je žiadne, d* = 0). Nech teplota klesá logaritmicky:

T_k = c/ln(k + 1),   k = 1, 2, …,   c > 0.

Potom P(s_k ∈ S*) → 1 pre k → ∞ práve vtedy, keď c ≥ d* (Hajek, 1988).

Slovami: ak sa chladí dosť pomaly, skončí žíhanie s pravdepodobnosťou blízkou jednej v globálnom minime, a „dosť pomaly“ je určené najhlbšou pascou, z ktorej musí algoritmus vedieť vyliezť.

keby stačilo c = 20 km, teplotu 0,5 by sme mali až pri ln(k + 1) = 20/0,5 = 40,

teda po k ≈ e⁴⁰ ≈ 2,4 · 10¹⁷ iteráciách — zhruba miliardkrát viac, než je všetkých 239 500 800 okruhov

7. Žíhanie na krajských mestách

Pustime žíhanie na tú istú úlohu: 10 000 iterácií, teplota klesá geometricky z 200 na 0,5. Mapa ukazuje, ako vyzerala trasa na začiatku a po 1 000, 3 000, 5 000 a 10 000 iteráciách:

Po tisícke iterácií je trasa stále chaotická (1 985 km) — pri vysokej teplote žíhanie prijíma takmer všetko. Po troch tisícoch už má tvar (1 159 km) a po piatich tisícoch je v optime, 1 060,4 km. Z 1 498 prijatých ťahov bolo 695 zhoršujúcich; horolezec by neurobil ani jeden z nich. Graf ukazuje, ako dĺžka trasy skáče hore aj dole, kým teplota neklesne:

Prechod od blúdenia k zostupu je vidieť aj na počte prijatých ťahov v jednotlivých tisíckach iterácií: 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. V prvej tisícke, keď je T medzi 200 a 110, sa prijme viac než polovica návrhov. Od piatej tisícky (T pod 20) už len desiatky; zhoršujúcich medzi nimi bolo 37, z toho 26 drobných, pod 3 km.

A nie je to náhoda jedného behu: zo sto behov s rôznymi semienkami skončilo v optime 98 a zvyšné dva necelé 3 km vedľa. Oproti 61 % horolezca z jedného štartu je to veľký rozdiel.

8. Kedy sa žíhanie oplatí

Férovo povedané: žíhanie robilo 10 000 iterácií, horolezec z jedného štartu len asi šesťsto vyhodnotení. Na malej úlohe by horolezec s reštartmi za rovnakú cenu dopadol rovnako. Rozdiel sa ukáže na väčšej úlohe. Vezmime 60 náhodne rozmiestnených miest a obom algoritmom dajme rovnaký rozpočet — 200 000 vyhodnotených ťahov 2-opt:

Horolezec sa do rozpočtu zmestil len dvakrát: so 60 mestami má okolie 1 711 ťahov a najstrmší zostup ich všetky prezrie v každom kroku. Žíhanie skúša po jednom náhodnom ťahu a rovnaký rozpočet rozloží do prieskumu celej krajiny. Každý z jeho troch behov skončil lepšie než horolezec.

9. Žíhanie v umelej inteligencii a inde

• Návrh čipov a rozvrhy. Rozmiestňovanie súčiastok na čipe bolo jedným z prvých veľkých nasadení žíhania v osemdesiatych rokoch; dodnes sa používa na rozvrhy, trasy vozidiel alebo usporiadanie skladu.
• Učenie neurónových sietí. Stochastický gradientný zostup počíta gradient z malej dávky dát, a tak je každý krok trochu náhodný — podobne ako žíhanie môže vykĺznuť z plytkej jamky. Rozvrhy rýchlosti učenia, ktoré ju postupne znižujú, sa dokonca volajú cosine annealing.
• Teplota jazykových modelov. Keď jazykový model volí ďalšie slovo, delí skóre slov teplotou T a prevedie ich funkciou softmax na pravdepodobnosti úmerné exp(z/T) — tá istá Boltzmannova formula. Vysoká teplota znamená nápaditejší a riskantnejší text, nízka opatrnejší a predvídateľnejší.
• Kvantové žíhanie. Špecializované počítače (napríklad D-Wave) hľadajú minimum energie fyzikálne, s využitím kvantových javov. Či a kedy sú rýchlejšie než klasické algoritmy, je stále predmetom výskumu.

Príklad — teplota pri voľbe ďalšieho slova

Model dá trom kandidátom na ďalšie slovo skóre z = (z₁, z₂, z₃) = (2, 1, 0). Pri teplote T > 0 je pravdepodobnosť i-tého slova (i = 1, 2, 3)

p_i = exp(z_i/T)/∑_j=1³ exp(z_j/T)

p_i

pravdepodobnosť, že model zvolí i-té slovo

exp(z_i/T)

váha slova — Boltzmannova váha z oddielu o žíhaní, len s „energiou“ −z_i: vyššie skóre, väčšia váha

∑_j exp(z_j/T)

súčet váh všetkých kandidátov; delíme ním, aby pravdepodobnosti dávali dohromady 1

T = 1:   váhy (e², e¹, e⁰) = (7,39; 2,72; 1), súčet 11,11 → 0,665; 0,245; 0,090

T = 0,5:   váhy (e⁴, e², 1) = (54,6; 7,39; 1), súčet 62,99 → 0,867; 0,117; 0,016

T = 2:   váhy (e¹, e^0,5, 1) = (2,72; 1,65; 1), súčet 5,37 → 0,506; 0,307; 0,186

napríklad pri T = 1: p₁ = 7,39/11,11 = 0,665

Nižšia teplota presúva pravdepodobnosť k najlepšiemu kandidátovi (pri T → 0 je to vždy on), vyššia ju rozlieva aj na menej pravdepodobné slová — rovnako ako žíhanie pri vysokej teplote prijíma aj horšie trasy.

10. Zhrnutie

• Optimalizačná úloha hľadá riešenie s najlepšou hodnotou účelovej funkcie; lokálne hľadanie sa pohybuje po okolí aktuálneho riešenia.
• Horolezec ide vždy k lepšiemu susedovi a uviazne v lokálnom minime — na krajských mestách v 39 zo 100 štartov. Náhodné reštarty pomáhajú pri malých úlohách.
• Simulované žíhanie prijíma aj horšie kroky s pravdepodobnosťou exp(−Δ/T); s klesajúcou teplotou prechádza od prieskumu k zostupu.
• Na krajských mestách našlo optimum v 98 zo 100 behov; na väčšej úlohe porazilo horolezca s rovnakým rozpočtom.
• Tá istá Boltzmannova formula žije v teplote jazykových modelov a myšlienka chladenia v rozvrhoch učenia neurónových sietí.

Chcete si to vyskúšať? Nechajte AI agenta napísať žíhanie pre vašu vlastnú trasu — napríklad cez miesta, kam chcete ísť cez prázdniny — a skúste, čo urobí príliš rýchle chladenie.

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