Szukaj szkoły ryb

Fish School Search (FSS), zaproponowany przez Bastosa Filho i Limę Neto w 2008 roku, jest w swojej podstawowej wersji jednomodalnym algorytmem optymalizacyjnym inspirowanym zbiorowym zachowaniem ławic ryb. Mechanizmy karmienia i skoordynowanego ruchu posłużyły jako inspiracja do stworzenia operatorów wyszukiwania. Główną ideą jest sprawienie, aby ryby „pływały” w kierunku dodatniego gradientu, aby „jeść” i „przybierać na wadze”. Łącznie cięższe ryby mają większy wpływ na cały proces poszukiwań, co powoduje, że środek ciężkości ławicy przesuwa się w kierunku lepszych miejsc w przestrzeni poszukiwań w kolejnych iteracjach.

FSS stosuje następujące zasady:

1. Proste obliczenia dla wszystkich osobników (tj. ryb)
2. Różne sposoby przechowywania informacji (np. wagi ryb i szkolna barycentrum)
3. Obliczenia lokalne (tj. pływanie składa się z odrębnych elementów)
4. Niska komunikacja między sąsiadującymi osobnikami (tj. ryby mają myśleć lokalnie, ale także być świadome społecznie)
5. Minimalna kontrola scentralizowana (głównie do samokontroli promienia szkoły)
6. Niektóre odrębne mechanizmy różnorodności (aby uniknąć niepożądanego zachowania stadnego)
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 ryba $lokalizacja$ reprezentuje możliwe rozwiązanie problemu optymalizacji. Algorytm wykorzystuje wagi dla wszystkich ryb, co stanowi zbiorczy rachunek tego, jak skuteczne było poszukiwanie 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ą:

Indywidualny składnik ruchu

Każda ryba w ławicy przeprowadza lokalne poszukiwania 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)krok_{ind},}$

gdzie ${\ Displaystyle x_ {i} (t)}$ i ${\ Displaystyle x_ {i} (t + 1)}$ reprezentują pozycję ryby ${\ displaystyle i}$ odpowiednio przed i po indywidualnym operatorze ruchu. ${\ Displaystyle Rand (-1,1)}$ jest równomiernie rozłożoną liczbą losową wahającą się od -1 do 1 i ${\ Displaystyle step_ {ind}}$ jest parametrem określającym maksymalne przemieszczenie dla tego ruchu. Nowa pozycja $.$ kondycja ryby poprawia się Jeśli tak nie jest, ryba pozostaje w tej samej pozycji i ${\ Displaystyle x_ {i} (t + 1) = x_ {i} (t)}$ .

Zbiorowo-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 $ważoną$ przemieszczeń każdej ryby. Oznacza to, że ryby, które doświadczyły większej poprawy, będą przyciągać ryby na swoje stanowisko. Po obliczeniu wektora każda ryba zostanie zachęcona do ruchu zgodnie z: ja $\ displaystyle I}$

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

Kolektywno-wolitywny składnik ruchu

Operator ten służy do regulowania możliwości eksploracji/eksploatacji szkoły podczas procesu wyszukiwania. ${i}}$ wszystkim środek ciężkości szkoły jest obliczany na podstawie pozycji $W_$ każdej ryby: ${ \ displaystyle$

${\ 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 szkoły $od$ ostatniej do bieżącej środek barytonu zgodnie z równaniem A. Jeżeli całkowita waga ławicy nie uległa poprawie, ryby są rozkładane od środka ciężkości zgodnie z równaniem B:

równanie A:

${\ Displaystyle x_ {i} (t + 1) = x_ {i} (t) -krok_ {tom} Rand (0,1) {\ Frac {x_ {i} ( t)-B(t)}{odległość(x_{i}(t),B(t))}},}$

równanie B:

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

gdzie $\ displaystyle step_ {vol}}$ określa wielkość maksymalnego przemieszczenia wykonywanego za pomocą tego operatora. ${\ Displaystyle odległość (x_ {i} (t), B (t)}}$ odległość euklidesowa między rybami ${\ Displaystyle i}$ pozycja i środek ciężkości szkoły. ${\ Displaystyle Rand (0,1)}$ jest równomiernie rozłożoną liczbą losową wahającą się od 0 do 1.

Oprócz operatorów ruchu zdefiniowano również operator karmienia służący do aktualizacji wag każdej ryby według:

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

gdzie $jest$ parametrem wagi dla ryb $Displaystyle$ Δ $f_ {i}}$ sprawności między ostatnim i nową pozycję, a $maksymalną$ sprawności $W}$$.$ może zmieniać się tylko od 1 użytkownika Wagi wszystkich ryb są inicjowane wartością $\ Displaystyle W_ {skala}/2}$ .

