Стохастический NSGA-II — Эволюционная многокритериальная оптимизация в условиях неопределенности
- Автор метода
- Deb, K. et al. (NSGA-II base); Hughes, E. J. and subsequent researchers for stochastic extensions
- Год
- 2001–2002
- Тип
- Evolutionary multi-objective optimization under uncertainty
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Стохастический NSGA-II расширяет эволюционный алгоритм NSGA-II для обработки целевых функций, которые являются зашумленными, неопределенными или вероятностными.
Усредняя или выбирая стохастические цели по нескольким оценкам, он идентифицирует Парето-оптимальные решения, устойчивые к неопределенности, что делает его подходящим для задач проектирования, оптимизации цепочек поставок и политики, где важна реальная изменчивость.
Интуиция метода
NSGA-II является одним из наиболее эффективных алгоритмов для нахождения разнообразного набора Парето-оптимальных компромиссных решений в многокритериальных задачах. Однако стандартная версия предполагает детерминированные оценки целей. На практике симуляции, эксперименты и реальные системы часто дают зашумленные результаты. Стохастический NSGA-II решает эту проблему путем повторной выборки или статистической оценки истинной приспособленности каждого решения, а затем применяет быструю сортировку по недоминируемости и выборку по плотности скопления NSGA-II для надежной навигации по фронту Парето, несмотря на шум. Ключевая идея заключается в том, что ранжирование решений по ожидаемой производительности — или по их вероятности доминирования — восстанавливает правильную структуру Парето, даже когда отдельные оценки ненадежны.
История
NSGA-II был представлен Deb et al. в 2002 году как быстрый, элитистский многокритериальный генетический алгоритм и быстро стал эталонным стандартом. Стохастические расширения появились вскоре после этого, вызванные сообществами инженеров-оптимизаторов, нуждающихся в обработке шума симуляции. Hughes (2001) формализовал многокритериальное ранжирование в условиях неопределенности. С середины 2000-х годов появилось множество вариантов, охватывающих адаптивную повторную выборку, вероятность доминирования и ожидаемое улучшение гиперобъема при шуме.
Когда применять
Используйте Стохастический NSGA-II, когда вы сталкиваетесь с задачей многокритериальной оптимизации, где цели оцениваются с помощью симуляции, эксперимента или зашумленных датчиков, и вам нужны решения, которые остаются хорошими в диапазоне неопределенности — а не только в среднем. Он особенно подходит для инженерного проектирования с учетом производственных допусков, оптимизации цепочек поставок с неопределенностью спроса и экологических или политических моделей со стохастическими входными данными. НЕ используйте его, когда цели детерминированы и дешевы для оценки (достаточно стандартного NSGA-II), когда количество реплик, необходимое для надежной оценки, делает общий бюджет невыполнимым, или когда задача является однокритериальной (вместо этого используйте стохастические однокритериальные ЭА). Избегайте его, когда распределение шума сильно нестационарно или структурировано таким образом, что нарушает предположение о независимой и одинаково распределенной выборке.
Ограничения и замечания
- Вычислительная стоимость масштабируется с количеством реплик r на оценку, умноженным на размер популяции и количество поколений — может стать непомерно высокой для дорогих симуляций.
- Выбор правильного количества реплик r нетривиален: слишком мало вносит ошибки ранжирования, слишком много — тратит бюджет.
- Нет формальных гарантий сходимости к истинному стохастическому фронту Парето; качество зависит от бюджета и уровня шума.
- Сравнения доминирования с использованием оцененных средних игнорируют неопределенность оценки, что может привести к неправильному ранжированию при высоком уровне шума.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Наследует сильное обнаружение фронта Парето и сохранение разнообразия NSGA-II посредством сортировки по недоминируемости и плотности скопления.
- Явно учитывает шум в целевых функциях, производя решения, которые являются робастными и надежными при реальном развертывании.
- Гибкая структура — стохастическая оценка может использовать усреднение, робастность на основе квантилей или вероятность доминирования без изменения основного алгоритма.
- Применим к моделям симуляции типа «черный ящик», где информация о градиенте недоступна.
- Производит полный фронт Парето, а не одно решение, предоставляя лицам, принимающим решения, явные компромиссные варианты.
Применение
- Робастное проектирование: оптимизация конструктивных или механических компонентов с учетом производственных допусков и изменчивости нагрузок.
- Проектирование сети цепочек поставок: минимизация затрат и времени выполнения заказа при стохастических величинах спроса и предложения.
- Моделирование экологической политики: поиск Парето-оптимальных стратегий сокращения выбросов, когда модели воздействия на климат имеют неопределенные параметры.
- Оптимизация портфеля: балансировка ожидаемой доходности и риска, когда доходность активов следует стохастическим процессам.
- Распределение ресурсов здравоохранения: оптимизация затрат и исходов лечения пациентов при неопределенных показателях поступления пациентов и эффективности лечения.
- Планирование энергетических систем: определение размеров установок возобновляемой энергетики при стохастических профилях генерации ветра и солнца.
Как это работает
Как это работает
Определить задачу многокритериальной оптимизации с k стохастическими целевыми функциями f_1(x,xi), ..., f_k(x,xi), где xi представляет случайные параметры, выбранные из известного или оцененного распределения. Указать границы переменных решения, ограничения и количество повторных оценок (реплик) r, используемых для оценки ожидаемого значения каждой цели.
Инициализировать популяцию из N кандидатных решений случайным образом в пределах допустимого пространства решений. Для каждого индивида выделить вектор оценки приспособленности длиной k, инициализированный нулем. Установить счетчик поколений g = 0 и определить критерии остановки (максимальное количество поколений G_max или допуск сходимости).
Для каждого индивида x_i в популяции оценить каждую цель f_j(x_i, xi) ровно r раз, выбирая xi из ее распределения (или выполняя r реплик симуляции). Оценить истинную цель как выборочное среднее: f_j_hat(x_i) = (1/r) * sum_{l=1}^{r} f_j(x_i, xi_l). Опционально вычислить стандартные ошибки для информирования стратегий адаптивной повторной выборки.
Применить быструю сортировку по недоминируемости к векторам оцененных целей. Решение x_a доминирует x_b, если f_j_hat(x_a) <= f_j_hat(x_b) для всех j и строго меньше хотя бы для одного j. Присвоить каждому решению ранг фронта Парето F_1, F_2, ..., где F_1 содержит решения, не доминируемые никакими другими.
Выбрать родителей с помощью бинарного турнирного отбора на основе ранга Парето и плотности скопления (для сохранения разнообразия). Применить генетические операторы — симулированное бинарное скрещивание (SBX) и полиномиальную мутацию — для генерации популяции потомков Q размером N. Объединить родительскую и потомковую популяции (размером 2N), повторно оценить стохастические цели, повторно отсортировать и выбрать N лучших решений по рангу, затем по плотности скопления.
Увеличить g. Если g < G_max и фронт Парето не стабилизировался, повторить с шага стохастической оценки. В противном случае вернуть финальный фронт Парето F_1 как набор недоминируемых робастных решений. Представить аппроксимированный фронт Парето в пространстве целей для выбора лицом, принимающим решения.
Частые ошибки
- Использование одной реплики (r=1) на индивида рассматривает шум как сигнал, что приводит к крайне нестабильным фронтам Парето между запусками — всегда используйте r >= 3 в качестве минимума и проверяйте сходимость.
- Игнорирование дисперсии стохастических целей может привести к выбору решений, которые выглядят хорошо в среднем, но плохо работают в крайних сценариях — рассмотрите квантильные или наихудшие формулировки целей, когда важен риск в крайних сценариях.
- Применение метода без проверки стационарности шума: если свойства шума изменяются в зависимости от значений переменных решения, требуются адаптивная повторная выборка или гетероскедастические модели.
- Рассмотрение выходного фронта Парето как окончательного решения без оценки робастности вне выборки — всегда проверяйте рекомендованные решения с помощью независимых симуляционных запусков.
Часто задаваемые вопросы
Сколько реплик r следует использовать на оценку индивида?
Общей отправной точкой является r = 5–30, в зависимости от коэффициента вариации цели. Адаптивные стратегии, которые выделяют больше реплик элитным решениям или используют последовательную выборку до достижения критерия уверенности, более эффективны. Для дорогих симуляций часто используется компромисс r = 3–5 с большой популяцией.
Чем Стохастический NSGA-II отличается от стандартного NSGA-II?
Единственное структурное отличие заключается в оценке целей: стандартный NSGA-II оценивает f(x) один раз и предполагает, что результат точен, в то время как Стохастический NSGA-II оценивает f(x, xi) r раз и использует выборочное среднее (или другую статистику робастности) в качестве эффективной цели. Все механики сортировки, отбора и генетических операторов остаются идентичными.
Могу ли я использовать Стохастический NSGA-II с вероятностью доминирования вместо средних целей?
Да. Подходы, основанные на вероятности доминирования, заменяют детерминированные сравнения доминирования вероятностями стохастического доминирования, что является более принципиальным при высоком уровне шума. Это требует большего количества выборок на сравнение, но дает более надежные ранжирования, когда шум велик по сравнению с различиями в целях.
Что, если моя симуляция слишком дорога для нескольких реплик?
Рассмотрите подходы с использованием суррогатов: постройте метамодель целевой функции на основе гауссовского процесса или нейронной сети, используйте ее для дешевой оценки среднего и дисперсии, и применяйте критерии ожидаемого улучшения или вероятности улучшения вместо повторных прямых оценок.
Гарантирует ли Стохастический NSGA-II нахождение истинного стохастического фронта Парето?
Нет. Как и все эволюционные алгоритмы, это эвристика без гарантии сходимости в конечное время к истинному фронту. Практическое руководство: проведите несколько независимых испытаний, сравните полученные фронты с использованием индикаторов гиперобъема и увеличьте размер популяции или количество поколений, если фронты существенно различаются между запусками.
Похожие методы
Источники
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Скопировано.Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer.
Открыть ссылку DOIСкопировано.