Optimalizace hejnem částic

Optimalizace hejnem částic (z anglického Particle Swarm Optimization, používá se zkratka PSO) je optimalizační meta-heuristická technika v oboru umělé inteligence inspirovaná chováním hejna ptáků při hledání potravy. Poprvé ji popsali Kennedy a Eberhart v roce 1995. Řadíme ji k dalším technikám používajících inteligenci hejna.

Každá částice je definována svoji polohou, rychlostí a pamětí předchozích úspěchů při hledání. Částice jsou ovlivňovány ostatními úspěšnějšími částicemi hejna. Algoritmus počítá pohyb hejna v diskrétních časových krocích a neustále upravuje hodnoty popisující částice.

Ačkoliv je PSO poměrně nová technika, získala na popularitě při řešení různých optimalizačních úloh. Mezi její hlavní výhody patří snadná implementace a rychlá konvergence k optimu pro širokou škálu účelových funkcí.

Popis algoritmu

Dle Clerca neexistuje žádný standardní PSO, ve svém článku však odkazuje na verzi Standard PSO 2007, jejímž je sám autorem. Implementace Standard PSO jsou na Particle Swarm Central uveřejňovány s motivací, aby vznikl jednotný základ, se kterým mohou vědci vytvářet srovnání. V dalším popisu budeme vycházet právě z této verze.

Popis Standard PSO 2007

Na počátku máme hejno $S$ částic, částice jsou náhodně rozmístěny v prohledávacím prostoru. Velikost hejna $S$ se obvykle volí $S=\lfloor 10+2{\sqrt {D}}\rfloor$, kde $D$ značí dimenzi prohledávacího prostoru. Každá částice $i$ si pamatuje svoji nejlepší polohu $p^{i}$(tj. bod, kde částice dosáhla maximální resp. minimální hodnoty účelové funkce). Dále se používá průběžné globální optimum částicemi v okolí částice $i$: $g^{i}$. Částici přiřazujeme její polohu $x_{t}^{i}\in \mathbb {R} ^{D}$ a rychlost $v_{t}^{i}\in \mathbb {R} ^{D}$ v čase $t$. Počáteční $x_{0}^{i}$ a $v_{0}^{i}$ volíme více méně náhodně. Předpokládá se ještě znalost omezení prohledávacího prostoru, prohledávacím prostorem je obvykle buď hyperkrychle nebo D-dimenzionální kvádr.

Algoritmus při svém běhu iteruje jeden výpočtový krok, který je jádrem celého PSO. Výpočtový krok se iteruje buď po danou dobu (konstantně-krát), nebo dokud není nalezeno přijatelné optimum (nejedná se tedy o skutečné optimum, ale o přibližné řešení). V průběhu algoritmu mohou částice opustit vyhledávací prostor. V závislosti na naší volbě pak lze pozici částic uvnitř prostoru vynutit, nebo naopak částice nechat, ale přiřadit jim například nulovou hodnotu účelové funkce.

Zásadní vlastností částic je jejich sociální chování, čímž se myslí komunikace mezi částicemi o jimi nalezených hodnotách účelové funkce. Každá částice se však nedorozumívá s každou, ale pouze se svým vybraným okolím. Okolí $L^{i}$ je zde pouze topologický pojem a vůbec nesouvisí s pozicemi částic v prostoru (tak tomu je až v různých modifikacích PSO). Na počátku se každá částice $i$ o každé jiné částici $j$ rozhodne s pravděpodobností $p$, zda bude od částice $j$ přebírat informace. Tedy zda $j\in L^{i}$. Toto okolí se však po každém kroku může změnit. Volíme si, zda chceme reinicializovat všechna spojení částic po každé úspěšné, nebo každé neúspěšné iteraci. Iteraci považujeme za úspěšnou, pokud se nám podařilo zlepšit doposud nejlepší známé řešení.

Další použité značení

• $f$ – účelová funkce, kterou se snažíme maximalizovat
• $c$ – první kognitivní/konfidenční koeficient, doporučená hodnota: ${0.5+\log(2)}{\dot {=}}1.193$
• $w$ – druhý kognitivní/konfidenční koeficient, doporučená hodnota: ${1 \over {2\cdot \log(2)}}{\dot {=}}0.721$
• $U(a,b)$ – náhodné číslo z rovnoměrného rozdělení na intervalu od $a$ včetně do $b$ včetně.
• $min_{d},max_{d}$ – omezení prohledávacího prostoru v dimenzi $d$

Inicializace algoritmu