Pseudokod dla FSS

1. Zainicjuj parametry użytkownika
2. Losowo inicjalizuj pozycje ryb
3. dopóki 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 kolektywno-instynktowny operator ruchu
9. Uruchom operatora ruchu kolektywno-wolitywnego
10. koniec póki

Parametry ${\ displaystyle step_ {ind}}$ i ${\ displaystyle step_ {vol}}$ zanikają liniowo zgodnie z:

${\ displaystyle step_ {ind}(t+1)=step_{ind}(t)-{\frac {step_{ind}(początkowy)}{It_{max}}},}$

i podobnie:

${\ displaystyle step_ {vol}(t+1)=step_{vol}(t)-{\frac {step_{vol}(initial)}{It_{max}}},}$

gdzie ${\ displaystyle step_ {ind} (początkowy)}$ i ${\ displaystyle step_ { vol} (początkowe)}$$vol}}$$step_$ użytkownika wartości początkowe odpowiednio dla p . ${\ Displaystyle It_ {max}}$ to maksymalna liczba iteracji dozwolona w procesie wyszukiwania.

Odmiany FSS

dFSS (wyszukiwanie ławic ryb w oparciu o gęstość)

Ta wersja doskonale sprawdza się w multimodalnych funkcjach hiperwymiarowych. Zawiera modyfikacje dotychczasowych operatorów: Feeding i Swimming, a także nowe: operatory Memory i Partition. Te dwie ostatnie zostały wprowadzone w celu uwzględnienia podziału szkoły głównej na podgrupy. Pewne zmiany zostały również uwzględnione w warunkach zatrzymania, które teraz muszą uwzględniać również podroje.

wFSS (wyszukiwanie szkół ryb na podstawie wagi)

wFSS to niszowa wersja FSS oparta na wadze, przeznaczona do tworzenia wielu rozwiązań. Strategia niszowania opiera się na nowym operatorze o nazwie link formator. Ten operator służy do definiowania liderów dla ryb w celu utworzenia szkół podrzędnych.

FSS-SAR (Rutynowe wyszukiwanie ławic ryb w celu unikania stagnacji)

W oryginalnej wersji algorytmu pojedynczy składnik ruchu może poruszyć rybę tylko wtedy, gdy poprawia kondycję. Jednak w bardzo gładkiej przestrzeni wyszukiwania byłoby wiele prób ruchu 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ładnikach ruchu. X maleje wykładniczo wraz z iteracjami i mierzy prawdopodobieństwo pogorszenia dodatku 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 kondycji, wybierana jest losowa liczba i jeśli jest mniejsza niż X , ruch jest dozwolony.

bFSS (Binary Fish School Search)

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

MOFSS (wyszukiwanie szkół ryb z wieloma celami)

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. Podejście to było szeroko stosowane w przypadku różnych inspirowanych biologią optymalizatorów wielocelowych. Ponadto rozwiązania w ramach Archiwum Zewnętrznego służą do kierowania przepływami ryb w wersji propozycji.

Zobacz też

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

Linki zewnętrzne

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