PSO OPTIMALIZACE V MATLABU

PSO OPTIMALIZACE V MATLABU ˇ M. Capek, P. Hazdra ˇ Katedra elektromagnetick´eho pole, CVUT - FEL, Technick´a 2, 166 27 Praha Abstrakt Pˇ r´ıspˇ evek se vˇ enuje implementaci PSO algoritmu v Matlabu a presentaci jednotliv´ ych optimalizaˇ cn´ıch u ´ loh. PSO1 je st´ ale relativnˇ e novou, velice rychlou a robustn´ı techniku optimalizace, kter´ a pod´ av´ a ve vˇ etˇ sinˇ e testovan´ ych pˇ r´ıpad˚ u v´ yborn´ e v´ ysledky. Z´ akladn´ı u ´ lohu lze d´ ale modifikovat zaveden´ım tzv. zd´ı pro zrychlen´ı cel´ eho procesu. Z´ avislost v´ ysledn´ eho ˇ reˇ sen´ı na vstupn´ıch parametrech, ale tak´ e efektivita cel´ e funkce bude pˇ redstavena na nˇ ekolika pˇ r´ıkladech. Pr˚ ubˇ eh optimalizace lze efektivnˇ e modeloval pomoc´ı nˇ ekolika parametr˚ u, coˇ z uk´ azaly i uveden´ e testy. Vytvoˇ ren´ ym programem lze ˇ reˇ sit takˇ rka libovoln´ y probl´ em, staˇ c´ı pouze, aby vztah mezi vstupem a (minimalizovan´ ym) v´ ystupem popisovala funkce (tzv. fitness funkce) naprogramovateln´ a v Matlabu. V tomto ˇ cl´ anku jsou – s jedinou v´ yjimkou – uvedeny pouze r˚ uznˇ e sloˇ zit´ e matematick´ e funkce; d˚ uraz je kladen na PSO.

´ Uvod

1

Od roku 1995, kdy bylo PSO poprv´e pˇredstaveno [3], se objevila cel´a ˇrada studi´ı a v´ yzkum˚ u, kter´e PSO vyuˇz´ıvaj´ı. Na z´akladˇe potˇreby testovat jejich z´avˇery, ale i rozv´ıjet vlastn´ı aktivity (zejm. spojen´e s IFS ant´enami, viz [6], [7], [8]), bylo rozhodnuto vyvinout vlastn´ı algoritmus. Mezi poˇzadavky byla prioritnˇe rychlost algoritmu, jeho univerz´alnost, moˇznost mˇenit jednotliv´e parametry (iterace, poˇcet agent˚ u . . . ), d´ale schopnost rekurzivn´ıho vol´an´ı2 , ˇreˇsitelnost probl´em˚ u libovoln´e dimenze a v neposledn´ı ˇradˇe stabilita (zdaleka ne vˇsechny sc´en´aˇre zadan´e algoritmu jsou ˇreˇsiteln´e – m˚ uˇze j´ıt napˇr. o fyzik´aln´ı omezen´ı v souvislosti s optimalizac´ı rozmˇer˚ u ant´eny). Pro realizaci tohoto algoritmu bylo zvoleno prostˇred´ı Matlab. Matlab obsahuje velice rychl´e j´adro pro pr´aci s maticemi, disponuje celou ˇradou knihoven a lze se tedy soustˇredit pˇr´ımo na ˇreˇsen´ y probl´em, umoˇzn ˇuje komformn´ı grafick´ y i textov´ y v´ ystup. Velk´a ˇc´ast literatury obsahuje pˇr´ıklady pr´avˇe z Matlabu, lze tedy porovn´avat jednotliv´a ˇreˇsen´ı a pro partikul´arn´ı probl´emy vyuˇz´ıvat publikovan´e segmenty k´odu (napˇr. [5], [2]). Velkou v´ yhodou je tak´e moˇzn´e propojen´ı s Comsolem, ve kter´em lze vyuˇz´ıt dutinov´eho modelu pro mod´aln´ı ˇreˇsen´ı ant´en. V´ ysledn´a funkce, representovan´a programem PSOptimizer, respektuje vˇsechny v´ yˇse uveden´e poˇzadavky. Podrobnˇeji ji budou vˇenov´any ˇc´asti 3 a 4.

2

PSO algoritmus

