Дискретная оптимизация

Определения

Задача коммивояжёра (TSP)

— дано n городов с расстояниями dᵢⱼ между ними. Найти кратчайший маршрут, посещающий каждый город ровно один раз и возвращающийся в начало.

Задача о рюкзаке (Knapsack)

— n предметов с ценностями cᵢ и весами wᵢ. Рюкзак вмещает W кг. Выбрать набор предметов максимальной суммарной ценности.

Задача покрытия множества (Set Cover)

— дано универсальное множество U и семейство подмножеств S₁,...,Sₘ. Выбрать минимальное подсемейство, покрывающее U. Применения: минимальное число пожарных депо для покрытия всего города.

MAX-CUT

— граф G=(V,E). Разбить V на два множества S, V∖S, максимизируя число рёбер между ними. Применения: кластеризация данных, VLSI layout.

Пример (TSP как ЦЛП)

— xᵢⱼ ∈ {0,1} — использование ребра (i,j). Ограничения: Σⱼ xᵢⱼ = 1 (въезд в каждый город), Σᵢ xᵢⱼ = 1 (выезд), yᵢ − yⱼ + n xᵢⱼ ≤ n−1 для i≠j≠1 (устранение подмаршрутов).

Класс P

— задачи, решаемые за полиномиальное время O(nᵏ). Примеры: сортировка O(n log n), кратчайший путь в графе O(n²), линейное программирование O(n^{3.5}).

Класс NP

— задачи, решение которых можно проверить за полиномиальное время. Например: TSP — данный маршрут можно проверить за O(n). Но найти оптимальный — неизвестно как.

NP-полные задачи

— самые «трудные» в NP. Любая NP-задача полиномиально сводится к любой NP-полной. Первая NP-полная задача: SAT (Кук, 1971).

Что это значит практически

— три стратегии для NP-трудных задач:

Данные

— W = 10 кг, 4 предмета: (c₁,w₁) = (6,4), (c₂,w₂) = (5,3), (c₃,w₃) = (4,2), (c₄,w₄) = (3,1).

Оптимум

— {1,2,3,4} с c = 18. Но при n = 50 предметах — 2⁵⁰ > 10¹⁵ вариантов, перебор нереален.

Компания FedEx доставляет 15 миллионов посылок в день. Маршрут каждого грузовика — это последовательность остановок. Как назначить маршруты, чтобы суммарный пробег был минимальным? Это задача маршрутизации транспорта — дискретная задача оптимизации. Или: авиакомпания должна составить расписание п...

Кажется, что можно просто перебрать все варианты. Но масштаб делает это невозможным. Задача коммивояжёра (найти кратчайший маршрут через n городов): число возможных маршрутов = (n−1)!/2. При n = 20: ≈ 60 квинтиллионов маршрутов. При 1 миллиарде операций в секунду перебор займёт 60 миллиардов лет ...

Решение? Умные алгоритмы, которые находят оптимум (или хорошее приближение) за разумное время.

Задача коммивояжёра (TSP): дано n городов с расстояниями dᵢⱼ между ними. Найти кратчайший маршрут, посещающий каждый город ровно один раз и возвращающийся в начало.

Определения

Постановка

— ориентированная сеть G = (V, E) с пропускными способностями c(e) > 0 на каждом ребре. Источник s, сток t. Найти максимальный поток из s в t.

Теорема Форда-Фалкерсона

— max flow = min cut.

Алгоритм Форда-Фалкерсона

— ищем «увеличивающий путь» (augmenting path) в остаточной сети: путь из s в t, где каждое ребро имеет остаточную пропускную способность > 0. Увеличиваем поток вдоль пути. Повторяем до отсутствия пути.

Сложность

— O(E · f_max) для рациональных пропускных способностей. Алгоритм Эдмондса-Карпа (Edmonds-Karp) — использует BFS для поиска кратчайшего пути → O(V E²).

Полный разбор примера

— сеть: s→a (c=4), s→b (c=3), a→t (c=3), a→b (c=2), b→t (c=4).

Двудольный граф

— V = A ∪ B, рёбра только между A и B.

Алгоритм Хопкрофта-Карпа

— O(E√V). Ищет увеличивающие пути с помощью BFS (находит все кратчайшие увеличивающие пути одновременно), затем DFS для нахождения максимального паросочетания этой длины.

Венгерский алгоритм (задача назначения)

