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

Robust Tabu Search — метаэвристика на основе табу-поиска с робастностью к неопределенности

Автор метода
Glover, F. (Tabu Search); robustness extensions by various authors
Год
1989 (TS); robust variant ~2000s
Тип
Metaheuristic with robustness mechanism
Семейство
Simulation / optimization

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

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

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

Robust Tabu Search (RTS) расширяет классическую метаэвристику Tabu Search, оценивая кандидатные решения не только по их номинальной целевой величине, но и по их производительности в условиях неопределенности.

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

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

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

История

Tabu Search был представлен Фредом Гловером в 1989–1990 годах как метаэвристика, основанная на памяти, которая выходит из локальных оптимумов, запрещая недавно обращенные ходы. Робастные расширения появились в конце 1990-х и 2000-х годах на фоне растущего интереса к робастной оптимизации; исследователи включили сценарные и наихудшие оценки в оценку соседства TS, породив Robust Tabu Search как практический инструмент для задач инженерии и логистики в условиях неопределенности.

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

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

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

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

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

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

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

Применение

  • Робастная маршрутизация транспортных средств при стохастическом времени в пути или спросе клиентов
  • Составление расписаний для цеховых и поточных производств с неопределенным временем обработки
  • Проектирование сетей и планирование мощностей при колебаниях спроса
  • Оптимизация цепочек поставок при неопределенном времени выполнения заказов поставщиками или затратах
  • Назначение частот в телекоммуникациях при неопределенности помех
  • Оптимизация портфеля с неопределенной доходностью активов с использованием комбинаторных ограничений

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

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

1

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

2

Для каждого кандидатного решения x, встреченного во время поиска, оценить его цель f(x, s) при каждом сценарии s из S. Вычислить меру робастности R(x) — например, R(x) = max_{s in S} f(x,s) для робастности по принципу минимума максимума, или R(x) = E[f(x,s)] + lambda * Var[f(x,s)] для робастности по среднему и дисперсии. Это заменяет единичную номинальную оценку, используемую в классическом Tabu Search.

3

Сгенерировать соседство N(x) текущего решения x путем применения всех допустимых ходов (обмены, вставки, обращения и т. д.). Оценить R(x') для каждого соседа x', исключая ходы, находящиеся в данный момент в списке табу, если только не выполняется критерий аспирации. Выбрать соседа x* с наилучшим значением робастности R(x*).

4

Перейти к x* и записать обратный ход в список табу с временем жизни t (обычно 5–20 итераций). Список табу предотвращает зацикливание и поощряет исследование. Критерии аспирации — такие как принятие хода из списка табу, если он дает наилучшее глобальное робастное решение — могут отменить ограничение табу.

5

Обновить наилучшее известное робастное решение, если R(x*) улучшает текущее наилучшее. Продолжать итерации до выполнения критерия остановки: максимальное количество итераций, истекшее время или отсутствие улучшения за предписанное количество шагов. Вернуть наилучшее найденное робастное решение вместе с его профилем производительности по сценариям.

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

  • Использование слишком малого количества сценариев недооценивает истинную неопределенность и приводит к решениям, которые кажутся робастными, но терпят неудачу на практике.
  • Смешение Robust Tabu Search со Stochastic Tabu Search: робастная оптимизация минимизирует подверженность наихудшим случаям, в то время как стохастический TS использует выборку для аппроксимации ожидаемого значения — цели и интерпретации различаются.
  • Применение робастности по принципу минимума максимума, когда сценарий наихудшего случая имеет незначительную вероятность, приводит к чрезмерно консервативным решениям при ненужных затратах.
  • Игнорирование критериев аспирации может привести к тому, что поиск упустит глобально робастные решения, которые случайно включают ходы из списка табу.
  • Установка слишком большого времени жизни табу создает чрезмерные ограничения; слишком малое вызывает зацикливание — оба фактора ухудшают качество решения.

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

Чем Robust Tabu Search отличается от Stochastic Tabu Search?

Stochastic Tabu Search обычно использует случайную выборку в самой процедуре поиска (например, вероятностное принятие или случайную выборку соседства) для аппроксимации ожидаемых значений. Robust Tabu Search явно оптимизирует критерий робастности — такой как производительность в наихудшем случае или по среднему и дисперсии — оцениваемый по заданному множеству неопределенности. Цель в робастном TS — стабильность решения по сценариям, а не просто ожидаемая производительность.

Насколько большим должен быть набор сценариев S?

Универсального правила нет. Для дискретных множеств неопределенности перечислите все правдоподобные сценарии, если это возможно. Для непрерывных распределений 50–500 выборочных сценариев часто обеспечивают адекватное покрытие; методы снижения дисперсии, такие как выборка Латинского гиперкуба, могут повысить эффективность. Анализ чувствительности по |S| рекомендуется перед принятием решения о количестве сценариев.

Может ли Robust Tabu Search обрабатывать многокритериальные задачи?

Да. При сочетании с многокритериальными фреймворками Tabu Search робастность становится дополнительным критерием или ограничением. Можно исследовать Парето-фронты (номинальная производительность, робастность), получая набор решений, которые балансируют оптимальность и надежность — полезно, когда заинтересованные стороны должны выбирать между рискованными и нерискованными вариантами.

Какой критерий робастности следует выбрать?

Минимум максимума (наихудший случай) подходит, когда отказы катастрофичны, и даже маловероятные плохие исходы недопустимы. Ожидаемое значение подходит для нейтральных к риску лиц, принимающих решения. Среднее и дисперсия балансируют среднюю производительность и изменчивость и распространены в проектировании. Метрики Value-at-Risk (VaR) или Conditional VaR используются в финансовых и логистических приложениях, где важны гарантии на основе процентилей.

Подходит ли Robust Tabu Search для очень больших экземпляров?

Это зависит от стоимости оценки сценария. Если каждая оценка f(x,s) дешева (миллисекунды), робастность по сотням сценариев остается трактуемой даже для больших экземпляров. Если каждая оценка требует симуляции или дорогостоящего вызова решателя, становятся необходимыми агрессивное сокращение сценариев или суррогатные модели. Параллельная оценка сценариев на потоках или машинах является распространенным смягчением.

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

Источники

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

    Открыть ссылку DOI
    Скопировано.
  2. Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.

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