• pro každou částici $i\in \{1,\dots ,S\}$
  1. $\forall d\in \{1,\dots D\}:(x_{0}^{i})_{d}:=U(min_{d},max_{d})$ – náhodně rozmístíme částice v prostoru
  2. $\forall d\in \{1,\dots D\}:(v_{0}^{i})_{d}:={1 \over 2}\cdot [U(min_{d},max_{d})-(x_{0}^{i})_{d}]$ – přidělíme jim vektory rychlosti
  3. $p^{i}:=x^{i}$ – a řekneme, že předchozí nejlepší pozice je ta aktuální
  4. $L^{i}:=\{\}$
  5. pro každou částici $j\in \{1,\dots ,i-1,i+1,\dots ,S\}$
     • Pokud je $U(0,1)\leq p$ potom $L^{i}:=L^{i}\cup \{j\}$

Výpočetní krok

Takto lze popsat výpočetní krok algoritmu v čase $t\in \{1,\dots T\}$, kde $T$ může být buď konstanta, nebo naopak není předem známo, protože algoritmus se nezastaví, dokud nenalezne uspokojivé řešení. Na konci každého kroku lze nejlepší řešení určit jako nejúspěšnější z řešení částic $\forall i:p^{i}$.

1. pro každou částici $i\in \{1,\dots S\}$
   1. spočítej globální optimum ze svého okolí
      • $g^{i}=0$
      • pro každé $j\in L^{i}$
        • pokud je $f(p^{j})>f(g^{i})$ potom $g^{i}:=p^{j}$
   2. pokud je $f(g^{i})>f(p^{i})$ potom
      • $v_{t}^{i}:=w\cdot v_{t-1}+U(0,c)\cdot (p^{i}-x_{t}^{i})+U(0,c)\cdot (g^{i}-x_{t}^{i})$
   3. jinak
      • $v_{t}^{i}:=w\cdot v_{t-1}+U(0,c)\cdot (p^{i}-x_{t}^{i})$
   4. aktualizujeme polohu částice
      • $x_{t}^{i}:=x_{t-1}^{i}+v_{t}^{i}$
      • Chceme-li vynutit omezení prohledávacího prostoru
        • Pro každé $d\in \{1,\cdots ,D\}$
          • Je-li $(x_{t}^{i})_{d}<min_{d}$ provedeme
            • $(x_{t}^{i})_{d}=min_{d}$
            • $(v_{t}^{i})_{d}=0$
          • Je-li $(x_{t}^{i})_{d}>max_{d}$ provedeme
            • $(x_{t}^{i})_{d}=max_{d}$
            • $(v_{t}^{i})_{d}=0$
2. nakonec aktualizujeme informaci o nejlepší předchozí poloze
   • pro každou částici $i\in \{1,\dots S\}$
     • pokud je $f(x_{t}^{i})>f(p^{i})$ potom $p^{i}:=x_{t}^{i}$
3. V závislosti na (ne)úspěšnosti kroku znovu vytvoříme $L^{i}$ pro každou částici $i$ podobně jako v Inicializace algoritmu v kroku 5

Explorace versus Exploatace

Technika optimalizace hejnem je meta-heuristika procházení prohledávacím prostorem. Metoda neprochází celý prohledávací prostor a v souvislosti s tím nás často zajímá takzvaný poměr explorace k exploataci. Explorace, neboli prozkoumávání, je tendence částic procházet nové dosud nenavštívené části prohledávacího prostoru. Toho se využívá, aby algoritmus nesklouzl do lokálního optima, neboli předčasně nekonvergoval. Naproti tomu přemíra explorace může vést k tomu, že se dostaneme do blízkosti optimálního řešení, nikdy však nezačneme zkoumat blízké okolí tohoto bodu a v důsledku zbytečně nenalezneme skutečné optimum. Částice tedy musí být schopny provádět i lokální prohledávání, ač to je samo o sobě na počátku nežádoucí. Clerc se ve svém článku zabývá explorací a exploatací v případě PSO.

Nejprve je potřeba upřesnit, co je exploatace. Vezmeme-li v úvahu body, které již částice navštívili, a nějaké jejich okolí, pak exploatací nazveme pohyb částice v prostoru, který odpovídá sjednocení těchto okolí. Řekněme, že za okolí bodu budeme považovat všechny body, které leží do vzdálenosti $M$. Můžeme použít například Eukleidovskou metriku. Explorací nazveme pohyb částice mimo toto sjednocení všech okolí navštívených bodů. Nazývejme sjednocená všech okolí navštívených bodů jako exploatační oblast.

Clerc ukazuje, že s rostoucí dimenzí prohledávacího prostoru klesá podíl velikosti exploatační oblasti vzhledem k velikosti celého prohledávacího prostoru. S tím nutně klesá i pravděpodobnost, že se částice posune do této exploatační oblasti. Pokud je tedy dimenze prohledávacího prostoru dostatečně velká, je míra exploatace skoro nulová. Autor upozorňuje, že je nutné dbát velké opatrnosti v případě tvrzení o "vyvážené míře explorace a exploatace", neboť často nemají opodstatnění.

