Hledání rybí školy - Fish School Search - Wikipedia

Hledání rybí školy (FSS), kterou v roce 2007 navrhli Bastos Filho a Lima Neto, je v základní verzi^[1] unimodální optimalizační algoritmus inspirovaný kolektivním chováním ryb. Mechanismy krmení a koordinovaný pohyb byly použity jako inspirace k vytvoření operátorů vyhledávání. Základní myšlenkou je přimět ryby „plavat“ směrem k pozitivnímu gradientu, aby „jedly“ a „přibraly na váze“. Kolektivně jsou těžší ryby více ovlivňovány v procesu vyhledávání jako celku, což způsobí, že se barycentrum rybářské školy přesune na lepší místa ve vyhledávacím prostoru přes iterace.^[2]

FSS používá následující principy:^[3]

1. Jednoduché výpočty u všech jedinců (tj. Ryb)
2. Různé způsoby ukládání informací (tj. Hmotnosti ryb a školního barycentra)
3. Místní výpočty (tj. Plavání se skládá z odlišných komponent)
4. Nízká komunikace mezi sousedními jednotlivci (tj. Ryby mají myslet na místní úroveň, ale také být společensky uvědomělé)
5. Minimální centralizované řízení (hlavně pro vlastní kontrolu poloměru školy)
6. Některé odlišné mechanismy rozmanitosti (aby se zabránilo nežádoucímu chování při hromadění)
7. Škálovatelnost (z hlediska složitosti optimalizačních / vyhledávacích úkolů)
8. Autonomie (tj. Schopnost sebeovládání fungovat)

Algoritmus

FSS je populační vyhledávací algoritmus inspirovaný chováním plaveckých ryb, které se při hledání potravy rozšiřují a smršťují. Každá ryba ${ displaystyle n}$-dimenzionální umístění představuje možné řešení problému optimalizace. Algoritmus využívá váhy pro všechny ryby, což představuje kumulativní záznam o tom, jak úspěšné bylo hledání každé ryby ve škole. FSS se skládá z operátorů krmení a pohybu, přičemž tyto operátory jsou rozděleny do tří dílčích složek, kterými jsou:^[4]

Jednotlivá složka pohybu

Každá ryba ve škole provede místní vyhledávání a hledá ve vyhledávacím prostoru slibné regiony. Provádí se, jak je znázorněno níže:

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

kde ${ displaystyle x_ {i} (t)}$ a ${ displaystyle x_ {i} (t + 1)}$ představují polohu ryby ${ displaystyle i}$ před a po jednotlivých operátorech pohybu. ${ displaystyle rand (-1,1)}$ je rovnoměrně rozložené náhodné číslo pohybující se od -1 do 1 a ${ displaystyle step_ {ind}}$ je parametr, který definuje maximální posunutí pro tento pohyb. Nová pozice ${ displaystyle x_ {i} (t + 1)}$ je akceptováno, pouze pokud se kondice ryb zlepšuje se změnou polohy. Pokud tomu tak není, zůstane ryba ve stejné poloze a ${ displaystyle x_ {i} (t + 1) = x_ {i} (t)}$.

Kolektivně instinktivní složka hnutí

Průměr jednotlivých pohybů se vypočítá na základě následujícího:

${ displaystyle I = { frac { sum _ {i = 1} ^ {N} Delta x_ {i} Delta f_ {i}} { sum _ {i = 1} ^ {N} Delta f_ {i}}}.}$

Vektor ${ displaystyle I}$ představuje vážený průměr posunutí každé ryby. To znamená, že ryby, které zaznamenaly vyšší zlepšení, přilákají ryby do své polohy. Po vektoru ${ displaystyle I}$ při výpočtu bude každá ryba povzbuzována k pohybu podle:

${ displaystyle x_ {i} (t + 1) = x_ {i} (t) + I.}$

Kolektivně-volitivní složka hnutí

Tento operátor se používá k regulaci průzkumné / vykořisťovatelské schopnosti školy během procesu vyhledávání. Za prvé, barycentrum ${ displaystyle B}$ školy se počítá na základě pozice ${ displaystyle x_ {i}}$ a váha ${ displaystyle W_ {i}}$ každé ryby:

${ displaystyle B (t) = { frac { součet _ {i = 1} ^ {N} x_ {i} (t) W_ {i} (t)} { součet _ {i = 1} ^ { N} W_ {i} (t)}},}$

a pak, pokud je celková hmotnost školy ${ displaystyle sum _ {i = 1} ^ {N} W_ {i}}$ se zvýšil z poslední na aktuální iteraci, ryby jsou přitahovány k barycentru podle rovnice A. Pokud se celková školní hmotnost nezlepší, ryby se rozšíří od barycentra podle rovnice B:

Rov. A:

${ displaystyle x_ {i} (t + 1) = x_ {i} (t) -step_ {vol} rand (0,1) { frac {x_ {i} (t) -B (t)} {vzdálenost (x_ {i} (t), B (t))}},}$

Rov. B:

