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

ПОИСК ПО САЙТУ | о проекте

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

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

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

Алгоритм

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

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

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

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

Полёты Леви

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

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

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

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

Вместе с тем в стандартном алгоритме CS вероятность 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.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2020
WikiSort.ru - проект по пересортировке и дополнению контента Википедии