Lokální hledání a simulované žíhání: obchodní cestující přes krajská města

Optimalizační úloha, problém obchodního cestujícího, horolezec s okolím 2-opt, lokální minima a restarty, simulované žíhání, teplota a rozvrh chlazení — na trase přes třináct krajských měst se známým optimem.

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

Série Základy AI Díl 26 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

Kovář, který chce pevnou čepel, nenechá rozžhavený kov prudce vychladnout — ochlazuje ho pomalu. Atomy tak mají čas najít pravidelné uspořádání s nejnižší energií. Kdyby kov zchladil naráz, atomy by zamrzly tam, kde zrovna byly, a čepel by byla křehká. V roce 1983 si fyzici všimli, že přesně tohle trápí i algoritmy, které hledají nejlepší řešení: když jdou jen „z kopce“, zamrznou v prvním dolíku. Tak vzniklo simulované žíhání — a s ním jedna z nejužitečnějších myšlenek optimalizace.

Tímhle dílem začíná modul o algoritmech inspirovaných přírodou. Navazuje na díl Prohledávání stavového prostoru, kde se horolezec a žíhání objevili poprvé.

1. Optimalizační úloha

Definice — optimalizační úloha a okolí

Nechť S je neprázdná množina, jejíž prvky nazýváme přípustná řešení, a f : S → ℝ je funkce, kterou nazýváme účelová funkce. Optimalizační (minimalizační) úloha (S, f) je úloha najít prvek s* ∈ S, pro který platí

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

Takový prvek s* nazýváme globální minimum. Je-li S konečná, globální minimum existuje (může jich být i víc). U maximalizační úlohy se nerovnosti obrátí; maximalizovat f je totéž jako minimalizovat −f.

Označme 2^S množinu všech podmnožin S. Okolí je zobrazení N : S → 2^S, které každému řešení s ∈ S přiřadí množinu N(s) ⊆ S jeho sousedů; v praxi jsou to řešení, která ze s vzniknou jednou malou změnou předepsaného typu. Řešení s ∈ S je lokální minimum vzhledem k okolí N, právě když

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

Globální minimum je tedy řešení, které nemá lepší řešení nikde v S, kdežto lokální minimum jen takové, které nemá lepší řešení mezi svými sousedy. Každé globální minimum je i lokální, naopak to neplatí.

2. Problém obchodního cestujícího

Obchodní cestující má objet všech třináct krajských měst Česka, v každém být jednou a vrátit se, odkud vyjel. Kterou trasou ujede nejméně? Vzdálenosti počítáme vzdušnou čarou.

Definice — problém obchodního cestujícího (TSP)

Nechť n ≥ 3 je počet měst, města jsou očíslována 1, …, n, a nechť d : {1, …, n} × {1, …, n} → ℝ je funkce vzdáleností, kde d(i, j) ≥ 0 je vzdálenost města i od města j. V tomto díle je d navíc symetrická: d(i, j) = d(j, i) pro všechna i, j.

Přípustné řešení (okruh) je permutace π = (π₁, …, π_n) množiny {1, …, n} — pořadí, ve kterém města projedeme, a z posledního se vrátíme do prvního. Účelová funkce je délka okruhu

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

Problém obchodního cestujícího je optimalizační úloha najít permutaci π s nejmenší délkou f(π).

Permutace, které se liší jen tím, ve kterém městě začínají (cyklickým posunutím), nebo směrem průjezdu, mají stejnou délku a popisují tentýž okruh. Různých okruhů je proto n!/2n = (n − 1)!/2 (rozbor níže). Rozhodovací verze úlohy („existuje okruh délky nejvýš L?“) je NP-úplná.

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

n!

všechna pořadí, ve kterých lze n měst vypsat — tolik je permutací; každý okruh je ale mezi nimi započítaný víckrát

n

okruh nemá začátek: Praha → Brno → … → Praha je tatáž cesta jako Brno → … → Praha → Brno. Každý okruh lze začít v kterémkoli z n měst, proto n-krát méně

2

vzdálenost tam je stejná jako zpět, takže okruh projetý obráceně je tatáž cesta stejné délky

Příklad — vzdálenost vzdušnou čarou z Prahy do Brna

Města máme dána zeměpisnou šířkou φ a délkou λ ve stupních. Na území Česka stačí rovinná přibližná projekce: stupeň šířky má 110,57 km, stupeň délky 111,32 · cos φ₀ km, kde φ₀ = 49,8° je střed republiky (poledníky se k pólu sbíhají). Pak

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 jih

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

