Rojová optimalizace v Matlabu

ˇ z, 2009 Rektorysova souteˇ

1

Rojová optimalizace v Matlabu 1 ˇ Miloslav CAPEK 1

ˇ Katedra elektromagnetického pole, Cesk´ e vysoké uˇcen´ı technické v Praze, Fakulta elektrotechniky, ˇ Technická 2, 166 27 Praha, Cesk´ a republika [email protected]

Abstrakt. Pˇr´ıspˇevek popisuje principy PSO optimalizace, jej´ı výhody i nevýhody. Mechanismus rojen´ı cˇ a´ stic byl implementován v prostˇred´ı Matlab. Jak bude ukázáno, vyuˇzit´ı je velice sˇiroké a nasazen´ı metody je vysoce efektivn´ı. Bylo testováno mnoho funkc´ı, vˇetˇsina se známým kanonickým pˇredpisem a s pˇresnˇe lokalizovatelným globáln´ım minimem. Tyto funkce jsou krátce pˇredstaveny, vˇc. výsledk˚u optimalizace. Zm´ın´ıme se i o nastaven´ı vstupn´ıch parametr˚u PSO, tzv. metaoptimalizaci a na závˇer uvedeme jeden praktický pˇr´ıklad, jak je PSO optimalizace vyuˇz´ıvána na domovské katedˇre autora (optimalizace fraktáln´ıch patch antén s ohledem na minimáln´ı vyzaˇrovac´ı frekvenci dominantn´ıho módu struktury). Tento cˇ lánek vznikl jako kompilát pro u´ cˇ ely Rektorysovy soutˇezˇe; volnˇe pˇrej´ımá statˇe z [1] – [6], coˇz jsou vlastn´ı práce autora. Takto pˇrejaté cˇ a´ sti budou citovány jen volnˇe.

maticemi, disponuje celou rˇadou knihoven a lze se tedy soustˇredit pˇr´ımo na ˇreˇsený problém, umoˇznˇ uje komfortn´ı grafický i textový výstup. Velká cˇ a´ st literatury obsahuje pˇr´ıklady právˇe z Matlabu, lze tedy porovnávat jednotlivá ˇreˇsen´ı a pro partikulárn´ı problémy vyuˇz´ıvat publikované segmenty kódu (napˇr. [8]). Velkou výhodou je také moˇzné propojen´ı s Comsolem, ve kterém lze vyuˇz´ıt dutinového modelu pro modáln´ı ˇreˇsen´ı antén. Výsledná funkce, representovaná programem PSOptimizer2 , respektuje vˇsechny výsˇe uvedené poˇzadavky. Podrobnˇeji ji bude vˇenována cˇ a´ st 2 a také cˇ a´ sti 4-5.

Kl´ıcˇ ová slova Particle swarm optimization (PSO), fitness funkce, testovac´ı funkce, Matlab, Iterated function system (IFS)

´ 1. Uvod Od roku 1995, kdy bylo PSO poprvé pˇredstaveno [7], se objevila celá ˇrada studi´ı a výzkum˚u, které PSO vyuˇz´ıvaj´ı. Na základˇe potˇreby testovat jejich závˇery, ale i rozv´ıjet vlastn´ı aktivity (zejm. spojené s IFS anténami, viz [4], [5], [6]), bylo rozhodnuto vyvinout vlastn´ı aplikaci. Mezi poˇzadavky byla prioritnˇe rychlost algoritmu, jeho univerzálnost, moˇznost mˇenit jednotlivé parametry (iterace, poˇcet agent˚u . . . ), dále schopnost rekurzivn´ıho volán´ı1 , ˇreˇsitelnost problém˚u libovolné dimenze a v neposledn´ı ˇradˇe stabilita (zdaleka ne vˇsechny scénáˇre zadané algoritmu maj´ı ˇreˇsen´ı – m˚uzˇ e j´ıt napˇr. o fyzikáln´ı omezen´ı daného problému). Pro realizaci tohoto algoritmu bylo zvoleno prostˇred´ı Matlab, které obsahuje velice rychlé jádro pro práci s 1 N´ avratová hodnota funkce mus´ı obsahovat nejen optimalizované u´ daje, ale i informace o nastaven´ı PSO, jednotlivých generac´ıch, konvergenci ke globáln´ımu minimu atd.

Obr. 1. Pohyb jednotlivých agent˚u (vˇcel) nad loukou“ ”

2. PSO algoritmus Nejprve se vˇsak krátce zm´ın´ıme o principu PSO. Optimalizace vycház´ı z rojové inteligence pozorované napˇr. u vˇcelstev a napodobuje jejich chován´ı. V nˇekterých aspektech je PSO podobná ACO3 , v jiných m˚uzˇ eme nalézt paralelu s GA4 . Souhrnnˇe potom mluv´ıme o evoluˇcn´ıch, nebo také heuristických algoritmech. Ve vˇsech pˇr´ıpadech 2 Ale

také programem PSOpost, urˇceným pro PSO postprocessing. – Ant Colony Optimization 4 GA – Genetic Algorithm 3 ACO

ˇ ´ OPTIMALIZACE V MATLABU M. CAPEK, ROJOVA

2

jde o samo se organizuj´ıc´ı systémy vykazuj´ıc´ı silnˇe kolektivn´ı chován´ı. Zásadn´ı rozd´ıl vˇsak spoˇc´ıvá v pˇr´ıstupu k cˇ lenu hejna (agentovi), nad kterým jsou definovány urˇcité operace a disponuje cˇ a´ st´ı znalost´ı, které má celý roj. Ve shodˇe s [11] m˚uzˇ eme chován´ı agent˚u oznaˇcit jako soutˇezˇ ivˇe-kooperativn´ı: v pr˚ubˇehu optimalizace se stˇr´ıdaj´ı fáze, kdy mezi sebou agenti vzájemnˇe soupeˇr´ı a fáze, kdy spolupracuj´ı. Uˇzivatel stanov´ı prostor (solution space, dále jen s.s.), nad kterým je definována optimalizovaná funkce a nad kterým hledá jej´ı minimum. V mnoha aplikac´ıch nemá ˇreˇsen´ı mimo s.s. smysl, proto se snaˇz´ıme udrˇzet agenty v urˇceném prostoru (podrobnˇeji rozebereme nˇekteré techniky n´ızˇ e). Kaˇzdý agent si pamatuje sv˚uj dosavadn´ı nejlepˇs´ı objev (pbest, promˇenná pnid v (1)). Nejlepˇs´ı objev celého hejna (gbest, pngd ) je potom t´ım nejlepˇs´ım ze vˇsech osobn´ıch objev˚u. Chován´ı jednotlivých agent˚u popisuj´ı následuj´ıc´ı dva vztahy. Nejprve uved’me výpoˇcet rychlosti agenta. Rychlost je stanovena v kaˇzdé iteraci pro kaˇzdého agenta zvlásˇt’ a ovlivˇnuje smˇer, j´ımˇz se pohybuje5 . Poˇcet sloˇzek tohoto vektoru je rovný dimenzi (index d) ˇreˇseného problému. 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ázen´ı celého hejna (index i oznaˇcuje agenty). Zabalen´ım do dalˇs´ıho for cyklu umoˇzn´ıme iterován´ı celého problému od n = 1 do n = N (paralela k jednotlivým generac´ım u GA, zde se vˇsak agenti pouze pohybuj´ı nad s.s. – nehroz´ı jim zánik, dokonce ani nevytváˇr´ıme nové jedince). Dále je nutno objasnit význam zbylých promˇenných a konstant. Koeficient w je cˇ asto nazýván váhovac´ı faktor (weighted factor). M˚uzˇ e být po celou dobu optimalizace konstantn´ı, nebo se m˚uzˇ e mˇenit (potom je zadávana dvojice parametr˚u wmax a wmin ). Klesaj´ıc´ı koeficient zabraˇnuje nepˇr´ıjemným oscilac´ım a zároveˇn stimuluje hejno ke konvergenci nad nalezeným globáln´ım minimem. Parametry c1 a c2 udávaj´ı, nakolik bude výsledná rychlost odvozena od osobn´ıho minima daného agenta a nakolik od spoleˇcného globáln´ıho min. Jejich optimáln´ı velikost bude diskutována v cˇ a´ sti 7. Bez komentáˇre z˚ustaly jiˇz pouze hodnoty r1n a r2n . V obou pˇr´ıpadech se jedná o náhodnˇe generovaná cˇ´ısla s normáln´ım rozloˇzen´ım v rozsahu (0,1), pro tyto u´ cˇ ely je v Matlabu k dispozici funkce rand(). V´ıme-li jiˇz, jakým smˇerem a jak rychle se pohybuj´ı agenti, m˚uzˇ eme aktualizovat jejich pozici: n+1 χn+1 = χnid + υid ∆t. id

