Алгоритм кукушки () — один из алгоритмов роевого интеллекта, представляет собой оптимизационный алгоритм, разработанный Янг Синьшэ (Xin-She Yang) и Суашем Дебом (Suash Deb) в 2009 году.
Вдохновением для его создания послужил гнездовой паразитизм некоторых видов кукушек, что подкладывают свои яйца в гнезда других птиц (других видов птиц). Некоторые из владельцев гнезд могут вступить в прямой конфликт с кукушками, что врываются к ним. Например, если владелец гнезда обнаружит, что яйца не его, то он или выбросит эти чужие яйца или просто покинет гнездо и создаст новое где-то в другом месте.
Некоторые виды кукушек, такие как гнездовые паразиты с Нового мира, например полосатая или четырёхкрылая кукушка (Tapera naevia), эволюционировали таким образом, что самки очень часто специализируются на имитации цветов и структуры яиц избранных видов птиц-хозяев.
Алгоритм Для простоты описания нового алгоритма кукушки воспользуемся следующими тремя идеализированными правилами:
Кукушка закладывает по одному яйцу за раз, и сбрасывает его в случайно выбранном гнезде; Лучшие гнезда с высоким качеством яиц (решения) переносятся на следующие поколения; Количество доступных хозяйских гнезд фиксировано, и хозяин может обнаружить инородное яйцо с вероятностью Pa ∈ [0, 1]. В этом случае птица-хозяин может либо выбросить яйцо из гнезда, либо покинуть гнездо, чтобы построить совершенно новое гнездо в новом месте.
Схему алгоритма можно представить в следующем виде:
Инициализируем популяцию S = (si, i ∈ [1 : |S|]) из |S| хозяйских гнёзд и кукушку, т.е. определяем начальные значения компонентов векторов Xi; i ∈ [1 : |S|], и вектор начального положения кукушки Xc; Находим новое Xc, с помощью полётов Леви (см. следующий раздел). Случайным образом находим гнездо si: i ∈ [1 : |S|], и, если f(Xc) > f(Xi), заменяем яйцо в этом гнезде на яйцо кукушки, т.е. полагаем Xi = Xc; С вероятностью pa удаляем из популяции некоторое число худших случайно выбранных гнезд и строим новые гнезда в местах определённых с помощью полётов Леви. Если поколение достигло заданного предела, то заканчиваем алгоритм, иначе переходим ко второму шагу.
Полёты Леви В природе животные ищут пищу случайным образом. В общем, путь поиска пищи животного является фактически случайным блужданием, потому что следующий ход основан на текущем местоположении и вероятности перехода на следующее местоположение. Какое направление он выбирает зависит неявно от вероятности, которая может быть смоделирована математически. Например, различные исследования показали, что полетные поведения многих животных и насекомых продемонстрировали типичные характеристики полетов Леви. Когда мы находим новое положение кукушки мы реализуем полёты Леви по следующей формуле: Xc(t+1) = Xc(t) + α ⊕ Levy(λ) где, t – поколение или номер итерации, a – размер шага, который зависит от масштаба задачи (обычно принимают равной единице), ⊕ - произведение Адамара.
Улучшенный алгоритм кукушки Вместе с тем, в стандартном алгоритме Cuckoo search вероятность pa и параметры полёта Леви являются константами. Существует улучшенный алгоритм кукушки (Improved Cuckoo Search, ICS), который использует динамические значения этих параметров. В целях повышения точности целесообразно использовать большие значения величин pa и a на начальных итерациях, и меньшие значения на поздних.
См. также Кукушкино хеширование
Литература X.-S. Yang; S. Deb (December 2009). Cuckoo search via Lévy flights. World Congress on Nature & Biologically Inspired Computing (NaBIC 2009). IEEE Publications. pp. 210–214. Карпенко А.П. «Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов»// «Информационные технологии» - 2012. - №7. - С. 13-15. Yang, X.-S., and Deb, S. (2010), “Engineering Optimisation by Cuckoo Search”, Int. J. Mathematical Modelling and Numerical Optimisation, Vol. 1, No. 4, 330–343 (2010). Barthelemy, P., Bertolotti, J., Wiersma, D. S., 2008. ‘A L´evy flight for light’, Nature, 453, 495-498.
Категория:Алгоритмы оптимизации