${ displaystyle x_ {i} (t + 1) = x_ {i} (t) + step_ {vol} rand (0,1) { frac {x_ {i} (t) -B (t)} {vzdálenost (x_ {i} (t), B (t))}},}$

kde ${ displaystyle step_ {vol}}$ definuje velikost maximálního posunutí provedeného s použitím tohoto operátoru. ${ displaystyle vzdálenost (x_ {i} (t), B (t))}$ je euklidovská vzdálenost mezi rybami ${ displaystyle i}$ pozice a školní barycentrum. ${ displaystyle rand (0,1)}$ je rovnoměrně rozložené náhodné číslo pohybující se od 0 do 1.

Kromě operátorů pohybu byl definován také operátor krmení používaný k aktualizaci hmotnosti každé ryby podle:

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

kde ${ displaystyle W_ {i} (t)}$ je hmotnostní parametr pro ryby ${ displaystyle i}$, ${ displaystyle Delta f_ {i}}$ je variace kondice mezi poslední a novou pozicí a ${ displaystyle max (| Delta f_ {i} |)}$ představuje maximální absolutní hodnotu variace kondice u všech ryb ve škole.${ displaystyle W}$ se může lišit pouze od 1 do ${ displaystyle W_ {scale} / 2}$, což je uživatelsky definovaný atribut. Váhy všech ryb se inicializují s hodnotou ${ displaystyle W_ {scale} / 2}$.

Pseudokód pro FSS

1. Inicializujte uživatelské parametry
2. Inicializujte pozice ryb náhodně
3. pokud není splněna podmínka zastavení
4. Vypočítejte kondici pro každou rybu
5. Spusťte individuální pohyb operátora
6. Vypočítejte kondici pro každou rybu
7. Spusťte operátora krmení
8. Spusťte operátor kolektivně instinktivního pohybu
9. Spusťte operátor kolektivního volitivního pohybu
10. skončit chvíli

Parametry ${ displaystyle step_ {ind}}$ a ${ displaystyle step_ {vol}}$ rozpadat se lineárně podle:

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

a podobně:

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

kde ${ displaystyle step_ {ind} (počáteční)}$ a ${ displaystyle step_ {vol} (počáteční)}$ jsou uživatelem definované počáteční hodnoty pro ${ displaystyle step_ {ind}}$ a ${ displaystyle step_ {vol}}$, resp. ${ displaystyle It_ {max}}$ je maximální počet iterací povolených v procesu vyhledávání.

Varianty FSS

dFSS (Hustota založená na rybí škole)

Tato verze vyniká pro multimodální hyper-dimenzionální funkce. Zahrnuje úpravy u předchozích operátorů: Krmení a Plavání a také nové: Operátory paměti a oddílů. Poslední dva byli představeni, aby vysvětlili rozdělení hlavní školy na podskupiny. Některé změny byly také zahrnuty do podmínek zastavení, které nyní také musí brát v úvahu zahřátí.^[5]

wFSS (Weight Based Fish School Search)

wFSS je váhová specializovaná verze FSS určená k výrobě více řešení. Strategie specializace je založena na novém operátoru s názvem link formator. Tento operátor se používá k definování vůdců pro ryby za účelem vytvoření sub-škol.^[6]

FSS-SAR (Stagnation Avoidance Routine Fish School Search)

V původní verzi algoritmu je jednotlivé pohybové složce povoleno pohybovat rybou pouze v případě, že zlepšuje kondici. Ve velmi plynulém vyhledávacím prostoru by však bylo mnoho pohyblivých pokusů bez úspěchu a algoritmus by se nemohl sblížit. K vyřešení těchto problémů byl zaveden parametr X, pro který 0 <= X <= 1 v jednotlivé složce pohyb. X se exponenciálně rozpadá spolu s iteracemi a měří pravděpodobnost zhoršení příspěvku pro každou rybu. To znamená, že pokaždé, když se ryba pokusí přesunout do polohy, která nezlepšuje její kondici, je vybráno náhodné číslo a pokud je menší než X, je pohyb povolen.^[7]

bFSS (Binary Fish School Search)

Účelem bFSS bylo vyrovnat se s předčasnou konvergencí. Navrhuje použití binárního kódovacího schématu pro vnitřní mechanismy hledání rybí školy. Kombinoval FSS s fuzzy modelováním v obálkovém přístupu pro výběr funkcí.^[8]

MOFSS (Multi-Objective Fish School Search)

V MOFSS jsou operátoři přizpůsobeni k řešení víceobjektových problémů. Algoritmus nasadí externí archiv k uložení nejlepších nedominovaných řešení nalezených během procesu vyhledávání. Tento přístup byl široce používán pro různé biologicky inspirované multiobjektivní optimalizátory.^[9][10] Kromě toho se řešení v externím archivu používají k vedení pohybů ryb ve verzi návrhu.^[11]

Viz také

• Algoritmy optimalizace kolonií mravenců
• Algoritmus umělé včelí kolonie
• Optimalizace roje částic

externí odkazy

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

Reference