Конспект: локальный поиск, отжиг и эвристики

Понятия

Локальный поиск - улучшать готовое решение маленькими правками. Три детали: пространство решений, соседство (что считается одним шагом), цель.

Локальный оптимум - решение без соседа лучше. Глобальный оптимум локален, обратное неверно. Исключение - линейное программирование: там локальный оптимум глобален.

Отжиг - локальный поиск, принимающий ухудшение на рост с вероятностью e^(−рост / T); температура T медленно падает.

Поиск с запретами (табу) - всегда к лучшему разрешённому соседу, даже худшему; недавние ходы нельзя отменять srok шагов, кроме хода, дающего новый рекорд.

Перезапуски - много спусков из случайных стартов, берётся лучший.

Что унести

ОСТАНОВКА И КАЧЕСТВО
остановка: цель строго растёт, значений конечно
    наибольший разрез: не больше m переводов
качество: отдельное доказательство, есть не всегда
    наибольший разрез: любой локальный оптимум >= m / 2
    24 ребра: локальный 16, гарантия 12, наибольший 18
    Ллойд, k-средние: старт 1 2 3 → ошибка 154,5; лучшее 6

2-opt
убрать a-b и c-e, поставить a-c и b-e, кусок b…c развернуть
выигрыш = d(a,b) + d(c,e) − d(a,c) − d(b,e)     O(1) на соседа
соседей ~ n² / 2;  порог выигрыша 0.000001 против ошибок округления
на плоскости: в локальном оптимуме нет пересечений
8 точек: двойное дерево 40,87 → 6 ходов → 32,23 = оптимум
25 точек: по номерам 1375,6 → 358,5;  ближайший 409,4 → 389,8
постоянной гарантии нет; на практике ~5% сверх оптимума

ОТЖИГ
принять: рост <= 0 всегда; иначе с вероятностью e^(−рост / T)
T = T · a,  a чуть меньше 1
вес решения e^(−f / T): T = 100 - почти поровну, T = 1 - в e^10 раз
T0 по масштабу цели: ~половина ухудшений принимается
забор высотой 10: спуск 150, отжиг 6 из трёх стартов
20 точек: холодно 440,7 · отжиг 426,3 · жарко 1266,2

ЧЕСТНЫЙ ЗАМЕР
бюджет - в оценках цели;  много фиксированных зёрен;
весь разброс (сколько раз оптимум, среднее, худшее);
эталон - точный ответ или нижняя граница;
настройка на одних входах, отчёт на других
перезапуски: 1 − (1 − p)^k
разбиение 16 чисел, 600 оценок, 20 зёрен, оптимум найден:
    спуск 2 · перезапуски 17 · отжиг 12
табу, 37 шагов по 16 оценок, 8 зёрен: срок 0 - 1 раз, срок 4 - 6 раз

Ловушки джокера

Принимал равные ходы. Поиск на плато ходит по кругу вечно.

Принял «сошёлся» за «лучше нельзя». Сошёлся - значит, соседи не лучше.

Решил, что хороший старт даёт хороший финиш. Маршрут «в ближайший» втрое лучше старта по номерам, а финиш хуже.

Обменял два города вместо разворота. Четыре новых ребра вместо двух, формула выигрыша врёт.

Задал температуру числом наугад. Метры вместо километров превращают отжиг в спуск.

Вернул последнее решение отжига. Хранить надо лучшее найденное.

Сравнил лучшие прогоны. По лучшему случаю спуск и отжиг неразличимы.

Дал методу больший бюджет. Выигрыш куплен оценками, а не идеей.

Проверь себя

Из каких трёх деталей состоит локальный поиск и почему он останавливается? Почему любой локальный оптимум наибольшего разреза режет хотя бы половину рёбер? Запиши ход 2-opt и его выигрыш; почему кусок разворачивают? Откуда в отжиге e^(−рост / T) и что делает температура? Как устроен поиск с запретами и зачем срок? Назови четыре правила честного замера.