Algorytm kukułki 📖 Wikipedia

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 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]}$.

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.

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 jest błądzeniem losowym, którego krok jest losowany z dystrybucji Lévy'ego^[4].