Nejprve se vˇsak kr´atce zm´ın´ıme o principu PSO. Optimalizace vych´az´ı z rojov´e inteligence pozorovan´e napˇr. u vˇcelstev a napodobuje jejich chov´an´ı. V nˇekter´ ych aspektech je PSO podobn´ a ACO3 , v jin´ ych m˚ uˇzeme nal´ezt paralelu s GA4 . Ve vˇsech pˇr´ıpadech jde o samo se organizuj´ıc´ı syst´emy vykazuj´ıc´ı siln´e kolektivn´ı chov´an´ı. Z´asadn´ı rozd´ıl vˇsak spoˇc´ıv´a v pˇr´ıstupu k ˇclenu hejna (agentovi), nad kter´ ym jsou definov´any urˇcit´e operace a disponuje ˇc´ast´ı znalost´ı, kter´e m´a cel´ y roj. Uˇzivatel stanov´ı prostor (solution space, d´ale jen s.s.), nad kter´ ym je definov´ana optimalizovan´a funkce a v kter´em hled´a jej´ı minimum. V mnoho aplikac´ıch nem´a ˇreˇsen´ı mimo s.s. smysl, proto se snaˇz´ıme udrˇzet agenty v urˇcen´em prostoru (podrobnˇeji n´ıˇze). 1

PSO – Particle Swarm Optimalization N´ avratov´ a hodnota funkce mus´ı obsahovat nejen optimalizovan´e u ´daje, ale i informace o nastaven´ı PSO, jednotliv´ ych generac´ıch, konvergenci ke glob´ aln´ımu minimu atd. 3 ACO – Ant Colony Optimization 4 GA – Genetic Algorithm 2

Kaˇzd´ y agent si pamatuje sv˚ uj dosavadn´ı nejlepˇs´ı objev (pbest, promˇenn´a pnid v rovnici (1)). Nejlepˇs´ı objev cel´eho hejna (gbest, pngd ) je potom t´ım nejlepˇs´ım ze vˇsech osobn´ıch objev˚ u. Chov´an´ı jednotliv´ ych agent˚ u popisuj´ı n´asleduj´ıc´ı dva vztahy. Nejprve uved’me v´ ypoˇcet rychlosti agenta. Rychlost je stanovena v kaˇzd´e iteraci pro kaˇzd´eho agenta zvl´aˇst’ a ovlivˇ nuje smˇer, j´ımˇz se pohybuje. Poˇcet sloˇzek tohoto vektoru je rovn´ y dimenzi (index d ) ˇreˇsen´eho probl´emu. n+1 n υid = wυid + c1 r1n (pnid − χnid ) + c2 r2n (pngd − χnid )

(1)

V Matlabu je potˇreba vsadit tuto rovnici do for cyklu, ˇc´ımˇz je zajiˇstˇeno proch´azen´ı cel´eho hejna (index i oznaˇcuje agenty). Zabalen´ım do dalˇs´ıho for cyklu umoˇzn´ıme iterov´an´ı cel´eho probl´emu od n = 1 do n = N (paralela k jednotliv´ ym generac´ım u GA). D´ale je nutno objastnit v´ yznam zbyl´ ych promˇenn´ ych a konstant. Koeficient w je ˇcasto naz´ yv´an v´ahovac´ı faktor (weighted factor ). M˚ uˇze b´ yt po celou dobu optimalizace konstantn´ı, nebo se m˚ uˇze mˇenit (potom je zad´avana dvojice parametr˚ u wmax a wmin ). Klesaj´ıc´ı koeficient zabraˇ nuje nepˇr´ıjemn´ ym oscilac´ım a z´aroveˇ n stimuluje hejno ke konvergenci nad nalezen´ ym glob´aln´ım minimem. Parametry c1 a c2 ud´avaj´ı nakolik bude v´ ysledn´ a rychlost odvozena od osobn´ıho minima dan´eho agenta a nakolik od spoleˇcn´eho glob´aln´ıho min. Jejich optim´aln´ı velikost bude diskutov´ana v ˇc´asti 5. Bez koment´aˇre z˚ ustaly jiˇz pouze hodnoty n n r1 a r2 . V obou pˇr´ıpadech se jedn´a o n´ahodnˇe generovan´a ˇc´ısla s norm´aln´ım rozloˇzen´ım v rozsahu (0,1), pro tyto u ´ˇcely je v Matlabu k dispozici funkce rand(). V´ıme-li jiˇz, jak´ ym smˇerem a jak rychle se pohybuj´ı agenti, m˚ uˇzeme aktualizovat jejich pozici: n+1 ∆t. (2) = χnid + υid χn+1 id Rovnice (2) odpov´ıd´a pohybov´e rovnic´ı. Nov´e um´ıstˇen´ı agenta tedy z´ısk´av´ame jako souˇcet koordin´at˚ u v minul´e iteraci pozmˇenˇen´e o pohyb v souˇcasn´e iteraci. Protoˇze ∆t m˚ uˇze obecnˇe nab´ yvat libovoln´ ych hodnot, lze pˇriˇradit ∆t = 1 (jednotkov´ y ˇcas).

