WikiSort.ru - Программирование

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

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

Некоторые виды кукушек, такие как гнездовые паразиты с Нового мира, например полосатая или четырёхкрылая кукушка (Tapera naevia), эволюционировали таким образом, что самки очень часто специализируются на имитации цветов и структуры яиц избранных видов птиц-хозяев.

Алгоритм

Для простоты описания нового алгоритма кукушки воспользуемся следующими тремя идеализированными правилами:

• Кукушка закладывает по одному яйцу за раз, и сбрасывает его в случайно выбранном гнезде;
• Лучшие гнезда с высоким качеством яиц (решения) переносятся на следующие поколения;
• Количество доступных хозяйских гнезд фиксировано, и хозяин может обнаружить инородное яйцо с вероятностью Pa ∈ [0, 1]. В этом случае птица-хозяин может либо выбросить яйцо из гнезда, либо покинуть гнездо, чтобы построить совершенно новое гнездо в новом месте.

Схему алгоритма можно представить в следующем виде:

1. Инициализируем популяцию S = (s_i, i ∈ [1 : |S|]) из |S| хозяйских гнёзд и кукушку, т.е. определяем начальные значения компонентов векторов X_i; i ∈ [1 : |S|], и вектор начального положения кукушки X_c;
2. Находим новое X_c, с помощью полётов Леви.
3. Случайным образом находим гнездо s_i: i ∈ [1 : |S|], и, если f(X_c) > f(X_i), заменяем яйцо в этом гнезде на яйцо кукушки, т.е. полагаем X_i = X_c;
4. С вероятностью p_a удаляем из популяции некоторое число худших случайно выбранных гнезд и строим новые гнезда в местах определённых с помощью полётов Леви.
5. Если поколение достигло заданного предела, то заканчиваем алгоритм, иначе переходим ко второму шагу.

Полёты Леви

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

          Xc(t+1)  = Xc(t) + α ⊕ Levy(λ)

где, t – поколение или номер итерации, a – размер шага, который зависит от масштаба задачи (обычно принимают равной единице), ⊕ - произведение Адамара.

Улучшенный алгоритм кукушки

Вместе с тем в стандартном алгоритме CS вероятность pa и параметры полёта Леви являются константами. Существует улучшенный алгоритм кукушки (Improved Cuckoo Search, ICS), который использует динамические значения этих параметров. В целях повышения точности целесообразно использовать большие значения величин p_a и 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.