Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie

Problem optymalizacyjny, problem komiwojażera, algorytm wspinaczkowy z sąsiedztwem 2-opt, minima lokalne i restarty, symulowane wyżarzanie, temperatura i schemat chłodzenia — na trasie przez trzynaście czeskich miast wojewódzkich o znanym optimum.

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

Seria Podstawy AI Część 26 z 52

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

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

Kowal, który chce mocnego ostrza, nie pozwoli rozżarzonemu metalowi gwałtownie ostygnąć — schładza go powoli. Atomy mają wtedy czas znaleźć regularne ułożenie o najniższej energii. Gdyby schłodził metal od razu, atomy zamarzłyby tam, gdzie akurat były, a ostrze byłoby kruche. W 1983 roku fizycy zauważyli, że dokładnie to samo dręczy algorytmy szukające najlepszego rozwiązania: gdy idą tylko „z górki”, zamarzają w pierwszym dołku. Tak powstało symulowane wyżarzanie — a wraz z nim jedna z najużyteczniejszych idei optymalizacji.

Tą częścią zaczyna się moduł o algorytmach inspirowanych przyrodą. Nawiązuje do części Przeszukiwanie przestrzeni stanów, w której wspinacz i wyżarzanie pojawiły się po raz pierwszy.

1. Problem optymalizacyjny

Definicja — problem optymalizacyjny i sąsiedztwo

Dany jest zbiór rozwiązań dopuszczalnych S i funkcja celu f : S → ℝ. Szukamy s* = argmin_{s ∈ S} f(s) — rozwiązania o najmniejszej wartości (przy maksymalizacji odwrotnie).

Sąsiedztwo to odwzorowanie N : S → 2^S, które każdemu rozwiązaniu przypisuje zbiór „sąsiednich” rozwiązań, powstających z niego przez małą zmianę. Rozwiązanie s jest minimum lokalnym, jeśli f(s) ≤ f(s′) dla wszystkich s′ ∈ N(s), i minimum globalnym, jeśli zachodzi to dla wszystkich s′ ∈ S.

2. Problem komiwojażera

Komiwojażer ma objechać wszystkie trzynaście czeskich miast wojewódzkich (stolic krajów), w każdym być raz i wrócić tam, skąd wyruszył. Którą trasą przejedzie najmniej? Odległości liczymy w linii prostej.

Definicja — problem komiwojażera (TSP)

Danych jest n miast i odległości d(i, j). Rozwiązaniem jest cykliczna permutacja π miast; jej długość to f(π) = ∑_k=1ⁿ d(π_k, π_k+1), gdzie π_n+1 = π₁.

Różnych tras okrężnych (bez względu na to, gdzie i w którym kierunku się zaczynają) jest (n − 1)! / 2. Decyzyjna wersja problemu jest NP-zupełna.

liczba cykli = n! / (n · 2) = (n − 1)! / 2

n!

wszystkie kolejności, w jakich można wypisać n miast — tyle jest permutacji; każdy cykl jest jednak wśród nich policzony wielokrotnie

n

cykl nie ma początku: Praha → Brno → … → Praha to ta sama trasa co Brno → … → Praha → Brno. Każdy cykl można zacząć w dowolnym z n miast, dlatego n razy mniej

2

odległość tam jest taka sama jak z powrotem, więc cykl przejechany w odwrotną stronę to ta sama trasa o tej samej długości

Przykład — odległość w linii prostej z Pragi do Brna

Miasta mamy dane szerokością geograficzną φ i długością λ w stopniach. Na terytorium Czech wystarczy przybliżone rzutowanie na płaszczyznę: stopień szerokości ma 110,57 km, stopień długości 111,32 · cos φ₀ km, gdzie φ₀ = 49,8° to środek kraju (południki zbiegają się ku biegunowi). Wtedy

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

Praha (50,08° N, 14,42° E), Brno (49,20°, 16,61°)

