Optimalizace hejnem světlušek

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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.[1]

Ú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í[editovat | editovat zdroj]

  • 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_max - počet iterací výpočtového kroku

Popis algoritmu[editovat | editovat zdroj]

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šší. Tedy N_i(t) = \{j :  0 < \|x_j(t) - x_i(t)\| < r_d^i(t) \and l_i(t) < l_j(t) \}
  • Mezi těmito si náhodně vybere jednu a vydá se jejím směrem. Z popisu algoritmu[2] 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 \cdot (x_j(t-1) - x_i(t-1) \over \|x_j(t-1) - x_i(t-1)\|).
  • 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)\|) \} \}.

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. Krishnanand, K.N., Ghose, D.: Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications; Multiagent and Grid Systems 2(3); str 209–222 (2006)
  2. Krishnanand, K. N., Ghose, D.: Glowworm Swarm Optimization for Searching Higher Dimensional Spaces; Collection of Innovations in Swarm Intelligence; 2009; str 61-75