Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії

Задача оптимізації, задача комівояжера, сходження на пагорб з околом 2-opt, локальні мінімуми й перезапуски, імітація відпалу, температура і графік охолодження — на маршруті через тринадцять обласних центрів із відомим оптимумом.

13 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 26 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

Коваль, який хоче міцний клинок, не дає розжареному металу різко охолонути — він охолоджує його повільно. Так атоми мають час знайти впорядковане розташування з найнижчою енергією. Якби метал охолодили одразу, атоми замерзли б там, де саме були, і клинок був би крихким. 1983 року фізики помітили, що те саме мучить і алгоритми, які шукають найкращий розв’язок: коли вони йдуть лише «з гори», то замерзають у першій западині. Так з’явилася імітація відпалу — а з нею одна з найкорисніших ідей оптимізації.

Ця частина відкриває модуль про алгоритми, натхненні природою. Вона продовжує частину Пошук у просторі станів, де альпініст і відпал з’явилися вперше.

1. Задача оптимізації

Означення — задача оптимізації та окіл

Задано множину допустимих розв’язків S і цільову функцію f : S → ℝ. Шукаємо s* = argmin_{s ∈ S} f(s) — розв’язок із найменшим значенням (для максимізації навпаки).

Окіл — це відображення N : S → 2^S, яке кожному розв’язку ставить у відповідність множину «сусідніх» розв’язків, що виникають із нього невеликою зміною. Розв’язок s — локальний мінімум, якщо f(s) ≤ f(s′) для всіх s′ ∈ N(s), і глобальний мінімум, якщо це виконується для всіх s′ ∈ S.

2. Задача комівояжера

Комівояжер має об’їхати всі тринадцять обласних центрів Чехії, у кожному побувати один раз і повернутися туди, звідки виїхав. Яким маршрутом він проїде найменше? Відстані рахуємо по прямій.

Означення — задача комівояжера (TSP)

Задано n міст і відстані d(i, j). Розв’язок — циклічна перестановка π міст; її довжина f(π) = ∑_k=1ⁿ d(π_k, π_k+1), де π_n+1 = π₁.

Різних кільцевих маршрутів (незалежно від того, де й у якому напрямку вони починаються) є (n − 1)! / 2. Версія задачі в формі розв’язності NP-повна.

кількість маршрутів = n! / (n · 2) = (n − 1)! / 2

n!

усі порядки, в яких можна виписати n міст, — стільки є перестановок; проте кожен маршрут серед них порахований кілька разів

n

кільцевий маршрут не має початку: Praha → Brno → … → Praha — це той самий шлях, що й Brno → … → Praha → Brno. Кожен маршрут можна почати в будь-якому з n міст, тому в n разів менше

2

відстань туди така сама, як назад, тож маршрут, пройдений у зворотному напрямку, — це той самий шлях тієї самої довжини

Приклад — відстань по прямій з Праги до Брно

Міста задано географічною широтою φ і довготою λ у градусах. На території Чехії досить наближеної плоскої проєкції: градус широти має 110,57 км, градус довготи 111,32 · cos φ₀ км, де φ₀ = 49,8° — центр країни (меридіани до полюса сходяться). Тоді

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

Praha (50,08° пн. ш., 14,42° сх. д.), Brno (49,20°, 16,61°)

Δλ = 2,19° → 71,85 · 2,19 = 157,35 км на схід

Δφ = −0,88° → 110,57 · 0,88 = 97,30 км на південь

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

Похибка порівняно з точним обчисленням на кулі для таких відстаней близько 1 %; для порівняння маршрутів це не заважає.

Тринадцять міст — ще досить мало, щоб оптимум обчислити точно: динамічним програмуванням Гелда — Карпа за підмножинами міст, яке потребує 2ⁿ · n² кроків замість (n − 1)!. Найкоротший маршрут має 1 060,4 км. Завдяки цьому для кожного наступного алгоритму ми точно побачимо, наскільки близько він підійшов до оптимуму:

Алгоритм — динамічне програмування Гелда — Карпа (1962)

Пронумеруймо міста 0, …, n − 1 і почнімо в місті 0. Для кожної множини міст M ∋ 0 і міста j ∈ M позначмо D(M, j) довжину найкоротшого шляху, який виїжджає з 0, проходить саме міста з M і закінчується в j. Тоді

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

а довжина оптимального маршруту дорівнює min_{j ≠ 0} [ D(усі міста, j) + d(j, 0) ]. Значень D щонайбільше 2ⁿ · n, і кожне є мінімумом щонайбільше з n чисел.

n = 13:   2¹³ · 13² = 8 192 · 169 = 1 384 448 кроків

перебрати всі порядки з фіксованого старту: 12! = 479 001 600 — приблизно в 346 разів більше

3. Сходження на пагорб і окіл 2-opt

Означення — хід 2-opt

Хід 2-opt вилучає з маршруту два несуміжні ребра (a, b) і (e, f) та замінює їх ребрами (a, e) і (b, f) — тобто обертає порядок міст між b і e. Довжина зміниться на Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f). Окіл маршруту через n міст містить (n − 1)(n − 2) / 2 ходів.

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

Δ

наскільки маршрут подовжиться; від’ємне Δ означає скорочення. За знаком вирішують і альпініст, і відпал, тому нам потрібно отримувати його дешево

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

два нові ребра, якими знову з’єднуємо розрізані кінці, — додаються, бо на них маршрут збільшиться

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

два ребра, які ми розрізали, — віднімаються, бо з маршруту зникнуть. Ділянку між b і e ми лише проїдемо навпаки, а відстані симетричні, тож її довжина не зміниться і у формулі її немає

Алгоритм — сходження на пагорб (найкрутіший спуск)

Почни з випадкового розв’язку s. Повторюй: знайди s′ ∈ N(s) з найменшим f(s′); якщо f(s′) < f(s), перейди до s′, інакше зупинись — s є локальним мінімумом.

def delta(c, i, j):                    # хід 2-opt: оберни 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))   # найкрутіший спуск
        if delta(c, i, j) >= 0:                        # ніщо маршрут не скоротить
            return c                                    # локальний мінімум
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

Перше місто лишаємо на місці (i ≥ 1) — маршрут не має початку, тож це нічого нового не дало б. Для n = 13 пари 1 ≤ i < j ≤ 12 дають рівно 12 · 11 / 2 = 66 ходів.

З випадкового маршруту завдовжки 2 402 км альпініст за 8 кроків доходить до 1 065,8 км — і там зупиняється. До оптимуму бракує лише 5 км, але жоден окремий хід 2-opt маршрут уже не скорочує. Альпініст опинився в локальному мінімумі й не знає про це:

4. Де застрягає альпініст

Зі ста випадкових стартів альпініст опинився в оптимумі 61 раз. У решті 39 випадків він застряг деінде, у найгіршому — на 1 162,6 км, на сто кілометрів далі. Пасток три:

• Локальний мінімум — западина, з якої кожен крок веде вгору.
• Плато — усі сусіди однаково добрі, тож альпініст не знає, куди йти.
• Хребет — добрий напрямок існує, але не збігається з жодним окремим ходом; до нього можна дійти лише через гірші розв’язки.

Приклад — чому альпініст не вибереться з 1 065,8 км

Альпініст із першого старту закінчив на маршруті Zlín → Ostrava → Olomouc → Pardubice → Hradec Králové → Liberec → Ústí nad Labem → Karlovy Vary → Plzeň → Praha → České Budějovice → Jihlava → Brno → Zlín. Обчислимо Δ усіх 66 ходів 2-opt: один із них (обертання всього, крім першого міста) дає той самий маршрут у протилежному напрямку і Δ = 0, усі інші маршрут подовжують. Найдешевший із них обертає пару 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 км