Vztahy uvedené výsˇe zˇ a´ dným zp˚usobem neomezuj´ı pohyb agent˚u, mohou tedy opustit s.s. Z toho d˚uvodu bylo navrˇzeno nˇekolik technik, které zajist´ı, aby se agenti nerozbˇehli daleko za hranice s.s. Mezi nejcitovanˇejˇs´ı a nejuˇz´ıvanˇejˇs´ı patˇr´ı následuj´ıc´ı: n+1 • Omezen´ı maximáln´ı rychlosti agenta (υid )

• Ohraniˇcuj´ıc´ı zdi: 1. Absorbˇcn´ı zed’ (Absorbing Wall, obr. 2a) 2. Odrazná zed’ (Reflecting Wall, obr. 2b) 3. Neviditelná zed’ (Invisible Wall, obr. 2c) Prvn´ı uvedená moˇznost, tedy omezen´ı rychlosti agent˚u, byla vyuˇzita napˇr. v [10]. Rychlost je omezena i uvnitˇr s.s., coˇz nen´ı zejm. pro prohledáván´ı rozsáhlých uzem´ı pˇr´ıliˇs vhodné. Lepˇs´ım ˇreˇsen´ım je pouˇzit´ı jedné ze zd´ı. Ty popisuj´ı zp˚usob, jakým je naloˇzeno s agentem, pokud pˇrekroˇc´ı povolené hranice. Neovlivˇnuj´ı pr˚ubˇeh optimalizace uvnitˇr s.s. a nav´ıc, pokud jiˇz agent opusil prohledávaný prostor, ho efektivnˇe nasmˇeruj´ı zpˇet. Podrobnˇeji bude popsána pouze zed’ z obr. 2c, vyuˇz´ıvaná funkc´ı PSOptimizer, ostatn´ı jsou popsány napˇr. v [9]. Jak m˚uzˇ eme vyˇc´ıst z obrázku, agent˚um je umoˇznˇeno vyletˇet ze s.s., ovˇsem po jeho opuˇstˇen´ı nen´ı vyhodnocována fitness funkce. To zapˇr´ıcˇ´ın´ı pozvolný návrat agent˚u zpˇet do s.s. Velkou pˇrednost´ı je výrazná u´ spora výpoˇcetn´ıho cˇ asu, ponˇevadˇz jsou vyhodnocována pouze ta schémata, o která se skuteˇcnˇe zaj´ımáme. I z tohoto d˚uvodu se jedná o pravdˇepodobnˇe nejlepˇs´ı ˇreˇsen´ı pro vˇetˇsinu inˇzenýrských problém˚u. Na závˇer zrekapitulujme d˚uleˇzité parametry PSO optimalizace: Parametr a jeho význam v PSO c1 poznávac´ı parametr (cognitive rate) c2 sociáln´ı parametr (social rate) wmin váhovac´ı koeficient (na konci optimalizace) wmax váhovac´ı koeficient (na zaˇca´ tku optimalizace) ∆t cˇ asová konstanta (nejˇcastˇeji volena ∆t = 1) it poˇcet iterac´ı (vliv velikosti iterac´ı viz n´ızˇ e) ag poˇcet agent˚u nad s.s. (viz n´ızˇ e) pni individiáln´ı nalezené min. agenta (fmin (xi )) png globáln´ı nalezené min. agenta fmin (xi ) Tab. 1. Shrnut´ı parametr˚u

(2)

Rovnice (2) odpov´ıdá pohybové rovnic´ı. Nové um´ıstˇen´ı agenta tedy z´ıskáváme jako souˇcet koordinát˚u v minulé iteraci pozmˇenˇené o pohyb v souˇcasné iteraci. Protoˇze ∆t m˚uzˇ e obecnˇe nabývat libovolných hodnot, lze pˇriˇradit ∆t = 1 (tedy diskrétn´ı, jednotkový cˇ as). 5 Resp.

se bude pohybovat po vyhodnocen´ı této iterace. Obr. 2. Typy zd´ı pouˇz´ıvané v PSO


3

3. Implementace

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. ...

Jak jiˇz bylo uvedeno, optimalizace je implementována v prostˇred´ı Matlab. Pro cˇ a´ sti programu jsme uˇzili lokáln´ıch funkc´ı, fitness funkce je ˇreˇsena separátnˇe (definuje ji uˇzivatel pro konkrétn´ı problém). V inicializaˇcn´ı cˇ a´ sti je ovˇeˇreno, jsou-li hodnoty správnˇe zadány, je stanovena poˇca´ teˇcn´ı generace agent˚u a vykresleno grafické rozhran´ı.

Obr. 3. GUI PSOptimizeru

GUI programu je navrˇzen tak, aby byl jednoduchý6 , ale zároveˇn podrobnˇe informoval o stávaj´ıc´ım stavu optimalizace. Text v levém rámu zobrazuje nastavené výchoz´ı parametry, v pravé cˇ a´ sti potom aktuáln´ı pr˚ubˇeh. Stupnice na ose y grafu zobrazuj´ıc´ıho cost funkci je v (zde názornˇejˇs´ım) logaritmickém mˇeˇr´ıtku. Tlaˇc´ıtko Exit ukonˇcuje optimalizaci, nejdˇr´ıve vˇsak po dokonˇcen´ı dané iterace. I v tomto pˇr´ıpadˇe jsou uloˇzeny a vráceny výsledky, kterých bylo dosaˇzeno. Vyjdeme-li ze základn´ıho tvaru volán´ı funkce:

res = PSOptimizer(PsoData,’fitnessFunction’,ag,it),

kde ag je poˇcet agent˚u, it poˇcet iterac´ı a ˇretˇezec fitnessFunction obsahuje jméno mfile souboru s fitness funkc´ı. Pro navazuj´ıc´ı analýzu a zpracován´ı dat, byly vytvoˇreny následuj´ıc´ı datové struktury: PsoData.data1 = [ ] PsoData.data2 = [ ] PsoData.data3 = [ ] PsoData.type = ’psopt’ PsoData.rank PsoData.bound{} = [ ] PsoData.cond{} = [ ]

6 Pokud

je program volán opakovanˇe, nezatˇezˇ uje PC.

Pˇrednˇe do funkce vstupuj´ı 3 sloty (PsoData.data1-3), ve kterých se mohou um´ıstit optimalizovaná data. Velikost matic data1-3 je libovolná, vˇzdy vˇsak mus´ı být vˇsechny tˇri matice definovány (alespoˇn jako prázdné). Poˇcet slot˚u vol´ıme tak, aby byl dostateˇcný pro ˇreˇsen´ı IFS antén (body základn´ıho u´ tvaru, transformace a iteraˇcn´ı matice). Obecnˇe vˇsak nen´ı poˇcet tˇechto slot˚u omezen, stejnˇe tak jako jejich vyuˇzit´ı. Dalˇs´ım polem je PsoData.type, které je fixnˇe zadáno string ˇretˇezcem psopt. Pole je potˇreba pˇri identifikaci pˇr´ıchoz´ıch dat uvnitˇr funkce. PsoData.rank je nepovinný u´ daj, jenˇz koresponduje s dimenz´ı optimalizace. Na závˇer zde figuruj´ı pole PsoData.bound, ve kterém jsou uloˇzeny hranice7 definuj´ıc´ı s.s. a také PsoData.cond, indexuj´ıc´ı optimalizované parametry8 . Matice PsoData.cond m˚uzˇ e m´ıt libovolný poˇcet ˇra´ dek. Protoˇze kaˇzdá ˇra´ dka oznaˇcuje jednu optimalizovanou pozici v jedné z matic, lze takto svázat do jedné dimenze (PsoData.cond{dim}) nˇekolik optimalizovaných hodnot. Takové hodnoty jsou potom v rámci PSO spˇraˇzeny a jsou optimalizovány spoleˇcnˇe. Tento postup je ideáln´ı v pˇr´ıpadˇe, zˇ e potˇrebujeme mezi nˇekterými hodnotami zachovat fixn´ı pomˇer (jejich rovnost). Uvedeným postupem zajist´ıme, zˇ e do funkce vstupuj´ı vˇsechna uˇzivatelská data (fitness funkce tedy m˚uzˇ e s tˇemito daty komplexnˇe pracovat) a nav´ıc ucelený u´ daj co a v jakých mez´ıch se má optimalizovat. Výstupn´ı pole obsahuje opˇet sloty 1-3, patˇriˇcné hodnoty jsou ale optimalizovány. Hodnota fitness funkce pro tyto je uvedena v res.score. Pole done referuje o zdárném ukonˇcen´ı PSO (res.done = 1), v opaˇcném pˇr´ıpadˇe je res.done = 0 (urˇceno jako návˇest´ı pro nadˇrazené programy). Res.options uvád´ı hodnoty, za kterých byla optimalizace dokonˇcena a koneˇcnˇe res.history obsahuje vˇetˇsinu vnitˇrn´ıch stav˚u PSOptimizeru v kaˇzdé iteraci9 . Zakonˇceme tuto cˇ a´ st pohledem na pseudokód, pˇrevoditelný do libovolného programovac´ıho jazyku: 7 Zp˚ usob zápisu: ProData.bound{dimenze}=

[min max] pro danou di-

menzi.  a1 b1 c1  a b c 2 2  8 Form´ at je: PsoData.cond{dimenze} =  2 , kde a .. .. .. . . . odpov´ıdá cˇ´ıslu datového slotu 1-3, b ukazuje na ˇra´ dku daného slotu, c potom znaˇc´ı pozici na ˇra´ dce (ˇc´ıslo sloupce). 9 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ých agent˚u v dané iteraci (obr. 15). 


4

krok 1. krok 2. krok 3. krok 4. krok 5. krok 6. krok 7. krok 8. krok 9. krok 10. krok 11. krok 12. krok 13. krok 14. krok 15. krok 16. krok 1. krok 2. krok 3.

PSOptimizer kontrola vstupn´ıch parametr˚u inicializace GUI tvorba (náhodného) hejna vyhodnocen´ı 1. iterace for i = 1:iteraciCelkem u´ prava wactual update rychlosti agent˚u update pozice agent˚u for j = 1:agent˚uCelkem if agent(j) ∈ s.s. callFF end end update pBest, gBest výpis informac´ı end callFF uprav´ı PsoData podle aktuáln´ıch agent˚u volá f.f. s aktuáln´ımi daty (PsoData) agent˚um je pˇriˇrazen výsledek f.f.

Tab. 2. Principiáln´ı schéma PSOptimizeru

4. Pouˇzité testovac´ı funkce Strukturu PsoData mus´ıme zohlednit pˇri návrhu jakékoliv fitness funkce. Nikoliv pouze hlaviˇcky, ale i pˇri zpracován´ı dat zaslaných PSO algoritmem na ohodnocen´ı. Definice funkce by mˇela odpov´ıdat následuj´ıc´ımu vzoru: function fitnessValue = fitnessFunction(sign, tested data)

kterých známe výsledek (tj. globáln´ı minima). Algoritmus byl provˇeˇren následuj´ıc´ımi funkcemi: • Kvadratická funkce • Rosenbrockova funkce (Rosenbrock’s saddle) • Funkce Levy No.5 (Levy’s function No.5) • Ackleyho funkce II (Ackley’s function II) • Ranova funkce (Rana’s function) • Rastrigrinova funkce (Rastrigrin’s function) Funkce jsou rozd´ılnˇe cˇ lenité (krajina, kterou se pohybuj´ı agenti) a jsou z velké cˇ a´ sti dostateˇcnˇe popsány v literatuˇre, lze tedy verifikovat z´ıskané hodnoty. Algoritmus byl vyuˇzit i pro optimalizaci jiných funkc´ı (Levy No.3, Mastersova, Schwefelova, 4. de Jongova . . . ), ve vˇsech pˇr´ıpadech PSO podalo oˇcekávané výsledky. Metodika vyuˇzitá pro hodnocen´ı výsledk˚u optimalizace respektuje obvyklé postupy ([8] a dalˇs´ı). Funkce 1 (kvadratická) fkv (x) = x2 − 10

(3)

Na této funkci demonstrujeme vliv neviditelné zdi12 . Pokud s.s. zvol´ıme pouze v rozsahu h2, 5i, bude nalezené minimum rovno -6, a to i pˇres to, zˇ e jednotliv´ı agenti mohou krátkodobˇe proniknout i bl´ızˇ e k nule na ose x. Situace je znázornˇena na obr. 4.