Δλ = 2,19° → 71,85 · 2,19 = 157,35 km na wschód

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

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

Błąd względem dokładnego obliczenia na kuli wynosi przy takich odległościach około 1 %; do porównywania tras to nie przeszkadza.

Trzynaście miast to jeszcze na tyle mało, że optimum możemy policzyć dokładnie — programowaniem dynamicznym Helda–Karpa po podzbiorach miast, które zajmuje 2ⁿ · n² kroków zamiast (n − 1)!. Najkrótszy cykl ma 1 060,4 km. Dzięki temu przy każdym kolejnym algorytmie zobaczymy dokładnie, jak blisko optimum się dostał:

Algorytm — programowanie dynamiczne Helda–Karpa (1962)

Ponumerujmy miasta 0, …, n − 1 i zacznijmy w mieście 0. Dla każdego zbioru miast M ∋ 0 i miasta j ∈ M oznaczmy przez D(M, j) długość najkrótszej drogi, która wyrusza z 0, przejeżdża dokładnie przez miasta z M i kończy się w j. Wtedy

D({0}, 0) = 0,   D(M, j) = min_{k ∈ M ∖ {j}} [ D(M ∖ {j}, k) + d(k, j) ],

a długość optymalnego cyklu to min_{j ≠ 0} [ D(wszystkie miasta, j) + d(j, 0) ]. Wartości D jest co najwyżej 2ⁿ · n i każda jest minimum z co najwyżej n liczb.

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

przejrzenie wszystkich kolejności ze stałego startu: 12! = 479 001 600 — około 346 razy więcej

3. Algorytm wspinaczkowy i sąsiedztwo 2-opt

Definicja — ruch 2-opt

Ruch 2-opt usuwa z cyklu dwie niesąsiadujące krawędzie (a, b) i (e, f) i zastępuje je krawędziami (a, e) i (b, f) — czyli odwraca kolejność miast między b a e. Długość zmienia się o Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f). Sąsiedztwo trasy przez n miast ma (n − 1)(n − 2) / 2 ruchów.

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

Δ

o ile cykl się wydłuży; ujemne Δ oznacza skrócenie. Według znaku decydują zarówno wspinacz, jak i wyżarzanie, dlatego potrzebujemy go tanio

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

dwie nowe krawędzie, którymi z powrotem łączymy przecięte końce — dodają się, bo o nie trasa przybywa

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

dwie krawędzie, które przecięliśmy — odejmują się, bo z trasy znikają. Odcinek między b a e tylko przejeżdżamy w odwrotną stronę, a odległości są symetryczne, więc jego długość się nie zmienia i we wzorze go nie ma

Algorytm — algorytm wspinaczkowy (najszybszy spadek)

Zacznij od losowego rozwiązania s. Powtarzaj: znajdź s′ ∈ N(s) o najmniejszej f(s′); jeśli f(s′) < f(s), przejdź do s′, w przeciwnym razie zakończ — s jest minimum lokalnym.

def delta(c, i, j):                    # ruch 2-opt: odwróć 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))   # najszybszy spadek
        if delta(c, i, j) >= 0:                        # nic nie skraca trasy
            return c                                    # minimum lokalne
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

Pierwsze miasto zostawiamy na miejscu (i ≥ 1) — cykl nie ma początku, więc nic nowego by to nie wniosło. Dla n = 13 pary 1 ≤ i < j ≤ 12 dają dokładnie 12 · 11 / 2 = 66 ruchów.

Z losowego cyklu o długości 2 402 km wspinacz dochodzi w 8 krokach do 1 065,8 km — i tam się zatrzymuje. Do optimum brakuje tylko 5 km, ale żaden pojedynczy ruch 2-opt nie skraca już trasy. Wspinacz jest w minimum lokalnym i nic o tym nie wie:

4. Gdzie wspinacz utyka

