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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$r^{2}=2dDt,$

където $D=s^{2}/2\tau$ e коефициентът на ефективна дифузия. Тук $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$ за d=10. Следователно, може да използваме s/L=0.001 to 0.01 за повечето проблеми, въпреки че точното отклонение може да изисква детайлен анализ на поведението на полетите на Леви. Алгоритмичният и конвергентният анализ биха били полезни, защото има много нерешени проблеми, свързани с метаевристиката.

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

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

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

new_nest=nest+stepsize.*K;

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

Алгоритъмът на кукувицата е адаптиран да решава сложни задачи за комбинаторна оптимизация като Задача за търговския пътник., за ефективно генериране на независими тестови пътеки за структурно тестване на софтуер, както и за генериране на тестови данни. Алгоритъмът на кукувицата е използван за оптимизация на нано-електронна технология базирана на операционно усилвателни интегрирани вериги, като довежда до оптимални резултати много бързо и точно.

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

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

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

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

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

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