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

Tabu Search — Метаэвристика локального поиска

Автор метода
Fred Glover
Год
1989
Тип
Local-search metaheuristic

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

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

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

Tabu Search — это метаэвристика локального поиска, представленная Фредом Гловером в 1989 году, которая использует список запретов (tabu list) — кратковременную память недавно посещенных решений — для предотвращения зацикливания и выхода из локальных оптимумов.

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

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

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

История

Tabu Search был представлен Фредом Гловером в знаковом труде 1989 года в журнале ORSA Journal on Computing, где он был представлен как стратегия управления локальным поиском путем использования памяти о прошлых ходах. Фундаментальные идеи были консолидированы и расширены в монографии Гловера и Лагуны 1997 года, изданной Springer, которая установила канонический краткосрочный список запретов, критерии аспирации, а также долговременные стратегии диверсификации и интенсификации, которые остаются центральными для этого метода и сегодня. С момента своего появления Tabu Search широко применялся в исследовании операций, планировании, логистике и комбинаторном дизайне, и он продолжает оставаться стандартной эталонной метаэвристикой наряду с имитацией отжига и генетическими алгоритмами.

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

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

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

  • Производительность чувствительна к определению окрестности и сроку действия запрета; плохой выбор может привести к застреванию поиска или его зацикливанию, несмотря на механизм запретов.
  • Требует минимального бюджета итераций — обычно более 1000 итераций — для достаточного исследования окрестности; при слишком малом количестве итераций результаты не лучше, чем при простом локальном поиске.
  • Список запретов хранит атрибуты ходов, а не полные решения, поэтому критерий аспирации необходим, чтобы предотвратить непреднамеренное блокирование действительно хороших ходов.
  • В отличие от точных решателей, Tabu Search не гарантирует оптимальности, и качество результата может варьироваться от запуска к запуску, если начальное решение или окрестность стохастичны.

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

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

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

Применение

  • Планирование производственных процессов (job-shop и flow-shop) — оптимизация последовательности операций для минимизации времени выполнения или опоздания.
  • Маршрутизация транспортных средств — поиск эффективных маршрутов доставки с учетом ограничений по грузоподъемности и временным окнам.
  • Распределение и размещение объектов — назначение задач ресурсам или размещение объектов для минимизации затрат.
  • Раскраска графов, проектирование сетей и телекоммуникации — решение дискретных задач структурной оптимизации.
  • Отбор признаков и поиск гиперпараметров — исследование дискретных пространств конфигураций в конвейерах машинного обучения.

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

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

1

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

2

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

3

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

4

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

5

После выполнения хода список запретов обновляется путем добавления обратного хода (или его характеризующего атрибута) к только что сделанному ходу, и старейшая запись удаляется, если список заполнен, сохраняя свою фиксированную длину — срок действия запрета (tabu tenure). Если новое решение лучше, чем лучшее записанное решение, лучшее решение обновляется. Опциональные долговременные структуры памяти могут отслеживать частоту или недавность решений для направления диверсификации в менее посещаемые области или интенсификации вокруг перспективных.

6

Алгоритм продолжает итерации до тех пор, пока не будет достигнут критерий остановки: максимальное количество итераций, целевое значение целевой функции или фиксированное количество итераций без улучшения. Лучшее решение, найденное за все время поиска, возвращается в качестве результата. Выбор адекватного бюджета итераций имеет решающее значение — слишком мало итераций препятствует достаточному исследованию окрестности.

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

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

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

Чем Tabu Search отличается от имитации отжига?

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

Каким должен быть размер списка запретов?

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

Гарантирует ли Tabu Search нахождение глобального оптимума?

Нет. Tabu Search — это метаэвристика, и она не дает гарантии оптимальности. Она стремится эффективно находить высококачественные решения, но результат зависит от структуры окрестности, срока действия запрета, количества итераций и начального решения. Для гарантии оптимальности требуется точный метод, такой как целочисленное программирование, хотя точные методы могут быть вычислительно невыполнимы для больших экземпляров.

Что такое критерий аспирации и почему он необходим?

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

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

Источники

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Открыть ссылку на публикацию
    Скопировано.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN: 9780792349907
    Скопировано.