Chyba proti přesnému výpočtu na kouli je u takových vzdáleností kolem 1 %; pro porovnávání tras to nevadí.

Třináct měst je ještě dost málo na to, abychom optimum spočítali přesně — Heldovým–Karpovým dynamickým programováním přes podmnožiny měst, které trvá 2ⁿ · n² kroků místo (n − 1)!. Nejkratší okruh měří 1 060,4 km. Díky tomu u každého dalšího algoritmu přesně uvidíme, jak blízko se k optimu dostal:

Algoritmus — Heldovo–Karpovo dynamické programování (1962)

Vstup: počet měst n ≥ 3, města očíslovaná 0, …, n − 1, a vzdálenosti d : {0, …, n − 1}² → ℝ, d ≥ 0. Výstup: délka nejkratšího okruhu (problém obchodního cestujícího výše); okruh sám se zjistí zpětným sledováním, ve kterém k se minimum nabylo.

Okruh nemá začátek, proto bez újmy na obecnosti začíná v městě 0. Pro každou množinu měst M ⊆ {0, …, n − 1} s 0 ∈ M a každé město j ∈ M označme D(M, j) délku nejkratší cesty, která vyjede z města 0, projede každé město z M právě jednou, žádné jiné, a skončí v j. Pro M ≠ {0} klademe D(M, 0) = ∞ (cesta se do 0 nesmí vrátit předčasně).

1. Polož D({0}, 0) = 0.
2. Pro m = 2, …, n postupně: pro každou M ∋ 0 s |M| = m a každé j ∈ M ∖ {0} spočítej D(M, j) = min_{k ∈ M ∖ {j}} [ D(M ∖ {j}, k) + d(k, j) ]. Všechny hodnoty vpravo mají množinu o prvek menší, takže už jsou spočítané.
3. Po dokončení m = n skonči a vrať min_{j ∈ {1, …, n − 1}} [ D({0, …, n − 1}, j) + d(j, 0) ].

Algoritmus tedy vždy skončí po konečném počtu kroků: hodnot D je nejvýš 2ⁿ · n a každá je minimum z nejvýš n čísel.

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

projít všechna pořadí z pevného startu: 12! = 479 001 600 — asi 346krát víc

3. Horolezec a okolí 2-opt

Definice — tah 2-opt

Nechť n ≥ 4, d je symetrická vzdálenost z definice TSP a c = (c₀, c₁, …, c_n−1) je okruh přes n měst (po c_n−1 následuje znovu c₀). Nechť i, j jsou indexy, 1 ≤ i < j ≤ n − 1. Tah 2-opt (i, j) přiřadí okruhu c okruh

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

tj. obrátí pořadí úseku c_i, …, c_j. Označme a = c_i−1, b = c_i, e = c_j a f = c_{(j+1) mod n} (zde f značí město, ne účelovou funkci). Tah z okruhu odebere hrany (a, b) a (e, f) a přidá hrany (a, e) a (b, f); ostatní hrany zůstanou, jen úsek mezi b a e se projede obráceně. Délka okruhu se proto změní o

Δ = délka(c′) − délka(c) = d(a, e) + d(b, f) − d(a, b) − d(e, f).

Okolí 2-opt N(c) je množina všech okruhů, které z c vzniknou jedním tahem (i, j); dvojic (i, j) je (n − 1)(n − 2)/2.

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

Δ

o kolik se okruh prodlouží; záporné Δ znamená zkrácení. Podle znaménka se horolezec i žíhání rozhodují, proto ho potřebujeme levně

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

dvě nové hrany, kterými přestřižené konce znovu spojíme — přičítají se, protože o ně trasa přibude

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

dvě hrany, které jsme přestřihli — odečítají se, protože z trasy zmizí. Úsek mezi b a e jen projedeme obráceně a vzdálenosti jsou symetrické, takže se jeho délka nezmění a ve vzorci chybí

Algoritmus — horolezec (nejstrmější sestup)

Vstup: optimalizační úloha (S, f) s konečnou množinou S, okolí N : S → 2^S s neprázdnými množinami N(s) a počáteční (náhodné) řešení s₀ ∈ S. Výstup: lokální minimum s ∈ S vzhledem k N.

