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

Алгоритм зозулі (англ. Cuckoo search) являє собою оптимізований алгоритм, розроблений англ. Xin-She Yang та англ. Suash Deb у 2009 році. Натхненням для його створення послужив гніздовий паразитизм деяких видів зозуль, що підкладають свої яйця до гнізд інших птахів (інших видів птахів). Деякі з власників гнізд можуть вступити у прямий конфлікт із зозулями, що вдираються до них. Наприклад, якщо власник гнізда виявить, що яйця не його, то він або викине ці чужі яйця або просто покине гніздо і збудує нове десь в іншому місці. Деякі види зозуль, такі як гніздові паразити з Нового світу, наприклад смугаста або чотирикрила зозуля (Tapera naevia) еволюціонувала таким чином, що самки дуже часто спеціалізуються на імітуванні кольорів і структури яєць обраних видів птахів-господарів. У алгоритмі зозулі такий спосіб поведінки був ідеалізований і таким чином може бути пристосованим для розв'язування різноманітних задач оптимізації. Можливо, він зможе перевершити інші метаевристичні алгоритми у прикладних програмах. Іншою сферою застосування, здавалось би зовсім не пов’язаною з алгоритмом, є алгоритм хешування (розміщення з використанням функції розстановки), що був розроблений Расмусом Пагом та Флемінгом Фреш Родлером у 2001 році.

Позначення

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

Алгоритм зозулі базується на трьох ідеалізованих правилах:
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}$).

Випадкові блукання і розмір кроку

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

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

де ${\displaystyle E_{t}}$ взято з нормального розподілу з нульовим середнім і єдиним стандартним відхиленням для випадкових блукань, або взяті зі стійкого розподілу для Lévy flights. Очевидно, що випадкове блукання також може бути пов'язане зі схожістю яєць зозулі і господаря, та може бути складніше в реалізації. Тут розмір кроку ${\displaystyle s}$ визначає, наскільки далеко ходок може піти за фіксоване число ітерацій. В генерації Леві визначення розміру кроку складне, тому використовують алгоритм Мантени. Якщо ${\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, для більшості завдань.

Реалізація

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

Модифікований пошук зозулі

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

Багатоцільовий пошук зозулі (MOCS)

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

Програми

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

Посилання

1. R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005).
2. Novel «Cuckoo Search Algorithm» Beats Particle Swarm Optimization [ 5 вересня 2016 у Wayback Machine.] (англ.) [Архівовано з першоджерела 10 червня 2016.]
3. R. Pagh and F. F. Rodler, Flemming Friche (2001), Cuckoo Hashing. doi:10.1.1.25.4189. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4189 [ 1 березня 2012 у Wayback Machine.].
4. R. N. Mantegna, Fast, accurate algorithm for numerical simulation of Levy stable stochastic processes, Physical Review E, Vol.49, 4677-4683 (1994).
5. M. Gutowski, Levy flights as an underlying mechanism for global optimization algorithms, ArXiv Mathematical Physics e-Prints, June, (2001).
6. N. Bacanin, An object-oriented software implementation of a novel cuckoo search algorithm, Proc. of the 5th European Conference on European Computing Conference (ECC'11), pp. 245-250 (2011).
7. S. Walton; O. Hassan, K. Morgan and M.R. Brown (30 червня 2011). Modified cuckoo search: A new gradient free optimisation algorithm. Chaos, Solitons & Fractals. doi:10.1016/j.chaos.2011.06.004.
8. S. Walton, O. Hassan, K. Morgan, Using proper orthogonal decomposition to reduce the order ot optimization problems, in: Proc. 16th Int. Conf. on Finite Elments in Flow Problems (Eds. Wall W.A. and Gvravemeier V.), Munich, p.90 (2011).
9. X. S. Yang and S. Deb, Multiobjective cuckoo search for design optimization, Computers and Operations Research, October (2011). doi:10.1016/j.cor.2011.09.026
10. Tein L. H. and Ramli R., Recent advancements of nurse scheduling models and a potential path, in: Proc. 6th IMT-GT Conference on Mathematics, Statistics and its Applications (ICMSA 2010), pp. 395-409 (2010). http://research.utar.edu.my/CMS/ICMSA2010/ICMSA2010_Proceedings/files/statistics/ST-Lim.pdf [ 13 березня 2012 у Wayback Machine.]
11. M. Dhivya, M. Sundarambal, L. N. Anand, Energy Efficient Computation of Data Fusion in Wireless Sensor Networks Using Cuckoo Based Particle Approach (CBPA), Int. J. of Communications, Network and System Sciences, Vol. 4, No. 4, 249-255 (2011).
12. M. Dhivya and M. Sundarambal, Cuckoo search for data gathering in wireless sensor networks,Int. J. Mobile Communications, Vol. 9, pp. 642-656 (2011).
13. A. Layeb, A novel quantum-inspired cuckoo search for Knapsack problems, Int. J. Bio-inspired Computation, Vol. 4, (2011).
14. P. R. Srivastava, M. Chis, S. Deb and X. S. Yang, An efficient optimization algorithm for structural software testing, Int. J. Artificial Intelligence, Vol. 9 (S12), 68-77(2012)

Див. також

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