Ze stu losowych startów wspinacz skończył w optimum 61 razy. W pozostałych 39 przypadkach utknął gdzie indziej, w najgorszym na 1 162,6 km — o sto kilometrów dalej. Pułapki są trzy:

• Minimum lokalne — dołek, z którego każdy krok prowadzi w górę.
• Płaskowyż — wszyscy sąsiedzi są równie dobrzy, więc wspinacz nie wie, dokąd iść.
• Grzbiet — dobry kierunek istnieje, ale nie prowadzi wzdłuż żadnego pojedynczego ruchu; dojść do niego można tylko przez gorsze rozwiązania.

Przykład — dlaczego wspinacz nie wydostanie się z 1 065,8 km

Wspinacz z pierwszego startu skończył na cyklu Zlín → Ostrava → Olomouc → Pardubice → Hradec Králové → Liberec → Ústí nad Labem → Karlovy Vary → Plzeň → Praha → České Budějovice → Jihlava → Brno → Zlín. Policzmy Δ wszystkich 66 ruchów 2-opt: jeden z nich (odwrócenie wszystkiego oprócz pierwszego miasta) daje ten sam cykl w przeciwnym kierunku i Δ = 0, wszystkie pozostałe trasę wydłużają. Najtańszy z nich odwraca parę 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

Każdy pojedynczy ruch wydłuża więc trasę co najmniej o 19,0 km — a przecież optimum jest krótsze o zaledwie 5,4 km. Droga do niego prowadzi przez gorsze cykle, a tych wspinacz nigdy nie przyjmie.

Najprostszym lekarstwem są losowe restarty: wypuścić wspinacza ponownie z innego miejsca i zachować najlepszy wynik. Jeśli jeden start udaje się z prawdopodobieństwem 0,61, to z pięciu startów co najmniej jeden się uda z prawdopodobieństwem 1 − 0,39⁵ ≈ 99 %. Przy małym problemie to wystarcza. Przy dużym dołków są miliony i restartów trzeba by było za dużo.

P_r = 1 − (1 − p)^r

P_r

prawdopodobieństwo, że co najmniej jeden z r startów znajdzie optimum — liczymy je przez dopełnienie, bo „co najmniej jeden” ma wiele postaci, a „ani jeden” tylko jedną

1 − p

prawdopodobieństwo, że jeden start się nie uda (u nas 0,39 ze stu prób)

r

liczba startów w wykładniku: starty są niezależne (każdy ma inne losowe ziarno), więc prawdopodobieństwa porażki się mnożą

5. Symulowane wyżarzanie

Algorytm — symulowane wyżarzanie

Zacznij od losowego rozwiązania s z temperaturą początkową T₀. W każdej iteracji:

1. wybierz losowego sąsiada s′ ∈ N(s) i oblicz Δ = f(s′) − f(s);
2. jeśli Δ ≤ 0, przejdź do s′; w przeciwnym razie przejdź do niego z prawdopodobieństwem e^−Δ/T (kryterium Metropolisa);
3. obniż temperaturę według schematu chłodzenia, na przykład T ← α · T dla 0 < α < 1.

Zwróć najlepsze rozwiązanie, jakie pojawiło się po drodze.

P(przyjąć) = min(1, e^{−Δ / T})

P(przyjąć)

z jakim prawdopodobieństwem przechodzimy do zaproponowanego sąsiada; w programie losujemy u jednostajnie z [0, 1) i przyjmujemy ruch, gdy u < P

min(1, …)

dla poprawy (Δ ≤ 0) wykładnik daje wartość ≥ 1, a prawdopodobieństwo nie może przekroczyć 1 — lepszy krok jest więc przyjmowany zawsze, tak samo jak u wspinacza

Δ

o ile sąsiad jest gorszy, w km. Stoi w wykładniku ze znakiem minus, więc każdy kolejny kilometr pogorszenia mnoży szansę przez tę samą liczbę mniejszą od 1 — duże pogorszenia są wykładniczo rzadsze niż małe

T

