Симульоване охолодження: Уникнення локальних мінімумів

Проблема з жадібним пошуком

Задача про туристичний маршрут запитує найкоротший маршрут, який відвідує кожен місто один раз і повертається додому. Вона є NP-складною, тому для будь-яких випадків, крім малих, ви не можете перевірити всі тури - кількість можливих маршрутів експоненціально зростає. Жардібний локальний пошук вирішує це, починаючи з будь-якого туру та повторно застосовуючи невеликі зміни, такі як рух 2-opt, який перевертає сегмент маршруту, зберігаючи зміну лише якщо вона скорочує тур. Проблема полягає в тому, що цей тип підйому зупиняється на першому локальному мінімумі, який він знаходить, і не має способу вийти з нього, навіть якщо коротший тур знаходиться просто над невеликим пагорбом.

Запозичення фізики: критерій Метаполіса

Симульоване annealing, представлене Кіркпатриком, Гелаттом та Веччі у 1983 році, бере свій механізм виходу з локальних мінімумів із статистичної механіки. Повільно охолоджені атоми металу переходячи до низькоенергетичної кристалічної решітки; якщо охолодити занадто швидко, вони застигають у безладному, вищому енергетичному стані скла. Критерій Метаполіса з 1953 року захоплює цю ідею: запропонувати випадкову зміну та прийняти її, якщо вона покращує об'єктивну функцію. Якщо це погіршує ситуацію на величину delta-E, прийняти її все ж таки з ймовірністю e в степені мінус delta-E поділеного на температуру T.

const candidate = perturb(tour); // наприклад, перевернути випадковий сегмент const dE = cost(candidate) - cost(tour); if (dE < 0 || Math.random() < Math.exp(-dE / T)) { tour = candidate; // прийняти, навіть якщо гірше } T *= alpha; // охолодити, alpha близький до 1 При високій початковій температурі delta-E над T мале, тому експонента близька до 1 і майже кожен рух приймається - пошук вільно блукає та досліджує весь ландшафт. Коли T падає, гірші ходи стають експоненціально менш ймовірними, і коли T наближається до нуля процес приймає лише покращуючі ходи і поводиться як простий hill-climbing, але тепер починаючи з кращого сусіднього середовища пошукового простору, ніж один жадібний запуск би знайшов.

const candidate = perturb(tour);           // e.g. reverse a random segment
const dE = cost(candidate) - cost(tour);
if (dE < 0 || Math.random() < Math.exp(-dE / T)) {
  tour = candidate;                        // accept, sometimes even if worse
}
T *= alpha;                                // cool down, alpha close to 1

Вибір градієнта охолодження

Градієнт - це вся алгоритм на практиці. Початковий теоретичний результат гарантує збіжність до глобального оптимуму лише для логарифмічного градієнту, T(k) пропорційний 1/log(k), що надзвичайно повільно для виконання. Реалізації використовують геометричний градієнт, T(k+1) = alpha * T(k), де alpha становить приблизно 0,95 - 0,999, іноді утримуючи температуру постійною для партії рухів на кожному рівні перед подальшим охолодженням. Занадто швидкий градієнт заморожує пошук у поганому локальному мінімумі, як і охолодження; занадто повільний марнує обчислення без додаткової вигоди. Повторний запуск з найкращого рішення, яке було знайдено до цього моменту, та зупинка, коли швидкість прийняття падає майже до нуля, є поширеними практичними вдосконаленнями.

Чому це узагальнюється за межами турніру подорожніх

Нічого в правилі Metropolis не є специфічним для турів. Будь-яка задача оптимізації з функцією вартості та способом запропонувати невеликі зміни до кандидата рішення може бути охолодженою: розміщення друкованих плат, мінімізація енергії складання білків, пошук гіперпараметрів нейронної мережі, планування роботи. Що робить це корисним, так це те, що йому не потрібен градієнт і жодне припущення про випукластість - лише функція вартості та структура сусідства - тому воно залишається стандартною базовою лінією для комбінаторних задач оптимізації, які не можуть дотягнутися градієнтними методами.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Simulated Annealing і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.