Obr´azek 1: Typy zd´ı pouˇz´ıvan´e v PSO Vztahy uveden´e v´ yˇse ˇz´adn´ ym zp˚ usobem neomezuj´ı pohyb agent˚ u, mohou tedy opustit s.s. Z toho d˚ uvodu bylo navrˇzeno nˇekolik technik, kter´e zajist´ı, aby se agenti nerozbˇehli daleko za hranice s.s. Mezi nejcitovanˇejˇs´ı a nejuˇz´ıvanˇejˇs´ı patˇr´ı n´asleduj´ıc´ı: n+1 ˆ Omezen´ı maxim´ aln´ı rychlosti agenta (υid )

ˆ Ohraniˇcuj´ıc´ı zdi:

1. Absorbˇcn´ı zed’ (Absorbing Wall, obr. 1a) 2. Odrazn´a zed’ (Reflecting Wall, obr. 1b) 3. Neviditeln´ a zed’ (Invisible Wall, obr. 1c)

Prvn´ı uveden´a moˇznost, tedy omezen´ı rychlosti agent˚ u, byla vyuˇzita napˇr. v [4]. Rychlost je omezena i uvnitˇr s.s., coˇz nen´ı vhodn´e. Lepˇs´ım ˇreˇsen´ım je pouˇzit´ı jedn´e ze zd´ı. Ty popisuj´ı zp˚ usob, jak´ ym je naloˇzeno s agentem, pokud pˇrekroˇc´ı povolen´e hranice. Neovlivˇ nuj´ı pr˚ ubˇeh optimalizace uvnitˇr s.s. a nav´ıc, pokud jiˇz agent opusil prohled´avan´ y prostor, ho efektivnˇe nasmˇeruj´ı zpˇet. Podrobnˇeji bude pops´ana pouze zed’ z obr. 1c, vyuˇz´ıvan´a funkc´ı PSOptimizer, ostatn´ı jsou pops´any napˇr. v [2]. Jak m˚ uˇzeme vyˇc´ıst z obr´azku, agent˚ um je umoˇznˇeno vyletˇet ze s.s., ovˇsem po jeho opuˇstˇen´ı nen´ı vyhodnocov´ana fitness funkce. To zapˇr´ıˇc´ın´ı pozvoln´ y n´avrat agent˚ u zpˇet do s.s. Velkou pˇrednost´ı je v´ yrazn´a u ´spora v´ ypoˇcetn´ıho ˇcasu, ponˇevadˇz jsou vyhodnocov´ana pouze ta sch´emata, o kter´a se skuteˇcnˇe zaj´ımame. I z tohoto d˚ uvodu se jedn´a o pravdˇepodobnˇe nejlepˇs´ı ˇreˇsen´ı pro vˇetˇsinu inˇzen´ yrsk´ ych probl´em˚ u. Na z´avˇer zrekapitujme d˚ uleˇzit´e parametry PSO optimalizace: Parametr c1 c2 wmin wmax ∆t iterace poˇcet agent˚ u pni png

pozn´avac´ı parametr (cognitive rate) soci´aln´ı parametr (social rate) v´ahovac´ı koeficient (na konci optimalizace) v´ahovac´ı koeficient (na zaˇc´atku optimalizace) ˇcasov´a konstanta (nejˇcastˇeji volena jednotkov´a, tj. ∆t = 1) poˇcet iterac´ı (vliv velikosti iterac´ı viz n´ıˇze) poˇcet agent˚ u nad s.s. (viz n´ıˇze) (souˇcasn´e) individi´aln´ı nalezen´e minimum agenta (fmin (xi )) (souˇcasn´e) glob´aln´ı nalezen´e minimum agenta fmin (xi ) Tabulka 1: Shrnut´ı parametr˚ u

3

Implementace

Jak jiˇz bylo uvedeno, optimalizace je implementov´ana do prostˇred´ı Matlab. Pro ˇc´asti programu jsme uˇzili lok´aln´ıch funkc´ı, fitness funkce je ˇreˇsena separ´atnˇe (definuje ji uˇzivatel pro konkr´etn´ı probl´em). V inicializaˇcn´ı ˇc´asti je ovˇeˇreno, jsou-li hodnoty spr´avnˇe zad´any, je stanovena poˇc´ateˇcn´ı generace agent˚ u a vykresleno grafick´e rozhran´ı.

Obr´azek 2: GUI PSOptimizeru

