Rojová optimalizace v Matlabu

Rojová optimalizace v Matlabu hledání „ideální“ (fraktální) antény

Miloslav Čapek K13117, B2-819

Obsah přednášky 

Fraktály – definice, příklady, typy fraktálů a jejich popis



editor IFS fraktálů v Matlabu: IFSMaker



IFS motiv jako patchová anténa



Numerické a heuristické (evoluční) metody



Particle swarm optimalizace – princip, chování hejna



PSO parametry, nástroj PSOptimizer, postprocessing



Zobecnění vstupu do optimalizátoru



Jednokriteriální vs. multikriteriální optimalizace



Testovací funkce (Levy, Corana, Rosenbrock a další)



Ukázky použití, výsledky

19.4.2010 14:48

I. II.



IFS kandidáti, kriteriální funkce (CM řešený pomocí FEM)



Nastavení optimalizačních mezí (IFSLimiter), start optimalizace



Výsledky, plánovaná rozšíření



Reference, diskuze

III.

Fraktály – pokus o definici … 

B.B.Mandelbrot (1) topologická dimenze ≠ fraktální dimenzi



(2) „Fraktál je objekt, jehož geometrická struktura se opakuje v něm samém; dělí se na soběpodobné a soběpříbuzné.“



fraktální charakter nemusí být vždy zcela zřejmý (dynamické atraktory atp.)



hodnocení tvaru (fraktální nebo euklidovský) závisí na přiblížení - viz delta řeky

19.4.2010 14:48

2/46

Matematická kolokvia 2010: Rojová optimalizace v Matlabu Miloslav Čapek, [email protected]

… a několik příkladů 

Příklady: 

Listy, kůra stromů, řečiště, větvení stromů



Chování ekonomiky (Elliottovy vlny), výskyt (a velikost povodní), rušení na telefonní lince (Cantorovo discontinuum)



Počasí (Lorenzův atraktor), kapání vody z kohoutku, fibrilace srdečních komor (zdvojnásobování periody)

19.4.2010 14:48

3/46


Topologická

 





Hausdorffova dimenze

Dt  {0 – bod, 1 – křivka, 2 – povrch, 3 – prostor R3, … } Dh je obecně kladné reálné číslo objekt

jedním z prvních, kdo intuitivně využil dimenze Dh byl Richardson s měřením obvodu Korsiky

Dh [-]

Pobřeží

~1.26

Povrch mozku člověka

~2.76

Povrch neerodovaných skal

~2.2 - 2.3

Sierpinského trojúhelník

1.585

Obvod 2D průmětu mraku *)

~1.33

výpočet na bázi sledování změn struktury podél délky a měřítka → Box-counting metoda

19.4.2010 14:48

4/46

x


Teorie míry → mřížková dimenze 

vnější (a vnitřní) míra μ: systém se σ-algebrou       Ai      Ai   i 1  i 1

      Ai      Ai   i 1  i 1 

ε-pokrytí: uvažujeme max. velikost množin, které pokrýváme diam  

= velikost obalu pro  objekty množiny 

Hausdorffova míra



Hausdorffova dimenze

19.4.2010 14:48

5/46


Metoda box-counting: výpočet Dh   

podstatou je zmenšování měřítka (až k nule) výsledkem je mřížková dimenze Db podle charakteru zdrojového objektu je potom buďto

změna měřítka

log N Dh  1 log

změna počtu elementů



1  

2 

1 14

hodnota Db resp. Dh koresponduje s „členitostí“ útvaru

19.4.2010 14:48

6/46

1 7


3 

1 28

Metoda box-counting: příklady Dh 

log N 1 log



1 

1 7

N1  16

2 

1 14

3 

N 2  52

1 28

N 3  164

Db _ sierp 

Dh _ orig 

log10 3  1.585 log10 2

log10 164  log10 16  1.679 log10 28  log10 7

nástroj boxcount: Db _ it 2  1.948  0.063  2

Db _ it 2  1.641  0.102

19.4.2010 14:48

