Алгоритъм на кукувицата (АК) е оптимизационен алгоритъм за сортиране, разработен от Син-шъ Ян (Xin-She Yang) и Суаш Деб (Suash Deb) през 2009. Той е вдъхновен от форма на гнездови паразитизъм на някои видове кукувици, които снасят яйцата си в гнезда на други видове птици-гостоприемници. Някои видове птици могат да влязат в пряк конфликт с кукувицата-натрапник. Например, ако птицата-гостоприемник открие, че яйцата в гнездото не са нейни, тя ще изхвърли чуждото яйце или просто ще напусне гнездото и ще създаде ново на друго място. Някои видове като раираната кукувица (Tapera naevia) са еволюирали по такъв начин, че женските птици напълно са се специализирали в имитирането на цветовете и шарките на яйца на няколко конкретни вида птици-гостоприемници.
Алгоритъмът на кукувицата взима метафората от този начин за размножаване и така може да приложен при многобройни оптимизационни проблеми. Неговите резултати биха могли да надминат други математически алгоритми, използвани дотогава. Алгоритъмът използва следната логика: Всяко яйце от гнездото представлява решение, а кукувичето яйце представлява ново решение. Целта е да се използва новото и потенциално по-добро решение (това на кукувицата) като заместител на не толкова добрите други решения в гнездата. В най-простата форма на алгоритъма във всяко гнездо има само едно яйце. Алгоритъмът може да бъде разгърнат и в по-сложни случаи, където в гнездото има повече от едно яйце, като всяко представлява съвкупност от решения.
Алгоритъмът се базира на три основни правила: Всяка кукувица снася само едно яйце и го изоставя в едно случайно избрано гнездо. Най-добрите гнезда с най-приспособени яйца (т.е. решения с най-добра фитнес функция) ще осигурят поява на идни поколения. Броят на гнездата-гостоприемници е фиксиран и яйцето, снесено от кукувицата, може да бъде открито от птицата-гостоприемник с вероятност . При откриване на лоша съвкупност, тя бива премахната от последващите изчисления.
Като допълнение Ян и Деб откриват, че Полетът на Леви дава по-добри резултати при случайното обхождане на съвкупността от обикновеното случайно блуждаене.
Псевдокодът може да бъде обобщен по следния начин:
Обхват на функцията: Генериране на първоначална популация от на брой гнезда – домакини; While (t < крайно поколение) или (критерий за спиране) Изберане на произволна кукувица(i) и замесване на нейното решение чрез полети на Леви; Повишаване на нейното качество/способност [За максимизиране, ]; Избиране на случайно гнездо(j) от съвкупността ; if (), Заместване на j с новото решение; end if Фракцията () от най-лошите изоставени гнезда и най-ново построените; Запазване на най-добрите решения/гнезда; Подреждане на решенията/гнездата и намиране на най-добрите; Предаване на най-добрите решения на следващите поколения; end while
Важно предимство на този алгоритъм е неговата простота. Всъщност, в сравнение с други метаевристични алгоритми и популационни алгоритми, пример за които са оптимизация в рояк от частици и хармоничното търсене, тук имаме само един параметър – вероятността (освен размера на множеството ). Следователно, алгоритъмът на кукувицата е много лесен за имплементиране.
Случайно обхождане и размер на стъпката Важен момент е приложението на полета на Леви и случайните обхождания в родовото уравнение с цел получаването на нови решения:
където е резултат от стандартно нормално отклонение с медиана нула и хармонично стандартно отклонение за случайните обхождания или е резултат от отклонението на Леви за полетите на Леви. Очевидно случайните обхождания могат също да се свържат с яйцата на кукувицата и яйцата на птицата-гостоприемник, което понякога е доста трудно за имплементация. Тук размерът на стъпката определя доколко далеч може да стигне случайното обхождане при фиксиран брой на итерациите. Генерирането на размера на стъпката на Леви често е сложно. Сравнение на трите алгоритъма (включително и алгоритъма на МантегмаR. N. Mantegna, Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes, Physical Review E, Vol.49, 4677 – 4683 (1994).) е извършено от ЛекардиM. Leccardi, Comparison of three algorithms for Levy noise generation, Proceedings of fifth EUROMECH nonlinear dynamics conference (2005)., който открива, че имплементацията на подхода на ЧеймбърсJ. M. Chambers, C. L. Mallows, and B. W. Stuck, A method for simulating stable random variables, Journal of the American Statistical Association, Vol.71, 340 – 344 (1976) за симулирането на стабилни производни променливи е най-ефективен от гледна точка на скорост на изчисление поради ниския брой произволни числа, които са необходими.
Ако стъпката е твърде голяма, тогава новогенерираното решение ще е твърде различно от старото (или в краен случай ще излезе извън пространстовото на търсенето). В такъв случай вероятността такъв ход да бъде приет е много малка. Ако стъпката е твърде малка, промяната ще е твърде малка, за да е от значение, което прави такъв вид търсене нискоефективно. Поради тези причини размерът на стъпката е с голямо значение, ако искаме да направим търсенето възможно най-ефикасно.
Например, за прости изотропни случайни обхождания знаем, че средното изминато разстояние в d-пространството е:
където e коефициентът на ефективна дифузия. Тук е размерът на стъпката или изминатото разстояние между всеки скок и е времето, необходимо за всеки скок. Горното уравнение загатва, чеX.-S. Yang, Nature-Inspired Metaheuristic Algorithms, 2nd Edition, Luniver Press, (2010).
За типичния мащаб за дължина L на измерението, което разглеждаме, локалното търсене е стандартно ограничено в допустимата област на . За и t=100 до 1000, имаме за d=1, и за d=10. Следователно, може да използваме s/L=0.001 to 0.01 за повечето проблеми, въпреки че точното отклонение може да изисква детайлен анализ на поведението на полетите на Леви.M. Gutowski, Lévy flights as an underlying mechanism for global optimization algorithms, ArXiv Mathematical Physics e-Prints, юни (2001). Алгоритмичният и конвергентният анализ биха били полезни, защото има много нерешени проблеми, свързани с метаевристиката.X. S. Yang, Metaheuristic optimization: algorithm analysis and open problems, in: Experimental Algorithms (SEA2011), Eds (P. M. Pardalos and S. Rebennack), LNCS 6630, pp.21 – 32 (2011).
Имплементация Псевдокодът е даден като процедурна имплементация, но Ян и Деб предоставят векторна имплементация, която е много ефективна в реалния свят, ако яйцето на кукувицата много прилича на яйцата на птицата, в чието гнездо е снесла яйцето. Тогава кукувичето яйце има по-малка вероятност да бъде разкрито и по този начин работата би трябвало да бъде свързана с трудността на решенията. Също така, добра идея е да се направи произволно обхождане по диагонал с някои произволни на големина стъпки. За MATLAB имплементация, това произволно диагонално обхождане може отчасти да бъде постигнато от: stepsize=rand*(nest(randperm(n),:)-nest(randperm(n),:)); new_nest=nest+stepsize.*K; където K = rand(size(nest))>pa и pa е стъпката на откриване. Стандартният алгоритъм на кукувицата за MATLAB е достъпен. Въпреки това има спор относно дали тази имплементация наистина отразява оригинално публикувания алгоритъм на кукувицата. Диагоналното обхождане описано по-горе доста прилича на друг алгоритъм за оптимизация, наречен диференциална еволюция. Показано е, че диагонално обхождане влияе повече на бързодействието на алгоритъма отколкото самият алгоритъм на кукувицата.
Обектно ориентирана имлементация на алгоритъма на кукувицата е предоставен от Баканин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).. От друга страна, модифициран алгоритъм на кукувицата е също така имплементиран като неограничен оптимизационен проблем.M. Tuba, M. Subotic, and N. Stanarevic, Modified cuckoo search algorithm for unconstrained optimization problems, Proc. of the 5th European Conference on European Computing Conference (ECC'11), pp. 263 – 268 (2011).
Теоретичен анализ Въпреки че е имало прогрес с алгоритмите, базирани на алгоритъма на кукувицата до 2009, трябват значителни усилия, за да се подобри още производителността: Теоретичен анализ подкрепящ сходството на алгоритмите базирани на алгоритъма на кукувицата; Осигуряването на необходимите и достатъчни условия за контрола на настройките на параметрите; Използвайки нехомогенни правила за търсене, за да наподоби още повече класическия алгоритъм на кукувицата.
Сходни анализи на оригиналния алгоритъм на кукувицата и варианта с нехомогенните правила за търсене, са били представени с идеята да осигурят теоретични доказателства.
Модифициран алгоритъм на кукувицата Модификация на стандартния алгоритъм на кукувицата е била направена от Лалтън. с идеята да увеличи сходствата. Модификацията включва допълнителна стъпка при размяната на най-горните яйца. Показано е че модифицирания алгоритъм на кукувицата (МАК) има по-добра производителност от стандартния алгоритъм на кукувицата и другите алгоритми като работи по-бързо, когато е приложен за серия от стандартни оптимизации. Впоследствие, модифицираният алгоритъм на кукувицата е прилаган за оптимизация на неструктурирани проблеми, което намалило времето за изпълнение значително. S. Walton, O. Hassan, K. Morgan, Using proper orthogonal decomposition to reduce the order of optimization problems, in: Proc. 16th Int. Conf. on Finite Elrments in Flow Problems (Eds. Wall W.A. and Gvravemeier V.), Munich, p.90 (2011).Walton, S., Hassan, O. and Morgan, K. (2012), Reduced order mesh optimisation using proper orthogonal decomposition and a modified cuckoo search. Int. J. Numer. Meth. Engng. doi: 10.1002/nme.4400 Като добавка, друго интересно подобрение на алгоритъма на кукувицата е така наречения квантов алгоритъм на кукувицата (quantum-inspired Cuckoo Search Algorithm (QICSA)) с убедителни резултати. A. Layeb, A novel quantum inspired cuckoo search for knapsack problems, Int. J. Bio-Inspired Computation, Vol. 3, 297 – 305 (2011).
Многообектен алгоритъм на кукувицата Многообектен алгоритъм на кукувицата е метод, разработен да решава задачи, които за да се оптимизират трябва да се вземат под внимание много фактори.X. S. Yang and S. Deb, Multiobjective cuckoo search for design optimization, Computers and Operations Research, October (2011). Този подход използва произволни тегла, за да обедини множество обекти до един-единствен. Както теглата варират произволно, Парето фронтовете могат да бъдат намерени, така че точките могат да бъдат разпределени разнопосочно през фронтовете.
Хибридизация Макар че алгоритъмът на кукувицата е базиран на колективно поведение от децентрализирани, самостоятелно организирани системи, той може да бъде хибридизиран с други алгоритми от този вид, като по този начин отстранява недостатъците им.F. Wang, L. Lou, X. He, Y. Wang, Hybrid optimization algorithm of PSO and Cuckoo Search, in: Proc. of 2nd Int. Conference on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC'11), pp. 1172 – 1175 (2011).
Приложения