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

Робастный NSGA-II — Многокритериальная оптимизация в условиях неопределенности

Автор метода
Kalyanmoy Deb and Himanshu Gupta
Год
2006
Тип
Robust evolutionary multi-objective optimization algorithm
Семейство
Simulation / optimization

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

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

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

Робастный NSGA-II расширяет классический эволюционный алгоритм NSGA-II для учета параметрической неопределенности, находя Парето-оптимальные компромиссные решения, которые остаются высокопроизводительными даже при отклонении входных параметров от их номинальных значений.

Вместо оптимизации значений целевых функций в одной точке, он оценивает каждое кандидатное решение в диапазоне или распределении реализаций неопределенности и отбирает решения по робастности наряду с Парето-доминированием.

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

На практике инженерные расчеты и политические решения сталкиваются с неопределенными условиями эксплуатации: свойства материалов варьируются, прогнозы спроса отличаются от реальности, а нагрузки окружающей среды колеблются. Решение, которое выглядит оптимальным при номинальных значениях параметров, может показывать плохие результаты при правдоподобных отклонениях. Робастный NSGA-II решает эту проблему, оценивая каждое кандидатное решение не только в его проектной точке, но и в окрестности или выборке сценариев неопределенности, а затем используя математическое ожидание и дисперсию (или наихудшее производительность) каждой целевой функции в качестве критериев отбора. Таким образом, алгоритм обменивает небольшую потерю в номинальной производительности на большой прирост надежности, выдавая Парето-фронт решений, которые являются одновременно конкурентоспособными и стабильными в условиях неопределенности.

История

Робастный NSGA-II возник из фреймворка робастной многокритериальной оптимизации, формализованного Дебом и Гуптой в 2006 году, которые ввели явные метрики робастности в механизм отбора NSGA-II. Фундаментальный алгоритм NSGA-II был опубликован Дебом, Пратапом, Агарвалом и Меяриваном в 2002 году. Последующие работы исследователей в области инженерного проектирования, исследования операций и энергетических систем расширили фреймворк на задачи со стохастическими ограничениями, смешанными типами неопределенности и оценкой робастности с использованием суррогатов.

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

Использовать Робастный NSGA-II, когда многокритериальная задача включает неопределенные параметры (свойства материалов, спрос, затраты, условия окружающей среды), и решения должны оставаться приемлемыми при правдоподобных отклонениях от номинальных значений, а не только в одной проектной точке. Он подходит для инженерного проектирования, планирования цепочек поставок при неопределенности спроса и оптимизации энергетических систем со стохастической генерацией. Избегайте его, когда вычислительные бюджеты очень ограничены, поскольку оценка M выборок неопределенности на особь в каждом поколении умножает затраты на оценку функций на M. Также избегайте его, когда неопределенности незначительны по сравнению с вариацией целевых функций, или когда возможны только две или три оценки целевых функций на кандидата — стандартный NSGA-II или методы с использованием суррогатов тогда более эффективны.

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

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

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

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

  • Производит Парето-оптимальные решения, которые явно проверены на хорошую производительность в условиях неопределенности, снижая риск получения решений, которые плохо работают на практике.
  • Наследует быструю не-доминирующую сортировку и элитизм NSGA-II, гарантируя, что робастно не-доминируемые решения никогда не будут отброшены между поколениями.
  • Гибкость в метрике робастности: математическое ожидание, штраф за дисперсию, наихудший случай или вероятностное ограничение могут быть подставлены в зависимости от предпочтений в отношении риска.
  • Работает как для непрерывных, так и для дискретных пространств решений без модификации основного механизма отбора.
  • Предоставляет лицам, принимающим решения, набор компромиссных вариантов, различающихся как по балансу многокритериальности, так и по уровню робастности, поддерживая информированное выражение предпочтений.

Применение

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

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

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

1

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

2