Отже, кожен окремий хід подовжує маршрут щонайменше на 19,0 км — хоча оптимум коротший лише на 5,4 км. Шлях до нього веде через гірші маршрути, а їх альпініст ніколи не приймає.

Найпростіші ліки — випадкові перезапуски: запустити альпініста знову з іншого місця і зберегти найкращий результат. Якщо один старт успішний з імовірністю 0,61, то з п’яти стартів принаймні один буде успішним з імовірністю 1 − 0,39⁵ ≈ 99 %. Для малої задачі цього досить. У великій западин мільйони, і перезапусків знадобилося б забагато.

P_r = 1 − (1 − p)^r

P_r

імовірність, що принаймні один з r стартів знайде оптимум, — обчислюємо її через доповнення, бо «принаймні один» має багато варіантів, а «жоден» — лише один

1 − p

імовірність, що один старт зазнає невдачі (у нас 0,39 зі ста спроб)

r

кількість стартів у показнику: старти незалежні (кожен має інше випадкове зерно), тож імовірності невдачі перемножуються

5. Імітація відпалу

Алгоритм — імітація відпалу

Почни з випадкового розв’язку s з початковою температурою T₀. На кожній ітерації:

1. вибери випадкового сусіда s′ ∈ N(s) і обчисли Δ = f(s′) − f(s);
2. якщо Δ ≤ 0, перейди до s′; інакше перейди до нього з імовірністю e^−Δ/T (критерій Метрополіса);
3. знизь температуру за графіком охолодження, наприклад T ← α · T для 0 < α < 1.

Поверни найкращий розв’язок, який ти бачив дорогою.

P(прийняти) = min(1, e^{−Δ / T})

P(прийняти)

з якою ймовірністю ми перейдемо до запропонованого сусіда; у програмі випадково вибираємо u рівномірно з [0, 1) і приймаємо хід, якщо u < P

min(1, …)

для покращення (Δ ≤ 0) експонента ≥ 1, а ймовірність не може перевищити 1 — кращий крок, отже, приймається завжди, так само як в альпініста

Δ

наскільки сусід гірший, у км. Стоїть у показнику зі знаком мінус, тож кожен наступний кілометр погіршення множить шанс на те саме число, менше за 1, — великі погіршення експоненційно рідші за малі

T

температура, в тих самих одиницях, що й Δ (км). Вона ділить Δ і тим задає масштаб: погіршення на T км проходить з імовірністю 1/e ≈ 0,37 за будь-якої температури. Висока T робить великі погіршення «малими», T → 0 забороняє всі

Правило прийняття гіршого кроку походить із фізики: 1953 року Ніколас Метрополіс і його колеги використали його для моделювання атомів у тепловій рівновазі, де ймовірність стану з енергією E пропорційна e^−E/kT. Для оптимізації його 1983 року незалежно пристосували Кіркпатрик, Гелатт і Веккі з IBM — а через два роки, теж незалежно, словацький фізик Владімір Черни, якраз на задачі комівояжера.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # геометричне охолодження
    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: жодного ходу
            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

Як це виглядає насправді: перші шість ітерацій нашого прогону і шість ітерацій з його середини. p — імовірність прийняття min(1, e^−Δ/T), u — випадково вибране число; хід, що погіршує, проходить, якщо u < p.

На початку, при T ≈ 200, проходить навіть хід, який подовжує маршрут на 146,6 км, — шанс 0,48, а випало u = 0,14. У середині прогону T = 10, і маршрут уже лежить в оптимумі; ходи, які подовжили б його на 70 і більше кілометрів, мають шанс менше одного проміле, і всі вони відхилені. Іноді обидва випадкові числа влучають в одне й те саме місце (i = j), і ітерація нічого не пропонує — за весь прогін таких ітерацій було 824.

Теорема — розподіл Больцмана (сучасне формулювання)