temperatura, w tych samych jednostkach co Δ (km). Dzieli Δ i tym samym wyznacza skalę: pogorszenie o T km przechodzi z prawdopodobieństwem 1/e ≈ 0,37 przy dowolnej temperaturze. Wysokie T czyni duże pogorszenia „małymi”, T → 0 zabrania wszystkich

Reguła przyjmowania gorszego kroku pochodzi z fizyki: w 1953 roku Nicholas Metropolis i jego współpracownicy użyli jej do symulacji atomów w równowadze termicznej, w której prawdopodobieństwo stanu o energii E jest proporcjonalne do e^−E/kT. Do optymalizacji przystosowali ją w 1983 roku niezależnie Kirkpatrick, Gelatt i Vecchi z IBM — a dwa lata później, również niezależnie, słowacki fizyk Vladimír Černý, właśnie na problemie komiwojażera.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # chłodzenie geometryczne
    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: brak ruchu
            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 wygląda naprawdę: pierwsze sześć iteracji naszego przebiegu i sześć iteracji z jego połowy. p to prawdopodobieństwo przyjęcia min(1, e^−Δ/T), u wylosowana liczba; pogarszający ruch przechodzi, gdy u < p.

Na początku, przy T ≈ 200, przechodzi nawet ruch, który wydłuża trasę o 146,6 km — szansa wynosi 0,48, a wypadło u = 0,14. W połowie przebiegu T = 10, a trasa leży już w optimum; ruchy, które wydłużyłyby ją o 70 i więcej kilometrów, mają szansę poniżej jednego promila i wszystkie zostają odrzucone. Czasem obie losowe liczby trafiają w to samo miejsce (i = j) i iteracja niczego nie proponuje — w całym przebiegu zdarzyło się to 824 razy.

Twierdzenie — rozkład Boltzmanna (dzisiejsze sformułowanie)

Jeśli trzymamy temperaturę T stałą i proponujemy sąsiadów symetrycznie (sąsiad s′ jest proponowany z s z tym samym prawdopodobieństwem co s z s′ — dla 2-opt to zachodzi, bo ten sam ruch (i, j) prowadzi też z powrotem), to proces Metropolisa jest łańcuchem Markowa, którego rozkład stacjonarny to

π_T(s) = e^−f(s)/T / Z(T)

π_T(s)

jak często po długim błądzeniu w temperaturze T znajdziemy się w rozwiązaniu s

e^−f(s)/T

waga rozwiązania: im krótsza trasa f(s), tym większa. To dokładnie ta waga, którą równoważy kryterium Metropolisa — stosunek wag dwóch sąsiadów wynosi e^−Δ/T

Z(T)

suma wag po wszystkich rozwiązaniach; dzielimy przez nią, aby prawdopodobieństwa sumowały się do 1

Dowód (warunek równowagi szczegółowej): dla sąsiadów z f(s′) = f(s) + Δ, Δ > 0, przepływ z s do s′ jest proporcjonalny do π(s) · e^−Δ/T, a przepływ z powrotem do π(s′) · 1. Dla π = π_T oba wyrażenia są równe e^−f(s′)/T / Z, przepływy się równoważą i rozkład już się nie zmienia.

optimum (1 060,4 km) wobec pułapki wspinacza (1 065,8 km): stosunek częstości e^5,38/T

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

6. Temperatura i schemat chłodzenia

Jaką szansę ma krok, który wydłuża trasę o 20 km? To zależy od temperatury:

Przy 200 przechodzi prawie każdy pogarszający krok, przy 0,5 żaden — wyżarzanie zachowuje się wtedy jak wspinacz. Schemat chłodzenia określa, jak długo algorytm „błądzi”, a jak długo „schodzi”. Najtańsza ucieczka z pułapki wspinacza (+19,0 km, zob. wyżej) przy T = 50 przeszłaby z prawdopodobieństwem 0,68, przy T = 10 z 0,15, a przy T = 2 praktycznie nigdy.

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

