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

Агентно-ориентированный NSGA-II — эволюционная многокритериальная оптимизация, управляемая симуляцией

Автор метода
Deb et al. (NSGA-II, 2002); integrated with agent-based modeling frameworks in the 2000s–2010s
Год
2000s–2010s
Тип
Simulation-embedded evolutionary multi-objective optimizer
Семейство
Simulation / optimization

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

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

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

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

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

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

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

История

NSGA-II был представлен Кальяном Мой Дебом и его коллегами из IIT Kanpur в 2002 году как быстрый, элитистский многокритериальный генетический алгоритм, быстро ставший одним из самых цитируемых алгоритмов в эволюционных вычислениях. Агентно-ориентированное моделирование как вычислительная парадигма развивалось в 1990-х годах с такими платформами, как Swarm, NetLogo и Repast. Сочетание NSGA-II с агентно-ориентированными симуляциями появилось в 2000-х и 2010-х годах, когда исследователи в области городского планирования, экологии, эпидемиологии и управления цепочками поставок стремились оптимизировать политику в системах, слишком сложных для аналитической формулировки.

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

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

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

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

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

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

  • Обрабатывает эмерджентные, зависимые от пути и стохастические ландшафты целевых функций, которые не могут быть выражены аналитически, что делает его применимым к сложным адаптивным системам.
  • Производит полный фронт Парето за один запуск оптимизации, предоставляя лицам, принимающим решения, явную видимость компромиссов без необходимости предварительных весовых коэффициентов предпочтений.
  • Механизм элитизма NSGA-II гарантирует, что высококачественные недоминируемые решения никогда не отбрасываются между поколениями.
  • Усреднение репликаций в рамках каждой оценки приспособленности позволяет методу принципиально обрабатывать стохастический шум симуляции.
  • Совместим с любой платформой агентно-ориентированной симуляции (NetLogo, Repast, AnyLogic, Mesa) через стандартизированный интерфейс-обертку.

Применение

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

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

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

1

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

2

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

3

Для каждого индивида в текущей популяции запустите агентно-ориентированную симуляцию R раз (репликаций) и усредните полученные значения целевых функций, чтобы уменьшить стохастический шум. Запишите средний вектор целевых функций для каждого индивида. Этот шаг доминирует по вычислительной стоимости: N индивидов умножить на R репликаций умножить на T временных шагов симуляции на оценку.

4

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

5

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

6

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

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

  • Использование слишком малого количества репликаций на индивида (R = 1 или 2), когда симуляция стохастична — шумная оценка приспособленности приводит к тому, что шаг сортировки по доминированию неправильно классифицирует решения и искажает фронт Парето.
  • Установка размера популяции N меньше ожидаемой сложности фронта Парето, что заставляет алгоритм отбрасывать целые области пространства компромиссов и возвращать фрагментарный фронт.
  • Применение этого метода к четырем или более критериям без перехода к NSGA-III или MOEA/D, что приводит к скоплению большинства индивидов в фронте F1 и делает выбор почти случайным.
  • Смешение калибровки модели агентов и оптимизации: симуляция должна быть откалибрована на наблюдаемых данных перед началом оптимизации — оптимизация некалиброванной модели дает фронты Парето, не имеющие реальной ценности.
  • Пренебрежение параллельными вычислениями: поскольку каждый запуск симуляции независим, агентно-ориентированный NSGA-II тривиально распараллеливается; его однопоточный запуск растрачивает доступное оборудование и делает время выполнения неоправданно долгим.

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

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

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

Сколько репликаций следует запускать на оценку индивида?

Достаточно, чтобы коэффициент вариации каждого критерия по репликациям упал ниже примерно 5-10%. Начните с R = 10 и увеличивайте, пока оценки критериев не станут стабильными. Для сильно стохастических моделей может потребоваться R = 30-50, что соответственно увеличивает стоимость.

Как сделать агентно-ориентированный NSGA-II вычислительно осуществимым?

Параллелизуйте по ядрам ЦП или кластеру — запуски симуляции каждого индивида независимы и тривиально распараллеливаются. Используйте суррогатные модели (гауссовские процессы или нейронные сети) для аппроксимации приспособленности для дешевого предварительного отбора, резервируя полные оценки симуляции для перспективных кандидатов.

Что делать, если у меня четыре или более критериев?

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

Как проверить надежность фронта Парето?

Запустите не менее 10 независимых запусков оптимизации с различными случайными начальными значениями и вычислите гиперобъем или IGD для каждого. Сообщите медиану и межквартильный размах по запускам. Согласованный гиперобъем по запускам указывает на то, что оптимизатор надежно сошелся к одному и тому же приближенному фронту Парето.

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

Источники

  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. Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.

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