Вопрос 45: Кукушкин поиск (Cuckoo Search)

Алгоритм вдохновлен поведением кукушек, подкладывающих в свои яйца в гнезда других птиц.

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

Положим, что речь идет о задаче глобальной безусловной оптимизации, в которой фитнес-функция подлежит максимизации. Алгоритм основан на трех следующих правилах: каждая кукушка откладывает одно яйцо за один раз в случайно выбранное гнездо; лучшие гнезда с яйцами высокого качества (высоким значением пригодности) переходят в следующее поколение; яйцо кукушки, отложенное в гнездо, может быть обнаружено хозяином с некоторой вероятностью $\xi_a \in (0; 1)$ и удалено из гнезда.

Схема алгоритма CS:

1. Инициализируем популяцию $S = {s_i,i \in [1:|S|]}$ из $|S|$ хозяйских гнезд и кукушку, то есть определяем векторы $X_i^0$ и вектор начального положения кукушки $X_c$.

2. Выполняя полеты Леви, находим новое положение кукушки

$X^\prime_c = X_c + V \otimes L_{|X|}( \lambda ),$

где $V = (v_j, j \in [1: |X|])$ - вектор размера шагов по соответствующим компо­нентам вектора $X$; $L_{|X|}( \lambda ) - (|X| \times 1)$ - случайный вектор независимых веще­ственных случаиных чисел, распределенных по закону Леви.

1. Случайным образом выбираем гнездо $s_j, j \in [1:|S|]$ и, если $\varphi( X_c ) > \varphi( X_j )$, заменяем яйцо в этом гнезде на яйцо кукушки, то есть полагаем $X_j = X_c$.

2. С вероятностью $\xi_a$ удаляем из популяции некоторое число худших случайно выбранных гнезд (включая, быть может, гнездо $s_j$) и по правилам шага 1 строим такое же число новых гнезд.

Начальные положения гнезд и кукушки принимаем случайными, равномерно распределенными в некотором гиперпараллелепипеде. Обычно полагают все компоненты вектора $V$ одинаковыми и равными $v$, где величина $v$ связана с масштабами области поиска. Основными свободными параметрами алгоритма являются константы, определяющие траекторию полетов Леви, и вероятность удаления гнезд $\xi_a$.

Модификации

Известно несколько модификаций алгоритма CS. В каноническом алгоритме CS кукушка в своих полетах Леви никак не учитывает информацию о лучших найденных решениях. В модифицированном алгоритме поиска кукушки (Modified Cuckoo Search, MCS) компоненты вектора $V$ вычисляют по формуле вида

$V = U_1 (0;1)( X_{ i_\ast } - X_{ i_1 } ),$

где $X_{ i_\ast }$ - лучшее текущее гнездо, а $X_{ i_1 }$- случайно выбранное гнездо $i_\ast \neq i_1$. Так определенный вектор $V$ обеспечивает большую вероятность полета кукушки к гнездам, имеющим высокую приспособленность.

С другой стороны, в каноническом алгоритме CS вероятность $\xi_a$ и параметры полета Леви являются фиксированными константами. С целью диверсификации поиска для ранних поколений целесообразно использовать большие значения величин $\xi_a$, $v$. На завершающих итерациях для повышения точности локализации экстремума разумны меньшие значения указанных величин. Улучшенный алгоритм поиска кукушки (Improved Cuckoo Search, ICS) использует динамические значения параметров $\xi_a$, $v$:

$\xi_a (t)=\xi_a^{ max }-\frac{t}{\hat{t}} (\xi_a^{ max }-\xi_a^{ min } )$

$v(t)=v^{ max } exp(dt), d= \frac{1}{\hat{t}} ln( \frac{ v^{ min } }{ v^{ max } } )$

Здесь $\xi_a^{ max }$, $\xi_a^{ min }$, $v^{ max }$, $v^{ min }$ - заданные константы.