1. Polož s ← s₀.
2. Najdi nejlepšího souseda s′ ∈ argmin_{t ∈ N(s)} f(t) (při shodě libovolného z nich).
3. Je-li f(s′) < f(s), polož s ← s′ a pokračuj krokem 2.
4. Jinak (f(s′) ≥ f(s)) skonči a vrať s.

Podmínka zastavení je v kroku 4: žádný soused není ostře lepší, tedy f(s) ≤ f(t) pro všechna t ∈ N(s) a s je lokální minimum. Protože f(s) v každém přechodu ostře klesne, žádné řešení se nezopakuje, a na konečné S proto algoritmus vždy skončí.

def delta(c, i, j):                    # tah 2-opt: obrať 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))   # nejstrmější sestup
        if delta(c, i, j) >= 0:                        # nic trasu nezkrátí
            return c                                    # lokální minimum
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

První město necháváme na místě (i ≥ 1) — okruh nemá začátek, takže by to nic nového nepřineslo. Pro n = 13 dávají dvojice 1 ≤ i < j ≤ 12 právě 12 · 11/2 = 66 tahů.

Z náhodného okruhu dlouhého 2 402 km dojde horolezec za 8 kroků na 1 065,8 km — a tam se zastaví. Do optima chybí jen 5 km, ale žádný jednotlivý tah 2-opt už trasu nezkrátí. Horolezec je v lokálním minimu a neví o tom:

4. Kde horolezec uvízne

Ze sta náhodných startů skončil horolezec v optimu 61krát. Ve zbylých 39 případech uvízl jinde, v nejhorším na 1 162,6 km — o sto kilometrů dál. Pasti jsou tři:

• Lokální minimum — dolík, ze kterého vede každý krok nahoru.
• Plošina — všichni sousedé jsou stejně dobří, takže horolezec neví, kam jít.
• Hřbet — dobrý směr existuje, ale nevede po žádném jednotlivém tahu; jde se k němu jen přes horší řešení.

Příklad — proč horolezec z 1 065,8 km nevyjde

Horolezec z prvního startu 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. Spočítáme Δ všech 66 tahů 2-opt: jeden z nich (obrácení všeho kromě prvního města) dá tentýž okruh opačným směrem a Δ = 0, všechny ostatní trasu prodlouží. Nejlevnější z nich obrátí dvojici 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

(Barvy podle rozboru tahu 2-opt výše.)

Každý jednotlivý tah tedy trasu prodlouží nejméně o 19,0 km — přitom optimum je o pouhých 5,4 km kratší. Cesta k němu vede přes horší okruhy, a ty horolezec nikdy nepřijme.

Nejjednodušší lék jsou náhodné restarty: pustit horolezce znovu z jiného místa a nechat si nejlepší výsledek. Uspěje-li jeden start s pravděpodobností 0,61, pak z pěti startů aspoň jeden uspěje s pravděpodobností P₅ = 1 − 0,39⁵ ≈ 99 % (barvy podle vzorce níže). U malé úlohy to stačí. U velké jsou dolíků miliony a restartů by bylo potřeba příliš mnoho.

P_r = 1 − (1 − p)^r

P_r

pravděpodobnost, že aspoň jeden z r startů najde optimum — počítáme ji přes doplněk, protože „aspoň jeden“ má mnoho podob, kdežto „ani jeden“ jen jednu

1 − p

pravděpodobnost, že jeden start selže (u nás 0,39 ze sta pokusů)

r

počet startů v exponentu: starty jsou nezávislé (každý má jiné náhodné semínko), takže pravděpodobnosti selhání se násobí

5. Simulované žíhání

Algoritmus — simulované žíhání

Vstup: optimalizační úloha (S, f), okolí N : S → 2^S s neprázdnými konečnými množinami N(s), počáteční (náhodné) řešení s₀ ∈ S, počáteční teplota T₀ > 0, koeficient chlazení α ∈ (0, 1) a počet iterací K ∈ ℕ. Výstup: nejlepší řešení s_nej ∈ S, které algoritmus během běhu navštívil.

