Эвристика поиска с запретами (Tabu Search): память в локальной оптимизации

Классические методы локального поиска (Local Search) — это жадные алгоритмы, которые пытаются улучшить текущее решение, переходя к наилучшему варианту в его ближайшей окрестности. Их фатальный недостаток заключается в том, что как только они достигают дна любой локальной впадины целевой функции, из которой нет путей вниз, они останавливаются, принимая этот локальный оптимум за глобальный. Чтобы научить компьютер выбираться из таких математических ловушек, в конце 1980-х годов Фред Гловер разработал алгоритм Поиска с запретами (Tabu Search). Внедрение механизма искусственной памяти позволило алгоритмам целенаправленно преодолевать барьеры ухудшения целевой функции без риска зацикливания.

Математическая философия Tabu Search заключается во временном запрете на возврат к недавно посещенным состояниям. Когда алгоритм спускается на дно локального оптимума, он вынужден сделать шаг вверх (выбрать ухудшающее решение), чтобы продолжить исследование ландшафта. Без механизма памяти на следующем шаге жадный алгоритм немедленно вернулся бы обратно на дно, породив бесконечный цикл. Алгоритм Гловера решает эту проблему введением Краткосрочной памяти (Табу-списка). В этот список записываются атрибуты последних сделанных ходов (например, запрет на удаление только что добавленного ребра в графе или запрет на перестановку двух конкретных работ в расписании). Длина этого списка (Tabu Tenure) является критическим гиперпараметром: если список слишком короткий, алгоритм зациклится; если слишком длинный — область поиска будет неоправданно ограничена.

Однако жесткий запрет может случайно заблокировать доступ к неисследованной зоне, содержащей истинный глобальный оптимум. Для предотвращения таких ситуаций вводится Критерий устремления (Aspiration Criterion). Этот логический переключатель позволяет алгоритму проигнорировать табу-статус хода. Самое популярное правило гласит: если табу-ход позволяет достичь решения, которое математически лучше абсолютно лучшего решения, найденного за всю историю поиска, алгоритм нарушает запрет и совершает этот ход. Это гарантирует, что система никогда не пройдет мимо глобального рекорда из-за формальных ограничений краткосрочной памяти.

Для исследования колоссальных комбинаторных пространств (таких как планирование маршрутов на тысячи городов) Tabu Search применяет механизмы долгосрочной памяти: интенсификацию и диверсификацию. Интенсификация (Intensification) анализирует матрицу частоты: если определенные элементы часто встречаются в лучших найденных решениях, алгоритм искусственно сужает область поиска, чтобы тщательно прочесать этот перспективный регион. Диверсификация (Diversification) действует наоборот: если алгоритм слишком долго топчется на месте, система штрафует часто посещаемые состояния и принудительно забрасывает точку поиска в совершенно неисследованные дебри пространства, заставляя алгоритм генерировать радикально новые решения.

Эвристика поиска с запретами не имеет строгого математического доказательства сходимости к глобальному оптимуму за полиномиальное время (что типично для всех метаэвристик). Тем не менее, на практике Tabu Search стал индустриальным стандартом для решения сложных задач целочисленной оптимизации. Алгоритм демонстрирует выдающиеся результаты в задачах раскраски графов (выделение радиочастот), составлении расписаний спортивных чемпионатов (минимизация перелетов команд) и маршрутизации флотилий морских танкеров. Использование адаптивных списков запретов, длина которых динамически меняется в процессе поиска, делает этот метод одним из самых гибких и интеллектуальных инструментов в арсенале современного исследования операций.

Оценить