Wyszukiwanie szkół rybnych - Fish School Search

Fish School Search (FSS), zaproponowany przez Bastosa Filho i Limę Neto w 2008 roku, jest w swojej podstawowej wersji jednomodalnym algorytmem optymalizacji inspirowanym zbiorowym zachowaniem ławic ryb. Mechanizmy zasilania i skoordynowanego ruchu zostały wykorzystane jako inspiracja do stworzenia operatorów wyszukiwania. Główną ideą jest sprawienie, aby ryby „płynęły” w kierunku dodatniego gradientu, aby „zjeść” i „przybrać na wadze”. Łącznie, cięższe ryby mają większy wpływ na cały proces poszukiwań, co powoduje, że barycentrum ławicy ryb przesuwa się w kierunku lepszych miejsc w przestrzeni poszukiwań w stosunku do iteracji.

FSS stosuje następujące zasady:

1. Proste obliczenia u wszystkich osobników (tj. ryb)
2. Różne sposoby przechowywania informacji (m.in. wagi ryb i barycentrum szkolne)
3. Obliczenia lokalne (tj. pływanie składa się z różnych elementów)
4. Słaba komunikacja między sąsiednimi osobnikami (tj. ryby mają myśleć lokalnie, ale także być świadome społecznie)
5. Minimalna kontrola scentralizowana (głównie do samodzielnej kontroli promienia szkoły)
6. Niektóre wyraźne mechanizmy różnorodności (w celu uniknięcia niepożądanego zachowania floka)
7. Skalowalność (pod względem złożoności zadań optymalizacji/wyszukiwania)
8. Autonomia (tj. zdolność do samokontroli funkcjonowania)

Algorytm

FSS to algorytm wyszukiwania oparty na populacji, inspirowany zachowaniem pływających ryb, które rozszerzają się i kurczą podczas poszukiwania pożywienia. Każda lokalizacja wymiarowa ryby reprezentuje możliwe rozwiązanie problemu optymalizacji. Algorytm wykorzystuje wagi dla wszystkich ryb, co stanowi skumulowany rachunek skuteczności wyszukiwania każdej ryby w ławicy. FSS składa się z operatorów karmienia i ruchu, przy czym ten ostatni jest podzielony na trzy podkomponenty, którymi są: ${\ Displaystyle n}$

Indywidualny składnik ruchu

Każda ryba w ławicy wykonuje lokalne poszukiwania w poszukiwaniu obiecujących regionów w przestrzeni poszukiwań. Odbywa się to w sposób przedstawiony poniżej:

${\ Displaystyle x_ {i} (t + 1) = x_ {i} (t) + rand (-1, 1) step_ {ind},}$

gdzie i przedstawiają pozycję ryby odpowiednio przed i za indywidualnym operatorem ruchu. to losowa liczba o rozkładzie jednostajnym od -1 do 1 i jest parametrem określającym maksymalne przemieszczenie dla tego ruchu. Nowa pozycja jest akceptowana tylko wtedy, gdy kondycja ryby poprawi się wraz ze zmianą pozycji. Jeśli tak nie jest, ryba pozostaje w tej samej pozycji i . ${\ Displaystyle X_ {i} (t)}$${\ Displaystyle x_ {i} (t + 1)}$${\displaystyle i}$${\ Displaystyle rand (-1,1)}$${\displaystyle step_{ind}}$${\ Displaystyle x_ {i} (t + 1)}$${\ Displaystyle x_ {i} (t + 1) = x_ {i} (t)}$

Kolektywno-instynktowny składnik ruchu

Średnia z poszczególnych ruchów jest obliczana na podstawie:

${\ Displaystyle I = {\ Frac {\ suma _ {i = 1} ^ {N} \ delta x_ {i} \ delta f_ {i}} {\ suma _ {i = 1} ^ {n} \ delta f_ {i}}}.}$

