Алгоритм кукушки

Алгоритм кукушки (англ. Cuckoo search) — это метаэвристический алгоритм оптимизации, вдохновлённый гнездовым паразитизмом некоторых видов кукушек и их стратегией подкладывания яиц в чужие гнёзда. Алгоритм был предложен в 2009 году исследователями Синь-Шэ Яном (Xin-She Yang) и Субхашем Дебом (Suash Deb) как метод решения задач глобальной оптимизации, в том числе в условиях многомодальности и ограничений. Относится к классу популяционных алгоритмов, таких как генетические алгоритмы или роевой интеллект, и основан на сочетании случайных блужданий (полётов Леви) и отбора решений.

История

Идея алгоритма была впервые опубликована в 2009 году в статье «Cuckoo Search via Lévy Flights» на конференции IEEE по природо-вдохновлённым вычислениям. Ян и Деб предложили использовать поведение кукушек, которые подкладывают яйца в гнёзда других птиц, как метафору для поиска оптимального решения. Если хозяин гнезда обнаруживает чужое яйцо, он либо выбрасывает его, либо покидает гнездо — это соответствует отбрасыванию неоптимальных решений. Первоначально алгоритм тестировался на стандартных тестовых функциях (сфера, Розенброк, Растригин) и показал высокую эффективность по сравнению с генетическими алгоритмами и методом имитации отжига. В последующие годы алгоритм получил множество модификаций и применений в инженерных задачах, биоинформатике и планировании маршрутов.

Основные принципы

Алгоритм кукушки моделирует три ключевых аспекта поведения птиц:

1. Гнездовой паразитизм: Каждая кукушка откладывает одно яйцо в случайно выбранное гнездо. В контексте оптимизации «яйцо» — это новое решение-кандидат, а «гнездо» — текущее решение в популяции.
2. Элитизм: Лучшие решения (гнёзда с наиболее качественными яйцами) переходят в следующее поколение без изменений.
3. Обнаружение и замена: Если хозяин гнезда с вероятностью \( p_a \) обнаруживает чужое яйцо (то есть новое решение оказывается хуже или равно текущему), гнездо заменяется новым случайным решением (или яйцо выбрасывается).

Ключевой особенностью является использование полётов Леви (Lévy flights) — типа случайного блуждания, при котором шаги имеют распределение с тяжёлыми хвостами (закон степени). Это позволяет алгоритму эффективно исследовать пространство поиска: короткие шаги обеспечивают локальную детализацию, а редкие длинные прыжки — выход из локальных оптимумов.

Алгоритм работы

Формально алгоритм можно описать следующим образом:

1. Инициализация: Генерируется начальная популяция из \( n \) гнёзд (решений). Каждое решение представляет собой вектор параметров в пространстве поиска. Вычисляется целевая функция (пригодность) для каждого гнезда.
2. Цикл поколений (итераций):

• Генерация нового решения: Для каждого гнезда \( i \) создаётся новое яйцо (решение) \( X_{new} \) по формуле:

\[ X_{new} = X_i + \alpha \cdot \text{Lévy}(\lambda) \cdot (X_i - X_{best}) \] где \( \alpha \) — параметр масштаба (обычно \( \alpha = 0.01 \)), \( \text{Lévy}(\lambda) \) — случайная величина с распределением Леви (параметр \( \lambda \) обычно равен 1.5), \( X_{best} \) — лучшее решение в текущей популяции.

• Отбор: Случайно выбирается другое гнездо \( j \). Если пригодность нового решения \( X_{new} \) лучше, чем у \( X_j \), то \( X_j \) заменяется на \( X_{new} \).
• Обнаружение: Часть худших гнёзд (с вероятностью \( p_a \)) отбрасывается. Вместо них генерируются новые случайные решения (например, с помощью равномерного распределения или полёта Леви от текущего лучшего).

1. Критерий остановки: Цикл повторяется до выполнения условия (например, достижение заданного числа итераций, точности или стагнации функции).

Параметры

Алгоритм имеет всего два основных параметра, что делает его простым в настройке:

• Размер популяции \( n \) (число гнёзд): обычно от 15 до 50. Большие значения увеличивают разнообразие, но замедляют сходимость.
• Вероятность обнаружения \( p_a \) (часто принимается равной 0.25): определяет, какая доля худших решений заменяется новыми. Высокая \( p_a \) усиливает разведку (exploration), низкая — эксплуатацию (exploitation).

