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

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

Автор метода
Bonabeau, Dorigo, Theraulaz; Coello Coello et al.
Год
1990s–2000s
Тип
Simulation-driven multi-objective search
Семейство
Simulation / optimization

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

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

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

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

Она подходит для сложных адаптивных систем, где критерии возникают из микроуровневых взаимодействий, а не из замкнутых уравнений.

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

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

История

Агентно-ориентированная многокритериальная оптимизация возникла в конце 1990-х и начале 2000-х годов, когда исследователи объединили фреймворки агентно-ориентированного моделирования (NetLogo, Repast, MASON) с многокритериальными эволюционными алгоритмами. Фундаментальные работы Бонабо, Дориго и Терола по роевому интеллекту и Коэльо Коэльо и др. по эволюционной многокритериальной оптимизации заложили теоретические основы, которые объединены в ABMOO. Подход получил распространение в науке о сложных системах, городском планировании и управлении экосистемами в 2000-х и 2010-х годах.

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

Использовать ABMOO, когда поведение системы возникает из взаимодействий агентов и не может быть охвачено замкнутыми уравнениями, когда два или более критерия конфликтуют и лицам, принимающим решение, нужен полный фронт компромиссов, и когда стохастичность или зависимость от пути делают аналитическую оптимизацию невыполнимой. Идеально подходит для разработки политики в социальных, экологических или цепочках поставок. Не использовать, когда достаточно одного критерия, когда существует быстрый аналитический решатель на основе градиента, когда бюджет вычислений сильно ограничен (оценки симуляции дороги), или когда критерии могут быть объединены в скалярную полезность без потери понимания.

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

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

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

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

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

Применение

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

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

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

1

Перечислить m критериев f_1, ..., f_m (все должны быть минимизированы или максимизированы) и переменные решения, закодированные в геноме или наборе правил каждого агента. Определить ограничения и симуляционную среду, которая преобразует решения агентов в наблюдаемые результаты.

2

Инициализировать популяцию из N агентов со случайными или эвристически засеянными геномами. Геном каждого агента кодирует параметры или поведенческие правила, которые будут настраиваться в процессе оптимизации на протяжении поколений.

3

Запустить агентно-ориентированную симуляцию вперед на T временных шагов. В конце каждого прогона считать значения критериев f_1(x), ..., f_m(x) для каждого агента или для коллективной системы. Множественные репликации могут быть усреднены для управления стохастическим шумом.

4

Применить не доминируемую сортировку: ранжировать агентов по Парето-доминированию. Агент x доминирует над y, если x не хуже по всем критериям и строго лучше хотя бы по одному. Сохранить недоминируемый фронт (Парето-фронт) и использовать расстояние скученности или вклад в гиперобъем для поддержания разнообразия.

5

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

6

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

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

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

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

Чем ABMOO отличается от стандартного многокритериального генетического алгоритма?

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

Какой многокритериальный алгоритм лучше всего работает в качестве оптимизатора в ABMOO?

NSGA-II является наиболее широко используемым благодаря своей не доминируемой сортировке и расстоянию скученности. MOEA/D и MOPSO также распространены. Выбор зависит от формы и размерности Парето-фронта; универсального лучшего выбора нет — сначала протестируйте на небольшой выборке.

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

Достаточно, чтобы уменьшить шум, чтобы сравнения Парето-доминирования были надежными. Распространенный эвристический метод — запускать до тех пор, пока коэффициент вариации каждого критерия не упадет ниже 5–10%. Это может потребовать 10–50 репликаций в зависимости от стохастичности системы.

Может ли ABMOO обрабатывать более двух критериев?

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

Когда следует предпочесть робастную оптимизацию стандартной ABMOO?

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

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

Источники

  1. Bonabeau, E., Dorigo, M., & Theraulaz, G. (2002). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.

    ISBN: 9780195131598
    Скопировано.
  2. Coello Coello, C. A., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems (2nd ed.). Springer.

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