Wektor reprezentuje średnią ważoną przemieszczeń każdej ryby. Oznacza to, że ryby, które doświadczyły większej poprawy, będą przyciągać ryby na swoją pozycję. Po obliczeniu wektora , każda ryba będzie zachęcana do poruszania się zgodnie z: ${\ Displaystyle I}$${\ Displaystyle I}$

${\ Displaystyle x_ {i} (t + 1) = x_ {i} (t) + ja.}$

Zbiorowo-woltywny składnik ruchu

Operator ten jest używany w celu regulowania zdolności szkoły do ​​eksploracji/eksploatacji podczas procesu poszukiwania. Przede wszystkim barycentrum ławicy jest obliczane na podstawie pozycji i wagi każdej ryby: ${\ Displaystyle B}$${\displaystyle x_{i}}$${\displaystyle W_{i}}$

${\ Displaystyle B (t) = {\ Frac {\ suma _ {i = 1} ^ {N} x_ {i} (t) W_ {i} (t)} {\ suma _ {i = 1} ^ { N}W_{i}(t)}},}$

a następnie, jeśli całkowita waga ławicy wzrosła od ostatniej do obecnej iteracji, ryby są przyciągane do barycentrum zgodnie z równaniem A. Jeśli całkowita waga ławicy nie uległa poprawie, ryby są odsuwane od barycentrum zgodnie z równaniem B: ${\ Displaystyle \ suma _ {i = 1} ^ {N} W_ {i}}$

Równ. A:

${\ Displaystyle x_ {i} (t + 1) = x_ {i} (t)-step_ {vol} rand (0,1) {\ Frac {x_ {i} (t) -B (t)} {odległość (x_{i}(t),B(t))}},}$

Równ. B:

${\ Displaystyle x_ {i} (t + 1) = x_ {i} (t) + step_ {objętość} rand (0, 1) {\ Frac {x_ {i} (t) -B (t)} {odległość (x_{i}(t),B(t))}},}$

gdzie określa wielkość maksymalnego przemieszczenia wykonywanego za pomocą tego operatora. to odległość euklidesowa między pozycją ryb a centrum barycznym w szkole. to liczba losowa o rozkładzie jednorodnym w zakresie od 0 do 1. ${\displaystyle step_{vol}}$${\ Displaystyle odległość (x_ {i} (t), B (t))}$${\displaystyle i}$${\ Displaystyle rand (0,1)}$

Oprócz operatorów ruchu zdefiniowano również operatora karmienia, który służy do aktualizacji wagi każdej ryby zgodnie z:

${\ Displaystyle W_ {i} (t + 1) = W_ {i} (t) + {\ Frac {\ Delta f_ {i}} {max (| \ Delta f_ {i} |)}}}$

gdzie jest parametrem wagi ryby , jest zmianą sprawności między ostatnią a nową pozycją i reprezentuje maksymalną bezwzględną wartość zmienności sprawności wśród wszystkich ryb w ławicy. może zmieniać się tylko od 1 do , co jest atrybutem zdefiniowanym przez użytkownika. Wagi wszystkich ryb są inicjowane wartością . ${\ Displaystyle W_ {i} (t)}$${\displaystyle i}$${\ Displaystyle \ Delta f_ {i}}$${\ Displaystyle max (| \ Delta f_ {i} |)}$${\ Displaystyle W}$${\displaystyle W_{skala}/2}$${\displaystyle W_{skala}/2}$

Pseudokod dla FSS

1. Zainicjuj parametry użytkownika
2. Inicjalizuj losowo pozycje ryb
3. podczas gdy warunek zatrzymania nie jest spełniony, wykonaj
4. Oblicz przydatność dla każdej ryby
5. Uruchom indywidualny ruch operatora
6. Oblicz przydatność dla każdej ryby
7. Uruchom operatora karmienia
8. Uruchom zbiorowy operator ruchu instynktownego
9. Uruchom operatora ruchu zbiorowo-wolitywnego
10. zakończ, gdy

