particle swarm optimization - cuni.cz
TRANSCRIPT
![Page 2: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/2.jpg)
Úvod
BIODAT Group 2
![Page 3: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/3.jpg)
Úvod
• swarms, flocks, herds, schools, blooms
• mravenci, termiti, ...
• včely, vosy, ...
• pakoně, zebry, ...
• ryby, ...
• lidé
• ...
BIODAT Group 3
![Page 4: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/4.jpg)
Proč hejna?
• Včely
– prohledávání
• Vysílají zvědy, kteří hledají nové místo pro hnízdo
• zvědi po návratu tancem přesvědčují ostatní zvědy, čím šťastnější tanec, tím větší pravděpodobnost, že se ostatní přidají
• Po určité době, když většina zvědů souhlasí s novým místem, celý roj se stěhuje
• Dobré místo musí být dostatečně prostorné, dobře chráněné před vnějšími elementy, mít správný přístup tepla i vzduchu a nesmí být zamořeno mravenci
BIODAT Group 4
![Page 5: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/5.jpg)
Proč hejna?
• Tadarida guánová • ochrana před predátory
• komunikace a rozhodování
– Výřivý sloup říká ostatním, kdy vylétnout z hnízda, kam se dnes poletí -fúze
zkušeností z předchozí noci – kolektivní rozhodování
BIODAT Group 5
![Page 6: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/6.jpg)
Proč hejna?
• Mravenci
– Přeprava
• Tvorba voru z vlastních těl, pontonové mosty
BIODAT Group 6
![Page 7: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/7.jpg)
Proč hejna?
• Ryby
– Znásobení smyslů, obrana před predátorem
BIODAT Group 7
![Page 8: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/8.jpg)
Proč hejna?
• Ryby
– vnímání ostatních i predátorů postraní čárou
– varovné signály pomocí feromonů,
rozechvívání vzduchových měchýřů, skřípění
požerákových zubů
BIODAT Group 8
![Page 9: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/9.jpg)
Proč hejna?
– Ptáci
• Hledání potravy
– Ptáci letící desítky metrů nad zemí dokážou vidět a
rozeznat zrnko obilí
– Sledují znamení zdroje potravy, t.j. aktivity ostatních:
» Krmení se na zemi
» Kroužení nad nějakým cílem
» Otočení se a oddělení se od hejna za něčím
»
BIODAT Group 9
![Page 10: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/10.jpg)
Proč hejna?
• Lov
BIODAT Group 10
![Page 11: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/11.jpg)
Simulace
• Ptačí hejna
– Craig Reynolds, 1987:BOIDS
– Tři lokální síly:
• Collision avoidance
– „odtažení“ v případě hrozící kolize
• Velocity matching
– Jedinci se snaží pohybovat zhruba podobnou rychlostí
jako jejich sousedi
• Flock centering
– Jedinci se snaží dostat do středu hejna
BIODAT Group 11
![Page 12: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/12.jpg)
Simulace
• Ptačí hejna
– Heppner, Grenander, Potter, 1990:BOIDS
• navíc přitahování k hnízdu
• tendenci udržovat si svou rychlost
• náhodná síla „větru“
– Toner and Tu, 1998: Flocks, herds and
schools: A quantitative theory of flocking
• Chování hejna připomíná celulární automat 4.
typu (charakteristické a nepredikovatelné vzory,
které emergují po dlouhou dobu aby pak
zanikly)
BIODAT Group 12
![Page 13: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/13.jpg)
Literatura
BIODAT Group 13
![Page 14: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/14.jpg)
Kde použít PSO?
BIODAT Group 14
Number of variables
Univariate
Multivariate
Type of variables
Continuous
Discrete (Integer)
Combinatorial
Number of optima
Unimodal
Multimodal
Number of optimization
criteria
Single-objective
Multi-objective
Constraints
Unconstrained
Constrained
Equality constraints
Inequality constraints
Degree of nonlinearity
of fitness function
Linear
Nonlinear
![Page 15: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/15.jpg)
Notace
Struktura swarmu 𝑆:
𝑛𝑠 ... počet jedinců (velikost populace)
𝑛𝑥 ... dimenzionalita prohledávaného prostoru
𝒙𝑖 ... pozice 𝑖 –tého jedince (𝑥𝑖1, 𝑥𝑖2, … , 𝑥𝑖𝑛𝑥 )
𝒗𝑖 ... rychlost 𝑖 –tého jedince (𝑣𝑖1, 𝑣𝑖2, … , 𝑣𝑖𝑛𝑥 )
𝒚𝑖 ... personal best pozice 𝑖 –tého jedince
𝒚 𝑖/𝒚 ... local/global best pozice 𝑖 –tého jedince
BIODAT Group 15
![Page 16: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/16.jpg)
Topologie
• Nejběžnější: Méně běžné:
• Kennedy, Mendes (2002): Population structure and particle swarm performance.
• Čím více lokálních optim, tím méně propojená topologie
BIODAT Group 16
![Page 17: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/17.jpg)
Local Best PSO
• Update rychlosti:
• Update pozice:
𝒙𝑖 t + 1 = 𝒙𝑖 t + 𝒗𝑖 t + 1
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 17
![Page 18: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/18.jpg)
Local Best PSO
• Update rychlosti:
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 18
Setrvačnost Kognitivní
komponenta
Sociální
komponenta
𝒗1(𝑡)
𝒙1(𝑡)
𝒚1(𝑡)
𝒚 1(𝑡)
![Page 19: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/19.jpg)
Local Best PSO
• Update rychlosti:
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 19
Setrvačnost Kognitivní
komponenta
Sociální
komponenta
𝒙1(𝑡)
𝒚1(𝑡)
𝒚 1(𝑡) 𝒘𝒗1(𝑡)
![Page 20: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/20.jpg)
Local Best PSO
• Update rychlosti:
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 20
Setrvačnost Kognitivní
komponenta
Sociální
komponenta
𝒙1(𝑡)
𝒚1(𝑡)
𝒚 1(𝑡) 𝒘𝒗1(𝑡)
![Page 21: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/21.jpg)
Local Best PSO
• Update rychlosti:
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 21
Setrvačnost Kognitivní
komponenta
Sociální
komponenta
𝒙1(𝑡)
𝒚1(𝑡)
𝒚 1(𝑡) 𝒘𝒗1(𝑡)
![Page 22: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/22.jpg)
Local Best PSO
• Update rychlosti:
• Situace: Jedinci 1 a 2 jsou sousedé a mají společného souseda,
který je zároveň nejlepším sousedem každého:
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 22
Setrvačnost Kognitivní
komponenta
Sociální
komponenta
𝒗1(𝑡)
𝒗2(𝑡)
𝒙1(𝑡)
𝒙2(𝑡)
𝒚1(𝑡)
𝒚2(𝑡)
𝒚 1 𝑡 = 𝒚 2 𝑡
![Page 23: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/23.jpg)
Local Best PSO
• Update rychlosti:
• Situace: Jedinec jedna našel zatím nejlepší pozici ze svého okolí.
Protože není sousedem jedince 2, má jedinec 2 jinou sociální
znalost než jedinec 1
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 23
Setrvačnost Kognitivní
komponenta
Sociální
komponenta
𝒗1(𝑡)
𝒗2(𝑡)
𝒙1(𝑡)
𝒙2(𝑡)
𝒚1 𝑡 = 𝒚 1 𝑡
𝒚2(𝑡)
𝒚 2 𝑡
![Page 24: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/24.jpg)
Local Best PSO
• Update rychlosti:
• Update pozice:
𝒙𝑖 t + 1 = 𝒙𝑖 t + 𝒗𝑖 t + 1
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 24
![Page 25: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/25.jpg)
Local Best PSO
• Update rychlosti:
• Vhodné nastavení parametrů:
𝑤 ... Lineárně klesající z 0.9 na 0.4
𝑐1 ... 2
𝑐2 ... 2
topologie ... Každý s každým/prstenec
𝑉𝑀𝐴𝑋 ... Podle rozsahu dané proměnné j
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 25
![Page 26: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/26.jpg)
Local Best PSO
Algoritmus: lbest PSO
Initialize 𝑛𝑥-dimenzional swarm of 𝑛𝑠 particles
repeat
for each particle 𝑖 = 1,… , 𝑛𝑠 do
if 𝑓 𝒙𝑖 < 𝑓 𝒚𝑖 then 𝒚𝑖 = 𝒙𝑖 end
end
for each particle 𝑖 = 1,… , 𝑛𝑠 do
𝒚 𝑖 = 𝑎𝑟𝑔𝑚𝑖𝑛𝒚𝑘 𝑓(𝒚𝑘) 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑘 ∈ 𝑁𝑖
end
for each particle 𝑖 = 1,… , 𝑛𝑠 do
update the velocity
update the position
end
until 𝑠𝑡𝑜𝑝𝑝𝑖𝑛𝑔 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑖𝑠 𝑡𝑟𝑢𝑒
BIODAT Group 26
![Page 27: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/27.jpg)
BIODAT Group 27
![Page 28: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/28.jpg)
Global Best PSO
• Všichni jedinci sdílejí jednu globální
informaci o best so far řešení
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
BIODAT Group 28
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
![Page 29: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/29.jpg)
Global Best PSO
Algoritmus: gbest PSO
Initialize 𝑛𝑥-dimenzional swarm
repeat
for each particle 𝑖 = 1,… , 𝑛𝑠 do
if 𝑓 𝒙𝑖 < 𝑓 𝒚𝑖 then 𝒚𝑖 = 𝒙𝑖 end
if 𝑓 𝒚𝑖 < 𝑓 𝒚 then 𝒚 = 𝒚𝑖 end
end
for each particle 𝑖 = 1,… , 𝑛𝑠 do
update the velocity
update the position
end
until 𝑠𝑡𝑜𝑝𝑝𝑖𝑛𝑔 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑖𝑠 𝑡𝑟𝑢𝑒
BIODAT Group 29
![Page 30: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/30.jpg)
Časté chyby
Algoritmus: lbest PSO
Initialize 𝑛𝑥-dimenzional swarm of 𝑛𝑠 particles
repeat
for each particle 𝑖 = 1,… , 𝑛𝑠 do
if 𝑓 𝒙𝑖 < 𝑓 𝒚𝑖 then 𝒚𝑖 = 𝒙𝑖 end
if 𝑓 𝒚𝑖 < 𝑓 𝒚 𝑖 then 𝒚 = 𝒚𝑖 end
end
for each particle 𝑖 = 1,… , 𝑛𝑠 do
update the velocity
update the position
end
until 𝑠𝑡𝑜𝑝𝑝𝑖𝑛𝑔 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 𝑖𝑠 𝑡𝑟𝑢𝑒
BIODAT Group 30
Engelbrecht (2005): Fundamentals of computational swarm intelligence.
Global best nemá v
local best algoritmu
co dělat.
Kdyby tam bylo
𝒚 𝒊 = 𝒚𝑖 nemohla by
být local best pozice
dosažená jiným
jedincem než je
jedinec i
![Page 31: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/31.jpg)
Časté chyby
• del Valle et al. (2008): Particle Swarm Optimization: Basic
Concepts, Variants and Applications in Power Systems
BIODAT Group 31
rand1 a rand2 by v
tomto případě musely
být diagonální matice
snáhodnými čísly na
diagonále
Při správné
inicializaci lze použí
pro řešení problémů
s lineárním
omezením
Ax=B
![Page 32: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/32.jpg)
Časté chyby
• del Valle et al. (2008): Particle Swarm Optimization: Basic
Concepts, Variants and Applications in Power Systems
BIODAT Group 32
Global best
pozice není
pozice jedince s
nejlepší
hodnotou fitness!
PSOtoolbox pro
Matlab trpěl touto
chybou
![Page 33: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/33.jpg)
Inicializace
• Rychlosti na nulovou hodnotu 𝒗𝑖 = 𝟎
• Pozice náhodně např. podle rozsahu
prohledávaného prostoru
• Personal, local nebo global best pozice
na aktuální pozici 𝒚𝑖 = 𝒙𝑖
• Dalčí metody:
– Sobol sequences
– Faure sequences
– Nonlinear simplex method
BIODAT Group 33
![Page 34: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/34.jpg)
Ukončovací kritérium
BIODAT Group 34
• Maximální počet iterací
• Nalezení řešení
• Stagnace po určitou dobu
• Ztratí se diverzita (normalizovaný průměr
swarmu je téměř 0)
• Pokles hodnoty cílové funkce je malý po
určitou dobu
![Page 35: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/35.jpg)
Exploze (divergence) swarmu
• Může vzniknout, pokud pozice jedince je
daleko od jeho personal best a
local/global best
• Lze řešit pomocí omezení rychlosti
• 𝑖𝑓 𝑣𝑖𝑗 > +𝑉𝑀𝐴𝑋,𝑗 𝑡ℎ𝑒𝑛 𝑣𝑖𝑗 = +𝑉𝑀𝐴𝑋,𝑗
• 𝑖𝑓 𝑣𝑖𝑗 < −𝑉𝑀𝐴𝑋,𝑗 , 𝑡ℎ𝑒𝑛 𝑣𝑖𝑗 = −𝑉𝑀𝐴𝑋,𝑗
BIODAT Group 35
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
![Page 36: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/36.jpg)
Exploze (divergence) swarmu
• Může vzniknout, pokud pozice jedince je
daleko od jeho personal best a
local/global best
• Lze také řešit pomocí constriction
coeficientu:
BIODAT Group 36
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
𝑣𝑖𝑗 𝑡 + 1 = 𝜒 𝑣𝑖𝑗 𝑡 + 𝑐1𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝑐2𝑟2𝑗 𝑡 𝑦 𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡
![Page 37: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/37.jpg)
Konvergence
• Konvergence do bodu 𝒑
• Základní PSO
– není garantována kovergence do globálního optima !!!!!!!
– není garantována kovergence do lokálního optima !!!!!!!
BIODAT Group 37
lim𝒕→∞
𝒚 𝑡 = 𝒑
![Page 38: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/38.jpg)
Konvergence
• GCPSO
– Guaranteed convergence PSO
– Van den Bergh and Engelbrecht (2002): A new locally convergent Particle Swarm Optimizer.
– Garantovaná konvergence do lokálního optima přidáním náhodného prohledávání okolí gbest pozice
– 𝜌 𝑡 se adaptivně prizpůsobuje a je vždy>0
BIODAT Group 38
𝑣𝑖𝑗 𝑡 + 1 = 𝑤(𝑡)𝑣𝑖𝑗 𝑡 + 𝑦 𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 + 𝜌 𝑡 [1 − 2𝑟2𝑗 𝑡 ]
![Page 39: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/39.jpg)
Konvergence
• Van den Bergh (2002): An analysis of particle swarm optimizers, PhD thesis:
• Algoritmy s garantovanou konvergencí do globálního optima:
• RPSO
– Random particle PSO
• V každé iteraci, nejméně jedna pozice je náhodně resetována
• MPSO
– Multi-start PSO
BIODAT Group 39
![Page 40: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/40.jpg)
Binární PSO
pokud
BIODAT Group 40
1)1( txij )1(1
1)1,0(
tvije
U
-10 -8 -6 -4 -2 0 2 4 6 8 100
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
vi(t+1)
P[x
i(t+
1)=
1]
![Page 41: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/41.jpg)
Multiobjective optimalizace
BIODAT Group 41
![Page 42: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/42.jpg)
Multiobjective optimalizace
• Agregace jednotlivých funkcí
– Např. vážený součet
• Různé části prohledávání používají různé funkce
– např. Dynamic Neighborhood MOPSO, Vector evaluated PSO (VEPSO),...
• Metody založené na dominanci
– Hledání a uchovácání pareto fronty – archiv
– Např. Moore a Chapman: Personal best je seznam, z kterého se vybírá náhodně
BIODAT Group 42
![Page 43: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/43.jpg)
Multiobjective optimalizace
• Další metody založené na dominanci:
– Coello Coello and Lechuga: Adaptive archive grid
– Mostaghim and Teich: Sigma method and 𝜀 –
dominance
– Hu, Eberhart and Shi: Global guide selection
– Zhang and Huang: Distance based selection
– Li: Non dominated sorting
– Yen and Lu
– Fieldsend and Singh: Dominated trees
– Ray and Liew: Swarm metaphor
BIODAT Group 43
![Page 44: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/44.jpg)
Dynamická optimalizace
• Detekce změny ztrátové funkce
– Např. sledováním chování global best pozice
a její příslušné hodnoty f
• Odezva na změnu a sledování optima
– Např. restart některých jedinců
• Např. Simulátor skleníku pro rajčata –
optimalizace podmínek pro růst rajčat
BIODAT Group 44
![Page 45: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/45.jpg)
Aplikace
• Učení skrytých Markovských modelů
– Nahrazení hill-climbingového EM algoritmu
PSO metodou
– Optimalizace s omezením
– Analýza nitrolebečního tlaku pro detekci
traumatického poranění mozku
– Detekce fází spánku z EEG
BIODAT Group 45
x1 x2
a21
a11 a22
G(m1,U1) G(m2,U2)
![Page 46: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/46.jpg)
Aplikace
• Plánování cesty robota
– Reprezentace cesty splineami
– Optimalizace parametrů spliny
BIODAT Group 46
![Page 47: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/47.jpg)
Aplikace
• Plánování cesty robota
BIODAT Group 47
![Page 48: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/48.jpg)
Aplikace
• Plánování cesty robota
BIODAT Group 48
![Page 49: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/49.jpg)
Aplikace
• Predikce aktivity reaktoru
– 17 vstupních prom.
– 1 výstupní prom.
– Cílem je
• Vytvořit adaptivní model
(adaptace na změny procesu
způsobené neměřitelnými
vlivy)
BIODAT Group 49
![Page 50: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/50.jpg)
Aplikace
• Predikce aktivity reaktoru
BIODAT Group 50
Inp
uts
P
red
icti
on
![Page 51: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/51.jpg)
Aplikace
– Nevýhoda
klasického přístupu:
• Uváznutí v lokálních
extrémech
• Aproximace
gradientu –
příspěvek vah
zpětné vazby je
zanedbán
BIODAT Group 51
![Page 52: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/52.jpg)
Aplikace
• Predikce aktivity reaktoru
– Adaptivita – reinicializace části swarmu
BIODAT Group 52
![Page 53: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/53.jpg)
Aplikace
• Selekce příznaků pro
rozpoznávání
– Binární PSO
– Klasifikace spánkového
EEG novorozenců
– Predikce stavu pacienta
– Klasifikace při hloubkové
stimulaci mozku
– Klasifikace srdečních
signálů plodu
BIODAT Group 53
![Page 54: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/54.jpg)
Aplikace
• Optimalizace extrakce příznaků
– Klasifikace úrovně frakcionace
intrakardiálních signálů – Křemen, V. - Lhotská, L. - Macaš, M. - Čihák, R. - Kautzner, J. - et al.: A New
Approach to Automated Assessment of Fractionation of Endocardial
Electrograms During Atrial Fibrillation.Physiological Measurement. 2008,
vol. 29, no. 12, p. 1371-1381. ISSN 0967-3334
BIODAT Group 54
![Page 55: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/55.jpg)
• Vizualizace – Štěpánová, K. - Macaš, M.: Visualizing Correlations Between EEG
Features by Two Different Methods. In BioDat 2012 - Conference on
Advanced Methods of Biological Data and Signal Processing [CD-ROM].
Praha: České vysoké učení technické v Praze, 2012, vol. 1, p. 1-4.
ISBN 978-80-01-05153-5.
BIODAT Group 55
![Page 56: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/56.jpg)
Aplikace
• Shlukování
– Detekce jednotlivých typů očních pohybů
BIODAT Group 56
Fixace
![Page 57: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/57.jpg)
Aplikace
• Shlukování
– Detekce jednotlivých typů očních pohybů
BIODAT Group 57
![Page 58: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/58.jpg)
PSO poslední trendy
• Výrazný nárůst aplikací v energetice
– Obnovitelné zdroje, kvalita elektřiny, ...
BIODAT Group 58
![Page 59: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/59.jpg)
PSO poslední trendy
BIODAT Group 59
1996 1998 2000 2002 2004 2006 2008 2010 2012 20140
500
1000
1500
2000
2500
Rok
Pocet
casopis
eckych c
lanku v
e W
OS
![Page 60: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/60.jpg)
Děkuji za pozornost
BIODAT Group 60
![Page 61: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/61.jpg)
Dodatek
BIODAT Group 61
![Page 62: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/62.jpg)
Formování názorů a optimalizace
BIODAT Group 62
tvs
?s
tvs
![Page 63: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/63.jpg)
10111 11101
00101 00100
00111
q1~-f(00101)
q2~-f(00101)
q3~-f(11101)
q4~-f(00100) qi~-f(00111)
63
Social impact theory based optimizer
![Page 64: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/64.jpg)
Aplikace
• Predicting Mortality of ICU Patients:
The PHYSIONET/COMPUTING IN CARDIOLOGY
Challenge 2012
– SITO based feature selection for Linear Bayes classifier
– Reduced initialization was used
– Event 1: maximize min(sensitivity, positive predictivity)
– Event 2: minimize Hosmer-Lemeshow statistic
– 30 participants
– We achieved
• 4th place in Event 1
• 3rd place in Event 2
BIODAT Group 64
![Page 65: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/65.jpg)
Aplikace
• Predicting Mortality of ICU Patients: The
PHYSIONET/COMPUTING IN
CARDIOLOGY Challenge 2012
BIODAT Group 65
![Page 66: Particle Swarm Optimization - cuni.cz](https://reader031.vdocumenti.com/reader031/viewer/2022012005/61d9242759d5e003cd14b967/html5/thumbnails/66.jpg)
Aplikace
• Optimization of classification system for
recognition of tea samples
– Central Scientific Instruments Organisation,
INDIA
BIODAT Group 66