GUI programu je navrˇzen tak, aby byl jednoduch´ y5 , ale z´aroveˇ n podrobnˇe informoval o st´avaj´ıc´ım stavu optimalizace. Text v lev´em r´amu zobrazuje nastaven´e v´ ychoz´ı parametry, v prav´e ˇc´asti potom aktu´aln´ı pr˚ ubˇeh. Stupnice na ose y grafu zobrazuj´ıc´ıho cost funkci je v (zde n´azornˇejˇs´ım) logaritmick´em mˇeˇr´ıtku. Tlaˇc´ıtko Exit ukonˇcuje optimalizaci, nejdˇr´ıve vˇsak po dokonˇcen´ı dan´e iterace. I v tomto pˇr´ıpadˇe se vrac´ı v´ ysledky, kter´ ych bylo dosaˇzeno. Vyjdeme-li ze z´akladn´ıho tvaru vol´an´ı funkce: res = PSOptimizer(PsoData,’fitnessFunction’,ag,it), kde ag je poˇcet agent˚ u, it poˇcet iterac´ı a ˇretˇezec fitnessFunction obsahuje jm´eno mfile souboru s fitness funkc´ı, vytv´aˇr´ıme potom n´asleduj´ıc´ı pole vstupu a v´ ystupu: PsoData.data1 = [ ] PsoData.data2 = [ ] PsoData.data3 = [ ] PsoData.type = ’psopt’ PsoData.rank PsoData.bound{} = [ ] PsoData.cond{} = [ ] res.data1 = [ ] res.data2 = [ ] res.data3 = [ ] res.done res.score res.type = ’optim’ res.history.populPosition = [ ] res.history.iter = [ ] res.history.value = [ ] res.history.psoDta = [ ] res.options. ... Pˇrednˇe do funkce vstupuj´ı 3 sloty (PsoData.data1-3), ve kter´ ych se mohou um´ıstit optimalizovan´a data. Velikost matic data1-3 je libovoln´a, vˇzdy vˇsak mus´ı b´ yt vˇsechny tˇri matice definov´any (alespoˇ n jako pr´azdn´e). Poˇcet slot˚ u vol´ıme tak, aby byl dostateˇcn´ y pro ˇreˇsen´ı IFS ant´en (body z´akladn´ıho u ´tvaru, transformace a iteraˇcn´ı matice). Dalˇs´ım polem je PsoData.type, kter´e je fixnˇe zad´ano string ˇretˇezcem psopt. Pole je potˇreba pˇri identifikaci pˇr´ıchoz´ıch dat uvnitˇr funkce. PsoData.rank je nepovinn´ yu ´daj, jenˇz koresponduje s dimenz´ı optimalizace. Na z´avˇer zde figuruj´ı pole PsoData.bound, ve kter´em jsou uloˇzeny hranice6 definuj´ıc´ı s.s. a tak´e PsoData.cond, indexuj´ıc´ı optimalizovan´e parametry7 . Matice PsoData.cond m˚ uˇze m´ıt libovoln´ y poˇcet ˇr´adek. Protoˇze kaˇzd´a ˇr´adka oznaˇcuje jednu optimalizovanou pozici v jedn´e z matic, lze takto sv´azat do jedn´e dimenze (PsoData.cond{dim}) nˇekolik optimalizovan´ ych hodnot. Takov´e hodnoty jsou potom v r´amci PSO spˇraˇzeny a jsou optimalizov´any spoleˇcnˇe. Tento postup je ide´aln´ı v pˇr´ıpadˇe, ˇze potˇrebujeme mezi nˇekter´ ymi hodnotami zachovat fixn´ı pomˇer (jejich rovnost). Uveden´ ym postupem zajist´ıme, ˇze do funkce vstupuj´ı vˇsechna uˇzivatelsk´a data (fitness funkce tedy m˚ uˇze s tˇemito daty komplexnˇe pracovat) a nav´ıc ucelen´ yu ´daj co a v jak´ ych mez´ıch se m´a optimalizovat. V´ ystupn´ı pole obsahuje opˇet sloty 1-3, patˇriˇcn´e hodnoty jsou ale optimalizov´any. Hod5

Pokud je program vol´ an opakovanˇe, nezatˇeˇzuje PC. Zp˚ usob z´ apisu: ProData.bound{dimenze}= [min max] pro danou dimenzi.   a1 b1 c1   7 Form´ at je n´ asleduj´ıc´ı: PsoData.cond{dimenze} =  a2 b2 c2 , kde a odpov´ıd´ a ˇc´ıslu datov´eho slotu 1-3, .. .. .. . . . b ukazuje na ˇr´ adku dan´eho slotu, c potom znaˇc´ı pozici na ˇr´ adce (ˇc´ıslo sloupce). 6