Parametry i zanikają liniowo według: ${\displaystyle step_{ind}}$${\displaystyle step_{vol}}$

${\ Displaystyle step_ {ind} (t + 1) = step_ {ind} (t) - {\ Frac {step_ {ind} (początkowy)} {It_ {max}}}}$

i podobnie:

${\ Displaystyle step_ {objętość} (t + 1) = step_ {objętość} (t) - {\ Frac {krok_ {objętość} (początkowy)} {It_ {max}}}}$

gdzie i są zdefiniowanymi przez użytkownika wartościami początkowymi odpowiednio dla i . to maksymalna liczba iteracji dozwolonych w procesie wyszukiwania. ${\ Displaystyle step_ {ind} (początkowy)}$${\displaystyle step_{vol}(początkowy)}$${\displaystyle step_{ind}}$${\displaystyle step_{vol}}$${\ Displaystyle It_ {maks.}}$

Odmiany FSS

dFSS (wyszukiwanie ławic ryb na podstawie gęstości)

Ta wersja wyróżnia się multimodalnymi funkcjami hiperwymiarowymi. Zawiera modyfikacje w poprzednich operatorach: Karmienie i Pływanie, a także nowe: Operatory pamięci i partycji. Dwie ostatnie wprowadzono ze względu na podział szkoły głównej na podgrupy. Niektóre zmiany zostały również uwzględnione w warunkach zatrzymania, które teraz muszą również uwzględniać podroje.

wFSS (wyszukiwanie ławic ryb w oparciu o wagę)

wFSS to niszowa wersja FSS oparta na wadze, przeznaczona do tworzenia wielu rozwiązań. Strategia niszowania opiera się na nowym operatorze zwanym formatorem linków. Operator ten służy do definiowania przywódców dla ryb w celu utworzenia podszkół.

FSS-SAR (Rutynowe wyszukiwanie ławic ryb w celu uniknięcia stagnacji)

W pierwotnej wersji algorytmu pojedynczy składnik ruchu może poruszać rybę tylko wtedy, gdy poprawia to kondycję. Jednak w bardzo płynnej przestrzeni poszukiwań byłoby wiele ruchomych prób bez powodzenia, a algorytm mógłby nie osiągnąć zbieżności. Aby rozwiązać te problemy, wprowadzono parametr X, dla którego 0 <= X <= 1 w poszczególnych składowych ruchu. X maleje wykładniczo wraz z iteracjami i mierzy prawdopodobieństwo pogorszenia dopuszczalnej dawki dla każdej ryby. Oznacza to, że za każdym razem, gdy ryba próbuje przemieścić się do pozycji, która nie poprawia jej sprawności, wybierana jest losowa liczba i jeśli jest mniejsza niż X, ruch jest dozwolony.

bFSS (binarne wyszukiwanie ławic ryb)

bFSS miał poradzić sobie z przedwczesną konwergencją. Zaproponowanie zastosowania schematu kodowania binarnego dla wewnętrznych mechanizmów przeszukiwania ławic ryb. Połączył FSS z modelowaniem rozmytym w opakowującym podejściu do wyboru funkcji.

MOFSS (wielocelowe wyszukiwanie ławic ryb)

W MOFSS operatorzy są przystosowani do rozwiązywania problemów wielocelowych. Algorytm wdraża zewnętrzne archiwum do przechowywania najlepszych niezdominowanych rozwiązań znalezionych podczas procesu wyszukiwania. To podejście jest szeroko stosowane w różnych inspirowanych biologią optymalizatorach wielozadaniowych. Ponadto rozwiązania w ramach Archiwum Zewnętrznego są wykorzystywane do kierowania ruchami ryb w wersji propozycji.

Zobacz też

• Algorytmy optymalizacji kolonii mrówek
• Algorytm sztucznej kolonii pszczół
• Optymalizacja roju cząstek

Zewnętrzne linki

• http://www.fbln.pro.br/fss/

Bibliografia