7/46

Db _ it 3  1.596  0.123


Fraktály: základní rozdělení

příkazy + iterace > gramatika

o L – systémy o IFS fraktály o dynamické systémy

„deterministický chaos“, systém zpravidla popsán dif. rovnicemi > atraktory

o nepravidelné fraktály

při tvorbě využíváme náhodných čísel

deterministický s. stochastický s.

19.4.2010 14:48

8/46

Brownův pohyb  střední bod  spektrální syntéza 


body, transformace, iterace > dláždění stochastický f. deterministický f.

Lindenmayerovy (L-) systémy   

syntetické fraktály fixní gramatika (stanovená před výpočtem) úvodní řetězec: inicializátor G = (V,S,,P)

Př.2: Fibonaccioho čísla Znaky: A, B Konstanty: žádné Start: A Pravidla: (A  B), (B  AB) n=0 A

Př.1: Cantorovo mračno Znaky: A, B Konstanty: žádné Start: A Pravidla: (A  ABA), (B  BBB)

n=1 B n = 2 AB n = 3 BAB n = 4 ABBAB

n=0 A

n = 5 BABABBAB

n = 1 ABA

n = 6 ABBABBABABBAB

n = 2 ABABBBABA

> 1,1,2,3,5,8,13,21,34 …

19.4.2010 14:48

9/46


IFS fraktály

  

syntetický původ, deterministické x stochastické pomocí zvolených (afinních) transformací dlaždíme objekt X IFS → potenciální antény: TVAR? (~ jaké parametry → PSO) m

w( X )   wi ( X ), X  R n i 1

x ( w)  A W  B

 

mřížková dimenze  fraktální dimenze pozoruhodné vlastnosti (obvod vs. obsah vs. objem apod.)

19.4.2010 14:48

10/46


rotace

IFS fraktály

 x   a b  xold   e       w new    y y c d  old   f   new   změna měřítka



afinní transformace:       

1.iterace

19.4.2010 14:48

11/46

posun bodu o vzdálenost [px py] změna měřítka Ms horizontální změna měřítka Mx vertikální změna měřítka My horizontální zešikmení Sx vertikální zešikmení Sy rotace kolem počátku o úhel α

3.iterace


posun

Dynamické fraktály

 

 

počáteční podmínky + popis soustavou (diferenciálních) rovnic některé dynamické systémy nedivergují, ani se neustalují zpravidla fraktální dynamika, užil se termín „deterministický chaos“ atraktor dynamického systému: stav, do něhož systém směřuje krom jiných (bodový, periodický, chaotický) tzv. podivný atraktor

 

19.4.2010 14:48

12/46

bifurkační graf (zdvojování periody, růst populace) Lorenzův atraktor


Nepravidelné fraktály  

(pseudo)náhodná čísla - koeficienty, pozice atp. roli může hrát pravděpodobnost   



z principu stochastický přístup

19.4.2010 14:48

13/46

Brownův pohyb půlení vzdálenosti spektrální syntéza (Fourierovy obrazy, jejich inverze je fraktál)


Generátor fraktálů (IFSMaker) 

Intuitivní, velice rychlá generace    



základní objekt (body) trasformace počet iterací (omezeno) export, další operace

FRC struktura FRC.base FRC.tran FRC.iter FRC.type

19.4.2010 14:48

14/46


IFSMaker FRC.base = [1.0 0.5 -0.5 -1.0 -0.5 0.5

0 0.886 0.886 0 -0.886 -0.886];

FRC.tran = [0.5

0

0

0.5

0.5 0.5

0 0

0 0

0.5 0.5

-0.5 0.25 0.25

0 0.443 -0.443];

FRC.iter = [3 3 3]; FRC.type = ‚pntstrns‘;

19.4.2010 14:48

15/46


Vytvořené fraktály

19.4.2010 14:48

16/46


Hegel, Pascal

19.4.2010 14:48

17/46


Evoluční optimalizace  

