Algorytm kukułki

Algorytm kukułki

Algorytm kukułki (ang. cuckoo search) to metaheurystyczna metoda optymalizacji, która została opracowana w 2009 roku przez Xin-She Yanga oraz Suasha Deba. Inspiracją dla tego algorytmu były zachowania niektórych gatunków kukułek, które składają jaja w gniazdach innych ptaków (co odnosi się do powiedzenia „kukułcze jajo”). W algorytmie zastosowano również loty Lévy’ego (ang. Lévy flights). W artykule jego twórców można znaleźć przykładową implementację algorytmu kukułki.

Reguły

W algorytmie kukułki obowiązują następujące zasady:

• W danym momencie kukułka może złożyć jedno jajo w losowo wybranym gnieździe gospodarza.
• W kolejnej iteracji algorytmu uwzględniane jest gniazdo o wysokiej jakości.
• Gospodarz gniazda, do którego zostało podrzucone jajo, może zauważyć obce jajo z prawdopodobieństwem p, gdzie p należy do przedziału [0, 1].

Oznaczenia

Funkcja f: R^c → R jest funkcją przystosowania. Gniazdo g_i,j ∈ R^c jest punktem w c-wymiarowej przestrzeni i stanowi potencjalne rozwiązanie problemu optymalizacyjnego. Indeksy i oraz j w symbolu g_i,j oznaczają i-te gniazdo w jt będzie używany 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 o rozmiarze μ: (g_i,0)_i=0^μ-1, gdzie g_i,0 jest i-tym gniazdem w tej populacji.

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

• Dokonywane jest podstawienie t := t + 1.
• Wybierany jest losowo indeks i i wykonywany jest lot Lévy’ego z punktu g_i,t do nowego punktu w przestrzeni g’ ∈ R^c.
• Wybierany jest losowo indeks j i jeśli f(g’) > f(g_j,t), dokonuje się podstawienia g_j,t := g’.
• Odrzucane jest p ⋅ μ gniazd o najniższej wartości funkcji przystosowania, które zastępowane są nowo wygenerowanymi losowo 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

Lot Lévy’ego jest rodzajem błądzenia losowego, w którym krok jest losowany z dystrybucji Lévy’ego.

Przypisy