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

Робастный имитированный отжиг — поиск решений, остающихся хорошими в условиях неопределенности

Автор метода
Kirkpatrick, Gelatt & Vecchi (SA basis); robust formulation developed across the operations research community
Год
1983 (SA); robust variant emerged 1990s–2000s
Тип
Metaheuristic with robustness evaluation
Семейство
Simulation / optimization

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

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

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

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

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

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

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

История

Имитированный отжиг был представлен Киркпатриком, Гелаттом и Векки (1983) на основе алгоритма Метрополиса для статистической механики. В 1990-х и 2000-х годах, по мере роста значимости робастной оптимизации — формализованной, в частности, Бен-Талом и Немировским — исследователи начали встраивать критерии робастной оценки в циклы поиска SA для решения задач оптимизации в условиях неопределенности, породив робастный SA как признанную практическую основу в исследовании операций и инженерном проектировании.

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

Использовать Robust SA при оптимизации систем со значительной неопределенностью параметров (изменчивость поставок, колебания спроса, шум измерений), где решение, которое номинально оптимально, но хрупко, неприемлемо. Он хорошо подходит для комбинаторных и непрерывных задач умеренного и большого размера, где точная робастная оптимизация вычислительно неподъемна. Предпочитать RSA обычному SA, когда заинтересованные стороны требуют гарантий или доверительных интервалов качества решения. Избегать RSA, когда неопределенность незначительна, когда внутренняя оценка робастности непомерно дорога по сравнению с доступными вычислительными ресурсами, или когда задача является выпуклой и поддается точным методам робастного программирования.

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

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

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

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

  • Обрабатывает невыпуклые, недифференцируемые и комбинаторные пространства решений, где точная робастная оптимизация неразрешима.
  • Гибкий критерий робастности: наихудший случай, математическое ожидание, CVaR или сожаление могут быть встроены без перестройки алгоритма.
  • Вероятностное принятие худших решений помогает выходить из локальных оптимумов в ландшафте робастной целевой функции, улучшая качество решения по сравнению с жадным робастным поиском.
  • Концептуально прост в реализации путем дополнения любой существующей кодовой базы SA оберткой для оценки сценариев.
  • Применим к широкому спектру областей: планирование, маршрутизация, выбор местоположения объектов, инженерное проектирование и оптимизация финансовых портфелей.

Применение

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

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

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

1

Определить задачу оптимизации с неопределенными параметрами: целевая функция f(x, xi), где x — вектор решений, а xi представляет неопределенные входные данные. Задать множество неопределенности или распределение вероятностей для xi. Выбрать критерий робастности: наихудший случай (минимакс), математическое ожидание, условное значение под риском или максимальное сожаление.

2

Для каждого кандидатного решения x вычислить меру робастности R(x), оценивая f(x, xi) по выборке или перечислению реализаций неопределенности. Для робастности на основе сценариев R(x) = max_s f(x, xi_s); для стохастической робастности R(x) = E[f(x, xi)]. Эта внутренняя оценка сама по себе может потребовать выборки Монте-Карло или перечисления сценариев.

3

Инициализировать допустимым начальным решением x_0 и начальной температурой T_0. На каждой итерации сгенерировать соседнее решение x' с помощью специфического для задачи оператора перемещения (например, обмен, возмущение). Оценить R(x') с использованием выбранной меры робастности.

4

Принять соседнее решение x' безусловно, если R(x') улучшает R(x). Принять ухудшающий шаг с вероятностью exp(-(R(x') - R(x)) / T), где T — текущая температура. Это правило принятия Метрополиса позволяет выходить из локальных оптимумов в ландшафте робастной целевой функции.

5

Уменьшить температуру согласно графику охлаждения, обычно геометрическое охлаждение T_{k+1} = alpha * T_k с alpha в диапазоне (0.9, 0.99), или адаптивные графики, которые настраиваются на основе частоты принятия. Продолжать до выполнения критерия остановки: максимальное количество итераций, минимальный порог температуры или стагнация.

6

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

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

  • Использование слишком малого количества выборок сценариев в оценке робастности вносит шум в критерий принятия, заставляя алгоритм преследовать ложно 'робастные' решения.
  • Слишком быстрое охлаждение (высокое альфа) приводит к преждевременной сходимости к локальному робастному оптимуму; слишком медленное охлаждение увеличивает время выполнения без пропорционального прироста качества.
  • Смешение номинальной оптимальности с робастной оптимальностью: сообщение о номинально лучшем встреченном решении вместо робастно лучшего решения сводит на нет цель метода.
  • Игнорирование компромисса между робастностью и оптимальностью в отчетности: всегда раскрывайте как R(x*), так и f(x*, xi_nominal), чтобы читатели могли оценить, чем пришлось пожертвовать ради робастности.

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

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

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

Сколько сценариев необходимо в оценке робастности?

Это зависит от структуры неопределенности и требуемой точности. Для дискретных наборов сценариев перечислите все или наиболее неблагоприятные сценарии. Для непрерывных распределений 50–500 выборок Монте-Карло на оценку являются обычным явлением на практике, при этом используются диагностические средства для обоснования размера выборки. Большее количество выборок улучшает точность, но пропорционально увеличивает время выполнения.

Может ли Robust SA обрабатывать несколько целей наряду с робастностью?

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

Когда следует предпочесть Robust SA перед Robust Tabu Search или Robust GA?

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

Полезно ли параллельное внедрение?

Да. Внутренняя оценка робастности (выборка сценариев) легко распараллеливается: все сценарии для кандидатного решения могут быть оценены параллельно. Параллелизация этого внутреннего цикла существенно сокращает время выполнения без изменения логики алгоритма.

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

Источники

  1. Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.

    Открыть ссылку DOI
    Скопировано.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

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