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. 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"). W algorytmie wykorzystane są loty Lévy'ego (ang. Lévy flights). Przykładowa implementacja algorytmu kukułki znajduje się w artykule jego twórców.

Reguły

Reguły algorytmu kukułki:

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 $p\in [0,1]$.

Oznaczenia

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

Algorytm

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

Algorytm rozpoczyna się w chwili $t=0$ od wygenerowania początkowej populacji gniazd gospodarzy rozmiaru $\mu$:

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

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

Następnie w pętli wykonywane są poniższe czynności:

1. Dokonywane jest podstawienie $t:=t+1$.
2. Wybierany jest losowo indeks $i$ i wykonywany jest lot Lévy'ego z punktu $g_{i,t}$ do nowego punktu w przestrzeni $g'\in \mathbb {R} ^{c}$.
3. Wybierany jest losowo indeks $j$ i jeśli $f(g')>f(g_{j,t})$ dokonywane jest podstawienie $g_{j,t}:=g'$.
4. Odrzucane jest $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 $t$ osiągnie wartość graniczną lub zostanie spełniony inny warunek zakończenia.

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.