Алгоритъм на кукувицата

Графично изобразяване на логическата последователност на алгоритъма

Алгоритъм на кукувицата (АК) е оптимизационен алгоритъм за сортиране, разработен от Син-шъ Ян (Xin-She Yang) и Суаш Деб (Suash Deb) през 2009. Той е вдъхновен от форма на гнездови паразитизъм на някои видове кукувици, които снасят яйцата си в гнезда на други видове птици-гостоприемници. Някои видове птици могат да влязат в пряк конфликт с кукувицата-натрапник. Например, ако птицата-гостоприемник открие, че яйцата в гнездото не са нейни, тя ще изхвърли чуждото яйце или просто ще напусне гнездото и ще създаде ново на друго място. Някои видове като раираната кукувица (Tapera naevia) са еволюирали по такъв начин, че женските птици напълно са се специализирали в имитирането на цветовете и шарките на яйца на няколко конкретни вида птици-гостоприемници.

Алгоритъмът на кукувицата взима метафората от този начин за размножаване и така може да приложен при многобройни оптимизационни проблеми. Неговите резултати биха могли да надминат други математически алгоритми, използвани дотогава. Алгоритъмът използва следната логика: Всяко яйце от гнездото представлява решение, а кукувичето яйце представлява ново решение. Целта е да се използва новото и потенциално по-добро решение (това на кукувицата) като заместител на не толкова добрите други решения в гнездата. В най-простата форма на алгоритъма във всяко гнездо има само едно яйце. Алгоритъмът може да бъде разгърнат и в по-сложни случаи, където в гнездото има повече от едно яйце, като всяко представлява съвкупност от решения.

Алгоритъмът се базира на три основни правила:

1. Всяка кукувица снася само едно яйце и го изоставя в едно случайно избрано гнездо.
2. Най-добрите гнезда с най-приспособени яйца (т.е. решения с най-добра фитнес функция) ще осигурят поява на идни поколения.
3. Броят на гнездата-гостоприемници е фиксиран и яйцето, снесено от кукувицата, може да бъде открито от птицата-гостоприемник с вероятност ${\displaystyle p_{a}\in (0,1)}$. При откриване на лоша съвкупност, тя бива премахната от последващите изчисления.

Като допълнение Ян и Деб откриват, че Полетът на Леви дава по-добри резултати при случайното обхождане на съвкупността от обикновеното случайно блуждаене.

Псевдокодът може да бъде обобщен по следния начин: 