1. Polož s ← s₀, s_nej ← s₀, T ← T₀.
2. Pro k = 1, …, K opakuj:
   1. vyber náhodně (rovnoměrně) souseda s′ ∈ N(s) a spočítej Δ = f(s′) − f(s);
   2. je-li Δ ≤ 0, polož s ← s′; jinak vylosuj u rovnoměrně z [0, 1) a je-li u < exp(−Δ/T), polož s ← s′ (Metropolisovo kritérium: horší soused se přijme s pravděpodobností exp(−Δ/T));
   3. je-li f(s) < f(s_nej), polož s_nej ← s;
   4. sniž teplotu podle rozvrhu chlazení, zde geometrického: T ← α · T.
3. Po K iteracích skonči a vrať s_nej.

Algoritmus se tedy zastaví vždy po předem daném počtu K iterací; jiné rozvrhy chlazení než geometrický viz oddíl o teplotě.

P(přijmout) = min(1, exp(−Δ/T))

P(přijmout)

s jakou pravděpodobností přejdeme do navrženého souseda; v programu losujeme u rovnoměrně z [0, 1) a tah přijmeme, když u < P

min(1, …)

pro zlepšení (Δ ≤ 0) je exponenciála ≥ 1 a pravděpodobnost nesmí přesáhnout 1 — lepší krok se tedy přijme vždy, stejně jako u horolezce

Δ

o kolik je soused horší, v km. Stojí v exponentu se záporným znaménkem, takže každý další kilometr zhoršení šanci vynásobí stejným číslem menším než 1 — velká zhoršení jsou exponenciálně vzácnější než malá

T

teplota, ve stejných jednotkách jako Δ (km). Dělí Δ, a tím určuje měřítko: zhoršení o T km projde s pravděpodobností exp(−1) = 1/e ≈ 0,37 při jakékoli teplotě. Vysoké T dělá velká zhoršení „malými“, T → 0 zakáže všechna

Pravidlo pro přijetí horšího kroku pochází z fyziky: v roce 1953 ho Nicholas Metropolis a jeho kolegové použili k simulaci atomů v tepelné rovnováze, kde pravděpodobnost stavu s energií E je úměrná exp(−E/kT). Pro optimalizaci ho v roce 1983 nezávisle přizpůsobili Kirkpatrick, Gelatt a Vecchi z IBM — a dva roky nato, rovněž nezávisle, slovenský fyzik Vladimír Černý, právě na problému obchodního cestujícího.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # geometrické chlazení
    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: žádný tah
            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

Jak to vypadá doopravdy: prvních šest iterací našeho běhu a šest iterací z jeho poloviny. p je pravděpodobnost přijetí min(1, exp(−Δ/T)), u vylosované číslo; zhoršující tah projde, když u < p. Sloupce T, Δ a p mají barvy podle vzorce výše.

Na začátku, při T ≈ 200, projde i tah, který trasu prodlouží o 146,6 km — šance je 0,48 a padlo u = 0,14. V polovině běhu je T = 10 a trasa už leží v optimu; tahy, které by ji prodloužily o 70 a víc kilometrů, mají šanci pod jedno promile a všechny jsou zamítnuty. Někdy se obě náhodná čísla trefí do téhož místa (i = j) a iterace nenavrhne nic — v celém běhu se to stalo 824krát.

Věta — Boltzmannovo rozdělení (dnešní formulace)

Nechť S je konečná množina řešení, f : S → ℝ účelová funkce, N okolí a T > 0 pevná teplota. Nechť souseda navrhujeme s pravděpodobnostmi q(s, s′) ≥ 0 (q(s, s′) > 0 jen pro s′ ∈ N(s), ∑_s′ q(s, s′) = 1), které jsou symetrické:

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

(u 2-opt to platí, protože každou dvojici (i, j) losujeme se stejnou pravděpodobností a týž tah (i, j) vede i zpět). Navržený soused se přijme s pravděpodobností min(1, exp(−f(s′) − f(s)/T)). Pak je tento Metropolisův proces Markovův řetězec na S a rozdělení

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

π_T(s)

jak často se po dlouhém bloudění při teplotě T ocitneme v řešení s

exp(−f(s)/T)

váha řešení: čím kratší trasa f(s), tím větší. Je to přesně ta váha, kterou Metropolisovo kritérium vyvažuje — poměr vah dvou sousedů je exp(−Δ/T)

Z(T)

součet vah přes všechna řešení; dělíme jím, aby pravděpodobnosti dávaly dohromady 1

je jeho stacionární rozdělení: když je řetězec v rozdělení π_T, zůstane v něm i po dalším kroku. Lze-li se navíc přes sousedy dostat z každého řešení do každého, je stacionární rozdělení jediné.