String sign má vˇzdy hodnotu ’eval’, cˇ asto ho vyuˇz´ıváme pro oznaˇcen´ı volán´ı10 . Promˇenná fitnessValue vrac´ı zpˇet hodnotu, podle které se celý roj pohybuje (hodnota funkce v daném bodˇe, rezonanˇcn´ı frekvence dané struktury . . . ). Uvnitˇr tested data nalezneme sloty .data1-3 podobnˇe jako v PsoData, v tomto pˇr´ıpadˇe obsahuj´ı aktuáln´ı hodnoty urˇcené k vyhodnocen´ı funkce. D´ıky volán´ı extern´ıho mfilu, m˚uzˇ eme vyuˇz´ıvat PSOptimizer pro libovolné u´ cˇ ely – postaˇc´ı dodrˇzet pˇredepsanou hlaviˇcku f.f. (mfile) a data zadávat ve formˇe PsoData11 . Vzhledem k neexistenci ˇra´ dného PSO toolboxu v Matlabu, m˚uzˇ e být vyuˇzit´ı PSOptimizeru dobrou volbou, nehledˇe na dalˇs´ı moˇznosti pˇrizp˚usoben´ı.

Obr. 4. Kvadratické fce v rozsahu x ∈ h2, 5i

Funkce 2 (Rosenbrockova) f (x) =

N X

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

(4)

i=1

Testované funkce Pˇred praktickým nasazen´ım programu je nutné ovˇeˇrit funkˇcnost PSOptimizeru na analytických funkc´ıch, u 10 Napˇr. nadˇrazen´ e specializované programy pro výpoˇcet anténn´ıch struk-

tur poznaj´ı, zˇ e prob´ıhá optimalizace a nezav´ıraj´ı zˇ a´ dná grafická okna. 11 Vyuˇ zit´ı PSO v anténn´ı technice je obrovské. Od optimalizace záˇriˇcu˚ , pˇres u´ pravy cˇ oˇcek, reflektor˚u a ohnisek, aˇz po komplexn´ı optimalizace celých systém˚u.

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

(5)

Funkce se sˇiroce uplatˇnuje ve vˇetˇsinˇe optimalizaˇcn´ı test˚u. Pro svou monotonii (obr. 5) lze vyuˇz´ıt i gradientn´ı metody, nebot’ nehroz´ı uv´ıznut´ı v lokáln´ım minimu. Globáln´ı mininum m˚uzˇ eme nalézt na souˇradnic´ıch x = 1, y = 1 a jeho hodnota je rovna f (xmin , ymin ) = 0. Podle vztahu (4) je


5

Obr. 5. Rosenbrockova fce, s.s. ∈ h−10, 10i×h−10, 10i a cost fce

funkce definována v N-rozmˇerném prostoru, my vyuˇzijeme 2D pˇrepisu (5). Obr. 6 ukazuje, jak rychle klesá chyba, s kterou je nalezeno globáln´ı minimum. Tuto rychlost lze výraznˇe ovlivnit nastaven´ım parametr˚u wmin a wmax . Pokud váhovac´ı koeficient s iterac´ı klesá, klesá také pˇr´ıspˇevek novˇe vypoˇctené rychlosti a agent je sp´ısˇe udrˇzován v souˇcasné pozici. Eliminujeme t´ım oscilace, pˇri kterých agenti kmitaj´ı kolem nalezeného minima.

Obr. 7. Fce Levy No.5, s.s. ∈ h−10, 10i × h−10, 10i a cost fce

Funkce 4 (II. Ackleyho) D−1 P f (x) = 20 + e − i=1

−e

1 2

20 s 1 e5

(x2 +x2 ) i i+1 2

− (7)

cos(2πxi )+cos(2πxi+1 )

Tato a obˇe následuj´ıc´ı funkce 5 a 6 maj´ı obecný pˇredpis, testovali jsme vˇsak pouze funkce s D = 2. Druhá Ackleyho funkce má jedno jasnˇe zˇretelné globáln´ı minimum na pozici (x1 = 0, x2 = 0), jeho hodnota je f (0, 0) = 0, obecnˇe lze potom naj´ıt minima vˇzdy na pozici (x1 , x2 , . . . , xn ) = (0, 0, . . . , 0), jeho hodnota je rovna nule.

Obr. 6. Konvergence ke skuteˇcnému minimu Rosenbrockovy fce

Funkce 3 (Levy No.5) fl5 (x, y) =

5 P

i cos (i − 1)x + i × i=1 5 P × j cos (j + 1)y + j +

(6)

j=1

+(x + 1.42513)2 + (y + 0.80032)2 Na prostoru h−2, 2i × h−2, 2i m˚uzˇ eme nalézt 760 lokáln´ıch a jedno globáln´ı 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˚ucˇ i uv´ıznut´ı agent˚u v lokáln´ıch extrémech. ´ esˇnost optimalizace pro r˚uzná nastaven´ı ukazuj´ı tab. 7.2 Uspˇ aˇz 7.5 a obr. 7.

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

Obr. 8. II. Ackleyho fce, s.s. ∈ h−20, 20i × h−20, 20i

Funkce 5 (Ranova) f (x) =

D−1 P

p xi sin |xi+1 + 1 − xi | × i=1 p × cos |xi+1 + 1p+ xi | + +(xi+1 + 1) cos |xi+1 + 1 − xi | × p × sin |xi+1 + 1 + xi |

(8)

Ranova funkce je sloˇzitá jiˇz ve dvou-rozmˇerném prostoru – plocha je modulována pomoc´ı harmonických funkc´ı a to dostateˇcnˇe komplikovaným zp˚usobem (viz obrázek 9). Pˇresná poloha globáln´ıho minima se autorovy nepodaˇrila zjistit, nicménˇe i tak m˚uzˇ eme sledovat konvergenci hejna a jeho tlumenou oscilaci ve smˇeru x a y od bodu s globáln´ım minimem.


6

funkˇcn´ıch hodnot v cˇ ase. Tento typ graf˚u je v anglické literatuˇre oznaˇcován jako cost funkce a dává dobrou pˇredstavu o pr˚ubˇehu optimalizace. Zaj´ımavé jsou zejména r˚uzˇ ové a fialová kˇrivka. Na nich vid´ıme, zˇ e v pˇr´ıpadˇe zcela nevhodnˇe nastavených parametr˚u nekonverguje hejno dostateˇcnˇe.

Obr. 9. Ranova fce, s.s. ∈ h−50, 50i × h−50, 50i Obr. 11. Optimalizace fce Levy5 pro r˚uzná c1 a c2 (20 agent˚u, 150 iterac´ı)

Funkce 6 (Rastrigrinova) f (x) = 2D

D X

x2i − 10 cos(2πxi )

(9)

i=1

I tato funkce byla optimalizována pouze pro D = 2. Globáln´ı minimum nalezneme na pozici (x = 0, y = 0) a rovno −80. Pro n-rozmˇerný prostor, je minimum rovno −40n.

Obr. 12. Optimalizace fce Levy5 pro r˚uzná c1 a c2 (20 agent˚u, 150 iterac´ı)

