Локальный поиск и его улучшения

Локальный поиск и его улучшения

Идея: движение по ландшафту решений

Представьте «ландшафт» пространства решений: каждое решение — точка, её «высота» — значение целевой функции. Мы хотим найти глубину долину (минимум). Локальный поиск — это «спуск по ландшафту»: начинаем с произвольной точки и итерационно переходим к «соседней» точке с лучшим значением. Просто и быстро — но легко застрять в «локальной долине», не являющейся глобальным минимумом. Улучшения (Tabu Search, VNS, Large Neighborhood Search) позволяют «вырваться» из таких ловушек.

Базовый локальный поиск

Компоненты:

• Начальное решение s (случайное или жадное)
• Функция окрестности N(s) = множество «соседних» решений
• Критерий улучшения (first improvement или best improvement)

Алгоритм:

1. Текущее решение s = s₀
2. Пока N(s) содержит лучшее решение s':
   • s ← s' (first improvement: берём первое лучшее; best improvement: лучшее из всех)
3. Возврат s (локальный оптимум)

Выбор окрестности — ключевой вопрос: маленькая окрестность → быстрая итерация, но слабое улучшение. Большая → медленная, но качественное улучшение.

2-opt для TSP: классика

Окрестность 2-opt: удаляем 2 ребра из тура и перестраиваем. Для маршрута a→b→c→d→e→a: удаляем (b,c) и (d,e), добавляем (b,d) и (c,e) — перестройка.

Число пар рёбер: C_n^2 = O(n²). Каждая итерация: O(n²) операций.

Алгоритм 2-opt:

1. Для каждой пары рёбер (i,j):
   • Вычислить улучшение от замены двух рёбер
   • Если улучшение > 0: сделать замену, начать заново
2. Остановка: нет 2-opt улучшения (2-opt оптимум)

Практика: 2-opt часто даёт туры, отличающиеся от оптимума на 3-5%. Для задачи 1000 городов работает за секунды.

3-opt: удаляем 3 ребра — O(n³) операций. Лучше качество, дороже.

Lin-Kernighan (LK): адаптивный k-opt с «умным» выбором кандидатов. Лучший известный TSP-эвристик. Дает туры в 0.5-1% от оптимума. Используется в программе LKH (Lin-Kernighan-Helsgott) — индустриальный стандарт.

Variable Neighborhood Search (VNS)

Проблема базового ЛП: застревание в локальном оптимуме. VNS решает это через несколько окрестностей:

Алгоритм VNS:

Задать N₁, N₂,...,Nₖ (с N₁ ⊆ N₂ ⊆ ... ⊆ Nₖ).

1. s = s₀ (начальное решение)
2. Пока не истекло время: a. i = 1 b. Пока i ≤ k:
   • s' = random_neighbor(Nᵢ(s))
   • s'' = local_search(s')
   • Если f(s'') < f(s): s = s'', i = 1 (нашли улучшение — начали сначала)
   • Иначе: i++ (переходим к более широкой окрестности)

Идея: если ЛП застрял в N₁-оптимуме, «выпрыгиваем» случайным образом в N₂-окрестность и снова спускаемся. Если и там локальный оптимум — в N₃ и т.д.

Tabu Search

Мотивация: базовый ЛП может «осциллировать» между несколькими решениями. Tabu Search запрещает недавно посещённые решения.

Алгоритм Tabu Search:

1. s = s₀, TabuList = ∅, BestSolution = s₀
2. Пока не критерий остановки:
   • Найти лучшее решение s' ∈ N(s) TabuList
   • Если s' отсутствует → разрешить Tabu (аспирация)
   • s ← s'
   • Если f(s) < f(BestSolution): BestSolution = s
   • Добавить s в TabuList (удалить старейший, если список полный)

Критерий аспирации: разрешить tabu-переход, если он улучшает BestSolution. Это позволяет «принять» хорошее решение, даже если оно запрещено.

Параметры:

• Длина TabuList: обычно √n или n. Слишком мало — осцилляция. Слишком много — сильно ограничен поиск.
• Что хранить: само решение (дорого по памяти) или только «движение» (перемещение переменной)

Полный разбор: 2-opt для 5-городского TSP

Города: A(0,0), B(2,0), C(2,2), D(0,2), E(1,1). Начальный тур: A→B→C→D→E→A.

Длина: |AB| + |BC| + |CD| + |DE| + |EA| = 2 + 2 + 2 + √2 + √2 = 6 + 2√2 ≈ 8.83.

2-opt проверка (пара рёбер AB и CD): заменяем на AC и BD.

AC: √(4+4) = 2√2. BD: √(4+4) = 2√2. Новый тур: A→C→B→D→E→A.

Длина: |AC| + |CB| + |BD| + |DE| + |EA| = 2√2 + 2 + 2√2 + √2 + √2 = 2 + 6√2 ≈ 10.49. Хуже.

2-opt проверка (пара BC и DE): заменяем на BD и CE.

Новый тур: A→B→D→C→E→A (обратили подмаршрут C→D).

Длина: 2 + 2√2 + 2 + √2 + √2 = 4 + 4√2 ≈ 9.66. Хуже исходного.

Итог: начальный тур A→B→C→D→E→A является 2-opt оптимальным для этих городов.