Обхват на функцията: ${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$
Генериране на първоначална популация от ${\displaystyle n}$ на брой гнезда – домакини;
While (t < крайно поколение) или (критерий за спиране)
   Изберане на произволна кукувица(i) и замесване на нейното решение чрез полети на Леви;
     Повишаване на нейното качество/способност ${\displaystyle F_{i}}$
         [За максимизиране, ${\displaystyle F_{i}\propto f(\mathbf {x} _{i})}$];
      Избиране на случайно гнездо(j) от съвкупността ${\displaystyle n}$;
   if (${\displaystyle F_{i}>F_{j}}$),
          Заместване на j с новото решение;
   end if
   Фракцията (${\displaystyle p_{a}}$) от най-лошите изоставени гнезда и най-ново построените;
  Запазване на най-добрите решения/гнезда;
  Подреждане на решенията/гнездата и намиране на най-добрите;
  Предаване на най-добрите решения на следващите поколения;
end while

Важно предимство на този алгоритъм е неговата простота. Всъщност, в сравнение с други метаевристични алгоритми и популационни алгоритми, пример за които са оптимизация в рояк от частици и хармоничното търсене, тук имаме само един параметър – вероятността ${\displaystyle p_{a}}$ (освен размера на множеството ${\displaystyle n}$). Следователно, алгоритъмът на кукувицата е много лесен за имплементиране.

Случайно обхождане и размер на стъпката

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

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

където ${\displaystyle E_{t}}$ е резултат от стандартно нормално отклонение с медиана нула и хармонично стандартно отклонение за случайните обхождания или е резултат от отклонението на Леви за полетите на Леви. Очевидно случайните обхождания могат също да се свържат с яйцата на кукувицата и яйцата на птицата-гостоприемник, което понякога е доста трудно за имплементация. Тук размерът на стъпката ${\displaystyle s}$ определя доколко далеч може да стигне случайното обхождане при фиксиран брой на итерациите. Генерирането на размера на стъпката на Леви често е сложно. Сравнение на трите алгоритъма (включително и алгоритъма на Мантегма^[1]) е извършено от Лекарди^[2], който открива, че имплементацията на подхода на Чеймбърс^[3] за симулирането на стабилни производни променливи е най-ефективен от гледна точка на скорост на изчисление поради ниския брой произволни числа, които са необходими.

Ако стъпката е твърде голяма, тогава новогенерираното решение ще е твърде различно от старото (или в краен случай ще излезе извън пространстовото на търсенето). В такъв случай вероятността такъв ход да бъде приет е много малка. Ако стъпката е твърде малка, промяната ще е твърде малка, за да е от значение, което прави такъв вид търсене нискоефективно. Поради тези причини размерът на стъпката е с голямо значение, ако искаме да направим търсенето възможно най-ефикасно.

Например, за прости изотропни случайни обхождания знаем, че средното изминато разстояние ${\displaystyle r}$ в d-пространството е:

${\displaystyle r^{2}=2dDt,}$

където ${\displaystyle D=s^{2}/2\tau }$ e коефициентът на ефективна дифузия. Тук ${\displaystyle s}$ е размерът на стъпката или изминатото разстояние между всеки скок и ${\displaystyle \tau }$ е времето, необходимо за всеки скок. Горното уравнение загатва, че^[4]

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

За типичния мащаб за дължина L на измерението, което разглеждаме, локалното търсене е стандартно ограничено в допустимата област на ${\displaystyle r=L/10}$. За ${\displaystyle \tau =1}$ и t=100 до 1000, имаме ${\displaystyle s\approx 0.01L}$ за d=1, и ${\displaystyle s\approx 0.001L}$ за d=10. Следователно, може да използваме s/L=0.001 to 0.01 за повечето проблеми, въпреки че точното отклонение може да изисква детайлен анализ на поведението на полетите на Леви.^[5] Алгоритмичният и конвергентният анализ биха били полезни, защото има много нерешени проблеми, свързани с метаевристиката.^[6]

Имплементация

Псевдокодът е даден като процедурна имплементация, но Ян и Деб предоставят векторна имплементация, която е много ефективна в реалния свят, ако яйцето на кукувицата много прилича на яйцата на птицата, в чието гнездо е снесла яйцето. Тогава кукувичето яйце има по-малка вероятност да бъде разкрито и по този начин работата би трябвало да бъде свързана с трудността на решенията. Също така, добра идея е да се направи произволно обхождане по диагонал с някои произволни на големина стъпки. За MATLAB имплементация, това произволно диагонално обхождане може отчасти да бъде постигнато от:

stepsize=rand*(nest(randperm(n),:)-nest(randperm(n),:));

new_nest=nest+stepsize.*K;

където K = rand(size(nest))>pa и pa е стъпката на откриване. Стандартният алгоритъм на кукувицата за MATLAB е достъпен.^[7] Въпреки това има спор относно дали тази имплементация наистина отразява оригинално публикувания алгоритъм на кукувицата. Диагоналното обхождане описано по-горе доста прилича на друг алгоритъм за оптимизация, наречен диференциална еволюция. Показано е, че диагонално обхождане влияе повече на бързодействието на алгоритъма отколкото самият алгоритъм на кукувицата.

Обектно ориентирана имлементация на алгоритъма на кукувицата е предоставен от Баканин^[8]. От друга страна, модифициран алгоритъм на кукувицата е също така имплементиран като неограничен оптимизационен проблем.^[9]

Теоретичен анализ

Въпреки че е имало прогрес с алгоритмите, базирани на алгоритъма на кукувицата до 2009, трябват значителни усилия, за да се подобри още производителността:^[10]

• Теоретичен анализ подкрепящ сходството на алгоритмите базирани на алгоритъма на кукувицата;
• Осигуряването на необходимите и достатъчни условия за контрола на настройките на параметрите;
• Използвайки нехомогенни правила за търсене, за да наподоби още повече класическия алгоритъм на кукувицата.

Сходни анализи на оригиналния алгоритъм на кукувицата и варианта с нехомогенните правила за търсене, са били представени с идеята да осигурят теоретични доказателства.^[10]

Модифициран алгоритъм на кукувицата

Модификация на стандартния алгоритъм на кукувицата е била направена от Лалтън.^[11] с идеята да увеличи сходствата. Модификацията включва допълнителна стъпка при размяната на най-горните яйца. Показано е че модифицирания алгоритъм на кукувицата (МАК) има по-добра производителност от стандартния алгоритъм на кукувицата и другите алгоритми като работи по-бързо, когато е приложен за серия от стандартни оптимизации. Впоследствие, модифицираният алгоритъм на кукувицата е прилаган за оптимизация на неструктурирани проблеми, което намалило времето за изпълнение значително. ^[12][13] Като добавка, друго интересно подобрение на алгоритъма на кукувицата е така наречения квантов алгоритъм на кукувицата (quantum-inspired Cuckoo Search Algorithm (QICSA)) с убедителни резултати. ^[14]

Многообектен алгоритъм на кукувицата

Многообектен алгоритъм на кукувицата е метод, разработен да решава задачи, които за да се оптимизират трябва да се вземат под внимание много фактори.^[15]Този подход използва произволни тегла, за да обедини множество обекти до един-единствен. Както теглата варират произволно, Парето фронтовете могат да бъдат намерени, така че точките могат да бъдат разпределени разнопосочно през фронтовете.

Хибридизация

Макар че алгоритъмът на кукувицата е базиран на колективно поведение от децентрализирани, самостоятелно организирани системи, той може да бъде хибридизиран с други алгоритми от този вид, като по този начин отстранява недостатъците им.^[16]

Приложения

Приложенията на алгоритъма на кукувицата в инженерни оптимизационни задачи са показали своята ефективност.^[17] Например, за проблемите свързани с конструкцията на пружини, както и на заваряване на метални греди, АК предлага по-добри решения, отколкото съществуващите в досегашната литературата. Предложен e АК за решаване на проблеми свързани с работните графици на медицинските сестри.^[18] Ефективен изчислителен подход базиран на алгоритъма на кукувицата е предложен за синтез на данни в безжични сензорни мрежи.^[19][20]

Алгоритъмът на кукувицата е адаптиран да решава сложни задачи за комбинаторна оптимизация като Задача за търговския пътник.^[21], за ефективно генериране на независими тестови пътеки за структурно тестване на софтуер^[22], както и за генериране на тестови данни.^[23][24] Алгоритъмът на кукувицата е използван за оптимизация на нано-електронна технология базирана на операционно усилвателни интегрирани вериги, като довежда до оптимални резултати много бързо и точно.^[25]

Концептуално сравнение на алгоритъма на кукувицата с алгоритмите за оптимизация в рояк от частици (Particle Swarm Optimization), диференциална еволюция (Differential evolution) и Алгоритъм на изкуствените пчелни семейства (Artificial bee colony) предполага, че алгоритъмът на кукувицата и алгоритъмът на диференциалната еволюция предоставят по-добри резултати от останалите алгоритми.^[26] Обширно и подробно проучване на различни проблеми, свързани със структурна оптимизация, стига до извода, че алгоритъмът на кукувицата постига по-добри резултати от други алгоритми.^[27] В допълнение е разработен нов подход за софтуерно тестване базиран на него^[28], както и че този алгоритъм е особено подходящ за задачи от големи мащаби (large-scale problems), което е показано в скорошно проучване.^[29] Алгоритъмът на кукувицата е прилаган да обучава невронни мрежи с подобрена производителност.^[30] Освен това АК се прилага успешно при обучаването на импулсни невронни модели.^[31] Алгоритъмът също е използван за оптимизиране процеса на изграждане на уеб услуги.^[32]

Алгоритъмът на кукувицата е надежден подход за изграждане на вградени системи (Embedded system)^[33], както и за оптимално проектиране на стоманени рамки.^[34]

По-нови изследвания показват, че АК може да надмине други алгоритми в приложения за фрезоване^[35], гъвкави производствени системи, разпределения на работни графици^[36] и други.^[37] Интересно приложение на алгоритъма е за решаване на проблеми свързани с гранични стойности.^[38]

Източници

1. R. N. Mantegna, Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes, Physical Review E, Vol.49, 4677 – 4683 (1994).
2. M. Leccardi, Comparison of three algorithms for Levy noise generation, Proceedings of fifth EUROMECH nonlinear dynamics conference (2005).
3. 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)
4. X.-S. Yang, Nature-Inspired Metaheuristic Algorithms, 2nd Edition, Luniver Press, (2010).
5. M. Gutowski, Lévy flights as an underlying mechanism for global optimization algorithms, ArXiv Mathematical Physics e-Prints, юни (2001).
6. 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).
7. www.mathworks.com
8. 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).
9. 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).
10. Cheung, Ngaam J. и др. A Non-homogeneous Cuckoo Search Algorithm based-on Quantum Mechanism for Real-Parameter Optimization // IEEE Transactions on Cybernetics. 2016. DOI:10.1109/TCYB.2016.2517140. Архивиран от оригинала на 2016-06-03. Посетен на 2016-04-25.
11. Walton, S. и др. Modified cuckoo search: A new gradient free optimisation algorithm // Chaos, Solitons & Fractals. 30 юни 2011. DOI:10.1016/j.chaos.2011.06.004.
12. 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).
13. 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
14. A. Layeb, A novel quantum inspired cuckoo search for knapsack problems, Int. J. Bio-Inspired Computation, Vol. 3, 297 – 305 (2011).
15. 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
16. 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).
17. Sean Walton, Oubay Hassan, Kenneth Morgan, Selected Engineering Applications of Gradient Free Optimisation Using Cuckoo Search and Proper Orthogonal Decomposition, Archives of Computational Methods in Engineering, June 2013, Volume 20, Issue 2, pp. 123 – 154.
18. Tein L. H. and Ramli R., Recent advancements of nurse scheduling models and a potential path Архив на оригинала от 2012-03-13 в Wayback Machine., in: Proc. 6th IMT-GT Conference on Mathematics, Statistics and its Applications (ICMSA 2010), pp. 395 – 409 (2010).
19. 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).
20. M. Dhivya and M. Sundarambal, Cuckoo search for data gathering in wireless sensor networks, Int. J. Mobile Communications, Vol. 9, pp. 642 – 656 (2011).
21. A. Ouaarab, B. Ahiod, and X.-S. Yang, Discrete cuckoo search algorithm for the travelling salesman problem, Neural Computing and Applications, (2013). doi:10.1007/s00521-013-1402-2.
22. 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)
23. K. Perumal, J. M. Ungati, G. Kumar, N. Jain, R. Gaurav and P. R. Srivastava, Test data generation: a hybrid approach using cuckoo and tabu search, Swarm, Evolutionary, and Memetic Computing (SEMCCO2011), Lecture Notes in Computer Sciences, Vol. 7077, 46 – 54 (2011)
24. Jeya Mala Dharmalingam, K. Sabari Nathan, S. Balamurugan: A hybrid test optimization framework using memetic algorithm with cuckoo flocking based search approach.SBST 2014 Proceedings of the 7th International Workshop on Search-Based Software Testing,37 – 38, ACM, doi:10.1145/2593833.2593843
25. G. Zheng, S. P. Mohanty, and E. Kougianos, „Metamodel-Assisted Fast and Accurate Optimization of an OP-AMP for Biomedical Applications Архив на оригинала от 2016-03-04 в Wayback Machine.“, in Proceedings of the 11th IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pp. 273 – 278, 2012.
26. P. Civicioglu and E. Besdok, A conception comparison of the cuckoo search, particle swarm optimization, differential evolution and artificial bee colony algorithms, Artificial Intelligence Review, DOI:10.1007/s10462-011-92760, 6 юли (2011).
27. A. H. Gandomi, X. S. Yang, A. H. Alavi, Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems, Engineering with Computers, Vol. 27, July (2011).
28. K. Choudhary and G. N. Purohit, A new testing approach using cuckoo search to achieve multi-objective genetic algorithm, J. of Computing, Vol. 3, No. 4, 117 – 119 (2011).
29. E. R. Speed, Evolving a Mario agent using cuckoo search and softmax heuristics, Games Innovations Conference (ICE-GIC), pp. 1 – 7 (2010). DOI:10.1109/ICEGIC.2010.5716893
30. E. Valian, S. Mohanna and S. Tavakoli, Improved cuckoo search algorithm for feedforward neural network training, Int. J. Artificial Intelligence and Applications, Vol. 2, No. 3, 36 – 43(2011).
31. R. A. Vazquez, Training spiking neural models using cuckoo search algorithm, 2011 IEEE Congress on Evolutionary Computation (CEC'11), pp.679 – 686 (2011).
32. V. R. Chifu, C. B. Pop, I. Salomie, D> S. Suia and A. N. Niculici, Optimizing the semantic web service composition process using cuckoo search, in: Intelligent Distributed Computing V, Studies in Computational Intelligence, Vol. 382, pp. 93 – 102 (2012).
33. A. Kumar and S. Chakarverty, Design optimization for reliable embedded system using Cuckoo Search,in: Proc. of 3rd Int. Conference on Electronics Computer Technology (ICECT2011), pp. 564 – 268 (2011).
34. A. Kaveh, T. Bakhshpoori, Optimum design of steel frames using cuckoo search algorithm with Lévy flights, Structural Design of Tall and Special Buildings, Vol. 21, online first 28 Nov 2011.
35. A. R. Yildiz, Cuckoo search algorithm for the selection of optimal machine parameters in milling operations, Int. J. Adv. Manuf. Technol., (2012). DOI:10.1007/s00170-012-4013-7
36. S. Burnwal, S. Deb, Scheduling optimization of flexible manufacturing system using cuckoo search-based approach, Int. J. Adv Manuf Technol, (2012).
37. H. Q. Zheng and Y. Zhou, A novel cuckoo search optimization algorithm based on Gauss distribution, J. Computational Information Systems, Vol. 8, 4193 – 4200 (2012).
38. A. Noghrehabadi, M. Ghalambaz and A. Vosough, A hybrid power series -- Cuckoo search optimization algorithm to electrostatic deflection of micro fixed-fixed actuators, Int. J. Multidisciplinary Science and Engineering, Vol. 2, No. 4,22 – 26 (2011).

Външни препратки

• Общодостъпна имплементация на модифицирания алгоритъм на кукувуцата

Тази страница частично или изцяло представлява превод на страницата Cuckoo search в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​