Для каждого кандидатного решения x в популяции извлечь M реализаций неопределенности из заданных распределений параметров (или перечислить структурированную окрестность). Оценить все целевые функции при каждой реализации и агрегировать результаты в робастные оценки целевых функций. Общая агрегация: использовать среднее как оценку робастности для ожидаемой производительности и добавить штраф, пропорциональный стандартному отклонению, для учета дисперсии, так что робастная целевая функция становится f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)].

3

Применить быструю не-доминирующую сортировку к популяции, используя робастные оценки целевых функций вместо номинальных значений. Присвоить каждому решению не-доминирующий фронт F1, F2 и т.д. на основе Парето-доминирования робастных целевых функций. Решения в F1 робастно не-доминируемы: ни одно другое решение не лучше по всем робастным целевым функциям одновременно.

4

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

5

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

6

Объединить родительскую популяцию P и потомков Q в общий пул из 2N решений. Пересортировать по робастному не-доминированию и расстоянию скученности. Выбрать лучшие N особей для формирования следующего поколения, сохраняя элитизм. Прекратить выполнение, когда достигнут максимальный предел поколений, гиперобъем стагнирует или исчерпан вычислительный бюджет. Вернуть финальный робастный Парето-фронт F1.

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

  • Использование слишком малого количества выборок неопределенности на оценку (M менее 20-30) вносит шум оценки, который искажает ранжирование по не-доминированию и приводит к ненадежному робастному Парето-фронту.
  • Смешение робастности значений целевых функций с робастностью оптимальных решений: решение, робастное в пространстве целевых функций, все еще может требовать точных значений переменных решения, которые трудно реализовать.
  • Применение стандартного расстояния скученности NSGA-II в пространстве робастных целевых функций без проверки, находятся ли робастные целевые функции на соизмеримых шкалах; нормализовать целевые функции перед вычислением расстояний.
  • Запуск одной репликации и рассмотрение результата как окончательного; всегда запускать несколько независимых репликаций и сообщать статистику гиперобъема для учета стохастической вариации.
  • Выбор лямбда (веса штрафа за дисперсию) ad hoc без анализа чувствительности; выбранная лямбда неявно кодирует отношение к риску, которое должно быть сделано явным и обоснованным.

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

Чем Робастный NSGA-II отличается от стандартного NSGA-II?

Стандартный NSGA-II оценивает каждое кандидатное решение при его номинальных значениях параметров и использует эти значения целевых функций для Парето-доминирования. Робастный NSGA-II оценивает каждое решение по M реализациям неопределенных параметров, агрегирует результаты в робастные оценки целевых функций (например, среднее и дисперсию) и использует эти оценки для ранжирования по доминированию. Это увеличивает вычислительную стоимость в M раз, но дает решения, которые остаются конкурентоспособными при отклонении параметров от номинальных значений.

Сколько выборок неопределенности M следует использовать на особь?

Универсального правила нет. Общая отправная точка — M = 30-50 выборок Монте-Карло, если оценки целевых функций дешевы. Для дорогих оценок может потребоваться M = 5-10. Проведите исследование чувствительности: увеличьте M до тех пор, пока робастные оценки целевых функций не стабилизируются. Квазислучайная выборка (латинский гиперкуб или Соболь) обеспечивает лучшее покрытие, чем чисто случайная выборка, при том же M.

Могу ли я использовать Робастный NSGA-II с более чем тремя целевыми функциями?

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

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

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

Как проверить, что возвращенные решения действительно робастны?

После завершения работы алгоритма переоцените каждое решение из Парето-фронта с помощью нового, большого набора выборок неопределенности (например, M = 1000), независимого от выборок, использованных во время оптимизации. Проверьте, соответствуют ли средние значения и дисперсии целевых функций оценкам, полученным в ходе эволюционного прогона. Большие расхождения указывают на то, что M было слишком мало во время оптимизации, или что модель неопределенности была неверно специфицирована.

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

Источники

  1. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

    Открыть ссылку DOI
    Скопировано.
  2. Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.

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