Varianty algoritmu

PSO je v podstatě velmi jednoduché. Nabízí se však řada otázek a různých modifikací. Například proč by první a druhý konfidenční koeficient $w$ a $c$ měly nabývat doporučených hodnot. Zajímavé je, že pokud jsou hodnoty významně jiné, často algoritmus předčasně konverguje nebo naopak tendence ke konvergování postrádá. Každý takovýto koeficient vyvolává snahu, abychom se ho zbavili, protože nalezení vhodných hodnot nezřídka vyžaduje mnoho experimentů. Fernández-Martínez a García-Gonzalo ve svém článku se pomocí analogií s fyzikálními ději snaží význam těchto hodnot vysvětlit. Následně navrhují své varianty algoritmu, které tyto koeficienty nevyžadují.

Úpravy koeficientů

Některé úpravy pouze přidávají koeficienty. Hlavní rovnice algoritmu
$v_{t}^{i}:=w\cdot v_{t-1}+U(0,c)\cdot (p^{i}-x_{t}^{i})+U(0,c)\cdot (g^{i}-x_{t}^{i})$
v SPSO 2007 se od staršího konceptu PSO například liší koeficientem $w$, který také bývá nazýván inerciální vahou. Často se uvádí dva koeficienty $c_{1},c_{2}$ místo jednoho, pak vypadá hlavní rovnice takto:
$v_{t}^{i}:=w\cdot v_{t-1}+U(0,c_{1})\cdot (p^{i}-x_{t}^{i})+U(0,c_{2})*(g^{i}-x_{t}^{i})$.

Eberhart a Shi navrhli variantu, kde se $w$ s rostoucím časem lineárně zmenšuje, cílem je zajistit lepší konvergenci.

Další variantu navrhli Clerc a Kennedy přidáním takzvaného zkracujícího faktoru (z originálu: constriction factor) $\mathrm {X}$:
$v_{t}^{i}:=\mathrm {X} [v_{t-1}+U(0,c_{1})\cdot (p^{i}-x_{t}^{i})+U(0,c_{2})\cdot (g^{i}-x_{t}^{i})]$, kde $\mathrm {X} ={2\kappa \over 2-\Phi -{\sqrt {\Phi ^{2}-4\Phi }}}$.
Přitom $\Phi =c_{1}+c_{2}$ a vyžaduje se omezení $\Phi >4$. Naproti tomu $\kappa$ je libovolná konstanta z intervalu $<0;1>$. Zkracující faktor i faktor inerciální váhy se mnohdy kombinují.

Varianty topologií

Hojná skupina variant PSO používá různé topologie mezi částicemi. Záměrem je dosáhnout možnosti aplikovat PSO na úlohy vyžadující multimodální optimalizaci, nebo prosté zlepšení konvergence. Někdy se rozděluje celé hejno (swarm) do menších podhejn (subswarm). Hlavní hejno pak mívá jinou topologii než jakou používají podhejna.

Model gbest

Model gbest vychází ze zkráceniny global best, tedy globálního optima. V tomto modelu komunikuje každá částice s každou. Tato topologie však obvykle trpí problémem s předčasnou konvergencí.

Model lbest

Název tohoto modelu pochází ze zkráceniny local best, tedy lokálního optima. Graf, který popisuje komunikaci mezi částicemi (tj. vrcholy jsou částice a hrany představují fakt, že částice komunikuje s jinou částicí) odpovídá kružnici. V tomto modelu se informace o globálním optimu šíří nejpomaleji. Pokud tedy je globálních optim více, mají částice topologicky vzdálenější více času konvergovat ke svému optimu.

von Neumannův model

V tomto modelu odpovídá graf popisující komunikaci čtvercové mřížce. Každá částice tedy komunikuje se 4 svými sousedy. Typicky se von Neumannův model aplikuje na hlavní hejno a na jednotlivá podhejna se pak používá topologie lbest nebo gbest.

Použití Nik

Nikování (z anglického Niching) vychází názvem z terminologie týkající se přírody (nika), kde se rozděluje hejno částic do jednotlivých menších populací. Tato technika se snaží zabránit konvergence celé populace ke globálnímu maximu. Jedná se o jednu z nejranějších metod používaných k multimodální optimalizaci genetických algoritmů, není však známo mnoho jejích aplikací na PSO.

NichePSO