— дан полный двудольный граф с весами wᵢⱼ (стоимость назначения задачи i исполнителю j). Найти минимальное назначение (= паросочетание минимального суммарного веса). Сложность: O(n³).

Задача MST

— найти остовное дерево минимального суммарного веса рёбер.

Алгоритм Крускала

— O(E log E)

Алгоритм Прима

— O(E log V) с кучей

Доказательство оптимальности (обрезающее свойство)

— для любого разреза (S, V∖S) минимальное ребро через разрез входит в любое MST.

Полный разбор

— граф 4 вершин: a-b (4), a-c (3), b-c (2), b-d (5), c-d (1).

Применения

— прокладка кабелей в сети при минимальной длине кабеля (телефонные, электрические сети), кластеризация данных (single-linkage), приближённые алгоритмы для TSP.

Алгоритм Дейкстры

— неотрицательные веса. O((V+E) log V) с двоичной кучей. Идея: жадно расширяем «фронт» кратчайших путей от s.

Граф — математическая абстракция сети: вершины (узлы) и рёбра (связи). Интернет — граф маршрутизаторов. Социальная сеть — граф пользователей. Транспортная сеть — граф городов и дорог. Многие задачи дискретной оптимизации — это задачи на графах. Три классических класса: задачи потоков (как направи...

Постановка: ориентированная сеть G = (V, E) с пропускными способностями c(e) > 0 на каждом ребре. Источник s, сток t. Найти максимальный поток из s в t.

Поток f: поток на ребре (u,v) ≤ c(u,v), в каждой вершине (кроме s,t) сумма входящих = сумма выходящих потоков.

Разрез (S, V∖S) с s ∈ S, t ∈ V∖S: мощность разреза = сумма пропускных способностей рёбер из S в V∖S. Минимальный разрез = «узкое место» сети.

Определения

Стандартная форма ЛП

— min cᵀx при Ax ≤ b, x ≥ 0.

Допустимое множество

— пересечение полупространств — политоп (выпуклый многогранник).

ЦЛП

— min cᵀx при Ax ≤ b, x ∈ {0,1}ⁿ.

ЛП-релаксация

— min cᵀx при Ax ≤ b, 0 ≤ x ≤ 1. (Убираем целочисленность)

Пример

— задача рюкзака с W=5, n=3: (c₁,w₁)=(4,3), (c₂,w₂)=(3,2), (c₃,w₃)=(2,1).

Определение

— матрица A называется вполне унимодулярной (TU), если определитель каждой квадратной подматрицы ∈ {−1, 0, +1}.

Теорема (Хоффман-Крускал)

— если A — TU-матрица и b целочисленный, то вершины политопа {x: Ax ≤ b, x ≥ 0} — целочисленные. Следовательно, ЛП-оптимум = ЦЛП-оптимум — решать ЦЛП через ЛП!

Следствие

— задача максимального паросочетания, задача о максимальном потоке, задача кратчайшего пути — все решаются ЛП!

Двойственность ЛП

— для задачи (P): min cᵀx при Ax ≥ b, x ≥ 0 двойственная (D): max bᵀy при Aᵀy ≤ c, y ≥ 0.

Слабая двойственность

— любое допустимое y дает bᵀy ≤ cᵀx для любого допустимого x. Следствие: bᵀy — нижняя оценка оптимума (P).

Метод Primal-Dual

— строим допустимое целочисленное решение x^ и допустимое двойственное y^ параллельно. Гарантия: cᵀx^ ≤ ρ · bᵀy^ ≤ ρ · OPT → ρ-аппроксимация.

Гарантия

— ln n-аппроксимация (ln n — максимальная степень вершины в гиперграфе покрытия).

Граф

— V = {1,2,3,4}, рёбра: (1,2)=2, (1,3)=4, (2,3)=1, (2,4)=5, (3,4)=2. Найти кратчайший путь от 1 до 4.

ЛП-формулировка потока

— xᵢⱼ ≥ 0 — поток по ребру (i,j). Задача: min Σ dᵢⱼ xᵢⱼ при балансных ограничениях (поток 1 из источника, −1 в сток, 0 везде).

Решение

— симплекс даёт x₁₂=1, x₂₃=1, x₃₄=1 (путь 1→2→3→4, стоимость = 2+1+2 = 5). Решение целочисленное (матрица сетевых задач — TU)!

Целочисленные задачи по природе своей дискретные. Но ключевой инструмент их решения — линейное программирование, непрерывная задача. Идея: «расслабить» целочисленные ограничения до непрерывных, решить гораздо более простую задачу, и использовать результат для нахождения целочисленного оптимума. Э...

Допустимое множество — пересечение полупространств — политоп (выпуклый многогранник).

Ключевая теорема: оптимальное решение ЛП всегда достигается в вершине политопа (при наличии оптимума). Вершина — точка, в которой n ограничений «активны» (выполняется равенство).

Число вершин: до C_{m+n}^n ≈ m^n/n! (экспоненциально). Но симплекс-метод на практике работает быстро, обходя лишь O(m) вершин. Метод Кармаркара (1984): полиномиальный — O(n^{3.5}), движется «через центр» политопа.

Определения

Дерево поиска

— каждый узел — это подзадача с дополнительными ограничениями. Корень — исходная задача без дополнительных ограничений.

Правило отсечения

— если LB(узел) ≥ incumbent, этот узел бесполезен — отсекаем его вместе со всеми потомками.

ЛП-оценка

— решаем ЛП-релаксацию. Хорошая оценка, но вычислительно дорого.

Лагранжева релаксация

— «смягчаем» часть ограничений, добавляя их в цель со штрафами λ.

Задача

— W=10, предметы (c,w): (6,4), (5,3), (4,2), (3,1).

Корневой узел

— ЛП-релаксация. Жадное решение по соотношению c/w: берём 4 (c=3,w=1), 3 (c=4,w=2), 2 (c=5,w=3). Остаток 4 кг → берём 6/4 = 1.5 единицы предмета 1: x₁ = 1, x₂ = 1, x₃ = 1, x₄ = 1, ценность = 3+4+5+6=18. LB = 18 (целочисленное!).

Полный перебор всех вариантов невозможен при больших n. Но можно быть умнее: если на каком-то шаге мы знаем, что «дальше ничего хорошего не будет» — отсечём целую ветвь дерева перебора. Метод ветвей и границ (Branch and Bound, B&B) систематизирует эту идею. Это основа всех промышленных ЦЛП-решате...

Дерево поиска: каждый узел — это подзадача с дополнительными ограничениями. Корень — исходная задача без дополнительных ограничений.

Нижняя оценка (lower bound, LB) для узла: минимально возможное значение целевой функции в этом узле. Обычно — оптимум ЛП-релаксации подзадачи.

Лучшее найденное решение (incumbent): лучшее целочисленное решение, найденное на данный момент.

Определения

Определение

— неравенство aᵀx ≤ b называется *режущей плоскостью* для ЦЛП, если:

Процедура

— пусть xᵢ = a₀ + Σⱼ aⱼ sⱼ (строка симплекс-таблицы, sⱼ — небазисные переменные). Пишем xᵢ = ⌊a₀⌋ + f₀ + Σⱼ (⌊aⱼ⌋ + fⱼ) sⱼ, где fⱼ = aⱼ − ⌊aⱼ⌋ ∈ [0,1).

Отсечение Гомори

— Σⱼ fⱼ sⱼ ≥ f₀. Это нарушается для текущего решения (sⱼ = 0 → 0 ≥ f₀ > 0), но выполняется для целочисленных.

Теорема Гомори

— за конечное число итераций с отсечениями Гомори любое ограниченное ЦЛП решается оптимально.

Неравенства исключения подтуров

— для любого подмножества городов S ⊊ V, |S| ≥ 2:

Почему это мощнее чистого B&B

— режущие плоскости «подтягивают» ЛП-оценки к целочисленным, делая отсечение более агрессивным. Меньше узлов нужно исследовать.

Данные

— 4 города, матрица расстояний d = [[0,2,9,10],[1,0,6,4],[15,7,0,8],[6,3,12,0]].

Нарушенное подтурное неравенство

— для S = {1,2}: x₁₂ + x₂₁ ≤ 1. Текущее значение: 0.5 + 0.5 = 1. Не нарушено строго — ищем другое.

После добавления

— ЛП перерешается, дробность уменьшается. Через несколько итераций ЛП-оптимум становится целочисленным или B&B завершает задачу.

ЛП-релаксация может давать дробные оптимумы (x₁ = 1.5, x₂ = 0.7...). Можно ли добавить «умные» линейные ограничения, которые «срежут» эти дробные решения, не убирая при этом ни одного целочисленного? Именно это делают режущие плоскости (cutting planes). Вместо того чтобы сразу ветвиться, добавляе...

Определение: неравенство aᵀx ≤ b называется *режущей плоскостью* для ЦЛП, если: 1. Оно выполнено для всех целочисленных допустимых точек x ∈ {0,1}ⁿ 2. Оно нарушено для текущего ЛП-оптимума x* (дробного)

Добавляя такое неравенство, мы «отрезаем» дробный x*, но не теряем ни одного целочисленного решения. Новая ЛП-релаксация даёт лучшую (более высокую) нижнюю оценку.

Идея Ральфа Гомори (1958): взять строку симплекс-таблицы для дробной переменной и сгенерировать режущую плоскость.

Определения

Формулировка

— оптимальное решение содержит оптимальные решения всех своих подзадач.

Постановка

— n предметов с ценностями cᵢ и весами wᵢ, рюкзак вместимостью W.

Состояние

— V[i][w] = максимальная ценность при использовании первых i предметов и вместимости w.

Начальные условия

— V[0][w] = 0 для всех w (нет предметов — нет ценности).

Сложность

— O(nW) по времени и памяти — псевдополиномиальная (не полиномиальная, так как W может быть огромным).

Bellman-Ford

— d[v] = min_{(u,v)∈E} {d[u] + w(u,v)}.

Обнаружение отрицательного цикла

— если d[n][v] < d[n−1][v] для какого-то v — отрицательный цикл!

Floyd-Warshall

— все пары кратчайших путей.

Задача

— даны строки s₁ и s₂. Найти наибольшую общую подпоследовательность (не обязательно непрерывную).

Применения

— биоинформатика — выравнивание последовательностей ДНК (программа BLAST). Системное программирование — алгоритм diff для сравнения файлов в git. Сжатие данных — LZW использует общие подстроки.

Рекуррентность

— dp[S][v] = min_{u ∈ S{v}} {dp[S{v}][u] + d(u,v)}.

Ответ

— min_{v ≠ 1} {dp[{2,...,n}][v] + d(v,1)}.

Динамическое программирование (ДП) — один из самых элегантных методов дискретной оптимизации. Идея проста и глубока одновременно: оптимальное решение большой задачи строится из оптимальных решений меньших подзадач. Это принцип оптимальности Беллмана. ДП «запоминает» результаты подзадач (memoizati...

Формулировка: оптимальное решение содержит оптимальные решения всех своих подзадач.

Когда принцип выполнен? Когда подзадачи независимы (решение одной не мешает другой) и структура оптимального решения допускает рекуррентное разложение.

Когда НЕ выполнен? Когда требуется учёт глобальных ограничений (например, задача о комивояжёре — подзадачи связаны между собой через ограничение «посетить каждый город один раз»). Впрочем, и TSP можно решить ДП за O(2ⁿ n²)!

Определения

Задача Vertex Cover

— граф G = (V, E). Найти минимальное по размеру множество вершин C ⊆ V, такое что каждое ребро (u,v) имеет хотя бы один конец в C.

Доказательство 2-аппроксимации

— M — паросочетание (рёбра в M не имеют общих вершин). Следовательно, |M| ≤ OPT (оптимум должен покрыть все рёбра M → нужно ≥ |M| вершин). |C| = 2|M| ≤ 2 · OPT. ✓

Пример

— K₄ (полный граф 4 вершины). OPT = 2 (любые 2 вершины покрывают все 6 рёбер? Нет: 2 вершины покрывают 5 рёбер. OPT = 3). Алгоритм выберет 2 ребра → 4 вершины. Аппроксимация = 4/3 < 2. ✓

APX-трудные задачи

— нет PTAS (Polynomial-Time Approximation Scheme) при P ≠ NP.

Max-3-SAT

— APX-трудная. Лучшая известная аппроксимация: 7/8 (рандомизированная — случайно назначаем каждую переменную). Невозможно лучше при P ≠ NP (Гастад 2001).

Задача

— n предметов с размерами sᵢ ∈ (0,1]. Минимальное число единичных корзин для размещения всех предметов.

First-Fit (FF)

— для каждого предмета кладём в первую корзину, куда помещается. Если нет — открываем новую. Аппроксимация: ≤ (17/10) OPT + 2 — не очень хорошо.

First-Fit Decreasing (FFD)

— сортируем предметы по убыванию, затем FF.

Теорема (Johnson, 1974)

— FFD(I) ≤ (11/9) OPT(I) + 4.

Как доказывается

— анализируем, сколько «пространства» теряется в каждой корзине. При сортировке по убыванию потери минимальны.

FPTAS для Bin Packing

— при заранее известных размерах существует (1+ε)-аппроксимация за O(n log n + f(1/ε)) — Fernandez de la Vega & Lueker (1981). Делим предметы на «большие» (sᵢ > ε) и «маленькие» (sᵢ ≤ ε), обрабатываем по-разному.

Задача k-Median

— даны n клиентов и n точек-«складов», метрика d. Выбрать k складов, минимизируя сумму расстояний клиентов до ближайшего склада.

Гарантия

— в локальном оптимуме алгоритм даёт ≤ (3+ε) · OPT. Доказательство: амортизационный анализ замен. Применение: оптимальное размещение серверов, распределение региональных центров.

Если задача NP-трудная, мы не можем (предположительно) найти оптимальное решение за полиномиальное время. Но часто нам не нужна идеальная точность — достаточно «достаточно хорошего» решения. Аппроксимационные алгоритмы находят решения с гарантированным качеством: не более чем в ρ раз хуже оптимум...

Задача Vertex Cover: граф G = (V, E). Найти минимальное по размеру множество вершин C ⊆ V, такое что каждое ребро (u,v) имеет хотя бы один конец в C.

1. C = ∅, M = ∅ (M — паросочетание) 2. Пока существует ребро, не покрытое C: 3. Вернуть C

Доказательство 2-аппроксимации: M — паросочетание (рёбра в M не имеют общих вершин). Следовательно, |M| ≤ OPT (оптимум должен покрыть все рёбра M → нужно ≥ |M| вершин). |C| = 2|M| ≤ 2 · OPT. ✓

Определения

Алгоритм Крускала

— сортируем рёбра по весу. Жадно добавляем минимальное ребро, не создающее цикл.

Лемма об отсечении (Cut Lemma)

— для любого разреза (S, V∖S) минимальное ребро через разрез входит в MST.

Доказательство

— пусть e* — минимальное ребро через разрез, и T — MST, не включающее e*. Добавим e* в T → образуется цикл, который пересекает разрез как минимум в одном другом ребре e'. Так как e* минимально в разрезе: w(e*) ≤ w(e'). Заменим e' на e* в T → новое д...

Базис матроида

— максимальное независимое множество. По I3 все базисы имеют одинаковый размер (ранг матроида).

Линейный матроид

— E = столбцы матрицы A над полем F, I = линейно независимые подмножества столбцов. Ранг матроида = ранг матрицы.

Матроид разбиения

— E разбит на группы E₁,...,Eₖ. I = множества с не более 1 элементом из каждой Eᵢ. Используется для представления расписаний.

Теорема

— жадный алгоритм оптимален для задачи максимального взвешенного независимого множества тогда и только тогда, когда (E, I) — матроид.

Жадный алгоритм

— сортировать элементы по убыванию веса. Добавлять следующий элемент, если после добавления множество остаётся независимым.

MST

— графовый матроид → алгоритм Крускала оптимален ✓.

Задача назначения

— двудольный граф G, нужно выбрать k рёбер, не инцидентных одной вершине (= паросочетание размера k). Это пересечение двух матроидов разбиения! → полиномиально решаемо (алгоритм Эдмондса).

Задача Хаффмана

— оптимальный префиксный код для сжатия. Жадный алгоритм Хаффмана оптимален — структура матроидная.

Задача

— найти максимальное независимое множество I ∈ I₁ ∩ I₂ (пересечение двух матроидов).

Алгоритм

— O(r² · T_oracle), где r — ранг, T_oracle — время проверки независимости. Полиномиально!

Пересечение 3 матроидов

— NP-трудно. Это граница полиномиальной разрешимости.

Жадный алгоритм принимает локально наилучшее решение на каждом шаге, не пересматривая прошлых решений. Просто и быстро — но не всегда оптимально. Жадный алгоритм для задачи о рюкзаке даёт не оптимум. Жадный алгоритм Крускала для MST — даёт оптимум. Почему? Ответ — матроидная структура задачи. Мат...

Алгоритм Крускала: сортируем рёбра по весу. Жадно добавляем минимальное ребро, не создающее цикл.

Лемма об отсечении (Cut Lemma): для любого разреза (S, V∖S) минимальное ребро через разрез входит в MST.

Доказательство: пусть e* — минимальное ребро через разрез, и T — MST, не включающее e*. Добавим e* в T → образуется цикл, который пересекает разрез как минимум в одном другом ребре e'. Так как e* минимально в разрезе: w(e*) ≤ w(e'). Заменим e' на e* в T → новое дерево T' с весом w(T') ≤ w(T). Но ...

Определения

Определение

— алгоритм Aε — PTAS, если:

Теорема

— это (1+ε)-аппроксимация. Доказательство: потери от масштабирования ≤ ε · OPT/n за предмет, суммарно ≤ ε · OPT.

Задача о рюкзаке — FPTAS

— масштабирование дает время O(n³/ε) = O(n² · n/ε) — полиномиально по n и 1/ε!

Задача расписания P||Cmax — FPTAS

— FPTAS существует через аналогичное масштабирование времён.

Доказательство

— Если бы PTAS для TSP существовал, то Hamiltonian Cycle (гамильтоновский цикл) был бы решаем в полиномиальное время. Hamiltonian Cycle — NP-полная задача.

Теорема (Ароre, 1998)

— для n точек в евклидовой плоскости, TSP имеет PTAS со временем O(n log^{O(1/ε)} n).

Ключевая идея

— рандомизированное разбиение плоскости на квадраты и «порталы». Оптимальный маршрут, проходящий через порталы, аппроксимирует произвольный. ДП по квадрантам даёт точное решение для «портального» TSP.

P||Cmax

— n задач на m машинах. Минимизировать makespan (время до завершения всех задач).

PTAS (Hochbaum-Shmoys, 1987)

— разделить на «длинные» (время > ε · OPT) и «короткие».

Практическое значение

— при ε = 0.1: время O(n + m^{10}). При n = 1000, m = 5: 5^{10} ≈ 10⁷ — за секунды! При ε = 0.01: 5^{100} ≈ 10^{70} — нереально. FPTAS нет для P||Cmax (APX-трудная).

Обычный аппроксимационный алгоритм даёт фиксированную гарантию: например, 2-аппроксимация. Но что, если нам нужно точнее — скажем, 1.01-аппроксимация? PTAS (Polynomial-Time Approximation Scheme) — это не один алгоритм, а целое семейство алгоритмов Aε, параметризованное точностью ε > 0: Aε находит...

Важно: зависимость от ε может быть произвольной. Например, O(n^{1/ε}) — PTAS, но O(2^{1/ε}·n) — тоже PTAS.

1. Находим максимальную ценность cmax = max cᵢ 2. Масштабируем: c̃ᵢ = ⌊cᵢ · n/(ε · cmax)⌋ (округляем вниз) 3. Решаем ДП с масштабированными ценностями: время O(n · Σc̃ᵢ) = O(n · n²/ε) = O(n³/ε) 4. Возвращаем найденный набор предметов

Теорема: это (1+ε)-аппроксимация. Доказательство: потери от масштабирования ≤ ε · OPT/n за предмет, суммарно ≤ ε · OPT.

Определения

Выбор окрестности — ключевой вопрос

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

Окрестность 2-opt

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

Практика

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

3-opt

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

Lin-Kernighan (LK)

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

Идея

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

Мотивация

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

Критерий аспирации

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

Города

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

Итог

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

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

Алгоритм: 1. Текущее решение s = s₀ 2. Пока N(s) содержит лучшее решение s': 3. Возврат s (локальный оптимум)

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

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

Определения

Вероятность принятия ухудшения

— exp(−Δ/T). При T → ∞: вероятность → 1 (принимаем любой шаг, случайное блуждание). При T → 0: вероятность → 0 (принимаем только улучшения, обычный ЛП).

Ключевое свойство

— при высокой T алгоритм «исследует» пространство решений, при низкой — «эксплуатирует» найденные хорошие решения.

Теорема Гемана-Гемана (1984)

— если T(k) = C/log(1+k) (логарифмическое охлаждение), SA сходится к глобальному оптимуму с вероятностью 1.

Практическая сходимость

— SA находит хорошие (но не гарантированно оптимальные) решения за разумное время. Для TSP: туры в 1-2% от оптимума за секунды.

Начальная температура T₀

— выбирается так, чтобы начальный «acceptance rate» ≈ 80-90%. Например, можно запустить 1000 случайных шагов, вычислить среднее ухудшение Δ̄, и выбрать T₀ так, чтобы exp(−Δ̄/T₀) = 0.8.

Темп охлаждения α

— компромисс между качеством и временем. α = 0.99 → длинный прогон, хорошее качество. α = 0.9 → быстро, хуже качество.

Число итераций Lₖ при каждой температуре

— часто Lₖ = n (размер задачи). Больше итераций при одной температуре → лучше «равновесие».

Критерий остановки

— T < T_min, или нет улучшений за последние k·Lₖ итераций.

Задача

— n компонентов на чипе, минимизировать суммарную длину соединительных проводников. Это задача размещения (Placement Problem) в VLSI (Very Large Scale Integration).

Историческое значение

— SA был впервые применён именно для VLSI Layout — IBM, 1983 (Kirkpatrick, Gelatt, Vecchi). Статья в Science — одна из самых цитируемых в информатике. SA сокращал длину проводников на 10-20% по сравнению с детерминированными методами.

Современные VLSI tools

— SA по-прежнему основа, но с десятками улучшений: адаптивная температура, параллельные прогоны, «перезапуск» при застревании.

Вывод

— SA подходит для задач с большим числом локальных оптимумов, где важна простота реализации. Tabu — для структурированных задач с выраженной «памятью». Для TSP лучше всего — LK-эвристик.

В металлургии «отжиг» — нагрев металла до высокой температуры и медленное охлаждение. При высокой температуре атомы имеют много энергии и могут «перепрыгивать» через энергетические барьеры, находя лучшую кристаллическую структуру. При медленном охлаждении — оседают в глобальном минимуме энергии (...

Идея метаэвристики Simulated Annealing (SA): имитировать этот процесс! Алгоритм принимает «ухудшающие» шаги с убывающей вероятностью — это позволяет «вырываться» из локальных оптимумов и в итоге найти глобальный.

Алгоритм: 1. s = s₀ (начальное решение), T = T₀, BestS = s₀ 2. Пока T > T_min: a. Повторить Lₖ раз: b. T ← α · T 3. Вернуть BestS

Вероятность принятия ухудшения: exp(−Δ/T). При T → ∞: вероятность → 1 (принимаем любой шаг, случайное блуждание). При T → 0: вероятность → 0 (принимаем только улучшения, обычный ЛП).

Определения

Хромосома (особь)

— кодировка решения в виде вектора. Для TSP — перестановка городов. Для задачи рюкзака — бинарная строка.

Приспособленность (fitness)

— значение целевой функции. В GA обычно работаем с максимизацией, поэтому: fitness = −cost для задач минимизации.

Задача

— хромосома = перестановка городов π = (π₁, π₂, ..., πₙ). Кроссовер должен давать корректные перестановки (каждый город ровно один раз).

Пример

— P1 = (1,2,3,4,5), P2 = (3,4,1,5,2), отрезок [2,4].

Schema Theorem (Холланд)

— шаблон H, имеющий выше среднего приспособленность f̄(H) > f̄_pop (среднее по популяции), растёт экспоненциально в следующем поколении:

Интерпретация

— «хорошие, короткие, старательные» шаблоны экспоненциально растут. Это основа теории «строительных блоков» (building blocks).

Результат

— MA для TSP значительно лучше чистого GA или чистого LS:

Применения NSGA-II

— аэрокосмическая инженерия (оптимизация конструкций), химическая промышленность (оптимизация реакторов), финансы (фронт риск-доходность), электроника (схемотехническая оптимизация). Это индустриальный стандарт многокритериальной оптимизации.

Природная эволюция решила «задачу оптимизации» колоссальной сложности: создать существ, способных выживать в меняющейся среде. Механизм: случайные мутации, рекомбинация генов (кроссовер), естественный отбор. Генетические алгоритмы (GA) имитируют этот процесс для оптимизации. Вместо одной «частицы...

Хромосома (особь): кодировка решения в виде вектора. Для TSP — перестановка городов. Для задачи рюкзака — бинарная строка.

Приспособленность (fitness): значение целевой функции. В GA обычно работаем с максимизацией, поэтому: fitness = −cost для задач минимизации.

Задача: хромосома = перестановка городов π = (π₁, π₂, ..., πₙ). Кроссовер должен давать корректные перестановки (каждый город ровно один раз).