Jak je možné, že hejna relativně primitivních jedinců vykazují nesmírně komplexní chování? GA, PSO, ACO, neuronové sítě hledané minimum

optimalizovaná funkce 

f (x min )  f (x) hledané minimum

n-dim. proměnné za podmínky:

19.4.2010 14:48

18/46

množina přípustných řešení (solution space v PSO)

pro x  D

f : D 


Particle swarm optimization (PSO)



r. 1995 (Kennedy, Eberhart) roje včel, hejna ryb a ptáků – silně kolektivní chování



celý koncept vychází z modelu chování, který navrhl Reynolds:



 

všichni členové hejna ~ agenti definované 3 operace:   

separace (agent hledá prázdné místo v s.s.) uspořádanost (agent se natáčí do směru, kterým se pohybují ostatní agenti) spojitost (agent hledá v okolním prostoru místo, které průměru pozici okolních sousedů)

J.Kennedy 19.4.2010 14:48

19/46


R.Eberhart

Koncept PSO 

Kennedy a Eberhart upravili předchozí model následovně:    



Avšak jak zajistit pohyb agentů do minima (neznámé) funkce?

19.4.2010 14:48

20/46

zavádějí tzv. roost všichni agenti jsou přitahování k/do roostu zavedena paměť agenta – pamatuje si, kde byl nejblíže roostu každý agent sdílí informaci o svém největším přiblížení k roostu s (původně všemi) ostatními agenty


Matematický popis rojení částic  

konvergence (lokální minima, kvalita řešení) dostatečná diverzita agentů váhovací faktor „poznávací“ koef. rand()(0,1)

aktuální poloha agenta

n vidn 1  wvidn  c1 r1n ( pidn   idn )  c 2 r2n ( p gd   idn )

rychlost minimum „sociální“ minimum agenta agenta koef. celého roje

   

19.4.2010 14:48

21/46

absorbční zeď odrazná zeď neviditelná zeď omezení rychlosti Matematická kolokvia 2010: Rojová optimalizace v Matlabu Miloslav Čapek, [email protected]

stará pozice

=1

 idn1   idn   t vidn1 nová pozice

nová rychlost

Parametry PSO 

počet agentů: doporučení počet agentů = dimenze x 10 + ...



počet iterací: závisí na složitosti funkce, v řádu stovek



pro hodnocení výsledků je nutné průměrovat více cyklů (typicky 25 nebo 50) hodnocení efektivity optimalizace je obecně složité (NFL, fit.f., kritéria: sucess rate vs. best minimum)





vhodné nastavení všech parametrů → optimalizace optimalizace (metaoptimalizace)



zásadní je způsob omezení agentů v s.s. (zdi) a topologie



váhovací koeficient w může být vytknut před závorku

19.4.2010 14:48

22/46


Topologie 

komunikace mezi jednotlivými agenty → lze ovlivnit rychlost, jakou jsou transportovány informace napříč hejnem

(1) plně propojená topologie (fully connected) (2) čtvercová topologie (squared topology) (3) kruhová topologie (ring topology) (4) hvězda (star topology) (5) strom (tree topology) (6) a další... (dynamic neighborhood, ...)

19.4.2010 14:48

23/46


Testovací funkce  

napovídají o efektivitě optimalizace (+ nastavení) velkou roli hraje dimenze problému a metodika měření

Rosenbrockovo sedlo

Rastrigrinova funkce

funkce Levy3 19.4.2010 14:48

24/46

funkce Levy5


Testovací funkce 4. de Jongova funkce Mastersova cosinová funkce

Ackleyho II. funkce

stretched sin wave

Schwefelova funkce

Griewangkova funkce 19.4.2010 14:48

25/46

Ranova funkce


Aplikace PSOptimizer    

využívá rojení částic (PSO) s neviditelnou ohraničující zdí plně náhodná generace vektorů r1 a r2 plně propojená topologie agentů, nastavitelné c1 a c2 váhovací faktor w klesá lineárně z 0.9 do 0.4

