Алгоритм зозулі

Алгоритм зозулі використовує наступні позначення: Кожне яйце в гнізді є розв'язком, а яйце зозулі являє собою новий розв'язок. Метою є використання нових і потенційно найкращих розв'язків (зозуль) для того, щоб замінити не дуже вдалі розв'язки у гніздах. У найпростішій формі, кожне гніздо має одне яйце. Алгоритм може бути розширеним до складніших випадків, в яких кожне гніздо має кілька яєць, що являють собою набір розв'язків.

Алгоритм зозулі базується на трьох ідеалізованих правилах:
1. Кожна зозуля кладе одне яйце за раз, і підкладає його у випадково обране гніздо;
2. Найкращі гнізда з високою якістю яєць будуть перенесені до наступного покоління;
3. Число доступних гнізд господарів фіксоване, а яйця підкладені зозулею будуть виявлені господарями гнізда з ймовірністю ${\displaystyle p_{a}\in (0,1)}$. .
Виявлення працює на деякій множині гірших гнізд і знайдені розв'язки викидаються з подальших розрахунків.

Псевдо-код алгоритму буде виглядати так:

Objective function: ${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$
Generate an initial population of ${\displaystyle n}$ host nests; 
While (t<MaxGeneration) or (stop criterion)
   Get a cuckoo randomly (say, i) and replace its solution by performing Lévy flights;
   Evaluate its quality/fitness ${\displaystyle F_{i}}$
         [For maximization, ${\displaystyle F_{i}\propto f(\mathbf {x} _{i})}$ ];
   Choose a nest among n (say, j) randomly;
   if (${\displaystyle F_{i}>F_{j}}$),
          Replace j by the new solution;
   end if
   A fraction (${\displaystyle 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

Важливою перевагою цього алгоритму є його простота. Насправді, в порівнянні з іншими еволюційними або агент-орієнтованими алгоритмами, такими як метод рою часток або гармонійний пошук, він керується тільки одним параметром ${\displaystyle p_{a}}$ в CS (крім розміру популяції ${\displaystyle n}$).

Важливим питанням є застосування en:Lévy flight і випадкових блукань у загальному рівнянні для генерації нових розв'язків

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

де ${\displaystyle E_{t}}$ взято з нормального розподілу з нульовим середнім і єдиним стандартним відхиленням для випадкових блукань, або взяті зі стійкого розподілу для Lévy flights. Очевидно, що випадкове блукання також може бути пов'язане зі схожістю яєць зозулі і господаря, та може бути складніше в реалізації. Тут розмір кроку ${\displaystyle s}$ визначає, наскільки далеко ходок може піти за фіксоване число ітерацій. В генерації Леві визначення розміру кроку складне, тому використовують алгоритм Мантени.[4] Якщо ${\displaystyle s}$ дуже велике, то новий згенерований розв'язок буде занадто далеко від старого (або може навіть не належати до допустимих розв’язків). Тоді такий крок навряд чи буде прийнято. Якщо ${\displaystyle s}$ занадто мале, зміни занадто малі, щоб бути значними, і, отже, такий пошук не є ефективним. Таким чином, для найбільшої ефективності пошуку розмір кроку має дуже велике значення. Наприклад, для простих ізотропних випадкових блукань, ми знаємо, що середня відстань r в d-мірному просторі ${\displaystyle r^{2}=2dDt,}$ , де ${\displaystyle D=s^{2}/2\tau }$ ефективний коефіцієнт дифузії. Де s розмір кроку або відстані в кожному стрибку, і τ є час, необхідний для кожного стрибка. Це рівняння означає, що

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

Локальний пошук, як правило, лімітовано в області ${\displaystyle r=L/10}$. Для τ = 1 і Т = 100 до 1000, маємо ${\displaystyle s\approx 0.01L}$ для d = 1, а ${\displaystyle s\approx 0.001L}$ для d = 10. Таким чином, можна використовувати S / L = 0,001 до 0,01, для більшості завдань.[5]

Псевдо-код був даний в послідовній формі, але автори алгоритму використали векторизовану реалізацію, яка є дуже ефективною. У реальному світі, якщо яйце зозулі дуже схоже на яйця господаря, то таке яйце буде виявлено з меншою ймовірністю, таким чином, придатність повинна бути пов'язана з різницею в розв’язках. Таким чином, це гарна ідея, щоб зробити випадкове блукання одностороннім з деяким випадковим розміром кроку. Для реалізації за допомогою Matlab, це упереджене випадкове блукання може частково бути досягнуто шляхом
stepsize=rand*(nest(randperm(n),:)-nest(randperm(n),:));
new_nest=nest+stepsize.*K;
K=rand(size(nest))>pa де pa є discovery rate. Об'єктно-орієнтована програмна реалізація пошуку зозулі була надана Баканіним[6]. З іншого боку, модифікований алгоритм пошуку зозулі також реалізовано для завдань безумовної оптимізації. Код модифікованого алгоритму можна знайти тут

Модифікацію стандартного пошуку зозулі було зроблено Уолтоном і співавторами[7] з метою прискорення збіжності. Модифікація включає в себе додатковий крок обміну інформацією між найголовнішими яйцями. Було показано, що модифікований пошук зозулі (MCS) перевершує стандартний пошук зозулі та деякі інші алгоритми, з точки зору швидкості збіжності, при нанесенні на серію стандартних тестів цільової функції. Згодом модифікований пошук зозулі був застосований для оптимізації неструктурованої сітки, що значно зменшує обчислювальні витрати.[8]

Метод багатоцільового пошуку зозулі був розроблений для розв'язування багатокритеріальної задачі оптимізації.[9] Цей підхід використовує випадкові ваги для об'єднання кількох цілей для однієї мети. Ваги змінюються випадковим чином.

Застосування пошуку зозулі в інженерних задачах оптимізації показали його ефективним. Наприклад, для розробки англ. spring design та нім. welded beam design пошук зозулі отримав кращі розв'язки в порівнянні з існуючими в літературі. Дискретний алгоритм пошуку зозулі нещодавно було використано для вирішення проблеми «планування медсестри»[10]. Ефективний підхід обчислення на основі пошуку зозулі був запропонований для злиття даних в бездротових мережах датчиків[11][12]. Нова модифікація пошуку зозулі була розроблена, щоб вирішити задачу про ранець[13], яка показує його ефективність. Пошук зозулі також може бути використаний для ефективної генерації незалежних тестів для структурного тестування програмного забезпечення[14] і генерації тестових даних.

• Алгоритм гравітаційного пошуку
• Алгоритм імітації відпалу
• Мурашиний алгоритм
• Евристика
• Евристичний алгоритм