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

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

Автор метода
Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
Год
1990s
Тип
Hybrid evolutionary-agent simulation
Семейство
Simulation / optimization

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

  • Поддерживает более высокое разнообразие популяции, чем панмиктические GA, уменьшая преждевременную сходимость на пересеченных ландшафтах приспособленности.
  • Естественным образом использует параллельную или распределенную вычислительную инфраструктуру для крупномасштабных задач оптимизации.
  • Гетерогенные настройки операторов для каждого агента позволяют одновременно исследовать и эксплуатировать различные стратегии.
  • Миграция приспособленных особей между агентами обеспечивает кросс-нишевую рекомбинацию, которая может обнаружить новые высококачественные решения.
  • Модульная архитектура облегчает интеграцию предметно-ориентированных эвристик в циклы эволюции отдельных агентов.
  • Хорошо масштабируется с размерностью задачи, когда субпопуляции могут быть осмысленно разделены.

Применение

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

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

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

1

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

2

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

3

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

4

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

5

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

6

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

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

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

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

Чем ABGA отличается от стандартного параллельного GA?

Стандартный параллельный GA обычно распределяет оценку приспособленности единой централизованной популяции по процессорам. ABGA предоставляет каждому агенту автономную субпопуляцию с собственным эволюционным циклом; взаимодействие происходит только через явную миграцию, а не через общий пул. Это различие сохраняет независимые селективные давления для каждого агента.

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

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

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

Распространенная эвристика — 4-16 агентов с размером субпопуляции 20-50 особей каждый, что в сумме дает популяцию, сравнимую с той, которую использовал бы стандартный GA. Слишком мало агентов сводит на нет преимущество архитектуры в плане разнообразия; слишком много агентов с крошечными субпопуляциями страдают от дрейфа. Требуется эмпирическая настройка на конкретную задачу.

Можно ли использовать ABGA для многоцелевой оптимизации?

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

Гарантирует ли ABGA нахождение глобального оптимума?

Нет. Как и все GA, ABGA являются эвристическими и не предоставляют гарантии глобальной оптимальности. Улучшенное сохранение разнообразия практически увеличивает вероятность избежания локальных оптимумов, но гарантии сходимости не сильнее, чем для стандартных GA, и являются активным вопросом теоретических исследований.

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

Источники

  1. Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.

    Открыть ссылку на публикацию
    Скопировано.
  2. Genetic algorithm. Wikipedia.

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