Algorytm kukułki

Algorytm kukułki (ang. cuckoo search, dosł. kukułcze poszukiwania) — metaheurystyczny, inspirowany naturą algorytm optymalizacyjny zaproponowany w 2009, którego twórcami są Xin-She Yang oraz Suash Deb^{[1][2][3][4][5]}. Został zainspirowany zachowaniami niektórych gatunków kukułek, które składają swoje jaja w gniazdach innych ptaków (por. powiedzenie "kukułcze jajo")^[1]. W algorytmie wykorzystane są loty Lévy'ego (ang. Lévy flights)^[1][6]. Przykładowa implementacja algorytmu kukułki znajduje się w artykule jego twórców^[2].

Reguły

Reguły algorytmu kukułki:^[1]

1. W danej chwili czasu kukułka może złożyć jedno jajo w losowo wybranym gnieździe gospodarza.
2. W następnej iteracji algorytmu są uwzględnianie gniazda wysokiej jakości.
3. Gospodarz gniazda, do którego zostało podrzucone jajo, może zauważyć to obce jajo z prawdopodobieństwem ${\displaystyle p\in [0,1]}$.

Oznaczenia

Funkcja ${\displaystyle f\colon \mathbb {R} ^{c}\rightarrow \mathbb {R} }$ jest funkcją przystosowania. Gniazdo ${\displaystyle g_{i,j}\in \mathbb {R} ^{c}}$ jest punktem w przestrzeni ${\displaystyle c}$-wymiarowej i jest potencjalnym rozwiązaniem problemu optymalizacyjnego. Indeksy ${\displaystyle i}$ oraz ${\displaystyle j}$ w symbolu ${\displaystyle g_{i,j}}$ oznaczają ${\displaystyle i}$-te gniazdo w ${\displaystyle j}$-tej iteracji algorytmu kukułki. Symbol ${\displaystyle t}$ będzie stosowany zamiennie z ${\displaystyle j}$ dla oznaczenia upływu czasu.

Algorytm

Poniżej przedstawiono przykładową wersję podstawowego algorytmu kukułki.

Algorytm rozpoczyna się w chwili ${\displaystyle t=0}$ od wygenerowania początkowej populacji gniazd gospodarzy rozmiaru ${\displaystyle \mu }$:^[1][2][4]

${\displaystyle (g_{i,0})_{i=0}^{\mu -1}}$

gdzie ${\displaystyle g_{i,0}}$ jest ${\displaystyle i}$-tym gniazdem w tej populacji.

Następnie w pętli wykonywane są poniższe czynności:^[1][2][4]

1. Dokonywane jest podstawienie ${\displaystyle t:=t+1}$.
2. Wybierany jest losowo indeks ${\displaystyle i}$ i wykonywany jest lot Lévy'ego z punktu ${\displaystyle g_{i,t}}$ do nowego punktu w przestrzeni ${\displaystyle g'\in \mathbb {R} ^{c}}$.
3. Wybierany jest losowo indeks ${\displaystyle j}$ i jeśli ${\displaystyle f(g')>f(g_{j,t})}$ dokonywane jest podstawienie ${\displaystyle g_{j,t}:=g'}$.
4. Odrzucane jest ${\displaystyle p\cdot \mu }$ gniazd o najniższej wartości funkcji przystosowania i zastępowane są one nowo wygenerowanymi w sposób losowy z użyciem lotów Lévy'ego.

Pętla kończy się, gdy zmienna ${\displaystyle t}$ osiągnie wartość graniczną lub zostanie spełniony inny warunek zakończenia^[1][2][4].

Lot Lévy'ego

Dystrybucja Lévy'ego

Lot Lévy'ego jest błądzeniem losowym, którego krok jest losowany z dystrybucji Lévy'ego^[4].

Przypisy

1. Xin-She Yang, Suash Deb. Cuckoo Search via Lévy flights. „2009 World Congress on Nature & Biologically Inspired Computing (NaBIC)”, s. 210-214, 2009. DOI: 10.1109/NABIC.2009.5393690. 
2. Xin-She Yang, Suash Deb. Engineering optimisation by cuckoo search. „International Journal of Mathematical Modelling and Numerical Optimisation”. 1 (4), s. 210-214, 2010. 
3. Xin-She Yang, Suash Deb. Cuckoo Search for Inverse Problems and Topology Optimization. „Proceedings of International Conference on Advances in Computing”, s. 291-295, 2012. DOI: 10.1007/978-81-322-0740-5_35. 
4. Xin-She Yang (ed.): Artificial Intelligence, Evolutionary Computing and Metaheuristics. In the Footsteps of Alan Turing. Springer-Verlag Berlin Heidelberg, 2013, s. I-XVIII, 1-794. DOI: 10.1007/978-3-642-29694-9. ISBN 978-3-642-29694-9.
5. Xin-She Yang, Suash Deb. Cuckoo search: recent advances and applications. „Neural Computing and Applications”. 24, s. 169-174, 2014. DOI: 10.1007/s00521-013-1367-1. 
6. Marek Gutowski. Lévy flights as an underlying mechanism for global optimization algorithms. „arXiv”, 2001. DOI: 10.48550/arXiv.math-ph/0106003.