Optimalizace hejnem světlušek

Optimalizace 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. 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.4
  • $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_{m}ax$ - 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_{m}ax$ 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šší. Tedy $N_{i}(t)=\{j:0<\|x_{j}(t)-x_{i}(t)\|<r_{d}^{i}(t)\land l_{i}(t)<l_{j}(t)\}$, 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. Podle autorů článku byl algoritmus v době své publikace mezi nejsofistikovanějšími algoritmy pro multimodální optimalizaci.

Související články

• Inteligence hejna
• Optimalizace hejnem částic
• Optimalizace mravenčí kolonií
• Optimalizace včelím rojem
• Kolektivní inteligence
• Celulární automat
• Evoluční výpočty