Obr´azek 3: Pozice agent˚ u v dan´e iteraci pro funkci Levy5, 10x10 nota fitness funkce pro tyto je uvedena v res.score. Pole done referuje o zd´arn´em ukonˇcen´ı PSO (res.done = 1), v opaˇcn´em pˇr´ıpadˇe je res.done = 0 (urˇceno jako n´avˇest´ı pro nadˇrazen´e programy). Res.options uv´ad´ı hodnoty, za kter´ ych byla optimalizace dokonˇcena a koneˇcnˇe res.history obsahuje vˇetˇsinu vnitˇrn´ıch stav˚ u PSOptimizeru v kaˇzd´e iteraci8 .

4

Vybran´ e funkce

Algoritmus byl testov´an n´asleduj´ıc´ımi funkcemi: ˆ Kvadratick´ a funkce ˆ Rosenbrockova funkce ˆ Funkce Levy No.5

Funkce jsou rozd´ılnˇe ˇclenit´e (krajina, kterou se pohybuj´ı agenti) a jsou dostateˇcnˇe pops´any v literatuˇre, lze tedy verifikovat z´ıskan´e hodnoty. Algoritmus byl vyuˇzit i pro optimalizaci jin´ ych funkc´ı (Levy No.3, Rastigrinova funkce. . . ), ve vˇsech pˇr´ıpadech PSO podalo oˇcek´avan´e v´ ysledky. Metodika vyuˇzit´a pro hodnocen´ı v´ ysledk˚ u optimalizace respektuje obvykl´e postupy ([1] a dalˇs´ı). Funkce 1 (kvadratick´ a) fkv (x) = x2 − 10 8

(3)

Tyto pole lze vyuˇz´ıt napˇr. pro vykreslen´ı COST funkce (napˇr. obr. 4 vpravo pro kvadratickou funkci), nebo pro vykreslen´ı pozice jednotliv´ ych agent˚ u v dan´e iteraci (screenshot 53. iterace je vidˇet na obr. 3).

Na t´eto funkci demonstrujeme vliv neviditeln´e zdi9 . Pokud s.s. zvol´ıme pouze v rozsahu h2, 5i, bude nalezen´e minimum rovno -6, a to i pˇres to, ˇze jednotliv´ı agenti mohou kr´atkodobˇe proniknout i bl´ıˇze k 0 na ose x. Situace je zn´azornˇena na obr. 4.

Obr´azek 4: Optimalizace kvadratick´e funkce v rozsahu x ∈ h2, 5i

Funkce 2 (Rosenbrockova) f (x) =

N  X

100(xi+1 − x2i )2 + (xi − 1)2



(4)

i=1

fro (x, y) = 100(y − x2 )2 + (x − 1)2

(5)

Funkce se ˇsiroce uplatˇ nuje ve vˇetˇsinˇe optimalizaˇcn´ı test˚ u. Pro svou monotonii (obr´azek 5) lze vyuˇz´ıt i gradientn´ı metody, nebot’ nehroz´ı uv´ıznut´ı v lok´aln´ım minimu. Glob´aln´ı mininum m˚ uˇzeme nal´ezt na souˇradnic´ıch x = 1, y = 1 a hodnota f (xmin , ymin ) = 0. Podle rovnice (4) je funkce definov´ana v [2], vyuˇzijeme vˇsak jednoduˇsˇs´ıho tvaru (5). Obr. 6 ukazuje, jak rychle kles´a chyba,

Obr´azek 5: Rosenbrockova funkce, s.s. ∈ h−10, 10i × h−10, 10i a cost funkce s kterou je nalezeno glob´aln´ı minimum. Tuto rychlost lze v´ yraznˇe ovlivnit nastaven´ım parametr˚ u wmin a wmax . Pokud v´ahovac´ı koeficient s iterac´ı kles´a, kles´a tak´e pˇr´ıspˇevek novˇe vypoˇcten´e rychlosti a agent je sp´ıˇse udrˇzov´an v souˇcasn´e pozici. Eliminujeme t´ım oscilace, pˇri kter´ ych agenti kmitaj´ı kolem nalezen´eho minima. 9

Neviditeln´ a zed’ se uplatˇ nuje nepˇr´ımo t´ım, ˇze neumoˇzn´ı vyhodnotit moˇzn´e niˇzˇs´ı minimum v rozsahu h−2, 2i. Vybran´ a pole PsoData pro tuto optimalizaci jsou rovna: PsoData.rank = 1; PsoData.cond{1} = [1 1 1]; PsoData.bound{1} = [2 5].