Důkaz (podmínka detailní rovnováhy). Nechť s ≠ s′ a f(s′) = f(s) + Δ s Δ ≥ 0 (jinak s a s′ prohodíme). Tok pravděpodobnosti ze s do s′ je π(s) · q(s, s′) · exp(−Δ/T) a tok zpět π(s′) · q(s′, s) · 1. Pro π = π_T a symetrické q jsou oba výrazy rovny q(s, s′) · exp(−f(s′)/T)/Z(T). Toky mezi každou dvojicí řešení se vyrovnají, takže sečtením přes všechna s dostaneme, že pravděpodobnost každého s′ se krokem nezmění. ∎

optimum (1 060,4 km) proti pasti horolezce (1 065,8 km), poměr četností:

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

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

6. Teplota a rozvrh chlazení

Jak velkou šanci má krok, který trasu prodlouží o Δ = 20 km? Záleží na teplotě (barvy podle vzorce pro P(přijmout) v předchozím oddílu):

Při 200 projde skoro každý zhoršující krok, při 0,5 žádný — žíhání se v tu chvíli chová jako horolezec. Rozvrh chlazení určuje, jak dlouho algoritmus „bloudí“ a jak dlouho „sestupuje“. Nejlevnější únik z pasti horolezce (Δ = +19,0 km, viz výše) by při T = 50 prošel s pravděpodobností 0,68, při T = 10 s 0,15 a při T = 2 prakticky nikdy.

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

T_k

teplota v k-té iteraci — určuje, jak velká zhoršení se v tu chvíli ještě přijímají

T₀

počáteční teplota; volí se tak, aby na začátku prošla většina zhoršení — u nás 200 km, víc než typický tah 2-opt na náhodné trase

α

koeficient chlazení těsně pod 1; počítáme ho z cílové teploty T_K a počtu iterací K, aby běh skončil přesně tam, kde chceme

k

číslo iterace v exponentu: každá iterace teplotu vynásobí stejným číslem, takže za stejný počet iterací klesne teplota vždy stejným poměrem — od 200 k 100 stejně dlouho jako od 1 k 0,5

Věta — konvergence žíhání

Nechť S je konečná množina řešení, f : S → ℝ účelová funkce a N okolí, které je symetrické (s′ ∈ N(s) ⇔ s ∈ N(s′)) a souvislé (z každého řešení se lze přes sousedy dostat do každého). Nechť S* ⊆ S je množina globálních minim a s_k řešení žíhání po k-té iteraci. Pro lokální minimum s ∉ S* definujme jeho hloubku

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) },

tj. o kolik nejméně musí cesta po sousedech ze s stoupnout, než dojde do ostře lepšího řešení, a nechť d* = max h(s) přes všechna lokální minima s ∉ S* (není-li žádné, d* = 0). Nechť teplota klesá logaritmicky:

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

Pak P(s_k ∈ S*) → 1 pro k → ∞, právě když c ≥ d* (Hajek, 1988).

Slovy: chladí-li se dost pomalu, skončí žíhání s pravděpodobností blízkou jedné v globálním minimu, a „dost pomalu“ je určeno nejhlubší pastí, ze které musí algoritmus umět vylézt.

kdyby stačilo c = 20 km, teplotu 0,5 bychom měli až při ln(k + 1) = 20/0,5 = 40,

tedy po k ≈ e⁴⁰ ≈ 2,4 · 10¹⁷ iteracích — zhruba miliardkrát víc, než je všech 239 500 800 okruhů

7. Žíhání na krajských městech

Pusťme žíhání na stejnou úlohu: 10 000 iterací, teplota klesá geometricky z 200 na 0,5. Mapa ukazuje, jak vypadala trasa na začátku a po 1 000, 3 000, 5 000 a 10 000 iteracích:

Po tisíci iteracích je trasa pořád chaotická (1 985 km) — při vysoké teplotě žíhání přijímá skoro všechno. Po třech tisících už má tvar (1 159 km) a po pěti tisících je v optimu, 1 060,4 km. Z 1 498 přijatých tahů bylo 695 zhoršujících; horolezec by neudělal ani jeden z nich. Graf ukazuje, jak délka trasy skáče nahoru i dolů, dokud teplota neklesne:

Přechod od bloudění k sestupu je vidět i na počtu přijatých tahů v jednotlivých tisícovkách iterací: 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. V první tisícovce, kdy je T mezi 200 a 110, se přijme víc než polovina návrhů. Od páté tisícovky (T pod 20) už jen desítky; zhoršujících mezi nimi bylo 37, z toho 26 drobných, pod 3 km.

A není to náhoda jednoho běhu: ze sta běhů s různými semínky skončilo v optimu 98 a zbylé dva o necelé 3 km vedle. Proti 61 % horolezce z jednoho startu je to velký rozdíl.

8. Kdy se žíhání vyplatí

Férově vzato: žíhání dělalo 10 000 iterací, horolezec z jednoho startu jen asi šest set vyhodnocení. Na malé úloze by horolezec s restarty za stejnou cenu dopadl stejně. Rozdíl se ukáže na větší úloze. Vezměme 60 náhodně rozmístěných měst a oběma algoritmům dejme stejný rozpočet — 200 000 vyhodnocených tahů 2-opt:

Horolezec se do rozpočtu vešel jen dvakrát: s 60 městy má okolí 1 711 tahů a nejstrmější sestup je všechny prohlédne v každém kroku. Žíhání zkouší po jednom náhodném tahu a stejný rozpočet rozprostře do průzkumu celé krajiny. Každý z jeho tří běhů skončil lépe než horolezec.

9. Žíhání v umělé inteligenci a jinde

• Návrh čipů a rozvrhy. Rozmisťování součástek na čipu bylo jedním z prvních velkých nasazení žíhání v osmdesátých letech; dodnes se používá na rozvrhy, trasy vozidel nebo uspořádání skladu.
• Učení neuronových sítí. Stochastický gradientní sestup počítá gradient z malé dávky dat, a tak je každý krok trochu náhodný — podobně jako žíhání může vyklouznout z mělkého dolíku. Rozvrhy rychlosti učení, které ji postupně snižují, se dokonce jmenují cosine annealing.
• Teplota jazykových modelů. Když jazykový model volí další slovo, dělí skóre slov teplotou T a převede je funkcí softmax na pravděpodobnosti úměrné exp(z/T) — tatáž Boltzmannova formule. Vysoká teplota znamená nápaditější a riskantnější text, nízká opatrnější a předvídatelnější.
• Kvantové žíhání. Specializované počítače (například D-Wave) hledají minimum energie fyzikálně, s využitím kvantových jevů. Zda a kdy jsou rychlejší než klasické algoritmy, je pořád předmětem výzkumu.

Příklad — teplota při volbě dalšího slova

Model dá třem kandidátům na další slovo skóre z = (z₁, z₂, z₃) = (2, 1, 0). Při teplotě T > 0 je pravděpodobnost i-tého slova (i = 1, 2, 3)

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

p_i

pravděpodobnost, že model zvolí i-té slovo

exp(z_i/T)

váha slova — Boltzmannova váha z oddílu o žíhání, jen s „energií“ −z_i: vyšší skóre, větší váha

∑_j exp(z_j/T)

součet vah všech kandidátů; dělíme jím, aby pravděpodobnosti dávaly dohromady 1

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

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

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

například při T = 1: p₁ = 7,39/11,11 = 0,665

Nižší teplota přesouvá pravděpodobnost k nejlepšímu kandidátovi (při T → 0 je to vždy on), vyšší ji rozlévá i na méně pravděpodobná slova — stejně jako žíhání při vysoké teplotě přijímá i horší trasy.

10. Shrnutí

• Optimalizační úloha hledá řešení s nejlepší hodnotou účelové funkce; lokální hledání se pohybuje po okolí aktuálního řešení.
• Horolezec jde vždy k lepšímu sousedovi a uvízne v lokálním minimu — na krajských městech v 39 ze 100 startů. Náhodné restarty pomáhají u malých úloh.
• Simulované žíhání přijímá i horší kroky s pravděpodobností exp(−Δ/T); s klesající teplotou přechází od průzkumu k sestupu.
• Na krajských městech našlo optimum v 98 ze 100 běhů; na větší úloze porazilo horolezce se stejným rozpočtem.
• Stejná Boltzmannova formule žije v teplotě jazykových modelů a myšlenka chlazení v rozvrzích učení neuronových sítí.

Chcete si to osahat? Nechte AI agenta napsat žíhání pro vaši vlastní trasu — třeba přes místa, kam chcete o prázdninách — a zkuste, co udělá příliš rychlé chlazení.

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