Kurz

logo

Rojová inteligence


V tomto závěrečném kurzu ze sekce biologicky-inspirovaných algoritmů se podíváme na dvě příbuzné metody. První z nich se bude inspirovat koloniemi maravenců. Druhou metodou bude rojová inteligence, podle níž je pojmenován i tento kurz. Jak již název napovídá půjde o přístup inspirovaný roji hmyzu, ale také např. hejny ptáků, či ryb.

Optimalizace pomocí mravenčích kolonií

Začněme nejdříve s optimalizací pomocí mravenčích kolonií (ACO - Ant Colony Optimization). Zde si představíme původní variantu, která provádí optimalizaci nad diskrétním prostorem. Pro úplnost uveďme, že pro reálné domény ACO již také existuje - tyto algoritmy však ponecháme již mimo tento kurz. Doposud jsme zmínili, že se jedná o optimalizační metodu - kam ale přesně ACO zařadit? Z pohledu optimalizace rozeznáváme následující metody.

úplný optimální algoritmus
pokud existuje řešení daného problému, najde optimum, jinak vyhodnotí, že řešení neexistuje
aproximační metody
pokud řešení existuje, naleznou lokální optimum, pokud neexistuje, skončí neúspěšně
lokální prohledávání/optimalizace
iterativně vylepšuje úplné řešení (náhodně inicializované), dokud nenarazí na lokální optimum
konstrukční algoritmus
začíná s prázdným řešením, které postupně buduje na zákledě heuristické informace specifické pro daný problém

Optimalizace pomocí mravenčích kolonií je aproximativní metodou, která rezšiřuje konstrukční algoritmus. Rozšíření spočívá v tom, že metoda ACO je schopna zohlednit v určitém kroku konstrukce řešení informace posbírané v předchozích krocích (obvykle se řešení konstruuje slepě - každá část nezávisle). Čím jsou mravenci z biologického pohledu inspirativní?

Jednotliví mravenci jsou schopni nalézt nejkratší cestu z kolonie ke zdroji potravy díky nepřímé komunikaci za pomoci feromonů. Komunikace probíhá tak, že jedinec "zapíše" feromonovou značku na učitém místě cesty (operace write) a jiný mravenec může "číst" intezitu feromonu a podle ní se řídit (operace read). Touto jednoduchou metodou je schopna kolonie jako celek nalézt nejkratší cestu ke zdroji potravy - tomu říkáme emergentní chování. Zmíněná komunikace probíhá nepřímo pomocí fyzické změny prostředí (angl. stigmergy), jež je jiný jedinec schopen zaznamenat ve svém nejbližším okolí (lokálnost). Povšimněme si, že čím více jedinců následuje určitou cestu, tím více je tato cesta označena feromony a tím více jedinců ji následuje, atd. - tomu říkáme autokatalytické chování. Poslední důležitou vlastností je proces vypařování feromonu, který realizuje zapomínání a zabraňuje, aby ACO uvázlo v lokálním extrému. Udělejme si nyní drobné porovnání skutečných a umělých mravenců.

Podobnosti

  • kolonie kooperujících mravenců
  • feromonové cesty a komunikace (stigmergy)
  • pravděpodobnostní rozhodování, lokální strategie, ovlivnění ostatními jedinci

Odlišnosti

  • umělí mravenci žijí v diskrétním světě
  • umělí mravenci mají vnitřní stav - osobní paměť
  • mravenci nejsou úplně slepí
  • určité detaily týkající se chvíle, množství a způsobu uvolňování feromonu

Optimalizace pomocí rojové inteligence

Optimalizace pomocí rojové inteligence (PSO - Particle Swarm Optimization) je koncepčně velmi jednoduchá populační metoda původně navržená pro optimalizaci reálné funkce. Opět dnes existují varianty PSO i pro diskrétní případ, ponecháme je ale mimo naši diskuzi. Uveďme některé základní výhody metody PSO.

PSO označuje každé kandidátní řešení daného problému jako částici (particle), které je reprezentováno jako $N$-dimenzionální vektor reálných čísel $\mathbf{x} = (x_1, \dots, x_N)$. Celou populaci v případě PSO nazýváme hejno (swarm). Dále definujeme relaci sousedství (neighborhood), jež určuje, zda spolu dvě částice sousedí (často je tato relace rovna celému prohledávanému prostoru). Průběh optimalizace (evoluce) probíhá tak, že každá částice "letí" tímto více-dimenzionálním prostorem a interaguje s ostatními částicemi. Kadá částice je popsána následujícími charakteristikami.

pozice (position)
pozice částice $i$ v čase $t$ je popsána $N$-dimenzionálním vektorem $x_i(t)$
vektor rychlosti (velocity)
rychlost částice $i$ v čase $t$ je popsána $N$-dimenzionálním vektorem $v_i(t)$
fitness
Fitness částice je rovna hodnotě optimalizované funkce v místě dané částice $f(x_i(t))$
ukázka částice i v čase t s pozicí x_i(t) a rychostí v_i(t)

Obrázek: ukázka částice $i$ v čase $t$ s pozicí $x_i(t)$ a rychostí $v_i(t)$

ukázka hejna částic

Obrázek: ukázka hejna částic

ukázka hejna částic letícího ve 3D prostoru

ukázka hejna částic letícího ve 3D prostoru

Nyní se podívejme na to, jak popsat prohlášení, že částice "letí" v prohledávaném prostoru. Nejdřive uvedeme celou formuli, která se může zdát na první pohled složitá, ale hned níže rozebereme jednotlivé složky a ukážeme, že se vlastně jedná o jednoduchou proceduru (pozice se pak již upraví jednoduše - viz. ukázka). Úprava vektoru tychlosti $i$-té částice: $v_i(t+1) = \omega v_i(t) + C_1 \phi_1 (pbest_i(t) - x_i(t)) + C_2 \phi_2 (gbest(t) - x_i(t))$

ukázka úpravy vektoru rychlosti částice

Obrázek: ukázka úpravy vektoru rychlosti částice

ukázka úpravy pozice částice

Obrázek: ukázka úpravy pozice částice

Závěrem připomeňme, že se PSO, jako každá populační metoda, výrazně neliší od klasicé procedury genetického algoritmu, jak je popsána v předešlém kurzu. Narozdíl od tradičních GA zde není operátor křížení a na úpravu rychlosti můžeme pohlížet jako na operátor mutace. Kapitolu zakončeme zjednodušeným schématem PSO.

  1. inicializuj $t = 0$ a náhodně nastav $\mathbf{X_i}(0)$ a $\mathbf{V_i}(0)$
  2. dokud nenastane ukončovací podmínka opakuj kroky 3-6
  3. $t = t + 1$
  4. spočítej hodnoty fitness $f(\mathbf{X_i})$ všech částic hejna
  5. uprav hodnoty $pbest_i(t)$ a $gbest(t)$
  6. uprav rychosti všech částic hejna a posléze jejich pozice

Reference:

Test znalostí