T_k

temperatura w k-tej iteracji — określa, jak duże pogorszenia są w tej chwili jeszcze przyjmowane

T₀

temperatura początkowa; wybiera się ją tak, aby na początku przechodziła większość pogorszeń — u nas 200 km, więcej niż typowy ruch 2-opt na losowej trasie

α

współczynnik chłodzenia tuż poniżej 1; liczymy go z docelowej temperatury T_K i liczby iteracji K, aby przebieg zakończył się dokładnie tam, gdzie chcemy

k

numer iteracji w wykładniku: każda iteracja mnoży temperaturę przez tę samą liczbę, więc w tej samej liczbie iteracji temperatura spada zawsze w tym samym stosunku — od 200 do 100 równie długo jak od 1 do 0,5

Twierdzenie — zbieżność wyżarzania

Jeśli temperatura spada dostatecznie wolno, logarytmicznie: T_k = c / ln(k + 1) z dostatecznie dużą stałą c, to prawdopodobieństwo, że wyżarzanie zakończy się w minimum globalnym, dąży wraz z liczbą iteracji do jedności (Hajek, 1988).

„Dostatecznie duża” oznacza dokładnie c ≥ d*, gdzie d* to głębokość najgłębszego minimum lokalnego, które nie jest globalne: o ile co najmniej musi wznieść się droga z niego, zanim dotrze do lepszego rozwiązania.

gdyby wystarczyło c = 20 km, temperaturę 0,5 mielibyśmy dopiero przy ln(k + 1) = 20 / 0,5 = 40,

czyli po k ≈ e⁴⁰ ≈ 2,4 · 10¹⁷ iteracjach — mniej więcej miliard razy więcej, niż jest wszystkich 239 500 800 cykli

7. Wyżarzanie na czeskich miastach wojewódzkich

Puśćmy wyżarzanie na ten sam problem: 10 000 iteracji, temperatura spada geometrycznie z 200 do 0,5. Mapa pokazuje, jak wyglądała trasa na początku i po 1 000, 3 000, 5 000 i 10 000 iteracji:

Po tysiącu iteracji trasa jest wciąż chaotyczna (1 985 km) — w wysokiej temperaturze wyżarzanie przyjmuje prawie wszystko. Po trzech tysiącach ma już kształt (1 159 km), a po pięciu tysiącach jest w optimum, 1 060,4 km. Z 1 498 przyjętych ruchów 695 było pogarszających; wspinacz nie wykonałby żadnego z nich. Wykres pokazuje, jak długość trasy skacze w górę i w dół, dopóki temperatura nie spadnie:

Przejście od błądzenia do schodzenia widać też po liczbie przyjętych ruchów w poszczególnych tysiącach iteracji: 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. W pierwszym tysiącu, gdy T jest między 200 a 110, przyjmowana jest ponad połowa propozycji. Od piątego tysiąca (T poniżej 20) już tylko dziesiątki; pogarszających było wśród nich 37, w tym 26 drobnych, poniżej 3 km.

I nie jest to przypadek jednego przebiegu: ze stu przebiegów z różnymi ziarnami 98 skończyło w optimum, a pozostałe dwa niecałe 3 km obok. W porównaniu z 61 % wspinacza z jednego startu to duża różnica.

8. Kiedy wyżarzanie się opłaca

Uczciwie mówiąc: wyżarzanie wykonało 10 000 iteracji, wspinacz z jednego startu tylko około sześciuset obliczeń. Na małym problemie wspinacz z restartami wypadłby za tę samą cenę tak samo. Różnica ujawnia się na większym problemie. Weźmy 60 losowo rozmieszczonych miast i obu algorytmom dajmy ten sam budżet — 200 000 obliczonych ruchów 2-opt:

