Оптимизатор "Серый волк" — 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).
Применение
- Оптимизация инженерного проектирования: минимизация структурного веса, проектирование антенн, оценка параметров энергосистем.
- Настройка гиперпараметров машинного обучения и выбор признаков для задач классификации.
- Энергетические системы: оптимальное распределение в электросетях и размещение установок возобновляемой энергии.
- Сегментация изображений и анализ медицинских изображений посредством оптимизации порогов.
- Задачи планирования и распределения ресурсов с непрерывной релаксацией.
Как это работает
Как это работает
Популяция потенциальных решений генерируется равномерно случайным образом в пределах заданных нижних и верхних границ поискового пространства. Размер популяции и максимальное количество итераций — единственные два параметра, которые должны быть установлены до начала выполнения.
Каждое потенциальное решение оценивается целевой функцией. Поскольку GWO не использует градиент, функция может быть "черным ящиком" — ей нужно лишь возвращать скалярное значение приспособленности для каждой позиции кандидата.
Кандидаты сортируются по приспособленности. Лучшее решение обозначается как альфа (α), второе лучшее — как бета (β), а третье лучшее — как дельта (δ). Все остальные кандидаты являются омега (ω) волками. Эти роли переназначаются на каждой итерации, так что метки всегда отслеживают три текущие лучшие позиции.
Каждый омега-волк обновляет свою позицию, вычисляя три вектора расстояния — по одному к α, β и δ — и перемещаясь к центроиду трех результирующих целевых позиций. Управляющий параметр a линейно уменьшается с 2 до 0 в течение выполнения: большие значения a способствуют исследованию (кандидаты могут перескакивать и искать далеко от лидеров), малые значения способствуют эксплуатации (кандидаты плотно сходятся вокруг лидеров).
Шаг охоты повторяется до достижения максимального количества итераций или выполнения критерия остановки. Позиция альфа-волка при завершении возвращается как найденное лучшее решение.
Частые ошибки
- Слишком малый размер популяции (менее примерно 10) рано снижает разнообразие; три лидера преждевременно сходятся, и выполнение исследует лишь небольшую область.
- Слишком малое количество итераций приводит к недостаточному циклу охоты; выполнение, которое завершается, пока a все еще велико, не вошло в фазу эксплуатации.
- Применение GWO к задачам с целочисленными или категориальными переменными без схемы дискретизации приводит к бессмысленным обновлениям позиций.
- Игнорирование масштаба границ поиска — очень широкие границы в сочетании с небольшой популяцией оставляют большую часть пространства неисследованной на ранних итерациях.
Часто задаваемые вопросы
Как выбрать размер популяции и количество итераций?
Обычная отправная точка — 30 агентов и 200–500 итераций для задач умеренной размерности (до примерно 30 переменных). Увеличивайте размер популяции и количество итераций по мере роста размерности задачи. Поскольку GWO является стохастическим, запускайте его не менее 20–30 раз с разными случайными начальными значениями и сообщайте среднее значение и стандартное отклонение лучшей приспособленности.
Может ли GWO работать с дискретными или бинарными переменными?
Не изначально. Стандартные уравнения обновления позиции определены для непрерывных вещественных пространств. В литературе существуют бинарные или дискретные варианты — обычно использующие передаточную функцию для отображения непрерывных позиций в бинарные решения, — но это расширения, а не исходный алгоритм.
Как GWO сравнивается с оптимизацией роем частиц?
Оба являются методами роевого интеллекта со схожей вычислительной стоимостью. GWO использует трех лидеров (альфа, бета, дельта) вместо одного глобального лучшего и личного лучшего для каждой частицы, что, как правило, дольше сохраняет разнообразие. Мирджали и соавт. (2014) обнаружили, что GWO конкурентоспособен или превосходит PSO на их эталонном наборе, но производительность зависит от задачи; ни один из методов не доминирует универсально.
Что контролирует параметр a, и нужно ли его настраивать?
Параметр a линейно уменьшается с 2 до 0 в течение выполнения и контролирует, исследуют ли волки (высокое a) или эксплуатируют (низкое a). Этот график фиксирован алгоритмом — вы не настраиваете a напрямую. Единственные рычаги, которые вы контролируете, — это размер популяции и общее количество итераций, которые вместе определяют, насколько медленно или быстро падает a.
Похожие методы
Источники
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.
Открыть ссылку DOIСкопировано.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Скопировано.