Následuj´ıc´ı tabulky demonstruj´ı zásadn´ı vliv parametr˚u ´ esˇnost c1 a c2 na koneˇcný výsledek optimalizace. Uspˇ algoritmu testujeme podm´ınkou, zda je nalezená hodnota menˇs´ı neˇz −176.1375 (Levy5, hodnota bl´ızká známému globáln´ımu minimu, viz [8]).

Obr. 10. Rastrigrinova fce, s.s. ∈ h−5, 5i × h−5, 5i

˚ výsledky 5. Nastaven´ı parametru, Výsledek, stejnˇe tak jako rychlost, s jakou je rˇeˇsen´ı nalezeno, lze významným zp˚usobem ovlivnit vhodnou volbou parametr˚u z tabulky 113 . Pr˚ubˇeh jednotlivých optimalizac´ı je v podstatˇe náhodný a jakékoliv u´ daje mus´ıme z´ıskat jako pr˚umˇer velkého poˇctu opakován´ı (zpravidla 50). Celá procedura se tak stává cˇ asovˇe nároˇcnˇejˇs´ı. Nejprve uved’me grafické pr˚ubˇehy. Jejich u´ kolem nen´ı zobrazit nalezenou hodnotu, sledujeme zde pr˚ubˇeh 13 Konkr´ etnˇe

se budeme zabývat poˇctem iterac´ı a velikost´ı hejna, a také koeficienty c1 a c2 .