Wspinacz zmieścił się w budżecie tylko dwa razy: przy 60 miastach sąsiedztwo ma 1 711 ruchów, a najszybszy spadek przegląda je wszystkie w każdym kroku. Wyżarzanie próbuje po jednym losowym ruchu i ten sam budżet rozkłada na eksplorację całego krajobrazu. Każdy z jego trzech przebiegów skończył się lepiej niż wspinacz.

9. Wyżarzanie w sztucznej inteligencji i nie tylko

• Projektowanie układów scalonych i harmonogramy. Rozmieszczanie elementów na chipie było jednym z pierwszych dużych zastosowań wyżarzania w latach osiemdziesiątych; do dziś używa się go do układania harmonogramów, tras pojazdów czy rozkładu magazynu.
• Uczenie sieci neuronowych. Stochastyczny spadek gradientu liczy gradient z małej partii danych, więc każdy krok jest trochę losowy — podobnie jak wyżarzanie może wyślizgnąć się z płytkiego dołka. Schematy współczynnika uczenia, które go stopniowo obniżają, nazywają się wręcz cosine annealing.
• Temperatura modeli językowych. Gdy model językowy wybiera kolejne słowo, dzieli wyniki słów przez temperaturę T i funkcją softmax zamienia je na prawdopodobieństwa proporcjonalne do e^z/T — ta sama formuła Boltzmanna. Wysoka temperatura oznacza tekst bardziej pomysłowy i ryzykowny, niska — ostrożniejszy i bardziej przewidywalny.
• Wyżarzanie kwantowe. Wyspecjalizowane komputery (na przykład D-Wave) szukają minimum energii fizycznie, z wykorzystaniem zjawisk kwantowych. Czy i kiedy są szybsze od klasycznych algorytmów, wciąż jest przedmiotem badań.

Przykład — temperatura przy wyborze kolejnego słowa

Model daje trzem kandydatom na kolejne słowo wyniki z = (2, 1, 0). Prawdopodobieństwo i-tego słowa to p_i = e^z_i/T / ∑_j e^z_j/T — rozkład Boltzmanna z rozdziału o wyżarzaniu, tylko z „energią” −z.

T = 1:   (e², e¹, e⁰) = (7,39; 2,72; 1), suma 11,11 → 0,665; 0,245; 0,090

T = 0,5:   (e⁴, e², 1) = (54,6; 7,39; 1), suma 62,99 → 0,867; 0,117; 0,016

T = 2:   (e¹, e^0,5, 1) = (2,72; 1,65; 1), suma 5,37 → 0,506; 0,307; 0,186

Niższa temperatura przesuwa prawdopodobieństwo ku najlepszemu kandydatowi (przy T → 0 to zawsze on), wyższa rozlewa je także na mniej prawdopodobne słowa — tak samo jak wyżarzanie w wysokiej temperaturze przyjmuje także gorsze trasy.

10. Podsumowanie

• Problem optymalizacyjny szuka rozwiązania o najlepszej wartości funkcji celu; przeszukiwanie lokalne porusza się po sąsiedztwie bieżącego rozwiązania.
• Wspinacz idzie zawsze do lepszego sąsiada i utyka w minimum lokalnym — na czeskich miastach wojewódzkich w 39 na 100 startów. Losowe restarty pomagają przy małych problemach.
• Symulowane wyżarzanie przyjmuje także gorsze kroki z prawdopodobieństwem e^−Δ/T; wraz ze spadkiem temperatury przechodzi od eksploracji do schodzenia.
• Na czeskich miastach wojewódzkich znalazło optimum w 98 na 100 przebiegów; na większym problemie pokonało wspinacza przy tym samym budżecie.
• Ta sama formuła Boltzmanna żyje w temperaturze modeli językowych, a idea chłodzenia w schematach uczenia sieci neuronowych.

Chcesz to wypróbować na własnej skórze? Niech agent AI napisze wyżarzanie dla twojej własnej trasy — na przykład przez miejsca, do których chcesz pojechać na wakacje — i sprawdź, co zrobi zbyt szybkie chłodzenie.

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