Дополнительно может настраиваться параметр масштаба \( \alpha \) и показатель распределения Леви \( \lambda \), но в базовой версии они фиксированы.

Разновидности и модификации

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

• Бинарный алгоритм кукушки: Используется для задач с дискретными переменными (например, выбор признаков). Решения кодируются бинарными строками, а полёт Леви заменяется бинарными операторами.
• Многокритериальный алгоритм кукушки: Расширение для задач с несколькими целевыми функциями (Pareto-оптимизация). Вводится понятие доминирования и архивирование недоминируемых решений.
• Гибридные версии: Комбинация с генетическими алгоритмами (кроссовер, мутация) или локальным поиском (например, симплекс-методом) для ускорения сходимости.
• Адаптивные версии: Параметры \( p_a \) и \( \alpha \) динамически изменяются в процессе работы (например, уменьшаются со временем) для баланса разведки и эксплуатации.

Применение

Алгоритм кукушки применяется в широком спектре областей:

• Инженерная оптимизация: Проектирование конструкций (фермы, балки), настройка параметров регуляторов (PID-контроллеры), оптимизация топологии сетей.
• Обработка изображений: Сегментация (кластеризация пикселей), распознавание образов, улучшение контраста.
• Машинное обучение: Обучение нейронных сетей (подбор весов и архитектуры), выбор признаков (feature selection) для классификаторов, настройка гиперпараметров.
• Планирование и логистика: Задачи коммивояжёра (TSP), маршрутизация транспорта, распределение ресурсов.
• Энергетика: Оптимизация режимов работы электростанций, размещение возобновляемых источников энергии (ветряки, солнечные панели).
• Биоинформатика: Выравнивание последовательностей ДНК, предсказание структуры белков.

Преимущества и недостатки

Преимущества

• Простота реализации: Алгоритм требует минимум кода и легко программируется.
• Эффективность на многомодальных функциях: Полёты Леви позволяют избегать преждевременной сходимости к локальным оптимумам.
• Малое число параметров: Всего два основных параметра (\( n \) и \( p_a \)), что упрощает настройку.
• Хорошая масштабируемость: Алгоритм работает как на маломерных, так и на многомерных задачах (до нескольких сотен переменных).

Недостатки

• Медленная сходимость на гладких функциях: В задачах с одним оптимумом алгоритм может уступать градиентным методам.
• Чувствительность к выбору \( p_a \): Неправильный выбор может привести к потере разнообразия или излишней случайности.
• Трудности с дискретными пространствами: Базовый алгоритм ориентирован на непрерывные переменные; для дискретных задач требуется модификация.
• Отсутствие гарантий глобальной оптимальности: Как и все метаэвристики, алгоритм не гарантирует нахождение глобального оптимума.

Сравнение с другими алгоритмами

По сравнению с генетическими алгоритмами (ГА) алгоритм кукушки часто демонстрирует более быструю сходимость на начальных итерациях благодаря полётам Леви. В отличие от роя частиц (PSO), он не требует хранения индивидуальных лучших позиций. По сравнению с методом имитации отжига (SA), алгоритм кукушки использует популяционный подход, что увеличивает разнообразие решений. Однако на задачах с гладкими унимодальными функциями ГА или градиентные методы могут быть эффективнее.

Интересные факты

• Название алгоритма не связано с кукушкой как биологическим видом в полной мере — метафора использует только принцип подкладывания яиц, а не другие аспекты поведения птицы (например, миграцию).
• Полёты Леви, лежащие в основе алгоритма, наблюдаются в природе не только у птиц, но и у насекомых (плодовые мушки) и даже у людей при поиске пищи.
• В 2014 году алгоритм кукушки был включён в список «10 лучших алгоритмов» по версии журнала IEEE Computational Intelligence Magazine.

Источники

• Yang X.-S., Deb S. Cuckoo Search via Lévy Flights // Proceedings of World Congress on Nature & Biologically Inspired Computing (NaBIC 2009). — IEEE, 2009. — P. 210–214.
• Yang X.-S. Nature-Inspired Metaheuristic Algorithms. — Luniver Press, 2010. — Chapter 9.
• Gandomi A. H., Yang X.-S., Alavi A. H. Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems // Engineering with Computers. — 2013. — Vol. 29, No. 1. — P. 17–35.
• Walton S., Hassan O., Morgan K., Brown M. R. Modified cuckoo search: A new gradient free optimisation algorithm // Chaos, Solitons & Fractals. — 2011. — Vol. 44, No. 9. — P. 710–718.