Эвристические алгоритмы — устные вопросы 23–24

Суть

Стохастический метод глобальной оптимизации по аналогии с охлаждением металла. Главная идея — иногда принимать ухудшающие решения, чтобы выйти из локального минимума. На высокой температуре алгоритм исследует пространство (допускает плохие переходы), на низкой — становится жадным (только улучшения).

Правило принятия

Если f(x′) < f(x) — принять всегда. Иначе принять с вероятностью P = exp(−(f(x′) − f(x)) / T).

x = initial_solution
T = initial_temperature
while T > Tmin:
    x_new = random_neighbor(x)
    dE = f(x_new) - f(x)
    if dE < 0: x = x_new
    else: accept with probability exp(-dE / T)
    decrease_temperature()
return best_solution

Расписания понижения температуры

• Геометрическое (основное): T_{k+1} = α·T_k, 0.8 ⩽ α ⩽ 0.999.
• Линейное (редко): T_{k+1} = T_k − c.
• Логарифмическое (медленно, но гарантирует сходимость): T_k = C / log(1+k).

Применение к TSP

Решение = перестановка городов. Стоимость = длина маршрута. Соседи = инверсия отрезка пути / случайное перемешивание подмножества.

Суть

Эволюционная оптимизация: поддерживаем популяцию решений-кандидатов и улучшаем её через отбор / скрещивание / мутацию. Полезен для огромных дискретных пространств, отсутствия гладкости, множества локальных экстремумов, NP-трудных задач.

Fitness

Каждое решение оценивается fitness-функцией F(x). Для минимизации часто F(x) = 1 / (1 + f(x)).

Цикл алгоритма

1. Инициализация популяции (часто случайные решения).
2. Оценка fitness.
3. Отбор родителей (лучшие кандидаты).
4. Скрещивание (crossover).
5. Мутация (случайные модификации — поддерживают разнообразие).
6. Формирование нового поколения.
7. Повтор до критерия останова.

Применение к TSP

Решение = перестановка городов. Мутация = инверсия отрезка. Скрещивания, сохраняющие корректность перестановки:

• PMX (Partially Matched Crossover): выбираем две точки, копируем средний сегмент, остальные элементы восстанавливаем через отображение.
• OX (Order Crossover): копируем подотрезок, остальные города добавляем в порядке второго родителя.