Якщо тримати температуру T сталою і пропонувати сусідів симетрично (сусіда s′ пропонують із s з тією самою ймовірністю, що й s із s′ — для 2-opt це виконується, бо той самий хід (i, j) веде й назад), то процес Метрополіса є марковським ланцюгом, стаціонарний розподіл якого

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

π_T(s)

як часто після довгого блукання за температури T ми опинимося в розв’язку s

e^−f(s)/T

вага розв’язку: що коротший маршрут f(s), то більша. Це саме та вага, яку врівноважує критерій Метрополіса, — відношення ваг двох сусідів дорівнює e^−Δ/T

Z(T)

сума ваг за всіма розв’язками; ділимо на неї, щоб імовірності в сумі давали 1

Доведення (умова детального балансу): для сусідів з f(s′) = f(s) + Δ, Δ > 0, потік з s до s′ пропорційний π(s) · e^−Δ/T, а потік назад — π(s′) · 1. Для π = π_T обидва вирази дорівнюють e^−f(s′)/T / Z, потоки врівноважуються, і розподіл більше не змінюється.

оптимум (1 060,4 км) проти пастки альпініста (1 065,8 км): відношення частот e^5,38/T

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

6. Температура і графік охолодження

Який шанс має крок, що подовжує маршрут на 20 км? Це залежить від температури:

При 200 проходить майже кожен крок, що погіршує, при 0,5 — жоден: відпал у цей момент поводиться як альпініст. Графік охолодження визначає, як довго алгоритм «блукає» і як довго «спускається». Найдешевший вихід із пастки альпініста (+19,0 км, див. вище) при T = 50 пройшов би з імовірністю 0,68, при T = 10 — з 0,15, а при T = 2 практично ніколи.

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

T_k

температура на k-й ітерації — визначає, які великі погіршення в цей момент ще приймаються

T₀

початкова температура; її вибирають так, щоб на початку проходила більшість погіршень, — у нас 200 км, більше, ніж типовий хід 2-opt на випадковому маршруті

α

коефіцієнт охолодження трохи менший за 1; обчислюємо його з цільової температури T_K і кількості ітерацій K, щоб прогін закінчився саме там, де ми хочемо

k

номер ітерації в показнику: кожна ітерація множить температуру на те саме число, тож за однакову кількість ітерацій температура завжди падає в однаковому відношенні — від 200 до 100 так само довго, як від 1 до 0,5

Теорема — збіжність відпалу

Якщо температура спадає досить повільно, логарифмічно: T_k = c / ln(k + 1) з досить великою сталою c, то ймовірність, що відпал закінчиться в глобальному мінімумі, із кількістю ітерацій прямує до одиниці (Гаєк, 1988).

«Досить велика» означає точно c ≥ d*, де d* — глибина найглибшого локального мінімуму, який не є глобальним: на скільки щонайменше мусить піднятися шлях із нього, перш ніж дійде до кращого розв’язку.

якби вистачило c = 20 км, температуру 0,5 ми мали б лише при ln(k + 1) = 20 / 0,5 = 40,

тобто після k ≈ e⁴⁰ ≈ 2,4 · 10¹⁷ ітерацій — приблизно в мільярд разів більше, ніж усіх 239 500 800 маршрутів

7. Відпал на обласних центрах

Запустімо відпал на тій самій задачі: 10 000 ітерацій, температура спадає геометрично з 200 до 0,5. Мапа показує, який вигляд мав маршрут на початку і після 1 000, 3 000, 5 000 та 10 000 ітерацій:

Після тисячі ітерацій маршрут усе ще хаотичний (1 985 км) — за високої температури відпал приймає майже все. Після трьох тисяч він уже має форму (1 159 км), а після п’яти тисяч перебуває в оптимумі, 1 060,4 км. Із 1 498 прийнятих ходів 695 були погіршувальними; альпініст не зробив би жодного з них. Графік показує, як довжина маршруту стрибає вгору й униз, доки температура не впаде:

Перехід від блукання до спуску видно й за кількістю прийнятих ходів в окремих тисячах ітерацій: 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. У першій тисячі, коли T між 200 і 110, приймається понад половину пропозицій. Від п’ятої тисячі (T нижче 20) — уже лише десятки; погіршувальних серед них було 37, з них 26 дрібних, менше 3 км.

І це не випадковість одного прогону: зі ста прогонів із різними зернами 98 закінчилися в оптимумі, а решта два — менш ніж на 3 км поруч. Порівняно з 61 % альпініста з одного старту це велика різниця.

8. Коли відпал окупається

Чесно кажучи, відпал зробив 10 000 ітерацій, а альпініст з одного старту — лише близько шестисот оцінювань. На малій задачі альпініст із перезапусками за ту саму ціну впорався б так само. Різниця проявляється на більшій задачі. Візьмімо 60 випадково розміщених міст і дамо обом алгоритмам однаковий бюджет — 200 000 оцінених ходів 2-opt:

Альпініст умістився в бюджет лише двічі: із 60 містами окіл має 1 711 ходів, і найкрутіший спуск переглядає їх усі на кожному кроці. Відпал пробує по одному випадковому ходу і той самий бюджет розподіляє на дослідження всього рельєфу. Кожен із трьох його прогонів закінчився краще, ніж альпініст.

9. Відпал у штучному інтелекті та деінде

• Проєктування чипів і розклади. Розміщення компонентів на чипі було одним із перших великих застосувань відпалу у вісімдесятих роках; досі його використовують для розкладів, маршрутів транспорту чи впорядкування складу.
• Навчання нейронних мереж. Стохастичний градієнтний спуск обчислює градієнт за малим пакетом даних, тож кожен крок трохи випадковий — подібно до відпалу він може вислизнути з мілкої западини. Графіки швидкості навчання, які поступово її знижують, навіть називаються cosine annealing.
• Температура мовних моделей. Коли мовна модель вибирає наступне слово, вона ділить оцінки слів на температуру T і функцією softmax перетворює їх на ймовірності, пропорційні e^z/T, — та сама формула Больцмана. Висока температура означає винахідливіший і ризикованіший текст, низька — обережніший і передбачуваніший.
• Квантовий відпал. Спеціалізовані комп’ютери (наприклад, D-Wave) шукають мінімум енергії фізично, використовуючи квантові явища. Чи й коли вони швидші за класичні алгоритми, досі є предметом досліджень.

Приклад — температура під час вибору наступного слова

Модель дає трьом кандидатам на наступне слово оцінки z = (2, 1, 0). Імовірність i-го слова p_i = e^z_i/T / ∑_j e^z_j/T — розподіл Больцмана з розділу про відпал, лише з «енергією» −z.

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

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

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

Нижча температура зміщує ймовірність до найкращого кандидата (при T → 0 це завжди він), вища розливає її й на менш імовірні слова — так само, як відпал за високої температури приймає й гірші маршрути.

10. Підсумок

• Задача оптимізації шукає розв’язок із найкращим значенням цільової функції; локальний пошук рухається околом поточного розв’язку.
• Альпініст завжди йде до кращого сусіда і застрягає в локальному мінімумі — на обласних центрах у 39 зі 100 стартів. Випадкові перезапуски допомагають у малих задачах.
• Імітація відпалу приймає й гірші кроки з імовірністю e^−Δ/T; зі спаданням температури вона переходить від дослідження до спуску.
• На обласних центрах вона знайшла оптимум у 98 зі 100 прогонів; на більшій задачі перемогла альпініста з тим самим бюджетом.
• Та сама формула Больцмана живе в температурі мовних моделей, а ідея охолодження — у графіках навчання нейронних мереж.

Хочете спробувати самі? Попросіть ШІ-агента написати відпал для вашого власного маршруту — скажімо, через місця, куди хочете поїхати на канікулах, — і подивіться, що зробить надто швидке охолодження.

Маєте іншу думку? Напишіть на support@coden-app.com.