Optimalizace hejnem částic

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

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

Popis algoritmu[editovat | editovat zdroj]

Dle Clerca neexistuje žádný standardní PSO[3], ve svém článku však odkazuje na verzi Standard PSO 2007[4], jejímž je sám autorem. Implementace Standard PSO jsou na Particle Swarm Central[5] 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[editovat | editovat zdroj]

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

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

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

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

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

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

PSO je ve své 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[6] 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ů[editovat | editovat zdroj]

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.[2] Č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.[7]

Další variantu navrhli Clerc a Kennedy[8] přidáním takzvaného zkracujícího faktoru (z originálu: constriction factor) \Chi:
v_t^i := \Chi [v_{t-1} +  U(0, c_1) \cdot (p^i - x_t^i) + U(0, c_2) \cdot (g^i - x_t^i)], kde \Chi = {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í[editovat | editovat zdroj]

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

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

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

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

Nikování (z anglického Niching) vychází názvem z terminologie týkající se přírody, 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[editovat | editovat zdroj]

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

Používání druhů v rámci genetických algoritmů poprvé představil Li a kolektiv[9] 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.[10] 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}) \ge f(x_{z_2}) \ge \dots \ge 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[editovat | editovat zdroj]

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

Za jednoduchou úpravu můžeme považovat přidání mutace do výpočtu PSO, kterou navrhl Esquivel a Coello Coello[11]. 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í střední hodnota takové změny.

Hybridní techniky[editovat | editovat zdroj]

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

Reference[editovat | editovat zdroj]

  1. Kennedy, J., Eberhart, R.: Particle swarm optimization; Neural Networks, 1995; Proceedings., IEEE International Conference, vol.4; str. 1942-1948 vol.4; Nov/Dec 1995; doi: 10.1109/ICNN.1995.488968; [1]
  2. a b Barrera, J., Coello, C.A.C.: A Review of Particle Swarm Optimization Methods Used for Multimodal Optimization; Innovations in Swarm Intelligence (2009); str. 9-37
  3. a b Clerc, M.: From Theory to Practice in Particle Swarm Optimization; Handbook of Swarm Intelligence; Springer Berlin Heidelberg 2010; ISBN: 978-3-642-17390-5; str. 3-86; Svazek 8; Doi: 10.1007/978-3-642-17390-5_1; [2]
  4. [3]
  5. [4]
  6. Fernández-Martínez, J. L., García-Gonzalo, E.: What Makes Particle Swarm Optimization a Very Interesting and Powerful Algorithm?; Handbook of Swarm Intelligence; Springer Berlin Heidelberg 2010; Isbn: 978-3-642-17390-5; str. 37-65; [5]; Doi: 10.1007/978-3-642-17390-5_2
  7. Shi, Y.; Eberhart, R.C.: Empirical study of particle swarm optimization; Evolutionary Computation 1999; CEC 99; Proceedings of the 1999 Congress on, vol.3, no., str.3 vol. (xxxvii+2348); 1999; doi: 10.1109/CEC.1999.785511; [6]
  8. Clerc, M., Kennedy, J.: Evolutionary Computation, IEEE Transactions on In Evolutionary Computation; IEEE Transactions on, Vol. 6, No. 1. (2002); str. 58-73
  9. Li, J.P., Balazs, M.E., Parks, G.T., Clarkson, P.J.: A species conserving genetic algorithm for multimodal function optimization. Evolutionary Computation 10(3); str. 207–234 (2002)
  10. Li, X.: Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization; In: Deb, K., et al. (eds.) GECCO 2004; LNCS, vol. 3102; str. 105–116; Springer, Heidelberg (2004)
  11. Esquivel, S.C.; Coello, C.A.C.: On the use of particle swarm optimization with multimodal functions; Evolutionary Computation, 2003; CEC '03; The 2003 Congress on , vol.2, no., str. 1130- 1136 svazek 2, 8-12 Dec. 2003; doi: 10.1109/CEC.2003.1299795; [7]
  12. Pant, M., Thangaraj, R., Grosan, C., Abraham, A.: Hybrid differential evolution - particle swarm optimization algorithm for solving global optimization problems; In: Third International Conference on Digital Information Management (ICDIM 2008); Listopad 2008; str. 18–24 (2008)

Externí odkazy[editovat | editovat zdroj]

PSC. Particle Swarm Central, [8]