Funkce Levy5 (10x10 s.s.) 50x, 20 agent˚u iter. u´ spˇesˇnost [%] chyb cˇ as [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 HP nx6125 (Turion64 1.86GHz, 768MB 333MHz) Tab. 3. Success rate fce Levy5 (se zmˇenou iterace), 20 agent˚u

Z aplikaˇcn´ıho hlediska jsou zaj´ımavé dva u´ daje. Prvn´ı je ten, kdy je u´ spˇesˇnost poprvé rovna 100%, tedy chv´ıle, kdy optimalizace vˇzdy najde správný výsledek. Tento moment lze urˇcit pouze pro jiˇz zmapované funkce. Druhý zaj´ımavý


7

Funkce Levy5 (10x10 s.s.) 50x, 45 agent˚u iter. u´ spˇesˇnost [%] chyb cˇ as [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 HP ,nx6125 (Turion64 1.86GHz, 768MB 333MHz) Tab. 4. Success rate fce Levy5 (se zmˇenou iterace), 45 agent˚u

výsledek je ten s nejvyˇssˇ´ı u´ cˇ innost´ı v nejkratˇs´ım moˇzném cˇ ase14 . Vid´ıme tedy, zˇ e u´ spˇesˇnost funkce lze významným zp˚usobem zvýsˇit u´ pravou parametr˚u (c1 , c2 , ale i dalˇs´ımi, kterými se zde nebudeme zabývat), coˇz popisuj´ı nˇekteré studie. Bohuˇzel optimalizované funkce maj´ı r˚uzný charakter, a proto jsou tyto parametry voleny zpravidla na základˇe doporuˇcen´ı v referenˇcn´ı literatuˇre. Pro u´ plnost uved’me i u´ cˇ innost optimalizace pˇri zmˇenˇe poˇctu agent˚u (tabulky 5 a 6, n´ızˇ e). Funkce Levy5 (10x10 s.s.) 50x, 150 iterac´ı agen. u´ spˇesˇnost [%] chyb cˇ as [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 Core2Quad 9450 64b (2.66GHz),12MB, 4GB 1333MHz

Funkce Levy5 (10x10 s.s.) 50x, 50 iterac´ı agen. u´ spˇesˇnost [%] chyb cˇ as [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 Core2Quad 9450 64b (2.66GHz),12MB, 4GB 1333MHz Tab. 6. Success rate fce Levy5 (podle poˇctu agent˚u), 50 iterac´ı

malizace. M˚uzˇ e být pˇredmˇetem dalˇs´ıho výzkumu, zda lze této závislosti vyuˇz´ıt k zefektivnˇen´ı PSO.

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

Tab. 5. Success rate fce Levy5 (podle poˇctu agent˚u), 150 iterac´ı

Poˇcet agent˚u je zpravidla pevnˇe stanoven (nejˇcastˇeji 20-25 jedinc˚u). Zvýsˇit jejich poˇcet je doporuˇceno u problém˚u, které jsou definovány na velmi rozlehlém s.s., anebo (zejména) pokud prohledávaný prostor obsahuje mnoho lokáln´ıch minim. Mnohem cˇ astˇeji je v pˇr´ıpadˇe problém˚u navýsˇen poˇcet iterac´ı, pˇr´ıpadnˇe jsou pozmˇenˇeny parametry c1 a c2 . Na závˇer krátce okomentujme obrázky 13 a 14. Vynásˇ´ıme zde dva parametry, které popisuj´ı optimalizaci nezávisle na zkoumané funkci. Poˇcet agent˚u mimo s.s., stejnˇe tak jako jejich rozptyl15 , lze pro stejnˇe velké s.s. vzájemnˇe porovnávat. Na prvn´ı pohled je patrné, zˇ e – aˇc pro zcela rozd´ılné funkce – jsou si pr˚ubˇehy dosti podobné a napov´ıdaj´ı, jakým zp˚usobem se pohybuje hejno bˇehem opti14 V pˇr´ım´ e u´ mˇerˇe odpov´ıdá pˇr´ıpadu s nejmenˇs´ım celkovým poˇctem vyhodnocen´ı fitness funkce (v tabulce evalFun) P 15 Definov´ an:

σ=

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

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

Obr. 14. Rozptyl agent˚u, Rosenbrockova a Levy5 funkce (20 agent˚u, 150 iterac´ı)

Z n´ızˇ e prezentovaných výsledk˚u je vidˇet, zˇ e návrh PSO algoritmu byl u´ spˇesˇný a mnohdy dosahuje vyˇssˇ´ı u´ cˇ innosti neˇz srovnatelné publikované algoritmy, viz [10]. To je dáno pravdˇepodobnˇe pouˇzit´ım vhodného typu zdi a testován´ım pro relativnˇe (v kontextu optimalizace) jednoduchých funkc´ı.

6. PSO postprocessing Ve vˇetˇsinˇe pˇr´ıpad˚u zcela postaˇcuje jako návratová hodnota velikost fitness funkce a parametry j´ı pˇr´ısluˇsné (tedy sloty .data1-3). Chceme-li vˇsak hloubˇeji proniknout do mechanism˚u PSO optimalizace a – zejména pracujemeli s urˇcitým problémem opakovanˇe – vylepˇsit/zrychlit jej´ı


8

pr˚ubˇeh, je vhodné analyzovat výsledky podrobnˇeji. Pro tyto pˇr´ıpady vznikl nástroj PSOpost, obr. 15. Umoˇznˇ uje následné vykreslen´ı pozice agent˚u, vˇc. isoˇcar prohledávané funkce. Dalˇs´ı moˇznost´ı je vykreslen´ı smˇer˚u (vektor˚u) pohybu agent˚u. Tak lze studovat chován´ı jednotlivých cˇ len˚u hejna, ale i celého roje, pro jednotlivé funkce. Napˇr´ıklad na funkci zobrazené na obr. 15 se po jistém cˇ ase agenti pohybuj´ı jen v horizontáln´ım a vertikáln´ım smˇeru kolem globáln´ıho minima. M˚uzˇ eme sledovat vliv parametr˚u wmin a wmax na tlumen´ı tˇechto oscilac´ı. V jiném pˇr´ıpadˇe se mohou agenti pˇr´ıliˇs rozlétnout, pak je vhodné upˇrednostnit sociáln´ı parametr pˇred poznávac´ım.

verguje dostateˇcnˇe, cˇ i sp´ısˇe v˚ubec. Vˇetˇsina parametr˚u je urˇcena pouze na základˇe emperických znalost´ı a liˇs´ı se podle zkuˇsenost´ı autor˚u – kupˇr´ıkladu pro parametry c1 a c2 se povaˇzuje za obecnˇe platné pravidlo, zˇ e c1 + c2 ≤ 4. Taková nastaven´ı vˇsak vˇetˇsinou zˇ a´ dným zp˚usobem nezohledˇnuj´ı pr˚ubˇeh a chován´ı f.f. a pouˇz´ıvaj´ı se zkrátka pouze proto, zˇ e funguj´ı“. ” M˚uzˇ eme se tedy oprávnˇenˇe tázat, jak naj´ıt ty nejvhodnˇejˇs´ı parametry PSO. Pro tuto techniku (optimalizaci optimalizace) se vˇzilo nˇekolik term´ın˚u, nejˇcastˇeji vˇsak oznaˇcen´ı metaoptimalizace. Aplikovat PSO na analytickou funkci pro nˇekolik r˚uzných nastaven´ı a vybrat to nejlepˇs´ı je jednou z mnoˇznost´ı. Obt´ızˇ nˇe ho ovˇsem budeme realizovat pro f.f., u které neznáme funkˇcn´ı pˇredpis (viz cˇ a´ st 8). Jinou moˇznost´ı je vyuˇzit´ı dalˇs´ıch informac´ı, které nám jednotliv´ı agenti a jejich chován´ı poskytuje. Touto cestou se m˚uzˇ eme vydat d´ıky programu PSOpost. Jiné moˇznosti vylepˇsen´ı ukazuj´ı následuj´ıc´ı odstavce.

7.2. Stretched PSO Klasické pojet´ı PSO je dostateˇcnˇe efektivn´ı, pˇresto existuj´ı funkce (Corana 4D, XOR, Freudenstein-Rothova a dalˇs´ı), kde selhává. K. E. Parsopoulos a M. N. Vrahatis v [8] navrhli postup, který dosahuje i pro problematické funkce stoprocentn´ı u´ cˇ innosti.

Obr. 15. Nástroj PSOPost

PSOpost také v reálném cˇ ase poˇc´ıtá vˇsechny agenty mimo stanovený s.s., stejnˇe jako rozptyl celého hejna. Tyto hodnoty jsou zaznamenány do graf˚u (v obrázku napravo), které jsme uvedli výsˇe. Umoˇznˇ uj´ı urˇcit, zda jiˇz hejno skuteˇcnˇe naˇslo hodnotu, která se bl´ızˇ´ı reálnému globáln´ımi minimu. Nástroj nen´ı zdaleka dokonˇcen a je v souˇcasné dobˇe urˇcen pouze pro u´ lohy, které obsahuj´ı dva optimalizované parametry. V budoucnu bude moˇzné tyto parametry zvolit. Bohuˇzel tato problematika je dosti komplexn´ı a jej´ı názorná demonstrace vyˇzaduje sofistikovanˇejˇs´ı médium neˇz je tento cˇ lánek (dostateˇcnˇe názorná jsou videa). Vˇetˇs´ı pozornost této problematice vˇenujeme v souvisej´ı presentaci.

7. Metaoptimalizace, mutace PSO 7.1. Metaoptimalizace Obecnˇe se vzr˚ustaj´ıc´ım poˇctem parametr˚u rostou moˇznosti nastaven´ı jakékoliv optimalizace. Na druhou stranu algoritmus s menˇs´ım poˇctem parametr˚u (tj. stupˇnu˚ volnosti, napˇr. simulované zˇ´ıhán´ı) je transparentnˇejˇs´ı a jeho nastaven´ı jednoduˇssˇ´ı. PSO je v tomto smˇeru relativnˇe sloˇzité, nebot’ obsahuje celou ˇradu parametr˚u, které mus´ı být nastaveny v patˇriˇcných mez´ıch. V opaˇcném pˇr´ıpadˇe optimalizace nekon-

Nejvˇetˇs´ım problémem zm´ınˇených funkc´ı je existence mnoha lokáln´ıch minim. Ty stoj´ı v cestˇe agent˚um pˇri hledán´ı globáln´ıho minima16 . Pro dalˇs´ı u´ cˇ ely si m˚uzˇ eme lokáln´ı minimum popsat jako nejmenˇs´ı hodnotu funkce f v okol´ı B bodu x: f (x) ≤ f (x), ∀x ∈ B. (10) A právˇe vˇsechny body x krom globáln´ıho minima si pˇrejeme eliminovat. Ukazuje se, zˇ e stretching technika je vhodným nástrojem na potlaˇcen´ı tˇechto (vedlejˇs´ıch) minim. V podstatˇe jde o transformaci pˇredpisu f (x), která je provedena ve dvou kroc´ıch. Ihned po objeven´ı lokáln´ıho minima podle (10) pˇrevedeme funkci podle vztah˚u: G(x) = f (x) + γ1 kx − xk sign f (x) − f (x) + 1 (11) a sign f (x) − f (x) + 1 H(x) = G(x) + γ2 , tanh µ G(x) − G(x)

(12)

kde γ1 , γ2 a µ jsou libovolnˇe zvolené vysoké konstantn´ı hodnoty a sign(x) splˇnuje podm´ınku:   1 pro x > 0 0 pro x = 0 sign(x) = (13)  −1 pro x < 0 Funkci (13) m˚uzˇ eme numericky modelovat pomoc´ı 16 Pochopitelnˇ e

lze situaci ˇreˇsit zvýsˇen´ım poˇctu agent˚u a iterac´ı, ale tento postup nen´ı pˇr´ıliˇs efektivn´ı, resp. jeho efektivita strmˇe klesá s rostouc´ı sloˇzitost´ı funkce.


9

i poˇcet rozmˇer˚u (dimenzi) ˇreˇsené funkce. V d˚usledku se tak optimalizace stává ˇra´ dovˇe obt´ızˇ nˇejˇs´ı.

Obr. 16. Funkce Levy5: bez transformace, s G(x) a po H(x), zdroj: [8]

Realizace GSO je nenároˇcná d´ıky tomu, zˇ e pouze sluˇcuje dva jiˇz známe postupy, viz obr. 17. Jako nejvˇetˇs´ı obt´ızˇ se jev´ı vytvoˇren´ı vlastn´ıho GA optimalizátoru, který komunikuje s PSO a zvolen´ı vhodného formátu, s kterým GA i PSO dokázˇ´ı pracovat.

vztahu17 : sign(x) ≈ log sig(x) =

λx 2 ∼ tanh , (14) = 1 + exp−λx 2

pˇr´ıpadnˇe m˚uzˇ eme volat funkci sign v Matlabu. SPSO konverguje pro funkci Levy5 o 10-20% rychleji. Jak vid´ıme na obr. 16 uprostˇred (po transformaci G(x), podle (11)) a vpravo (po transformaci G(x) i H(x), podle (12)), lokáln´ı minima jsou roztaˇzena a rozmazána, zat´ımco globáln´ı minimum z˚ustalo nedotˇceno. V takto upravené krajinˇe“ se mohou agenti pohybovat mnohem snadnˇeji. ” V souˇcasné podobˇe PSOptimizeru nen´ı stretched PSO vyuˇz´ıváno – vˇsechny dosavadn´ı u´ koly spojené s optimalizac´ı patch antén se ukázaly dostateˇcnˇe ˇreˇsitelné i pomoc´ı klasického PSO v kombinaci s neviditelnou zd´ı, nicménˇe jeho pozdˇejˇs´ı nasazen´ı je stále zvaˇzováno.

7.3. GSO algoritmus V roce 2006 byla publikována práce [12], zabývaj´ıc´ı se moˇznost´ı spojit GA a PSO. Tato metoda je oznaˇcována jako GSO (Genetical Swarm Optimization).

8. Optimalizace IFS patch antén Pˇredposledn´ı cˇ a´ st vˇenujeme praktické ukázce vyuˇzit´ı PSOptimizeru pro efektivn´ı návrh patch antény. C´ılem je navrhnout takovou patch18 anténu, která by mˇela co nejniˇzsˇ´ı rezonanˇcn´ı frekvenci fr . Maximáln´ı rozmˇery záˇriˇce jsou fixnˇe zadány, u´ pravy lze tedy dosáhnou pouze zmˇenou geometrie. Vlastn´ı motiv je tvoˇren IFS fraktálem. Fraktáln´ı patche maj´ı v kontextu anténn´ı techniky nˇekolik velice zaj´ımavých vlastnost´ı (v´ıcepásmovost, lokalizaci proud˚u zvyˇsuj´ıc´ı smˇerovost, menˇs´ı rozmˇery . . . ), proto jim vˇenujeme zvýsˇenou pozornost.

Obr. 18. Pˇr´ıklad IFS patch motivu (1., 2. a 3. iterace)

Systém iterovaných funkc´ı IFS19 popisuje tvorbu syntetických fraktál˚u pomoc´ı základn´ıho objektu a nˇekolika transformac´ı, jimiˇz je tento objekt ve vzr˚ustaj´ıc´ıch iterac´ıch dlázˇ dˇen. Princip je odvozen z Banachovy vˇety o pevném bodu a vyuˇz´ıvá Hutchinson˚uv operátor. Pro u´ cˇ ely tohoto cˇ lánku je zásadn´ı, zˇ e objekt je zcela popsán námi vytvoˇrenými poli: FRC.base FRC.tran FRC.iter FRC.type

Obr. 17. Princip GSO optimalizace, na základˇe [12]

Motivac´ı bylo mj. zjiˇstˇen´ı, zˇ e v pˇr´ıpadˇe mimoˇra´ dnˇe sloˇzitých funkc´ı (10, 20 i v´ıce rozmˇer˚u s.s.) klesá u´ cˇ innost PSO i GA k nule. Jejich spojen´ı do GSO vˇsak poskytuje potˇrebnou flexibilitu a rapidnˇe zvyˇsuje u´ spˇesˇnost nalezen´ı globáln´ıho minima. V kaˇzdé iteraci jsou agenti novˇe vyb´ıráni a upraveni pomoc´ı PSO nebo GA, cˇ´ımˇz kombinujeme dva odliˇsné evoluˇcn´ı pˇr´ıstupy. GSO je vhodné m´ıt do budoucna na pamˇeti, nebot’ s poˇzadavkem optimalizaci komplexnˇejˇs´ıch funkc´ı jsme nuceni na jedné stranˇe zvˇetˇsovat rozlohu s.s., na druhé stranˇe se vzr˚ustaj´ıc´ım poˇctem podm´ınek 17 Rovnice

(14) je sˇiroce vyuˇz´ıvána i v oblasti umˇelých neuronových s´ıt´ı.

= = = =

[] [] [ od do celkem] ’pntstrns’

V promˇenné typu FRC jsou jednoznaˇcnˇe uloˇzeny body základn´ıho u´ tvaru FRC.base20 , transformace ve tvaru [a b c d e f ] a iterace v poli FRC.iter. Na u´ rovni IFS návrhu bychom se bez takového formátu jeˇstˇe obeˇsli, potˇrebujeme ho vˇsak v pˇr´ıpadˇe analýzy pomoc´ı dutinového modelu a PSO optimalizace. Podrobnˇeji se fraktál˚um vˇenuje [1], [2] a [13]. Máme-li vykreslenou strukturu, je potˇreba ji dále zpracovat a ohodnotit fitness funkc´ı. Tou je v naˇsem pˇr´ıpadˇe procedura na výpoˇcet rezonanˇcn´ı frekvence. Protoˇze pˇresný výpoˇcet je cˇ asovˇe nároˇcný, vyuˇzijeme aproximativn´ı duti18 Ploˇsn´ a rezonanˇcn´ı struktura se zemn´ı rovinou, v naˇsem pˇr´ıpadˇe bez pˇripojeného napájen´ı. Jde o sˇiroce vyuˇz´ıvaný typ antén. V´ıce v [14]. 19 Iterated function system 20 Jde o matici n × 2, kde n odpov´ıd´ a poˇctu bod˚u základn´ıho u´ tvaru (nejménˇe vˇsak 3).


10

D´ıky PSOptimizeru z´ıskáváme velký objem dat vhodných k pozdˇejˇs´ı analýze. Pod´ıváme-li se na napˇr´ıklad na pokles rezonance dominantn´ıho módu se vzr˚ustaj´ıc´ı iterac´ı (k poklesu docház´ı vˇzdy) pˇred a po optimalizaci, odhal´ıme, zˇ e tento trend je v obou pˇr´ıpadech stejný (obr. 22). Spolu s t´ım vyvstáváj´ı otázky po koneˇcné konvergenci frekvence (v nekoneˇcné iteraci) a dalˇs´ı.

Obr. 19. Význam transformaˇcn´ıch koeficient˚u

nový model (Cavity Model), implementovaný v Comsol Multiphysics (pˇristupujeme z Matlabu). Celý program slouˇz´ı jako fitness funkce pro PSOptimizer.

Obr. 22. Pokles rezonanˇcn´ı frekvence s iterac´ı

Obr. 20. Záriˇc FRC-H pˇred a po optimalizaci, vˇc. pozice agent˚u

Pˇred vlastn´ı optimalizac´ı je kl´ıcˇ ový správný výbˇer parametr˚u a odpov´ıdaj´ıch mez´ı, které nesmˇej´ı pˇrekroˇcit. Pro 25 agent˚u, 150 iterac´ı PSO algoritmu, a 3. iteraci fraktálu trvá optimalizace zpravidla kolem 2-3 hodin na výkonˇejˇs´ım stroji (Core2Quad 9450, 12MB L2, 4GB DDR3). Výsledky m˚uzˇ eme vidˇet na obrázku 20, ukázku nˇekolika agent˚u jiné optimalizace ukazuje následuj´ıc´ı obrázek 21.

Ukázali jsme, jak lze optimalizovat relativnˇe komplikované struktury. Detailn´ı ˇreˇsen´ı vˇsech cˇ a´ st´ı je popsáno v [2] a dalece pˇresahuje vymezený rozsah tohoto cˇ lánku. V budoucnu bude moˇzné optimalizovat antény nejen s ohledem na rezonanˇcn´ı frekvenci, ale budeme moci uvázˇ it i smˇer vyzaˇrován´ı, popˇr´ıpadˇe dalˇs´ı kl´ıcˇ ové parametry.

9. Závˇer V pˇr´ıspˇevku byla rozvedena implementace PSO algoritmu do Matlabu. Optimalizace byla popsána formálnˇe i na konkrétn´ıch pˇr´ıkladech. Ukázali jsme, jakým zp˚usobem ovlivˇnuj´ı jednotlivé parametry pr˚ubˇeh optimalizace a jaké m˚uzˇ eme oˇcekávat výsledky. Prostor byl vˇenován i popisu vstupn´ıch a výstupn´ıch pol´ı, jejichˇz charakter – spolu s pˇreindexován´ım hodnot uvnitˇr funkce – umoˇznˇ uje vyuˇz´ıvat PSOptimizer pro ˇreˇsen´ı celé ˇrady problém˚u. Dále jsme se krátce vˇenovali moˇznosti modelovat pr˚ubˇeh PSO, cˇ´ımˇz by se výraznˇe zkrátila doba potˇrebná ke konvergenci do globáln´ıho minima. Pˇresný postup nen´ı v souˇcasné dobˇe dostateˇcnˇe publikován v referenˇcn´ı literatuˇre a experimentáln´ıch dat nen´ı zat´ım dostatek pro formulaci vlastn´ıch závˇer˚u. Pro hlubˇs´ı srovnán´ı je nutné implementovat dalˇs´ı, odliˇsnou metodu optimalizace (zvaˇzována je metoda SOMA, simulované zˇ´ıhán´ı, pˇr´ıp. výsˇe uvedený GSO algoritmus). Teprvé poté m˚uzˇ eme porovnávat skuteˇcnou efektivitu PSO. Na závˇer jsme zm´ınili praktické vyuˇzit´ı celé metody v oblasti optimalizace fraktáln´ıch patch antén a nast´ınili dalˇs´ı moˇzný vývoj. Tento cˇ lánek mˇel za c´ıl pouze revidovat partikulárn´ı u´ spˇechy na poli rojové optimalizace.

Obr. 21. Ukázka nˇekolika agent˚u bˇehem optimalizace FRC-C


11

Podˇekován´ı Rád bych na tomto m´ıstˇe podˇekoval RNDr. Nˇemeˇckovi za zaslán´ı pozvánky do soutˇezˇ e, a také Ing. Hazdrovi, Ph.D., jenˇz se na celé, výsˇe prezentované práci pod´ılel. Sv˚uj vdˇek bych rád vyjádˇril i Prof. Ing. Mazánkovi, CSc. za vytvoˇren´ı skvˇelých pracovn´ıch podm´ınek. Tento cˇ lánek vznikl s podporou grantu DG 102/08/H018 – Modelován´ı a simulace elektromagnetického pole.

Reference ˇ [1] CAPEK, M. Modáln´ı analýza mikropáskových patch antén. Praha: ˇ CVUT-FEL, 2007, bakaláˇrská práce. ˇ [2] CAPEK, M. Nástroj pro modáln´ı analýzu fraktálových patch antén. ˇ Praha: CVUT-FEL, 2009, diplomová práce. ˇ [3] CAPEK, M., HAZDRA, P. PSO optimalizace v Matlabu. Technical Computing Prague, 2008. ˇ [4] CAPEK, M. PSO Optimalization of IFS Fractal Patch Antennas in Poster 2009, Praha. ˇ [5] HAZDRA, P., CAPEK, M. IFS Tool for Fractal Microstrip Patch Antenna Analysis in COMITE, Praha, 2008. ˇ ˇ [6] HAZDRA, P., CAPEK, M., KRACEK, J. Optimization Tool for Fractal Patches Based on the IFS Algorithm. EuCAP, Berl´ın, 2009. [7] KENNEDY, J., EBERHART, R. Particle Swarm Optimization. IEEE, 1995. [8] PASOPOULOS, K., E., PLAGIANAKOS, V., P., MAGOULAS, G., D., VRAHATIS, M., N. Stretching Technique for Obtaining Global Minimizers Through Particle Swarm Optimization. [Online]. Available: http://www.mat.univie.ac.at/neum/glopt/mss/ParPM01.pdf [9] ROBINSON, J., RAHMAT-SAMII, Y. Particle Swarm Optimization in Electromagnetics. IEEE Trans-AP, vol. 52, no. 2, pgs. 397-407, 2004. ´ R., M., OLCAN, ´ [10] GOLUBOVIC, D., I. Antenna Optimization Using Particle Swarm Optimization Algorithm. Journal of Automatic Control, Vol. 16, pp.21–24, 2006. ˇ ˇ ´ Z., SEDA, [11] ZELINKA, I., OPLATKOVA, M., OSMERA, P., ˇ ˇ F. Evoluˇcn´ı výpoˇcetn´ı technika. Praha: BEN, 2009. VCELA R, [12] GANDELLI, A., GRIMACCIA, F., MUSSETTA, M., PIRINOLI, P., ZICH, R., E. Genetical Swarm Optimization: an Evolutionary Algorithm for Antenna Design. AUTOMATIKA 47 (2006) 3 − 4, str.105 − 112. ˘ ´ P. Interaktivn´ı editor afinn´ıch transformac´ı. Brno: [13] TISNOVSK Y, VUT, 1999. [14] JAMES, J., R., HALL, P., S. Handbook of Microstrip Antennas vol.1. London: Peter Peregrinus Ltd., 1989. [15] The MATLAB website. [Online]. Available: http://www.mathworks.com/ [16] The COMSOL website. [Online]. Available: http://www.comsol.com/

Autor. . . ˇ Miloslav CAPEK se narodil v ˇCeských Budˇejovic´ıch roku 1985. Po dokonˇcen´ı bakaláˇrské etapy r. 2007 na katedˇre elektromagnetického pole ˇ CVUT-FEL pokraˇcoval magistersskou etapou tamtézˇ . Studium zakonˇcil r. 2009 diplomovou prac´ı na téma Nástroj pro modáln´ı analýzu fraktáln´ıch patch antén. Nyn´ı studuje

postgraduáln´ı etapu, zamˇerˇuje se na optimalizace (zejm. PSO), fraktáln´ı geometrii, patchové antény a teorii elektromagnetického pole. Pro tato témata vyv´ıj´ı aplikace v Matlabu. C´ılem disertace je syntéza multipásmové patch antény.

Rojová optimalizace v Matlabu

Recommend Documents