Стохастическая многокритериальная оптимизация — Оптимизация нескольких конфликтующих целей в условиях неопределенности
- Автор метода
- Various (Fonseca, Fleming, Deb, Zitzler, and others)
- Год
- 1990s–2000s
- Тип
- Stochastic metaheuristic optimization
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Стохастическая многокритериальная оптимизация (SMOO) — это класс методов, которые одновременно оптимизируют две или более конфликтующие цели, когда параметры, затраты или ограничения являются неопределенными или случайными.
Вместо единственного оптимального решения она генерирует фронт Парето недоминируемых решений, каждое из которых представляет собой различный баланс между целями в условиях моделируемой неопределенности.
Интуиция метода
Большинство реальных решений включают компромиссы между несколькими целями — минимизация затрат при максимизации качества и скорости — и мир неопределенен. Стохастическая многокритериальная оптимизация признает, что значения целевых функций являются не фиксированными числами, а случайными величинами, формируемыми неопределенными входными данными, такими как спрос, цены или частота отказов. Путем выборки или аналитического распространения этой неопределенности через множественные оценки целей метод находит набор робастных компромиссных решений, которые остаются недоминируемыми при реалистичных проявлениях неопределенности, предоставляя лицам, принимающим решения, честный выбор, а не ложно точные единичные ответы.
История
Многокритериальная оптимизация в условиях неопределенности появилась в 1990-х годах одновременно с развитием эволюционной многокритериальной оптимизации. Фундаментальные работы Фонсеки и Флеминга (Fonseca and Fleming, 1993) и Деба и др. (Deb et al., 2002) заложили основы эволюционных фреймворков, основанных на Парето. Интеграция стохастических элементов — через цели ожидаемого значения, ограничения по вероятности и подходы, основанные на сценариях — стала активной областью исследований в 2000-х и 2010-х годах, поддерживаемая растущей вычислительной мощностью, позволяющей проводить интенсивный поиск методом Монте-Карло.
Когда применять
Используйте стохастическую многокритериальную оптимизацию, когда существуют две или более действительно конфликтующие цели И ключевые параметры (спрос, затраты, длительность, вероятности отказов) являются неопределенными или переменными. Она подходит для инженерного проектирования в условиях неопределенности, планирования цепочек поставок, оптимизации энергетического портфеля и оценки политики с множественными критериями благосостояния. НЕ используйте ее, когда все параметры детерминированы (вместо этого используйте стандартную многокритериальную оптимизацию), когда важна только одна цель (используйте стохастическую однокритериальную оптимизацию), когда неопределенность является эпистемической и не поддается количественной оценке, или когда вычислительный бюджет слишком ограничен для поддержки многократных стохастических оценок функций — каждое кандидатное решение может потребовать от десятков до тысяч выборок Монте-Карло.
Ограничения и замечания
- Вычислительно затратен: каждая оценка функции требует выборки методом Монте-Карло или перечисления сценариев, умноженной на множество оценок, необходимых для многокритериального поиска.
- Результаты сильно зависят от качества модели неопределенности; плохие предположения о распределении приводят к вводящим в заблуждение фронтам Парето.
- Сходимость к истинному стохастическому фронту Парето труднее гарантировать, чем в детерминированном случае; уверенность в результатах требует тщательного статистического анализа.
- Большое количество решений Парето может перегрузить лиц, принимающих решения, без эффективных инструментов визуализации или артикуляции предпочтений.
- Требует достаточных данных или предметных знаний для определения распределений неопределенности для каждого неопределенного параметра.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Явно учитывает неопределенность в значениях целей, производя решения, которые робастны к изменчивости параметров, а не оптимальны только при предполагаемых фиксированных значениях.
- Генерирует полный фронт Парето компромиссных решений, сохраняя автономию лица, принимающего решения, в выборе между альтернативами на основе предпочтений.
- Совместим с широким спектром представлений неопределенности (распределения, сценарии, множества неоднозначности) и оптимизационных движков (эволюционные алгоритмы, декомпозиция, методы с использованием суррогатных моделей).
- Учитывает отношения стохастического доминирования между решениями, которые детерминированная многокритериальная оптимизация упустила бы.
- Применим в различных областях, включая инженерию, логистику, финансы и государственную политику.
Применение
- Инженерное проектирование: одновременная оптимизация веса конструкции, стоимости и надежности при неопределенных свойствах материалов.
- Управление цепочками поставок: балансирование затрат, уровня обслуживания и выбросов углерода в условиях неопределенного спроса и сроков выполнения заказов.
- Энергетические системы: планирование портфелей генерации, которые минимизируют затраты и выбросы при соблюдении целевых показателей надежности в условиях переменной выработки возобновляемых источников энергии.
- Оптимизация финансового портфеля: максимизация ожидаемой доходности при минимизации риска (CVaR) в условиях неопределенной доходности активов.
- Проектирование транспортных сетей: минимизация времени в пути и затрат на инфраструктуру при неопределенном будущем транспортном спросе.
- Распределение ресурсов здравоохранения: балансирование результатов лечения и бюджета в условиях неопределенной частоты поступления пациентов и эффективности лечения.
Как это работает
Как это работает
Определите вектор целевых функций f(x) = [f1(x,xi), f2(x,xi), ..., fk(x,xi)], где x — вектор переменных решения, а xi представляет неопределенные параметры. Укажите границы переменных решения, детерминированные и стохастические ограничения, а также структуру неопределенности (распределения, сценарии или множества неоднозначности).
Представляйте неопределенные параметры с помощью вероятностных распределений (например, нормального, равномерного, эмпирического), дискретных наборов сценариев с соответствующими вероятностями или робастных наборов неоднозначности. Выберите представление, соответствующее имеющимся данным: подходы, основанные на сценариях, требуют меньше предположений о распределении; полные дистрибутивные модели позволяют проводить выборку методом Монте-Карло.
Примените многокритериальный поисковый алгоритм — обычно эволюционный алгоритм, такой как NSGA-II, MOEA/D или SPEA2, или декомпозицию математического программирования — для исследования пространства решений и поддержания популяции или архива кандидатных недоминируемых решений на протяжении итераций.
Для каждого кандидатного решения x, встреченного в процессе поиска, оцените стохастические цели, вычисляя ожидаемые значения E[fi(x,xi)], дисперсии, условную стоимость под риском (CVaR) или усредненные по сценариям значения с помощью выборки Монте-Карло или аналитического интегрирования. Это заменяет детерминированные оценки функций статистически робастными оценками пригодности.
Обновляйте и сокращайте недоминируемый архив, используя отношения Парето-доминирования, примененные к оцененным стохастическим значениям целей. Решение x доминирует над x', если его оцененный вектор целей не хуже по всем измерениям и строго лучше хотя бы по одному, с учетом неопределенности оценки, если это необходимо.
Представьте оцененный стохастический фронт Парето лицам, принимающим решения, сопроводив его доверительными интервалами или вероятностными распределениями по целям для каждого решения Парето. Обеспечьте выбор предпочтительного решения с использованием скаляризации функции ценности, методов опорных точек или интерактивного анализа компромиссов.
Частые ошибки
- Использование слишком малого количества выборок Монте-Карло на каждую оценку приводит к зашумленным оценкам пригодности, которые искажают сравнения Парето-доминирования и вводят в заблуждение поиск.
- Рассмотрение неопределенных целей как детерминированных путем подстановки средних значений параметров игнорирует дисперсию и может привести к решениям, которые плохо работают при фактических реализациях.
- Смешение робастной оптимизации (наихудший случай) со стохастической оптимизацией (ожидаемое значение): эти две формулировки дают разные фронты Парето и подходят для разных типов отношения к риску.
- Пренебрежение неопределенностью ограничений: неспособность моделировать стохастические ограничения как ограничения по вероятности или ограничения по ожидаемому значению приводит к невыполнимым решениям на практике.
- Представление фронта Парето без доверительных интервалов вводит в заблуждение заинтересованные стороны, заставляя их верить в точность оценок целей.
Часто задаваемые вопросы
Чем стохастическая многокритериальная оптимизация отличается от стандартной (детерминированной) многокритериальной оптимизации?
В детерминированной многокритериальной оптимизации значения целевой функции фиксированы для данного вектора решения. В стохастической многокритериальной оптимизации цели являются случайными величинами, поскольку некоторые параметры неопределенны. Каждое кандидатное решение должно быть оценено путем оценки его ожидаемой производительности (или меры риска) при различных реализациях неопределенности, как правило, с помощью выборки Монте-Карло, что делает оптимизацию значительно более вычислительно требовательной.
Сколько выборок Монте-Карло требуется для оценки одного решения?
Универсального правила нет; это зависит от дисперсии целей и требуемой точности оценки. Общая отправная точка — 100–1000 выборок на оценку, но практики должны провести пилотное исследование, чтобы оценить, сколько выборок необходимо для получения стабильных оценок пригодности и стабильных рейтингов Парето.
Могу ли я использовать любой многокритериальный алгоритм в качестве поискового движка?
Да. NSGA-II, MOEA/D, SPEA2 и другие алгоритмы, основанные на Парето или декомпозиции, могут быть адаптированы путем замены детерминированных оценок функций стохастическими. Варианты с использованием суррогатных моделей становятся все более популярными для сокращения количества дорогостоящих стохастических оценок.
Какую меру риска следует использовать для стохастических целей?
Это зависит от контекста решения. Ожидаемое значение подходит для лиц, принимающих решения, нейтральных к риску; дисперсия или стандартное отклонение наказывают за изменчивость; CVaR (условная стоимость под риском) учитывает хвостовой риск для условий неприятия риска. Для инженерной надежности вероятность выполнения ограничений (ограничения по вероятности) часто более значима, чем ожидаемое значение.
Является ли робастная оптимизация тем же самым, что и стохастическая многокритериальная оптимизация?
Нет. Робастная оптимизация обычно использует модели неопределенности наихудшего случая (формулировки min-max) без требования вероятностных распределений. Стохастическая многокритериальная оптимизация использует вероятностные модели и оптимизирует ожидаемые или скорректированные по риску значения целей. Обе решают проблему неопределенности, но они кодируют различное отношение к риску и требуют разных типов информации о неопределенности.
Похожие методы
Источники
Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester.
ISBN: 9780471873396Скопировано.Caramia, M., Dell'Olmo, P. (2008). Multi-Objective Management in Freight Logistics. Springer, London.
Открыть ссылку DOIСкопировано.