Př.: funkce Levy5 Rozsah s.s.: <-10 x 10>(x,y) Dimenze: 2 (x,y) Iterací: 50 (na obr. 150) Agentů: 20 (na obr. 30) Glob.min.: -176.1376 <x,y>: <-1.307,-1.425>

+ MOPSO  Matlab toolbox? PsoData_Levy5. data1 = [2 2] data2 = [] data3 = [] rank = 2 type = ‘psopt‘ cond = {[1 1 1] [1 1 2]} bound = {[-10 10] [-10 10]}

5

5

i 1

j 1

fl 5 ( x, y )   (i cos((i  1) x  i )) ( j cos(( j  1) y  j ))  ( x  1.42513) 2  ( y  0.80032)2

19.4.2010 14:48

26/46


Universalita PSOptimizeru  

universální vstup (m-file jako f.f.) neomezený počet dimenzí PsoData.data1 .data2 .data3 .cond .bound . … PSOptimizer

results. …

~ FRC.base = [x1 y1;x2 y2;…]; ~ FRC.tran = [a1 b1 c1 d1 e1 f1; …]; ~ FRC.iter = [total from to]; ~ {[1 1 2],[2 1 3;2 1 6]} ~ {[10 15],[0.2 0.8]}

fitness funkce

function fVal = mFileExmp(sg,in) % sg = ‚eval‘; in.data1, in.data2, in.data3 % … zdrojový kód % … % fVal ~ hodnota fitness funkce

ResTb = PSOptimizer(PsoData, ‘mFileExmp‘, 25, 175) PSO input data

19.4.2010 14:48

27/46


fitness function

agents iteration

PSOptimizer: pseudokód

19.4.2010 14:48

28/46


Postprocessing   

nástroj PSOPost pohyb hejna je názorný omezení jen na dim = 2

19.4.2010 14:48

29/46


Vliv parametrů, výsledky

Levy5

kvadrat.fce.

19.4.2010 14:48

30/46


Vliv parametrů, výsledky

Levy5

19.4.2010 14:48

31/46

Rosenbrock


Rozšíření PSO



SPSO: stretched PSO GSO: kombinace genetického algoritmu (GA) a rojení částic (PSO)



MOPSO: Multiobjective PSO



  

decision & objective space úkolem je nalezení Paretovo hranice (obecně hyperplochy) nutný vyšší level abstrakce

M.Lepš: Moderní metody optimalizace, FsV 19.4.2010 14:48

32/46


MOPSO

M.Lepš: Moderní metody optimalizace, FsV 19.4.2010 14:48

33/46


Optimalizace IFS patch antén



Motivace: optimalizace antény vzhledem k fr (pracovní frekvenci), vyzařovacímu diagramu atd. výhodné vlastnosti fraktálních antén – modální řešení IFS skvělé na optimalizace (zejm. se „spřažením“)



nutná spolupráce všech bloků, ošetření všech vyjímek



Postup:





(1) generace antény podle výsledků it-1 (2) úprava geometrie, fyziky, ošetření vyjímek (3) CM solver (Comsol, FEM) (4) úprava výsledků, jejich návrat do optimalizátoru 19.4.2010 14:48

34/46


Cavity model

 

= dutinový model anténu považujeme za 2D rezonátor → aproximace E  z  0, H  z  0 ; for z  0, z  h, H  n  0, E  n  0 ; boundary of antenna.

( t  k ) E z ,n  0 2 n

 

kde

numerický výpočet vlastních čísel rezonanční frekvence potom: fn 

19.4.2010 14:48

35/46

2 2 t  2  2 x y

c0 2  r

 n , k n2   2  0  .


Optimalizace IFS patch antén  

IFSLimiter – zadávání podmínek (+check, sweep) EvalInFem (obecný problém)

19.4.2010 14:48

36/46


Optimalizace obdélníku a FRC_A

19.4.2010 14:48

37/46


Optimalizace FRC_B a FRC_C

19.4.2010 14:48

38/46


Výsledky



zatím nutná kontrola komerčním softwarem pracujeme na teorii charakteristických modů



