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

Оптимизатор "Серый волк" — GWO

Автор метода
Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis
Год
2014
Тип
Swarm-intelligence metaheuristic

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

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

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

Оптимизатор "Серый волк" (Grey Wolf Optimizer, GWO) — это метаэвристический алгоритм роевого интеллекта, предложенный Мирджали, Мирджали и Льюисом в 2014 году.

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

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

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

История

GWO был предложен Сейедали Мирджали, Сейедом Мохаммадом Мирджали и Эндрю Льюисом в 2014 году в журнале Advances in Engineering Software. Алгоритм был вдохновлен экологическими наблюдениями за структурой стаи серых волков: строгая социальная иерархия (альфа, бета, дельта, омега) и трехфазная стратегия охоты, включающая окружение, преследование и атаку добычи. Мирджали и соавт. сравнили GWO с оптимизацией роем частиц (Particle Swarm Optimization), алгоритмом гравитационного поиска (Gravitational Search Algorithm) и дифференциальной эволюцией (Differential Evolution) на 29 тестовых функциях и нескольких задачах инженерного проектирования, сообщив о конкурентоспособных или превосходящих результатах. С 2014 года алгоритм породил значительную последующую литературу: Фарис и соавт. (2018) рассмотрели более десяти лет вариантов — бинарных, многоцелевых, хаотических и гибридных расширений — и задокументировали применения в выборе признаков, энергетических системах, сегментации изображений и планировании.

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

GWO подходит для задач непрерывной оптимизации, где целевая функция является дорогостоящей для аналитической оценки или является "черным ящиком". Он не требует информации о градиенте и предположений о распределении данных. Метод подходит для задач инженерного проектирования, настройки параметров и выбора признаков. Поскольку он основан на популяции, рекомендуется минимальный размер популяции примерно 10–30 агентов; очень маленькие популяции снижают разнообразие и увеличивают риск преждевременной сходимости. GWO не подходит для дискретных или комбинаторных задач без модификации, а также для задач, где существует точное математическое решение.

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

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

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

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

  • Безградиентный: работает с любой целевой функцией, которая возвращает скаляр, включая симуляции и модели "черного ящика".
  • Минимальная параметризация: необходимо задать только размер популяции и количество итераций; a уменьшается автоматически.
  • Балансирует исследование и эксплуатацию с помощью одного линейно убывающего параметра, делая механизм баланса прозрачным.
  • Конкурентоспособная производительность на эталонных задачах инженерного проектирования с низкой сложностью реализации (уровень сложности 2 из 5).

Применение

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

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

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

1

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

2

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

3

Кандидаты сортируются по приспособленности. Лучшее решение обозначается как альфа (α), второе лучшее — как бета (β), а третье лучшее — как дельта (δ). Все остальные кандидаты являются омега (ω) волками. Эти роли переназначаются на каждой итерации, так что метки всегда отслеживают три текущие лучшие позиции.

4

Каждый омега-волк обновляет свою позицию, вычисляя три вектора расстояния — по одному к α, β и δ — и перемещаясь к центроиду трех результирующих целевых позиций. Управляющий параметр a линейно уменьшается с 2 до 0 в течение выполнения: большие значения a способствуют исследованию (кандидаты могут перескакивать и искать далеко от лидеров), малые значения способствуют эксплуатации (кандидаты плотно сходятся вокруг лидеров).

5

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

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

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

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

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

Обычная отправная точка — 30 агентов и 200–500 итераций для задач умеренной размерности (до примерно 30 переменных). Увеличивайте размер популяции и количество итераций по мере роста размерности задачи. Поскольку GWO является стохастическим, запускайте его не менее 20–30 раз с разными случайными начальными значениями и сообщайте среднее значение и стандартное отклонение лучшей приспособленности.

Может ли GWO работать с дискретными или бинарными переменными?

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

Как GWO сравнивается с оптимизацией роем частиц?

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

Что контролирует параметр a, и нужно ли его настраивать?

Параметр a линейно уменьшается с 2 до 0 в течение выполнения и контролирует, исследуют ли волки (высокое a) или эксплуатируют (низкое a). Этот график фиксирован алгоритмом — вы не настраиваете a напрямую. Единственные рычаги, которые вы контролируете, — это размер популяции и общее количество итераций, которые вместе определяют, насколько медленно или быстро падает a.

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

Источники

  1. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.

    Открыть ссылку DOI
    Скопировано.
  2. Faris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S. (2018). Grey Wolf Optimizer: A Review of Recent Variants and Applications. Neural Computing and Applications, 30(2), 413-435.

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