Obr´azek 6: Konvergence ke skuteˇcn´emu minimu Rosenbrockovy funkce Funkce 3 (Levy No.5) fl5 (x, y) =

5  X i=1

5    X   i cos (i−1)x+i j cos (j+1)y+j +(x+1.42513)2 +(y+0.80032)2 (6) j=1

Na prostoru h−2, 2i×h−2, 2i m˚ uˇzeme nal´ezt 760 lok´aln´ıch a jedno glob´aln´ı minimum (souˇradnice x = −1.3068, y = −1.4248). Velikost s.s. je u ´myslnˇe zvˇetˇsena na h−10, 10i × h−10, 10i (jako u Rosenbrockovy f.). Tato funkce dobˇre testuje odolnost v˚ uˇci uv´ıznut´ı agent˚ u v lok´aln´ıch extr´emech.

Obr´azek 7: Funkce Levy No.5, s.s. ∈ h−10, 10i × h−10, 10i a cost funkce

5

Optim´ aln´ı parametry PSO

V´ ysledek, stejnˇe tak jako rychlost, s jakou je ˇreˇsen´ı nalezeno, lze v´ yznamn´ ym zp˚ usobem ovlivnit 10 vhodnou volbou parametr˚ u z tabulky 1 . Jednotliv´e optimalizace jsou velkou mˇerou z´avisl´e na n´ahodˇe a jak´ekoliv u ´daje mus´ıme z´ıskat jako pr˚ umˇer velk´eho poˇctu opakov´an´ı (zpravidla 50). Cel´a procedura se tak st´av´a ˇcasovˇe n´aroˇcnˇejˇs´ı. Nejprve uved’me grafick´e pr˚ ubˇehy. Jejich u ´kolem nen´ı zobrazit nalezenou hodnotu, sledujeme zde pr˚ ubˇeh funkˇcn´ıch hodnot v ˇcase. Tento typ graf˚ u je v anglick´e literatuˇre oznaˇcov´an jako 10

Konkr´etnˇe se budeme zab´ yvat poˇctem iterac´ı a velikost´ı hejna, a tak´e koeficienty c1 a c2 .

cost funkce a d´av´a dobrou pˇredstavu o pr˚ ubˇehu optimalizace. Zaj´ımav´e jsou zejm´ena r˚ uˇzov´e a fialov´a kˇrivka. Na nich vid´ıme, ˇze v pˇr´ıpadˇe zcela nevhodnˇe nastaven´ ych parametr˚ u nekonverguje hejno dostateˇcnˇe.

Obr´azek 8: Optimalizace funkce Levy5 pro r˚ uzn´a c1 a c2 (20 agent˚ u, 150 iterac´ı)

Obr´azek 9: Optimalizace funkce Levy5 pro r˚ uzn´a c1 a c2 (20 agent˚ u, 150 iterac´ı) N´asleduj´ıc´ı tabulky demonstruj´ı z´asadn´ı vliv parametr˚ u c1 a c2 na koneˇcn´ y v´ ysledek ´ eˇsnost algoritmu testujeme podm´ınkou, zda je nalezen´a hodnota menˇs´ı neˇz optimalizace. Uspˇ −176.1375 (Levy5, hodnota bl´ızk´a zn´am´emu glob´aln´ımu minimu, viz [1]). Z aplikaˇcn´ıho hlediska jsou zaj´ımav´e dva u ´daje. Prvn´ı je ten, kdy je u ´spˇeˇsnost poprv´e rovna 100%, tedy chv´ıle, kdy optimalizace vˇzdy najde spr´avn´ y v´ ysledek. Tento moment lze urˇcit pouze pro jiˇz zmapovan´e funkce. Druh´ y zaj´ımav´ y v´ ysledek je ten s nejvyˇsˇs´ı u ´ˇcinnost´ı v nejkratˇs´ım moˇzn´em ˇcase11 . Vid´ıme tedy, ˇze u ´spˇeˇsnost funkce lze v´ yznamn´ ym zp˚ usobem zv´ yˇsit u ´pravou parametr˚ u (c1 , c2 , ale i dalˇs´ımi, kter´ ymi se zde nebudeme zab´ yvat), coˇz popisuj´ı nˇekter´e studie. Bohuˇzel optimalizovan´e funkce maj´ı r˚ uzn´ y charakter, a proto jsou tyto parametry voleny zpravidla na z´akladˇe doporuˇcen´ı v referenˇcn´ı literatuˇre. Pro u ´plnost uved’me i u ´ˇcinnost optimalizace pˇri zmˇenˇe poˇctu agent˚ u (tabulky 4 a 5, n´ıˇze). Poˇcet agent˚ u je zpravidla pevnˇe stanoven (nejˇcastˇeji 20-25 jedinc˚ u). Zv´ yˇsit jejich poˇcet je 11

