PSO ­ Optimalizace rojem částic
(Particle Swarm Optimization)
Algoritmy PSO patří k metodám prohledávání prostoru. Jsou příbuzné s genetický-
mi algoritmy.
PSO, optimalizace rojem částic, vychází z existence určité populace nějakých čás-
tic, které tvoří roj směřující ke globálnímu optimu. Inspirace pochází například od
hejna ryb, které se drží pohromadě a směřují k nalezení co nejvíce co nejlepší po-
travy. Roj či hejno se pohybuje určitým nenáhodným směrem, který je částečně na-
rušován nepředvídatelnými odbočováními do stran. Směr pohybu je v každém časo-
vém kroku dán v principu dvěma složkami:
 momentálním globálním optimem a
 optimem momentálně nejlepší z částic.
Podobnost s genetickými algoritmy (GA) spočívá ve vytvoření počáteční populace
náhodných řešení, optimum se hledá aktualizací generace. Na rozdíl od GA však
PSO nepoužívá evoluční operátory typu křížení, mutace, apod. Částice, představují-
cí potenciální řešení, se pohybují prohledávaným prostorem vždy směrem udáva-
ným momentálně nejlepší částicí z roje (rybou z hejna). PSO je jednoduché na im-
plementaci, nemá mnoho parametrů, je náročné na výkon paměti i procesoru. PSO
lze používat tam, kde GA, a naopak, i když samozřejmě výsledky nemusejí být to-
tožné a zaručené. V principu jde o stochastickou optimalizační techniku, vycházejí-
cí z odvětví artificial life (umělý život). Tyto techniky původně byly vyvíjeny pro
simulaci a studium živých organismů a jevů s nimi spojených, ale obecně je lze ap-
likovat na nejrůznější výpočetní problémy.
PSO je zaměřeno na "společenské" biologické systémy, kde se zkoumá chování je-
dinců tvořících součásti kolektivu, jejich vzájemné interakce a interakce s okolím
(existuje název swarm intelligence, tj. inteligence roje/hejna/davu). Používá se na-
příklad ke zkoumání nepředvídatelné dynamiky společenského chování různých ži-
vých organismů (ptáci, ryby, mravenci, atd.).
Nyní existují dvě hlavní skupiny: optimalizace mravenčí kolonie (souboru mraven-
ců), ACO (ant colony optimization) a PSO (particle swarm optimization). Používají
se pro diskrétní optimalizační problémy.
1
Princip PSO inspirovaný hejnem ptáků
Skupina ptáků náhodně hledá v určité oblasti potravu, a je v ní pouze jeden kus po-
travy. O potravě vědí jen někteří ptáci, ne všichni. Jako nejlepší strategie se používá
následování ptáka, jemuž je ta potrava nejblíž. Každá částice v roji představuje jed-
noho ptáka v prohledávaném prostoru a má určitou hodnotu své kvality, kterou sta-
novuje funkce přizpůsobenosti (fitness function). Kromě toho má každá částice ně-
jakou rychlost, s níž se pohybuje a která udává i směr pohybu. Částice se pohybují
prostorem tak, že následují tu, která je momentálně nejlepší. Hledání optima se pro-
vádí iterativně. V každém iteračním kroku je každá částice aktualizována pomocí
dvou "optimálních" hodnot:
 doposud nalezeným nejlepším řešením každé částice pbest (particle best), a
 doposud nejlepším řešením populace gbest (global best).
Po nalezení obou nejlepších hodnot pbest a gbest jsou částice upravovány z hlediska
jejich rychlosti a polohy pomocí dvou jednoduchých vztahů:
(1) v  v + c1  rand()  (pbest - present) + c2  rand()  (gbest - present), a
(2) present  present + v,
kde v je rychlost částice, present je její současná kvalita, a rand() je náhodné
číslo  [0.0, 1.0]. Konstanty c1 a c2 jsou tzv. akcelerační konstanty, ovlivňující míru
aktualizace částic, např. 0.5 nebo 2.0 nebo 1.0, apod.
Pseudokód algoritmu
do
for each particle
spočítej hodnotu přizpůsobenosti f
if(f) > pbest nastav současnou hodnotu jako novou pbest
end
vyber hodnotu částice s nejlepší přizpůsobeností
jako gbest
for each particle
spočítej rychlost částice dle vztahu (1)
aktualizuj pozici částice dle vztahu (2)
end
while není dosažen max. počet iteračních kroků nebo
min. hodnota chyby
2
Rychlosti částic (složky vektoru rychlosti) jsou v každé dimensi omezeny na uživa-
telem stanovenou hodnotu vmax, která se použije při překročení limitu rychlosti.
Použití PSO
Pro aplikaci PSO je nutno 1) vhodně representovat řešený problém a 2) navrhnout
funkci přizpůsobenosti (fitness). PSO obecně pracuje s reálnými čísly.
Parametry PSO:
 počet částic ­ řádově desítky, obvykle 20-40 (málo částic snižuje výpočetní
složitost, ale zároveň i možnost nalést optimum; hodně částic vede k opačným
výhodám a nevýhodám ­ někdy se používají stovky částic);
 počet dimenzí částic ­ je dán optimalizovaným problémem;
 rozsah hodnot částic ­ je dán optimalizovaným problémem;
 vmax ­ ovlivňuje maximální možnou změnu rychlosti částice při jedné iteraci;
 konstanty učení c1 a c2 ­ obvykle mívají hodnotu 2.0, experimenty používají
nejčastěji rozsah hodnot [0, 4];
 podmínka ukončení ­ minimální chyba požadovaná uživatelem a předem
zadaná (funkce přizpůsobenosti se použije pro výpočet chyby v každé iteraci),
nebo stanovení max. počtu iteračník kroků (stovky, tisíce).
Obvykle je nutno vhodné parametry a jejich kombinaci najít experimentálně.
3