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

Многокритериальная оптимизация роем частиц (MOPSO)

Автор метода
Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S.
Год
2004
Тип
Population-based swarm metaheuristic
Семейство
Simulation / optimization

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

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

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

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

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

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

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

История

Оптимизация роем частиц была представлена Кеннеди и Эберхартом в 1995 году, вдохновленная социальным поведением стай птиц. Первое широко принятое многокритериальное расширение, MOPSO, было предложено Коэльо Коэльо, Пулидо и Лечугой в 2004 году, которое ввело внешний архив Парето и выбор лидера на основе гиперкуба. Последующие варианты — включая OMOPSO, dMOPSO и SMPSO — усовершенствовали управление архивом, адаптивные параметры и обработку ограничений, утвердив MOPSO как основной алгоритм аппроксимации фронта Парето наряду с NSGA-II.

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

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

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

  • Производительность чувствительна к весовому коэффициенту инерции (w) и коэффициентам ускорения (c1, c2); плохо настроенные параметры вызывают преждевременную сходимость или чрезмерный дрейф.
  • Управление архивом и выбор лидера вводят дополнительные гиперпараметры (размер архива, метрика скученности), которые зависят от задачи.
  • Гарантии сходимости и разнообразия являются эвристическими, а не математическими — аппроксимированный фронт Парето может пропустить области истинного фронта.
  • Испытывает трудности с более чем пятью-семью критериями из-за проклятия размерности в отборе на основе доминирования.
  • Неприменим напрямую к дискретным или комбинаторным пространствам поиска без кодирования, специфичного для задачи, и адаптации ограничения скорости.

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

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

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

Применение

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

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

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

1

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

2

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

3

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

4

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

5

Обновить скорость и позицию каждой частицы, используя правило обновления PSO: v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x), где w — весовой коэффициент инерции, контролирующий баланс исследования/эксплуатации, c1 и c2 — коэффициенты когнитивного и социального ускорения, а r1, r2 — равномерно распределенные случайные числа. Применить обработку границ, чтобы частицы оставались в допустимом пространстве решений.

Формула
v_{id}^{t+1} = w v_{id}^t + c_1 r_1 (pbest_{id} - x_{id}^t) + c_2 r_2 (gbest_d - x_{id}^t)
6

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

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

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

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

Чем MOPSO отличается от NSGA-II?

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

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

Общепринятым значением по умолчанию является 100–200 решений для задач с двумя или тремя критериями. Большие архивы улучшают покрытие фронта Парето, но замедляют выбор лидера. Для задач с четырьмя или более критериями размер архива должен масштабироваться с ожидаемой сложностью фронта Парето; схемы адаптивного управления архивом могут помочь.

Может ли MOPSO обрабатывать ограничения?

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

Сколько целевых функций MOPSO может эффективно обрабатывать?

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

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

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

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

Источники

  1. Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.

    Открыть ссылку DOI
    Скопировано.
  2. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks (ICNN), Perth, Australia, 4, 1942–1948.

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