V pˇr´ım´e u ´mˇeˇre odpov´ıd´ a pˇr´ıpadu s nejmenˇs´ım celkov´ ym poˇctem vyhodnocen´ı fitness funkce (v tabulce evalFun)

Funkce Levy5 (10x10 s.s.) 50x spuˇstˇeno, 20 agent˚ u iterace u ´spˇeˇsnost [%] chyb celkov´ y ˇcas [s] evalFun c1 = 2.0, c2 = 2.0, wmin = 0.4, wmax = 0.9 50 5% 48/50 187 1000 100 78% 11/50 378 2000 150 92% 4/50 571 3000 300 100% 0/50 1258 6000 500 100% 0/50 2308 10000 c1 = 0.5, c2 = 0.6, wmin = 0.4, wmax = 0.9 100 80% 10/50 387 2000 c1 = 1.0, c2 = 1.0, wmin = 0.4, wmax = 0.9 100 92% 4/50 387 2000 PC: HP Compaq nx6125 (Turion64 1.86GHz, 768MB 333MHz) Tabulka 2: Success rate funkce Levy5 (se zmˇenou iterace), 20 agent˚ u Funkce Levy5 (10x10 s.s.) 50x spuˇstˇeno, 45 agent˚ u iterace u ´spˇeˇsnost [%] chyb celkov´ y ˇcas [s] evalFun c1 = 2.0, c2 = 2.0, wmin = 0.4, wmax = 0.9 50 16% 42/50 370 2250 100 98% 1/50 711 4500 150 98% 1/50 1083 6750 300 100% 0/50 2328 13500 500 100% 0/50 ¿4000 22500 c1 = 0.5, c2 = 0.6, wmin = 0.4, wmax = 0.9 50 72% 14/50 362 2250 c1 = 1.0, c2 = 1.0, wmin = 0.4, wmax = 0.9 50 90% 5/50 363 2250 PC: HP Compaq nx6125 (Turion64 1.86GHz, 768MB 333MHz) Tabulka 3: Success rate funkce Levy5 (se zmˇenou iterace), 45 agent˚ u Funkce Levy5 (10x10 s.s.) 50x spuˇstˇeno, 150 iterac´ı agent˚ u u ´spˇeˇsnost [%] chyb celkov´ y ˇcas [s] evalFun c1 = 2.0, c2 = 2.0, wmin = 0.4, wmax = 0.9 5 44% 28/50 84 750 10 64% 18/50 121 1500 20 92% 4/50 198 3000 30 100% 0/50 276 4500 45 100% 0/50 370 6750 PC: 64bit Core2Quad 9450 (2.66GHz),12MB cache, 4GB 1333MHz Tabulka 4: Success rate funkce Levy5 (podle poˇctu agent˚ u), 150 agent˚ u

doporuˇceno u probl´em˚ u, kter´e jsou definov´any na velmi rozlehl´em s.s., anebo (zejm´ena) pokud prohled´avan´ y prostor obsahuje mnoho lok´aln´ıch minim. Mnohem ˇcastˇeji je v pˇr´ıpadˇe probl´em˚ u nav´ yˇsen poˇcet iterac´ı, pˇr´ıpadnˇe jsou pozmˇenˇeny parametry c1 a c2 . Na z´avˇer kr´atce okomentujme obr´azky 10 a 11. Vyn´aˇs´ıme zde dva parametry, kter´e popisuj´ı

Funkce Levy5 (10x10 s.s.) 50x spuˇstˇeno, 50 iterac´ı agent˚ u u ´spˇeˇsnost [%] chyb celkov´ y ˇcas [s] evalFun c1 = 2.0, c2 = 2.0, wmin = 0.4, wmax = 0.9 5 0% 50/50 32 250 10 0% 50/50 42 500 20 2% 49/50 65 1000 30 6% 47/50 88 1500 45 12% 44/50 118 2250 c1 = 0.5, c2 = 0.6, wmin = 0.4, wmax = 0.9 45 76% 12/50 160 2250 c1 = 1.0, c2 = 1.0, wmin = 0.4, wmax = 0.9 45 92% 4/50 154 2250 c1 = 1.5, c2 = 1.5, wmin = 0.4, wmax = 0.9 45 90% 5/50 165 2250 PC: 64bit Core2Quad 9450 (2.66GHz),12MB cache, 4GB 1333MHz Tabulka 5: Success rate funkce Levy5 (podle poˇctu agent˚ u), 50 iterac´ı