pracujeme na multikriteriální optimalizaci (MOPSO)



19.4.2010 14:48

39/46


1. problém: určení vnější normály Můžeme integrovat plošný proud nebo proud na hranách.  Výpočet na hranách je výrazně rychlejší: vnější normála +z / -z hledáme 

  L   z  nV (c)...dc

Problém zejm. s „děravými“ objekty – obtížné určení směru vnější normály.

19.4.2010 14:48

40/46

hodnota pole na hraně


2. problém: operace nad polygony 

Existuje algoritmus, který umožňuje vyřadit duplicitní body?



Balík na práci s polygony (Booleovské operace, …)

19.4.2010 14:48

41/46


3. problém: vyzařování fraktálních obj. 





Fraktální charakter zásadním způsobem mění způsob disipace energie. Lze tvrdit, že fraktálové antény mají – z hlediska vyzařování – optimální TVAR? (Sapoval stanovil hypotézu, že pobřeží má fraktální charakter z důvodu ideálního tlumení dopadající vlny). Matematicky i fyzikálně velice komplexní problém (viz Sapoval, Berry a další)

19.4.2010 14:48

42/46


IFS+PSO+CM v Matlabu (1)

Matematická kolokvia 2010: Rojová optimalizace v Matlabu

43/46

Miloslav Čapek, [email protected]

IFS+PSO+CM v Matlabu (2)

Matematická kolokvia 2010: Rojová optimalizace v Matlabu

44/46

Miloslav Čapek, [email protected]

Reference 

Tým: Ing. Miloslav Čapek (student Ph.D. etapy – 1.rok)  Ing. Pavel Hazdra, Ph.D (školitel specialista)  Ing. Pavel Hamouz (student Ph.D etapy – 3.rok)  Prof. Ing. Miloš Mazánek, CSc. (školitel) - všichni z katedry elektromagnetického pole (K13117) 



Podpora: 

  

19.4.2010 14:48

45/46

prezentovaná témata budou částí dizertační práce, součást většího celku (Širokopásmové a multipásmové antény) doktorský grant (DG 13117/13/08005) SGS grant (SGS 10-801700-13117) aplikace využívá diplomant (katedra elmag. pole)


Literatura 

Publikační činnost:      



Hazdra, P., Čapek, M.: IFS Tool for Fractal Microstrip Patch Antenna Analysis, COMITE, 2008 Hazdra, P., Čapek, M., Kraček, J.: Optimization Tool for Fractal Patches Based on the IFS Algorithm, EuCAP 2009

Další:  

   



19.4.2010 14:48

46/46

Čapek, M., Hazdra, P.: PSO optimalizace v Matlabu, TCP 2008 Čapek, M.: PSO optimalization of IFS fractal patch antennas, Poster 2009 Čapek, M.: Rojová optimalizace v Matlabu, Rektorysova soutěž 2009 Čapek, M.: Design of IGS Patch Antennas Using Particle Swarm Optimization, EuCAP 2010

Benoit B. Mandelbrot: The Fractal Geometry of Nature. W.H.Freeman,1982 James Kennedy, Russell Eberhart: Particle Swarm Optimization. In Proceedings of IEEE International Conference on Neural Networks,pages 1942–1948, USA, 1995. IEEE Press. Constantine A.Balanis: Antenna Theory: Analysis and Design. 2nd ed., USA, 1997. John Wiley J. R. James, P. S. Hall: Handbook of Microstrip Antennas vol.1. London, 1989. Peter Peregrinus M. V. Berry: Distribution of Modes in Fractal Resonators. University of Bristol, Bristol. 1986 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 K. E.Parsopoulos, M. N.Vrahatis: Recent approaches to global optimization problems through Particle Swarm Optimization. Natural Computing, pp.235-306, 2002 Matematická kolokvia 2010: Rojová optimalizace v Matlabu Miloslav Čapek, [email protected]

Děkuji za pozornost [email protected]

Rojová optimalizace v Matlabu

Recommend Documents