Поиск кукушки

Эта статья об алгоритме поиска. Алгоритм хеширования см. в разделе « Хеширование с кукушкой» .

В исследовании операций поиск с кукушкой — это оптимизации, алгоритм разработанный Синь-Ше Яном и Суашем Деб. в 2009 году. Было показано, что это частный случай известной стратегии (μ + λ)-эволюции . Он был вдохновлен облигатным выводковым паразитизмом некоторых видов кукушек , откладывающих яйца в гнезда птиц-хозяев других видов. Некоторые птицы-хозяева могут вступить в прямой конфликт с вторгшимися кукушками. Например, если птица-хозяин обнаружит, что яйца чужие, она либо выбросит эти чужие яйца, либо просто покинет свое гнездо и построит новое гнездо в другом месте. Некоторые виды кукушек, такие как Нового Света, , паразитирующая на выводках тапера развились таким образом, что самки паразитических кукушек часто очень специализируются на имитации цвета и рисунка яиц нескольких выбранных видов-хозяев. Поиск с кукушкой идеализировал такое поведение при размножении и, следовательно, может применяться для решения различных задач оптимизации.

Метафора

Поиск с кукушкой (CS) использует следующие представления:

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

CS основан на трех идеализированных правилах:

1. Каждая кукушка откладывает по одному яйцу и сбрасывает его в случайно выбранное гнездо;
2. Лучшие гнезда с высоким качеством яиц перейдут в следующее поколение;
3. Число доступных гнезд-хозяев фиксировано, и яйцо, снесенное кукушкой, обнаруживается птицей-хозяином с вероятностью $p_{a}\in (0,1)$. В этом случае птица-хозяин может выбросить яйцо/покинуть гнездо и построить совершенно новое гнездо.

Кроме того, Янг и Деб обнаружили, что поиск в стиле случайного блуждания лучше выполняется с помощью полетов Леви, чем простое случайное блуждание .

Алгоритм

Псевдокод : можно резюмировать следующим образом

Objective function: $f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,$
Generate an initial population of $n$ host nests; 
While (t<MaxGeneration) or (stopping criterion)
    Get a cuckoo randomly (say, i) and replace its solution by performing Lévy flights;
    Evaluate its quality/fitness $F_{i}$
        [For maximization, $F_{i}\propto f(\mathbf {x} _{i})$ ];
    Choose a nest among n (say, j) randomly;
    if ($F_{i}>F_{j}$),
        Replace j by the new solution;
    end if
    A fraction ($p_{a}$) of the worse nests are abandoned and new ones are built;
    Keep the best solutions/nests;
    Rank the solutions/nests and find the current best;
    Pass the current best solutions to the next generation;
end while

Важным преимуществом этого алгоритма является его простота. Фактически, по сравнению с другими метаэвристическими алгоритмами, основанными на популяциях или агентах, такими как оптимизация роя частиц и поиск гармонии , по существу существует только один параметр. $p_{a}$ в CS (не считая численности населения $n$). Поэтому это очень легко реализовать.

размер

Важным вопросом является применение полетов Леви и случайных блужданий в общем уравнении для генерации новых решений.

$\mathbf {x} _{t+1}=\mathbf {x} _{t}+sE_{t},$

где $E_{t}$ извлекается из стандартного нормального распределения с нулевым средним значением и единичным стандартным отклонением для случайных блужданий или извлекается из распределения Леви для полетов Леви . Очевидно, что случайные блуждания также могут быть связаны со сходством яйца кукушки и яйца хозяина, что может быть сложно реализовать. Здесь размер шага $s$ определяет, как далеко может зайти случайный ходок за фиксированное количество итераций. Генерация размера шага Леви часто является сложной задачей, и сравнение трех алгоритмов (включая алгоритм Мантеньи) ) исполнил Леккарди который нашел реализацию подхода Чемберса и др. быть наиболее эффективным в вычислительном отношении из-за небольшого количества требуемых случайных чисел.

Если s слишком велико, то новое сгенерированное решение будет слишком далеко от старого решения (или даже выйдет за пределы). Тогда такой шаг вряд ли будет принят. Если s слишком мало, изменение слишком мало, чтобы быть значимым, и, следовательно, такой поиск неэффективен. Поэтому правильный размер шага важен для обеспечения максимально эффективного поиска.

Например, для простых изотропных случайных блужданий мы знаем, что среднее расстояние $r$ путешествовавший в d-мерном пространстве

$r^{2}=2dDt,$

где $D=s^{2}/2\tau$ – эффективный коэффициент диффузии. Здесь $s$ - размер шага или расстояние, пройденное при каждом прыжке, и $\tau$ время, необходимое для каждого прыжка. Из приведенного выше уравнения следует, что

$s^{2}={\frac {\tau \;r^{2}}{t\;d}}.$

Для типичного масштаба длины L интересующего измерения локальный поиск обычно ограничен областью $r=L/10$. Для $\tau =1$ и t=100–1000, мы имеем $s\approx 0.01L$ для d=1 и $s\approx 0.001L$ для д=10. Следовательно, для большинства задач мы можем использовать s/L=0,001–0,01. Хотя точный вывод может потребовать детального анализа поведения полетов Леви.

Анализ алгоритмов и сходимости будет плодотворным, поскольку существует множество открытых проблем, связанных с метаэвристикой.

Теоретический

В качестве значительных усилий требуется теоретический анализ для улучшения производительности алгоритмов на основе CS:

1. Теоретический анализ сходимости алгоритмов на основе CS
2. Обеспечение достаточных и необходимых условий для настройки параметров управления.
3. Использование неоднородных правил поиска для улучшения классического алгоритма CS

поиска

Сходимость алгоритма поиска кукушки можно существенно улучшить за счет генетической замены заброшенных гнезд (вместо использования случайных замен из исходного метода). Также в алгоритм были внесены изменения путем дополнительного скрещивания лучших (высококачественных) гнезд. и этот подход был успешно применен к ряду задач промышленной оптимизации.