Obr´azek 10: Poˇcet agent˚ u mimo s.s. pro Rosenbrockovu a Levy5 funkci (20 agent˚ u, 150 iterac´ı)

Obr´azek 11: Rozptyl agent˚ u, Rosenbrockova a Levy5 funkce (20 agent˚ u, 150 iterac´ı) optimalizaci nez´avisle na zkouman´e funkci. Poˇcet agent˚ u mimo s.s., stejnˇe tak jako jejich rozptyl12 , lze pro stejnˇe velk´e s.s. vz´ajemnˇe porovn´avat. Na prvn´ı pohled je patrn´e, ˇze – aˇc pro zcela rozd´ıln´e funkce – jsou si pr˚ ubˇehy dosti podobn´e a napov´ıdaj´ı, jak´ ym zp˚ usobem se pohybuje hejno bˇehem optimalizace. M˚ uˇze b´ yt pˇredmˇetem dalˇs´ıho v´ yzkumu, zda lze t´eto z´avislosti vyuˇz´ıt k zefektivnˇen´ı PSO. 12

Pag

Definov´ an: σ =

n n i=1 (kpg k−kpi k)

ag

, kde ag je celkov´ y poˇcet agent˚ u.

6

Shrnut´ı

V pˇr´ıspˇevku byla rozvedena implementace PSO algoritmu do Matlabu. Optimalizace byla pops´ ana form´alnˇe i na konkr´etn´ıch pˇr´ıkladech. Uk´azali jsme, jak´ ym zp˚ usobem ovlivˇ nuj´ı jednotliv´e parametry pr˚ ubˇeh optimalizace a jak´e m˚ uˇzeme oˇcek´avat v´ ysledky. Prostor byl vˇenov´an i popisu vstupn´ıch a v´ ystupn´ıch pol´ı, jejichˇz charakter – spolu s pˇreindexov´an´ım hodnot uvnitˇr funkce – umoˇzn ˇuje vyuˇz´ıvat PSOptimizer pro ˇreˇsen´ı cel´e ˇrady probl´em˚ u. D´ale jsme se kr´atce vˇenovali moˇznosti modelovat pr˚ ubˇeh PSO, ˇc´ımˇz by se v´ yraznˇe zkr´atila doba potˇrebn´a ke konvergenci do glob´aln´ıho minima. Pˇresn´ y postup nen´ı v souˇcasn´e dobˇe dostateˇcnˇe publikov´an v referenˇcn´ı literatuˇre a experiment´aln´ıch dat nen´ı zat´ım dostatek pro formulaci vlastn´ıch z´avˇer˚ u. Dokonˇcen´ y optimaliz´ator je v souˇcasn´e dobˇe vyuˇz´ıv´an pro rozliˇcn´e u ´lohy na katedˇre elektromagnetick´eho pole, kde autoˇri p˚ usob´ı. V´ yˇse uveden´e poznatky jsou aplikov´any zejm. v oblasti ant´enn´ı techniky a teorie pole.

Reference [1] K. E. Parsopoulos, M. N. Vrahatis: Recent approaches to global optimization problems through Particle Swarm Optimization, Natural Computing, pp.235–306, 2002. [2] Jacob Robinson, Yahya Rahmat-Samii: Particle Swarm Optimization in Electromagnetics, IEEE Trans. on Antennas and Propagation, Vol. 52, No. 2, pp.397–407, February 2004. [3] James Kennedy, Russell Eberhart: Particle Swarm Optimization, IEEE, pp.1942–1948, 1995. [4] Ruˇzica M. Golubovi´c, Dragan I. Ol´can: Antenna Optimization Using Particle Swarm Optimization Algorithm, Journal of Automatic Control, Vol. 16, pp.21–24, 2006. [5] Sergey N. Makarov: Antenna and EM Modeling with Matlab, Wiley-Interscience, New York, 2002, ISBN: 0-471-21876-6. ˇ ˇ [6] Miloslav Capek: Mod´ aln´ı anal´yza mikrop´ askov´ych patch ant´en, Bakal´aˇrsk´a pr´ace, CVUTFEL, Praha, 2007. [7] Pavel Tiˇsnovsk´ y: Interaktivn´ı editor afinn´ıch transformac´ı. Diplomov´a pr´ace, VUT. Brno, 1999. ˇ [8] Pavel Hazdra: Frakt´ alov´e ant´eny. Diplomov´a pr´ace, CVUT-FEL, Praha, 2003.

ˇ Miloslav Capek [email protected] Ing. Pavel Hazdra [email protected]