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

Многокритериальная оптимизация методами роя муравьев (MOACO)

Автор метода
Gambardella, Taillard & Agazzi; Dorigo & Stützle
Год
1999
Тип
Population-based metaheuristic
Семейство
Simulation / optimization

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

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

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

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

Искусственные муравьи конструируют кандидатные решения, руководствуясь феромонными следами и эвристической информацией, постепенно формируя архив Парето-оптимальных решений, а не сходясь к единственному наилучшему ответу.

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

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

История

Оптимизация методами роя муравьев (ACO) была предложена Марко Дориго в его докторской диссертации 1992 года и формализована совместно с Маньеццо и Колорни. Многокритериальные расширения появились в конце 1990-х годов; MACS-VRPTW Гамбарделлы, Тайяра и Агацци (1999) продемонстрировал использование нескольких муравьиных колоний, нацеленных на разные цели. Последующие фреймворки Дёрнера, Хартла и других формализовали MOACO как класс, а учебник Дориго и Штютцле 2004 года предоставил каноническое алгоритмическое изложение. MOACO остается активной областью исследований с приложениями в сетевой маршрутизации, биоинформатике и устойчивой логистике.

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

Использовать MOACO, когда задача имеет две или более конфликтующие цели, комбинаторное или дискретное пространство решений (например, маршрутизация, планирование, проектирование сетей) и нет сильных априорных предпочтений относительно целей, которые оправдывали бы их сведение к скаляру. Метод превосходно работает в задачах логистики, цепочек поставок и планирования рабочих процессов, где ACO уже хорошо себя зарекомендовал для одиночных целей. Избегать MOACO, когда задача является непрерывной и градиентные многокритериальные методы (например, NSGA-II с вещественным кодированием или байесовская оптимизация) более эффективны; когда вычислительный бюджет строго ограничен, поскольку MOACO требует множества оценок; или когда требуется точный фронт Парето для задачи, где точное многокритериальное программирование (например, многокритериальное MILP) решаемо.

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

  • Требует тщательной настройки нескольких гиперпараметров (α, β, ρ, размер колонии, емкость архива), и чувствительность к этим настройкам может быть высокой.
  • Сходимость медленнее, чем у точных решателей для малых, хорошо структурированных задач, где применимы методы целочисленного или динамического программирования.
  • Качество аппроксимации и разнообразие фронта Парето не гарантированы; результаты варьируются между прогонами из-за стохастического конструирования.
  • Масштабирование до многомерных целевых пространств (>3 цели) затруднено и может потребовать специализированных стратегий декомпозиции.
  • Отсутствуют доказательства сходимости для произвольных экземпляров задач; теоретические гарантии ограничены по сравнению с математическим программированием.

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

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

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

Применение

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

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

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

1

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

2

Каждый муравей шаг за шагом строит полное решение, вероятностно выбирая компоненты решения. Вероятность перехода использует силу феромона τ и эвристическую привлекательность η, возведенные в степени настройки α и β. Различные варианты MOACO назначают матрицы феромонов для каждой цели или используют веса скаляризации, которые меняются у разных муравьев.

Формула
p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta}
3

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

4

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

5

Испарить все феромонные следы с коэффициентом (1 − ρ), чтобы старая информация постепенно исчезала. Отложить новый феромон на компоненты решения, принадлежащие элитным (архивным) решениям. Велика отложения Δτ отражает качество, специфичное для цели, или ранг, основанный на скученности, усиливая компоненты, связанные с хорошо распределенными Парето-оптимальными решениями.

Формула
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^k
6

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

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

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

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

Чем MOACO отличается от многократного запуска однокритериального ACO с различными комбинациями весов?

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

Какой вариант MOACO мне следует использовать для новой задачи?

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

Сколько муравьев и итераций обычно требуется?

Универсального ответа нет, но типичная начальная конфигурация — 20–100 муравьев на колонию и 500–2000 итераций для комбинаторных задач умеренного размера. Большие пространства решений и большее количество целей требуют больше итераций. Всегда проводите несколько независимых повторений и сообщайте средние значения индикаторов гиперобъема или IGD по начальным значениям.

Может ли MOACO обрабатывать задачи непрерывной оптимизации?

Стандартный ACO разработан для дискретных пространств. Существуют непрерывные варианты MOACO (например, на основе ACOR), но они, как правило, уступают NSGA-II или MOEA/D в непрерывных задачах. Оставляйте MOACO для комбинаторных или смешанных целочисленных задач, где его построение на основе графов дает естественное преимущество.

Как следует устанавливать размер архива Парето?

Ограничение размера архива определяет количество элитных решений, используемых для отложения феромона. Слишком маленький архив теряет разнообразие; слишком большой замедляет усиление феромона. Типичные значения варьируются от 10 до 100 решений; используйте стратегию расстояния скученности или основанную на сетке для поддержания хорошо распределенного архива независимо от размера.

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

Источники

  1. Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 63–76). McGraw-Hill.

    Открыть ссылку на публикацию
    Скопировано.
  2. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.

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