Cesko.wiki Optimalizace hejnem světlušek
Author
Albert FloresOptimalizace hejnem světlušek je technika používaná v umělé inteligenci, která se inspiruje biologickým chováním světlušek a lze ji řadit mezi další techniku z inteligence hejna. V originále se nazývá Glowworm Swarm Optimization (GSO) a byla prvně publikována roku 2006.
Úkolem této techniky je nalézt globální optima (čím více, tím lépe) dané účelové funkce, jejíž definiční obor označujeme jako prohledávací prostor. GSO využívá hejno světlušek (agentů), které jsou na počátku náhodně rozmístěni v prohledávacím prostoru. +more Každý agent si vybere směr svého pohybu v závislosti na síle signálu od ostatních agentů. Zde lze právě spatřit podobnost s bioluminiscencí světlušek - čím jasnější světlo, tím spíše naláká kořist či partnera k páření. Proto se označují agenti GSO jako světlušky. Nicméně už se v algoritmu nepočítá s jevem úbytku intenzity světla se vzdáleností. Každý agent i má v čase t přidělenu svoji hladinu luciferinu l_i. Na počátku mají všichni agenti tuto hodnotu stejnou, tedy \forall i : l_i(0) = l_0. Agent má rovněž omezený obzor (kam až dohlédne).
Použité značení
poloha agenta i v čase t : x_i(t) * účelová funkce : f * vzdálenost, kam agent i v čase t dohlédne (obzor) : r_d^i(t) * parametry algoritmu ** \gamma - luciferinový koeficient, doporučená hodnota: 0. 6 ** \rho - koeficient rozpadu luciferinu za časovou jednotku, doporučená hodnota: 0. +more4 ** s - parametr algoritmu určující velikost kroku agenta, doporučená hodnota: 0. 03 ** \beta - konstantní parametr, doporučená hodnota: 0. 08 ** n_t - parametr používaný pro řízení počtu sousedů, doporučená hodnota: 5 ** t_max - počet iterací výpočtového kroku.
Popis algoritmu
Algoritmus postupuje po diskrétních krocích a iteruje se jeden výpočtový krok, který se opakuje konstantně-krát (parametr zadaný uživatelem).
Pro t od 1 do t_max prováděj: * Každá světluška i aktualizuje svoji hladinu luciferinu v závislosti na hodnotě účelové funkce: l_i(t) = l_i(t-1) * \rho + \gamma * f(x_i(t)). * Poté se porozhlédne ve svém okolí N_i(t) po ostatních světluškách, které mají svoji hladinu luciferinu vyšší. +more Tedy N_i(t) = \{j : 0 , kde \|x_j(t) - x_i(t)\| je vhodně zvolená norma polohy dvou světlušek * Mezi těmito si náhodně vybere jednu a vydá se jejím směrem. Z popisu algoritmu není zcela zřejmé další chování, pokud žádná zářivější světluška v dosahu není. Publikovaný pseudokód však lze interpretovat tak, že taková světluška se během dané iterace nepohne, protože je blízko optima. Přesněji se tedy odehraje toto: ** Světluška j \in N_i(t) bude vybrána s pravděpodobností P(j) = \sum_{k \in N_i(t)} {l_j(t) - l_i(t) \over l_k(t) - l_i(t)} ** x_i(t) = x_i(t-1) + s \left ({x_j(t-1) - x_i(t-1) \over \|x_j(t-1) - x_i(t-1)\|}\right ). * V další části iteračního kroku si agent upraví velikost svého obzoru: r_d^i(t) = min\{ r_s, max\{0, r_d^i(t-1) + \beta \cdot (n_t - |N_i(t)|) \} \}, kde |N_i(t)| je počet (mohutnost) vhodných světlušek v okolí.
Výstupem algoritmu jsou pozice jednotlivých agentů. Jejich shluky považujeme za jednotlivá nalezená optima.
Ve srovnání s algoritmem optimalizace hejnem částic je tento vhodnější pro paralelismus, protože vyžaduje minimální interakci agentů. Při použití v robotice navíc lépe odpovídá reálným podmínkám, kdy může být komunikační dosah robotů omezen. +more Podle autorů článku byl algoritmus v době své publikace mezi nejsofistikovanějšími algoritmy pro multimodální optimalizaci.