Název lze volně přeložit jako Niková optimalizace hejnem částic. Metoda používá sledování vývoje účelové funkce pro každou částici. Pokud se hodnota této funkce po nějakou dobu nemění. Je částice zařazena do vlastní niky, budeme ji říkat zakládající částice. Spolu s ní je do niky zařazen její nejbližší soused (použije se eukleidovská metrika). Každé nice se spočítá její poloměr $r$, který odpovídá vzdálenosti mezi dvěma jejími nejvzdálenějšími členy. Tato vzdálenost se používá při absorbování nových částic a spojování nik. Pokud se nějaká částice dostane do vzdálenosti menší nebo rovné $r$ od zakládající částice niky, bude do niky přidána. Pokud se přiblíží k sobě dvě niky, tedy vzdálenost jejich zakládajících částic klesne pod součet poloměrů nik, budou tyto niky spojeny. Pokud nějaká nika dosáhla optima, může její poloměr klesnout k nule. Pak se jako její poloměr považuje malá prahová hodnota$\mu$.

NichePSO nevyžaduje znalost počtu optim účelové funkce, ani žádnou informaci o velikosti niky. Potřebuje však parametr, který určuje po jaké době částice zakládá vlastní niku. Zároveň je nutné určit prahovou hodnotu$\mu$.

Použití druhů

Používání druhů v rámci genetických algoritmů poprvé představil Li a kolektiv Tato metoda vybírá silné jedince (podle jejich hodnoty účelové funkce) a používá je jako semena (z anglického seeds) vlastních skupin nazývaných druhy. Všechny částice, které jsou od vybraného semena do nějaké vzdálenosti $r$ jsou pak přiřazeny k vybranému semenu, patří s ním do jednoho druhu.

Li v roce 2004 aplikoval druhy i v PSO. Hlavní myšlenkou je, že v rámci každého druhu nahradí semeno globální optimum $g$ pro ostatní částice. Lze tedy na tento algoritmus nazírat jako na modifikaci SPSO 2007, kde se před každým iteračním krokem nejprve přepočtou okolí $L^{i}$ podle následujícího postupu:

1. $\forall i:L^{i}:=\{\}$
2. Setřídíme částice do posloupnosti $z_{1},z_{2},\dots z_{S}$, kde platí $f(x_{z_{1}})\geq f(x_{z_{2}})\geq \dots \geq f(x_{z_{S}})$ (stejně jako výše, je $f$ účelová funkce a $x_{i}$ poloha částice $i$ v prohledávacím prostoru; hodnotu účelové funkce se snažíme maximalizovat).
3. Buď $Druhy:=\{\}$ množina druhů
4. Dokud existuje $i$ takové, že částice $z_{i}$ nepatří do žádného druhu, opakuj:
   1. Vezmi nejmenší $i$ takové, že částice $z_{i}$ nepatří do žádného druhu
   2. Buď $M$ množina všech částic $z_{j}$ takových, že $z_{j}$ nepatří do žádného druhu a platí $\|x_{z_{i}}-x_{z_{j}}\|<r$. Speciálně tedy $z_{i}\in M$
   3. $Druhy:=Druhy\cup \{M\}$, všechny částice z $M$ tedy nyní patří do jednoho druhu
   4. $\forall z_{j}\in M:L^{z_{j}}:=M\setminus \{z_{j}\}$

Další modifikace

Uvedené modifikace nelze v žádném případě považovat za úplný výčet. Tento obor se neustále vyvíjí a vzniká množství nových poznatků. Níže uvedené modifikace, které byly zařazeny pod tento nadpis lze pak považovat za příklady dalších technik.

Použití mutace

Za jednoduchou úpravu můžeme považovat přidání mutace do výpočtu PSO, kterou navrhl Esquivel a Coello Coello. Mutace původně patří k operátorům genetických algoritmů, zde se konkrétně používá mutace pracující geny reprezentovanými reálnými čísly. V závislosti na aktuálním čase $t$ jsou s určitou pravděpodobností mutovány některé složky polohových vektorů částic. S rostoucím časem klesá střední hodnota takové změny.

Hybridní techniky

Hybridních technik opět existuje více. Popíšeme zde techniku jednu, která kombinuje PSO s diferenční evolucí, jak ji navrhl Pant a kolektiv. Tento algoritmus pracuje ve dvou fázích. V první fázi je dopočten mutant každé částice stejně jako to provádí diferenční evoluce. Pokud je tento mutant úspěšnější než původní částice, nahradí tuto částici. V opačném případě se s částicí naloží jako v běžném PSO.

Související články

• Inteligence hejna
• Optimalizace mravenčí kolonií
• Optimalizace včelím rojem
• Optimalizace hejnem světlušek
• Kolektivní inteligence
• Evoluční výpočty

Externí odkazy

• Obrázky, zvuky či videa k tématu Optimalizace hejnem částic na Wikimedia Commons

PSC. Particle Swarm Central, [8]