Skip to content
Назад к результатам поиска

Стохастический поиск с запретами — рандомизированная метаэвристика с памятью

Автор метода
Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
Год
1990s
Тип
Stochastic metaheuristic optimizer
Семейство
Simulation / optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Стохастический поиск с запретами (Stochastic Tabu Search, STS) — это расширение классического поиска с запретами (Tabu Search), которое вводит случайность на этапах исследования окрестности и выбора перемещений.

Комбинируя память запретов (которая исключает недавно посещенные решения) с вероятностным принятием или случайной выборкой кандидатов, STS более эффективно выходит из локальных оптимумов и исследует сложные ландшафты решений, которые детерминированный TS может не преодолеть.

Интуиция метода

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

История

Поиск с запретами был формально представлен Фредом Гловером в 1986 году и подробно разработан в знаковых статьях 1989-1990 годов. Стохастические расширения появились в 1990-х годах, когда исследователи осознали, что детерминированная оценка окрестности является узким местом в крупномасштабных задачах. Случайная выборка кандидатов, вероятностное принятие перемещений и введение шума были включены для улучшения диверсификации, что привело к тому, что широко называется стохастическим поиском с запретами. Этот метод широко применяется в исследовании операций, инженерном проектировании и оптимизации гиперпараметров машинного обучения.

Когда применять

Используйте стохастический поиск с запретами при решении комбинаторных или непрерывных задач оптимизации «черного ящика» со сложными, мультимодальными ландшафтами, где детерминированный локальный поиск постоянно застревает (например, планирование, маршрутизация, выбор признаков). Он особенно ценен, когда полная оценка окрестности является вычислительно дорогой, что делает необходимым случайную подвыборку. НЕ используйте STS, когда задача выпуклая или унимодальная — градиентные или точные методы быстрее и оптимальнее. Избегайте его, когда вам нужна гарантированная глобальная оптимальность, поскольку STS не предлагает гарантии сходимости, кроме эвристически найденных лучших решений. Также избегайте, когда целевая функция дешева для полной оценки и детерминированный TS с исчерпывающим поиском соседей осуществим.

Ограничения и замечания

  • Нет теоретической гарантии нахождения глобального оптимума; качество решения сильно зависит от настроек параметров.
  • Срок действия запрета и размер списка кандидатов требуют настройки под конкретную задачу; плохой выбор приводит к преждевременной сходимости или медленному прогрессу.
  • Стохастические запуски невоспроизводимы без фиксированного случайного зерна, что усложняет бенчмаркинг и аудит.
  • Накладные расходы на память растут с размером списка запретов; для больших пространств решений требуются представления запретов на основе атрибутов.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

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

Применение

  • Маршрутизация транспортных средств и оптимизация логистики в условиях неопределенного спроса
  • Планирование работ в цехах и открытых цехах со стохастическим временем обработки
  • Выбор признаков в высокоразмерных наборах данных машинного обучения
  • Проектирование сетей и оптимизация топологии
  • Оптимизация портфеля с комбинаторными ограничениями на выбор активов
  • Настройка гиперпараметров для сложных имитационных моделей

Как это работает

Как это работает

1

Сгенерируйте начальное решение x0 (случайным образом или эвристически). Установите пустой список запретов T, определите срок действия запрета tau, лимит итераций I_max и стохастические параметры (например, размер списка кандидатов k, вероятность возмущения p_perturb).

2

На каждой итерации случайным образом выбирайте подмножество N_s из полной окрестности N(x_current), вместо того чтобы оценивать всех соседей. Это снижает затраты на итерацию и вносит стохастичность в исследуемые области пространства.

3

Выберите следующее решение x_next из N_s: либо (а) выберите лучшего не запрещенного кандидата с вероятностью 1-p_perturb, либо (б) с вероятностью p_perturb выберите случайного не запрещенного кандидата для диверсификации. Критерии аспирации могут отменять статус запрета, если x_next улучшает лучшее известное решение.

4

Добавьте x_current (или атрибут перемещения) в список запретов T. Удалите самую старую запись, если |T| > tau. Обновите текущее лучшее решение x_best, если f(x_next) < f(x_best).

5

Повторяйте выборку окрестности до обновления запретов, пока не будет достигнуто I_max итераций, не будет достигнуто целевое значение функции или не произойдет улучшений в течение окна терпения. Верните x_best как окончательное решение.

Частые ошибки

  • Установка слишком короткого срока действия запрета допускает зацикливание, несмотря на список запретов; слишком длинный срок блокирует перспективные области без необходимости.
  • Использование слишком малого списка кандидатов (агрессивная подвыборка) может привести к тому, что поиск будет постоянно пропускать хороших соседей.
  • Игнорирование критериев аспирации приводит к тому, что алгоритм отклоняет глобально улучшающие перемещения, которые оказываются запрещенными.
  • Сообщение только об одном запуске без множественных перезапусков или зерен дает вводящую в заблуждение картину типичного качества решения.
  • Смешение стохастического поиска с запретами с имитацией отжига: оба являются стохастическими, но принципиально различаются — STS использует явную память, тогда как SA использует вероятностное принятие на основе температуры без памяти.

Часто задаваемые вопросы

Чем стохастический поиск с запретами отличается от имитации отжига?

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

Сколько итераций (I_max) мне следует выполнить?

Универсального правила нет. Распространенная практика — выполнять несколько независимых испытаний (например, 10-30 перезапусков) с бюджетом, пропорциональным размеру задачи, а затем сообщать о лучших и средних результатах. Для бенчмаркинга сопоставьте общий бюджет оценки функции, используемый конкурирующими методами.

Может ли стохастический поиск с запретами обрабатывать непрерывные переменные?

Да, но это требует определения непрерывной окрестности (например, гауссово возмущение вокруг текущего решения) и подходящего атрибута для списка запретов (например, область или направление). Большая часть литературы по STS ориентирована на комбинаторные задачи; для непрерывных пространств дифференциальная эволюция или CMA-ES часто являются более естественными альтернативами.

Какова роль критериев аспирации?

Критерии аспирации отменяют статус запрета перемещения, если его принятие приводит к решению, лучшему, чем лучшее из найденных на данный момент. Без аспирации алгоритм может постоянно отклонять глобально улучшающие перемещения, которые оказываются запрещенными, что серьезно ограничивает качество решения.

Следует ли мне фиксировать случайное зерно для воспроизводимости?

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

Похожие методы

Источники

  1. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.

    Открыть ссылку DOI
    Скопировано.
  2. Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.

    Открыть ссылку DOI
    Скопировано.