Obr´ azek 1: Tˇr´ıdy Consumer, Producer a Solver
0.1
Knihovna JCool
JCool je open-source knihovna pro jazyk Java pro optimalizaci spojit´ ych funkc´ı. Implemetuje jak numerick´e (Gradient, Sdruˇzen´ y gradient, Quasi-Newton,...) a pˇr´ırodou inspirovan´e (Evoluˇcn´ı, PSO, ACO) algoritmy. Souˇc´ast´ı knihovny je sada testovac´ıch funkc´ı.
0.2
Z´ akladn´ı rozhran´ı knihovny JCool
Pˇred´ av´ an´ı v´ ysledk˚ u a pr´ ace s v´ ysledky oˇstˇruj´ı rozhran´ı Consumer a Producer. Producer m´ a na starosti vytv´aˇren´ı v´ ysledk˚ u, zat´ımco Consumer informace pˇr´ıj´ım´a. Vol´ an´ı a pˇred´ av´ an´ı v´ ysledk˚ u do tˇr´ıdy konzumenta m´a na starosti odpov´ıdaj´ıc´ı potomek tˇr´ıdy OptimizationMethod . Tˇr´ıdy Consumer a Producer m˚ uˇze obsluhovat jeden z potomk˚ u rozhran´ı Solver. Solver pracuje s producentem i konzumenetem a star´a se o ˇr´adn´e vol´ an´ı producenta a pˇred´ av´an´ı v´ ysledk˚ u konzumentovi. K dispozici jsou tˇri tˇr´ıdy BasicSolver,TimeoutSolvera StepSolver. V´ ysledky lze ze tˇr´ıdy Solver z´ıskat pˇres metodu getResults, kter´a vrac´ı instanci OptimizationMethod. Potomci tˇr´ıdy Solver v´ ysledky z v´ ypoˇctu algoritmu pˇred´avaj´ı jako instanci tˇrd´ıy Synchronization. Tˇr´ıda OptimizationMethod zapouzdˇruje informace o zastavovac´ıch podm´ınk´ach, poˇcet iterac´ı algoritmu, v´ ysledn´e ˇreˇsen´ı (potomek tˇr´ıdy Telemetry) a statistick´e informace tˇr´ıdy Statistics.
0.3
Implementace algoritm˚ u v knihovnˇ e JCool
Pˇredek generick´e tˇr´ıdy OptimizationMethod , generick´a tˇr´ıda Producer slouˇz´ı k pˇred´ av´ an´ı dosavadn´ıch v´ ysledk˚ u dan´eho algoritmu. Vˇsechny instance t´eto tˇr´ıdy jsou producenty. Tˇr´ıda m´ a dvˇe abstraktn´ı metody a to: 1
Obr´ azek 2: Hierarchie tˇr´ıd pro telemetrie void addConsumer(Consumer consumer); T getValue(); prvn´ı metoda pˇrid´ av´ a nov´e instance pˇr´ıjemc˚ u informac´ı o stavu algoritm˚ u, tedy instanc´ı abstraktn´ı tˇr´ıdy Consumer. Pro tyto u ´ˇcely vˇsichni potomci mus´ı implementovat metody, addConsumer , kter´ y slouˇz´ı k nastaven´ı objektu konzumenta, kam se budou odes´ılat v´ ysledky dan´eho algoritmu. K z´ısk´av´an´ı v´ ysledk˚ u je getValue, kter´ a vrac´ı v´ ysledky. V´ ysledky mohou b´ yt instance potomk˚ u abstraktn´ı generick´e tˇr´ıdy Telemetry, tedy • ValueTelemetry - uchov´av´a st´avaj´ıc´ı hodnotu value fitness funkce f . • ValuePointTelemetry - uchov´av´a st´avaj´ıc´ı hodnotu value fitness funkce f a pozici x hodnoty value = f (x). • ValuePointTelemetryList - uchov´av´a st´avaj´ıc´ı hodnoty valuei fitness funkce f a jejich odpov´ıdaj´ıc´ı pozice xi hodnoty valuei = f (xi ). • ValuePointTelemetryList - uchov´av´a st´avaj´ıc´ı hodnoty valuei fitness funkce f a jejich odpov´ıdaj´ıc´ı pozice xi hodnoty valuei = f (xi ) a barvu colori (hodnocen´ı, zda je odpov´ıdaj´ıc´ı bod i nejlepˇs´ı z cel´eho seznamu). na obr´ azku ?? je UML diagram tˇr´ıdy Telemetry a jeho potomk˚ u. D´ ale m´ a knihovna JCool rozhlan´ı OptimizationMethod , od n´ıˇz jsou odvozen´e vˇsechny tˇr´ıdy implementuj´ıc´ı algoritmy pro optimalizaci. Rozhran´ı m´a tˇri metody, kter´e mus´ı potomek implementovat void init(ObjectiveFunction function); StopCondition[] getStopConditions(); void optimize(); 2
prvn´ı metoda init slouˇz´ı k inicializaci dan´e optimalizaˇcn´ı metody v potomkovi a pˇred´ an´ı dan´e fitness funkce f , kter´a je potomkem tˇr´ıdy ObjectiveFunction. Druh´ a metoda getStopConditions vrac´ı pole instanc´ı StopConditions, coˇz je seznam zastavovac´ıch podm´ınek dan´e metody. Tˇr´ıda, kter´a pracuje s optimalizaˇcn´ımi algoritmy m´ a potom na starosti obsluhu zastaven´ı algoritmu, tedy vol´ a cyklicky vˇsechny zastavovac´ı podm´ınky, kter´e vr´at´ı v poli a metoda isConditionMet tˇr´ıdy StopCondition a vr´at´ı v z´avislosti na stavu, zda se m´a algoritmus zastavit, ˇci ne. A posledn´ı abstraktn´ı metoda optimizezapouzdˇruje slouˇz´ı sv´ ym potomk˚ um k implementaci jednoho kroku optimalizaˇcn´ıho algoritmu. Jedno vol´ an´ı metody optimize odpov´ıd´a jedn´e iteraci dan´eho algoritmu. To jak by mˇel mˇela vypadat obsluha obecn´eho optimalizaˇcn´ıho algoritmu v knihovnˇe JCool pomoc´ı abstraktn´ıho pˇredka OptimizationMethodje podrobnˇeji pops´ ano v n´ıˇze uveden´em algoritmu. input : Instance optimalizaˇcn´ı metody method while true do method.optimize() 3 stopConditions = method.getStopConditions() 4 foreach stopCondition in stopConditions do 5 if stopCondition. isConditionMet() is true then 6 Break; 7 end 8 end 9 end Algorithm 1: Obsluha optiamlizaˇcn´ıch metod pomoc´ı abstraktn´ı tˇr´ıdy OptimizationMethod 1
2
Algoritmy vyhodnocuj´ı svou kvalitu na z´akladˇe fitness funkce f , kter´a je reprezentov´ ana v knihovnˇe rozhran´ım Function. Pokud m´a fitness funkce urˇcen´ y gradient, druhou derivaci (Hessi´an), nebo je nˇejak omezen´a, je moˇzn´e odvodit implementaci funkce kvality od tˇr´ıd FunctionGradient, FunctionHessian, nebo FunctionBounds. Vˇsechna tato rozhran´ı v sobˇe sjednocuje rozhran´ı ObjectiveFunction, kter´ a je i pˇred´ av´ ana jako parametr pˇri vol´an´ı funkce init odvozen´ ych tˇr´ıd od OptimizationMethod. Ne vˇsechny fitness funkce maj´ı zn´am´ y gradient, Hessi´an, nebo omezen´ı, pro tento u ´ˇcel exituje tˇr´ıda BaseObjectiveFunction,kter´a v sobˇe zastˇreˇsuje obecnou funkci a z´ aroveˇ n je potomkem ObjectiveFunction. Pokud m´a funkce gradient, Hessi´ an, nebo omezen´ı vyvol´a odpov´ıdaj´ıc´ı metodu pˇredka, jinak vyvol´a vyj´ımku. Instance tˇr´ıdy BaseObjectiveFunction slouˇz´ı k pˇred´av´an´ı instance fitness funkce v metodˇe init.
3
1
Implementace
Na zaˇc´ atku jsem pˇredpokl´ adal, ˇze budu implementovat pouze z´akladn´ı algoritmus CMA-ES, takˇze z´ akladn´ı myˇslenka byla koncipov´ana tak, ˇze neubudu dˇedit ˇz´ adnou dalˇs´ı tˇr´ıdu z hlavn´ı tˇr´ıdy CMAESMethod. Ale jeˇstˇe pˇred t´ım, neˇz jsem zaˇcal implementovat jsem se rozhod, ˇze doimplementuji i dalˇs´ı variantu IPOP-CMAES, takˇze cel´ a koncepce se rozˇs´ıˇrila o dalˇs´ı tˇr´ıdu, kter´a se m´ırnˇe odchylovala od v´ ypoˇctu klascik´eho algoritmu CMA-ES. N´avrh jsem tedy rozˇs´ıˇril o dalˇs´ı ˇctyˇri tˇr´ıdy, kter´e maj´ı hierarchii, kter´a je zn´azornˇena na obr´azku ??. V metodˇe je znaˇcn´e mnoˇzstv´ı maticov´ ych operac´ı i z pokroˇcilejˇs´ı algebry, proto jsem pro maticov´e operace pouˇzil knihovnu java-commons-math verze 2.1, kter´ a plnˇe vyhovovala k algebraick´ ym v´ ypoˇct˚ um a z´aroveˇ n je u t´eto knihovny zaruˇceno, ˇze se jedn´ a o velmi stabiln´ı, dlouhodobˇe testovanou a efektivn´ı knihovnu. Z knihovny jsem vyuˇzil velk´e mnoˇzstv´ı funkc´ı pro operace nad maticemi a vektory, rozklad na vlastn´ı ˇc´ısla a vlastn´ı vektory a implementaci gener´ atoru vektor˚ u s norm´ aln´ım rozdˇelen´ım podle kovarinˇcn´ı matice. Vˇsechny instance RealMatrix, RealVector jsou tˇr´ıdy knihovny java-commons-math. D´ıky pouˇzit´ı maticov´e knihonvy jsem dos´ahl efektivn´ı a pˇredevˇs´ım pˇrehledn´e implementace, nebot’ pˇredpokl´ad´am, ˇze ve v´ yvoji se jeˇstˇe bude pokraˇcovat i po obhajobˇe.
1.1
Z´ akladn´ı tˇ r´ıda CMAESMethod
Tˇr´ıda CMAESMethod je koncipov´ana jako abstraktn´ı pˇredek vˇsech mnou implenetovan´ ych variant a tˇr´ıd algoritmu CMAES. Tˇr´ıda je abstraktn´ı, takˇze implementace ˇcist´eho algoritmu CMA-ES je pˇrench´ana tˇr´ıdˇe PureCMAESMethod.
4
1.1.1
Obecnˇ e k implementaci tˇ r´ıdy CMAESMethod
CMAESMethod implementuje nˇekter´e z´akladn´ı v´ ypoˇcty, kter´e jsou obecn´e pro vˇsechny metody jako je v´ ypoˇcet hodnot pc , pσ , σ a C, tyto z´akladn´ı v´ ypoˇcty jsou rozdˇeleny do separ´ atn´ıch metod, tak aby se kaˇzd´a ˇclensk´a metoda mohla jmenovat podle toho jakou promˇennou poˇc´ıt´a a pˇr´ıpadnˇe bylo moˇzn´e od n´ı odvodit patˇriˇcnou tˇr´ıdu, kter´ a m˚ uˇze v´ ypoˇcet prov´adˇet jinak. D´ale pak tˇr´ıda implementuje z´ akladn´ı podm´ınky pro zastaven´ı, jako konvergence k ˇreˇsen´ı. Zb´ yvaj´ıc´ı zastavovac´ı podm´ınky jsem pˇrenechal na jejich potomc´ıch, protoˇze potomci RestartCMAESMethod vyuˇz´ıvaj´ı tyto zastavovac´ı podm´ınky jako podm´ınky pro restart algoritmu. Cel´ y algoritmus potom prov´ad´ı metoda optimize, kter´a sjednocuje z´ akladn´ı v´ ypoˇcty hodnot jedn´e metody. Pˇredch˚ udce, generick´ a tˇr´ıda OptimizationMethod , a jako generick´ y parametr pˇredka jsem dal typ ValuePointListTelemetry, protoˇze m´am populaci v´ıce jedinc˚ u (ValuePointListTelemetry obsahuje seznam ValuePoint instanc´ı) K implementaci jsem pouˇzil jako pˇredlohu ˇcl´anek [?] a pˇredevˇs´ım pˇredlohovou variantu algoritmu v jazyce Matlab. K porovn´an´ı jsem pouˇzil referenˇcn´ı k´od v jazyce Matlab ze zdroje [?]. Pokud jsem potˇreboval podrobnˇejˇs´ı a pˇredevˇs´ım aktu´ alnˇejˇs´ı informaci, pouˇzil jsem plnou implementaci [?]. V´ yslednou implementaci jsem ovˇeˇroval porovn´av´an´ım hodnot v jednotliv´ ych kroc´ıch pˇri generov´ an´ı stejn´ ych n´ahodn´ ych hodnot v˚ uˇci implementaci [?] jej´ıˇz k´ od je zjednoduˇsen a nem´ a vˇetˇsinu zastavovac´ıch podm´ınek, kromˇe ConditionCov. Seznam vˇsech atribut˚ u tˇr´ıdy CMAESMethod s popisem a jeho ekvivaltentem v ana´ yze a popisu algoritmu je v tabulce ?? 1.1.2
Integrace tˇ r´ıdy CMAESMethod do knihovny JCool
Abstraktn´ı pˇredch˚ udci tˇr´ıdy CMAESMethod, tˇr´ıda OptimizationMethod a Producer maj´ı 5 abstraktn´ıch metod, kter´e implemetuji • addConsumer pouze nastavuje konzumenta“ v´ ysledk˚ u algoritmu. Tˇelo ” metody tedy nastavuje pouze ˇclensk´ y consumer atribut. • getValue, jenˇz vrac´ı typ ValuePointListTelemetry, kter´ y jsem definoval jako generick´ y parametr pˇredchodce OptimizationMethod . • init, v n´ıˇz vol´ am metodu initializeDefaultParameters, kter´a mi nastavuje vˇsechny hodnoty do inici´aln´ıho stavu, nastav´ım v parametru pˇredanou fitness funkci a nˇekter´e jej´ı parametry. • getStopConditions, vrac´ı pr´azdn´e pole instanc´ı StopCondition • optimize, je metoda kter´a implementuje v nˇekolika metod´ach z´akladn´ı kroky algoritmu CMA-ES tˇr´ıda m´ a jedinou abstraktn´ı metodu, setStopConditionParameters, v n´ıˇz by jej´ı potomci mˇeli nastavit parametry pro zastavovac´ı podm´ınky.
5
1.1.3
Inicializaˇ cn´ı krok ve tˇ r´ıde CMAESMethod
O inicializaci algortimu se star´a metoda init, kter´e ten kdo j´ı vol´a pˇred´a parametrem instanci tˇr´ıdy ObjectiveFunction. V inicializaˇcn´ı ˇc´asti metody se nastavuj´ı atributy dan´eho probl´emu, inicializace promˇenn´ ych algoritmu je implementovan´ a v metodˇe initializeDefaultParameters. D˚ uvodem proˇc m´ am rozdˇelenou inicializaˇcn´ı ˇc´ast algoritmu na dvˇe ˇc´asti je kv˚ uli implementac´ım zaloˇzen´ ych na restartech. Implementace CMA-ES zaloˇzen´e na restartech vyˇzaduj´ı inicializaci vˇetˇsiny atribut˚ u na poˇc´ateˇcn´ı hodnoty. Metoda init je zde pˇredevˇs´ım pro pˇred´an´ı informac´ı o ˇreˇsen´em probl´emu z jin´eho k´ odu. Takˇze metoda init sice vol´a initializeDefaultParameters,ale rovnˇeˇz j´ı volaj´ı potomci tˇr´ıdy RestartCMAESMethod. Stejn´ y d˚ uvod, jako je rozdˇelen´ı init na dvˇe metody m´a i rozdˇelen´ı promˇenn´e σ na dva atributy sigma a initialSigma. Pokud totiˇz obsluha algoritmu nastav´ı, ˇze chce nˇejakou poˇc´ ateˇcn´ı hodnotu atributu sigma, tak jej algoritmus v pr˚ ubˇehu v´ ypoˇctu modifikuje a p˚ uvodn´ı poˇc´ateˇcn´ı hodnotu a v pˇr´ıpadˇe strategi´ıch zloˇzen´ ych na restartech nem´ame nikde opˇc´ateˇcn´ı hodnotu. Metoda initnastavuje atribut fitness funkce function ,pˇr´ıpadnˇe nastavuje minim´ aln´ı, resp. maxim´ aln´ı meze dan´e funkce a nastavuje atribut nejlepˇs´ı hodnoty ve vˇsech generac´ıch theBestPoint na hodnotu pozici s nulov´ ymi souˇradnicemi (statick´ a metoda Point.getDefault()) a fitness na Double.MAX_VALUE a naopak theWorstPoint s nejlepˇs´ı fitness -Double.MAX_VALUE se stejn´ ymi souˇradnicemi jako theBestPoint aby v prvn´ı generaci nahradili hodnoty theBestPoint a theWorstPoint inicializovan´e hodnoty. Nyn´ı pop´ıˇsu m´ırnˇe zobecnˇenou metodu initializeDefaultParameters, ˇr´adek po ˇr´ adku. 1-5 Inicializuji vektor xmeann´ahodn´ ymi hodnotami s rovnomˇern´ ym rozdˇelen´ım v kruhu o pr˚ umˇeru rozd´ılu maxim´aln´ı a minim´aln´ı moˇzn´e hodnoty fitness funkce function. 6 Nastav´ım poˇc´ ateˇcn´ı hodnoty step-size parametru sigma, tedy σ (0) na pˇredem nastavenou poˇc´ ateˇcn´ı hodnotu initialSigma. 8 Nastav´ım velikost populace, promˇennou λ, tedy atribut lambda. 9 Nastav´ım velikost velikost selektovan´e populace, romˇennou µ, tedy atribut \verbmu. Atribut by mˇel b´ yt pˇribliˇznˇe polovina celkov´eho mnoˇzstv´ı populace. 11-19 Nastaven´ı vah selekce, podle vzorce z teorie. Nejdˇr´ıve nainicializuji hodnoty jako rostouc´ı posloupnost od 0 do µ, potom v´ahy zlograritmji dekadick´ ym logaritmem. 21 Vypoˇc´ıt´ am maximovou normu v´ahov´eho vektoru weight pro v´ ypoˇcet atributu muEff. 22 Vypoˇc´ıt´ am efektivn´ı hodnoty selekce µef f jako pomˇer druh´e mocniny normy k normˇe druh´e mocniny. 6
24 Vypoˇc´ıt´ am kumulaˇcn´ı konstantu cc , tedy atribut cCumulation. Poˇc´ıt´a se podle urˇcen´eho vzorce podle z [?]. 25 Vypoˇc´ıt´ am konstantu pro historii σ promˇennou cσ , tedy atribut cSigma. Poˇc´ıt´ a se podle urˇcen´eho vzorce z [?]. 26 Vypoˇc´ıt´ am konstantu pro rank-1-update c1 , tedy atribut cRank1. Poˇc´ıt´a se podle urˇcen´eho vzorce z [?]. 27 Vypoˇc´ıt´ am konstantu pro rank-µ-update cµ , tedy atribut cRankMu. Poˇc´ıt´a se podle urˇcen´eho vzorce z [?]. 28 Vypoˇc´ıt´ am tlum´ıc´ı konstantu σ promˇennou dσ , tedy atribut dampingForSigma. Poˇc´ıt´ a se podle urˇcen´eho vzorce z [?]. (0)
ypoˇcet rank-1-update na nulov´ y 30 Nastav´ım vektor kumulace cesty pc pro v´ vektor, tedy atribut pCumulation z [?]. (0)
31 Nastav´ım vektor normalizovan´e kumulace cesty pc σ na nulov´ y vektor, tedy atribut pSigma z [?].
pro v´ ypoˇcet step-size
33-34 Nastav´ım souˇradn´e syst´emy pro norm´aln´ı rozdˇelen´ı na kruˇznici, resp. B nastav´ım na matici identity, stejnˇe jako vektor D nastav´ım na jednotkov´ y, takˇze norm´ aln´ı rozdˇelen´ı bude m´ıt tvar kruˇznice, takˇze body stejnˇe vzd´ alen´e od stˇredn´ı hodnoty budou m´ıt stejnou pravdˇepodobnost. 35 Nastav´ım matici C(0) , tedy atribut C na matici identity. Hodnoty C poˇc´ıt´am podle rozkladu na vlastn´ı ˇc´ısla D a vlastn´ı vektory B, abych pˇredeˇsel probl´em˚ um s nejednoznaˇcnost´ı rozkladu, kdybych volil jin´e poˇc´ateˇcn´ı hodnoty D a B. 1
(0)
36 Nastav´ım matici C− 2 , tedy atribut inverseAndSqrtC na matici identity. Hodnoty invserseAndSqrtC poˇc´ıt´am podle rozkladu ze stejn´eho d˚ uvodu, jako poˇc´ıt´ am atribut C. 38 Vypoˇc´ıt´ am odhad L2 normy norm´aln´ıho rozdˇelen´ı N (0, I) podle [?]
1.1.4
Optimalizaˇ cn´ı krok ve tˇ r´ıde CMAESMethod
Nyn´ı pop´ıˇsu m´ırnˇe zobecnˇenou metodu optimize, ˇr´adek po ˇr´adku. Metoda je implementov´ ana tak, aby mˇela minimum lok´an´ıch promˇenn´ ych a vˇetˇsinu promˇenn´ ych ukl´ adala do sv´ ych atribut˚ u, aby je pˇr´ıpadnˇe mohla sd´ılet se sv´ ymi potomky. 1 Vytvoˇr´ım novou populaci pomoc´ı norm´aln´ıho rozdˇelen´ı z parametr˚ u vypoˇcten´ ych z p˚ uvodn´ı generace (pˇr´ıpadnˇe inicializaˇcn´ıch parametr˚ u). Metoda generatePopulation vrac´ı pole instanc´ı ValuePoint, tedy novou ohodnocenou mnoˇzinu jedinc˚ u.
7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27
28
this.xmean =RealVector (this.N); for n =0 to N-1 do this.xmean.setEntry (n, (Max- Min)*(Math.random () - 0.5)); n=n+1 end this.attributeSigma =initialSigma // inicializace parametr˚ u ES pro selekci, λ, µ this.attributeLambda = 4+Math.floor (3*Math.logarithm (this.N)); this.Mu = Math.floor (attributeLambda/2); // inicializace vah pro selekci w this.weights =RealVector (N); for n =0 to this.N-1 do this.weights.setEntry (n,n +1) n =n +1 end this.weights = this.weights.mapLog ().mapMultiply (-1).mapAdd (Math.logarithm (this.Mu +0.5)) Norm = this.weights.getNorm (); // normalizce vah this.weights.mapDivideToSelf (Norm); // souˇcen normalizovan´ ych vah pro v´ ypoˇcet µef f Norm = this.weights.getNorm (); this.muEff = Math.pow (Norm, 2) / this.weights.mapPow (2).getNorm (); // inicializace koeficient˚ u adapace cc , cσ , c1 , cµ , dσ this.cCumulation = (4 + this.muEff/ this.N) / (this.N + 4 + 2 * this.muEff/ 2); this.cSigma = (this.muEff + 2) / (this N + this.muEff + 5); this.cRank1 = 2 / (Math.pow (this.N + 1.3, 2) + this.muEff); this.cRankMu = 2 * (this.muEff- 2 + 1 / this.muEff) / (Math.pow (this.N + 2, 2) + this.muEff); this.dampingForSigma = 1 + 2 * Math.maximum (0, Math.sqrt ((this.muEff- 1) / (this.N + 1)) - 1) + this.cSigma; (
(0)
1
(0)
// dynamick´e parametry strategie pc 0), pσ , B( 0), D(0) , C(0) a C− 2 30 this.pCumulation =RealVector (this.N); 31 this.pSigma =RealVector (this.N); 32 // definuje souˇ radn´ y syst´em 33 this.B = MatrixUtils.createRealIdentityMatrix (this.N); 34 this.D = RealVector (this.N, 1); 35 this.C = B.mapMultiply (MatrixUtils.createRealDiagonalMatrix (this.D.mapPow (2).toArray ())).mapMultiply (this.B.transpose ()); 36 this.inverseAndSqrtC = this.B.mapMultiply (MatrixUtils.createRealDiagonalMatrix (this.D.toArray ())).mapMultiply (this.B.transpose ()); 37 // odhad normy kN (0, I) k pro v´ ypoˇcet dσ this.chiN = Math.sqrt (N) * (1 - 1 / (4 * N)) + (1 / (21 * Math.pow (N, 2)))); Algorithm 2: Jeden krok metody initializeDefaultParametes tˇr´ıdy CMAESMethod 8 29
2 Uloˇz´ım si p˚ uvodn´ı stˇredn´ı hodnotu z p˚ uvodn´ı generace, nebot’ bude potˇreba pˇri v´ ypoˇctu nˇekter´ ych dalˇs´ıch parametr˚ u. 3 Setˇr´ıd´ım celou populaci. Protoˇze je tˇr´ıda ValuePoint potomkem rozhran´ı Comparable, setˇr´ıd´ı se mi populace vzestupnˇe. 4 Uloˇz´ım nejlepˇs´ıho a nejhorˇs´ıho jedince pro vˇsechny generace pokud takov´ y existuje v novˇe vytvoˇren´e generaci. 5 Pomoc´ı metody createMatrixFromPopulationvytvoˇr´ım instanci nejlepˇs´ıch vybran´ ych (µ) jedinc˚ u tˇr´ıdy RealMatrix z instanc´ı ValuePoint, tak, ˇze kaˇzd´ y sloupec pˇredstavuje jednoho jedince. Instance tˇr´ıdy RealMatrix m´a N ˇr´ adk˚ u 7 Kaˇzd´ y sloupec vyn´ asob´ım hodnotou na odpov´ıdaj´ıc´ım indexu vektoru vah weight. Touto operac´ı udˇel´am ze stˇredn´ı hodnoty vybran´e popualce v´aˇzenou, coˇz odpov´ ad´ a v´ ypoˇctu promˇenn´e m(g+1) (g+1)
8 V´ ypoˇcet hodnoty atributu pSigmapσ
pomoc´ı metody calculatePSigma.
9 V´ ypoˇcet hodnoty hσ pomoc´ı metody calculateHSigma. Hodnota hσ slouˇz´ı (g) (g) yv´a velk´ ych hodnot. Tato hodnota se k udrˇzen´ı pc , jestliˇze kpσ k nab´ (g+1) a C(g+1) , tedy v metod´ach calculatePCumulation vyuˇz´ıv´ a pˇri v´ ypoˇctu promˇenn´ ych pc a calculateCovariance, kde se pˇredaj´ı v parametrech. (g+1)
, tedy atributu pCumulationpomoc´ı metody 10 Vypoˇctu hodnoty promˇenn´e pc caculatePCumulation. Pˇred´ame starou stˇredn´ı hodnotu xold a hodnotu hSigma, kter´ a reguluje zda bude hodnota zmˇenˇena, nebo ne. Tento v´ ypoˇcet pozdˇe poslouˇz´ı v kovarianˇcn´ı matici k rank-1-update. 11-12 Vypoˇctu vzd´ alenost nejlepˇs´ıch mu jedinc˚ u z populace od stˇredn´ı hodnoty dˇelen´e hodntou sigma. V´ ysledek bude opˇet instance tˇr´ıdy RealMatrix, tak, ˇze kaˇzd´ y sloupec pˇredstavuje jednoho jedince. Kaˇzd´ y sloupec odpov´ıd´a T v´ ypoˇctu yi:λ . 15 Vypoˇctu novou hodnotu atributu C, tedy kovarianˇcn´ı matice C(g+1) pomoc´ı metody calculateCovariance. Vˇsechny promˇenn´e, kter´e jsou nutn´e k v´ ypoˇctu kromˇe hSigmaa muDifferenceFromOldMean(kter´e pˇredstavuj´ı ve v´ ypoˇctu rank-1-update) jsou atributy tˇr´ıdy CMAESMethod. 17 Vypoˇctu novou hodnotu sigma, tedy step-size parametr σ (g+1) . 18 Rozklad na vlastn´ı ˇc´ısla a vlastn´ı matice pomoc´ı metody calculateEigendecomposition, tedy ortonorm´ aln´ı matice B(g+1) a diagon´aln´ı matice vlastn´ıch ˇc´ısel D(g+1) . D´ ale pak metoda poˇc´ıt´ a hodnotu atributu inverseAndSqrtC,tedy promˇenn´e (g+1) − 21 C , kter´ a slouˇz´ı k transofrmaci pSigma,tedy pσ 19 Inkrementace ˇc´ıtaˇce poˇctu generac´ı
9
20 Uloˇzen´ı nejlepˇs´ıho jedince do atributu bestValueInCurrentGeneration,coˇz (g) je hodnota x1:λ 21 Nastaven´ı atributu telemetrypro pˇred´an´ı v´ ysledk˚ u. Protoˇze se jedn´a o instanci tˇr´ıdy ValuePointListTelemetry, pˇred´av´ame celou populaci. 22,23,24 Pˇred´ an´ı v´ ysledk˚ u dan´eho generace instanci consumer. Promˇenn´ a hSigmaje lok´ aln´ı, protoˇze neuchov´av´a svou historii, ani nen´ı pouˇziteln´ y v r´ amci jin´ ych implementac´ı, stejnˇe V´ ypoˇcet hodnoty hσ je 1 jestliˇze plat´ı rovnice ??, jinak je rovna 0. (
kpσ g)k
q < 2(g+1) 1 − (1 − cσ )
√
1 1 n 1− + 4N 21N 2
(1)
population = generatePopulation () xold = xmean 3 Arrays.sort (population) 4 storeTheBestAndWorst (population) 5 muBestIndividuals = createMatrixFromPopulation (population, this.Mu, this.N) 6 // v´ ypoˇcet nov´e v´ aˇzen´e stˇredn´ı hodnoty m(g+1) 7 this. xmean = muBestIndividuals.operate (weights) 8 calculatePSigma (xold) 9 hSigma = calculateHSigma () 10 calculatePCumulation (hSigma,xold) 11 // v´ ypoˇcet y pro rank-µ-update 12 muDifferenceVectorsFromOldMean = 13 calculateMuDifferenceFromOldMean (muBestIndividuals,this.xold, this.N, this.Mu, this.stepSize) 14 // v´ ypoˇcet nov´e kovarianˇcn´ı matice C(g+1) 15 calculateCovariance (hSigma,muDifferenceVectorsFromOldMean) ypoˇcet nov´e hodnoty σ (g+1) 16 // v´ 17 calculateSigma () 18 calculateEigendecomposition () 19 this.currentGeneration =this.currentGeneration +1 20 bestValueInCurrentGeneration = population [0].getValue (); 21 telemetry = Arrays.asList (population); 22 if consumer!= null then 23 consumer.notifyOf (this) 24 end Algorithm 3: Jeden krok v k´odu metody optimize tˇr´ıdy CMAESMethod 1 2
Metody, kter´e poˇc´ıtaj´ı promˇenn´e algoritmu: 10
• initializeDefaultParameters - nastavuje vˇsechny promˇenn´e, kter´e algoritmus poˇz´ıv´ a k v´ ypoˇct˚ um na poˇc´ateˇcn´ı hodnotu • generatePopulation - generuje novou populaci o λ prvn´ıch s norm´aln´ım rozˇelen´ım. Generov´ an´ı je prov´adˇeno pomoc´ı tˇr´ıdy CorrelatedRandomVectorGenerator z knihovny java-commons-math. • calculateEigendecomposition - poˇc´ıt´a rozklad na vlastn´ı ˇc´ısla a vlastn´ı vektory z kovarianˇcn´ı matice C(g+1) . Rozklad je prov´adˇen pomoc´ı tˇr´ıdy EigenDecomposition z knihovny java-commons-math. • calculateCovariance - poˇc´ıt´a novou kovarianˇcn´ı matici C(g+1) (g+1)
• calculatePSigma- poˇc´ıt´a novou hodnotu pσ
(g+1)
• calculatePCumulation- poˇc´ıt´a novou hodnotu pc • calculateHSigma- poˇc´ıt´a hodnotu hσ • calculateSigma- poˇc´ıt´a novou hodnotu σ (g)
V jednotliv´ ych metod´ ach prob´ıhaj´ı znaˇcnˇe komplikovan´e maticov´e operace. Pomocn´e metody, kter´e slouˇz´ı k v´ ypoˇct˚ um promˇenn´ ych algoritmu: • calculateMuDifferenceFromOldMean - poˇc´ıt´a vzd´alenost matice popu (g) T (g) T lace x1:λ , . . . xµ:λ od stˇredn´ı hodnoty m(g) dˇelen´e stepsize atributem σ (g) . Statick´ a metoda pom´ah´a v´ ypoˇctu rank-µ-update pˇri poˇc´ıt´an´ı kovarianˇcn´ı matice C(g+1) . • createMatrixFromPopulation - vytv´aˇr´ı z µ vybran´ ych jedinc˚ u matici (g) T (g) T x1:λ , . . . xµ:λ . Statick´a metoda pom´ah´a pˇri celkov´em zjednoduˇsov´an´ı v´ ypoˇct˚ u. • triu - vrac´ı horn´ı troj˚ uheln´ıkovou matici ze zadan´e matice toTriu. Statick´ a metoda se pouˇz´ıv´ a pˇri v´ ypoˇctu v metodˇe computeEigendecomposition v n´ıˇz zaruˇcuje symetrii kovarianˇcn´ı matice pˇri jej´ım rozkladu na C(g+1) = (g+1) (g+1) T B(g+1) D2 B zb´ yvaj´ıc´ı nepopsan´e metody jsou jiˇz popsan´e a slouˇz´ı k nastavov´an´ı parametr˚ u z GUI, nebo k informov´ an´ı o v´ ysledc´ıch a jiˇz jsem je dˇr´ıve popsal.
1.2
Tˇ r´ıda RestartCMAESMethod
Tˇr´ıda RestartCMAESMethod je koncipov´ana jako abstraktn´ı pˇredek vˇsech mnou implementovan´ ych variant a tˇr´ıd algoritmu CMA-ES zaloˇzen´ ych na restartech. Takˇze obsahuje implementace obsluh restart˚ u algoritmu. Odvozen´a tˇr´ıda mus´ı implementovat podm´ınky pro restart a novou hodnotu v´ ypoˇctu promˇenn´e po restartu λ, protoˇze pr´ avˇe tyto dvˇe vˇeci jsou podstatou restartovac´ıho algoritmu. 11
1.2.1
Obecnˇ e k implementaci tˇ r´ıdy RestartCMAESMethod
Tˇr´ıda RestartCMAES rozˇsiˇruje abstraktn´ıho pˇredka CMAESMethodo n´asleduj´ıc´ı metody: abstract void calculateLambda(); abstract boolean isRestartConditionsMet(); void restart(); public void optimize(); int getRestartCounter() pˇriˇcemˇz rozˇsiˇruje chov´ an´ı metody optimize o kontrolu, zda nebyla v pr´avˇe probˇehl´e iteraci splnˇena nˇekter´a z restartovac´ıch podm´ınek. Vyvol´ an´ı restartu ssebou obn´aˇs´ı vol´an´ı metod initializeDefaultParameterspˇredka CMAESMethod(viz. popis) , kter´a inicializuje vˇsechny promˇenn´e pro v´ ypoˇcet algoritmu na poˇc´ ateˇcn´ı hodnotu a metodu pro pˇrepoˇcet parametru λ po restartu (IPOP-CMA-ES po restartu zvyˇsuje mnoˇzstv´ı populace o nˇejak´ y n´asobek increasePopulationMultiplier) calculateLambda. To, zda jsou restartovac´ı podm´ınky splnˇeny je plnˇe na benevolenci potomk˚ u, nebot’ implementace t´eto metody je startos´ı potomk˚ u v metodˇe isRestartConditionMet. Podrobnˇeji rozeberu tuto metodu u popisu tˇr´ıdy IPOPCMAESMethod, kter´a tuto metodu implementuje. Stejnˇe tak potomek mus´ı implementovat zmˇenu populace λ po restartu, tedy metodu calculateLambda. Posledn´ı metoda je getRestartCounter, kter´a vrac´ı mnoˇzstv´ı jiˇz proveden´ ych restart˚ u (tedy poˇcet vol´an´ı metody restart).
1 2 3
restartCounter +=restartCounter +1 calculateLambda() initializeDefaultParameters() Algorithm 4: Obsluha jednoho restartu restartovac´ı strategie
super.optimize() if isRestartConditionsMet() then 3 restart() 4 end Algorithm 5: Obsluha jednoho optimalizaˇcn´ıho kroku instance restartovac´ı strategie
1 2
1.3
Tˇ r´ıda IPOPCMAESMethod
Tˇr´ıda IPOPCMAESMethod implementuje abstraktn´ı tˇr´ıdu CMAESMethod, kde sv´emu pˇredkovi implementuje restartovac´ı podm´ınky, kter´e jsou shodn´e s podm´ınkami pro zastaven´ı tˇr´ıdy PureCMAESMethod. Jedn´a se o tyto podm´ınky: 12
• NoEffectAxis v instanci noEffectToAxisStopCondition tˇr´ıdy NoEffectAxisStopCondition. • NoEffectCoord v instanci noEffectToAxisStopCondition tˇr´ıdy NoEffectAxisStopCondition. • EqualFunValues v instanci equalFunValuesStopCondition tˇr´ıdy EqualFunValuesStopCondition. • ConditionCov v instanci conditionCovStopCondition tˇr´ıdy ConditionCovStopCondition. • TolFun v instanci tolFunStopCondition tˇr´ıdy TolFunStopCondition. • TolX v instanci tolXStopCondition tˇr´ıdy TolXStopCondition. • instance tˇr´ıdy SimpleStopCondition, coˇz je obecn´a zastavovac´ı podm´ınka kter´ a detekuje konvergenci fitness . Tˇr´ıda m´ a jednu promˇennou increasePopulationMultiplier, kter´a ud´av´a n´ asobek λ po restartu. Tento atribut pouˇzit pˇri vol´an´ı metody calculateLambda, kter´ a je vol´ ana pˇri kaˇzd´em restartu metodou restart. Metody jsou n´ asleduj´ıc´ı void init(ObjectiveFunction function) void setStopConditionParameters() void optimize() boolean isRestartConditionsMet() void restart() void calculateLambda() Metoda init se star´ a pouze o spr´avn´e poˇc´ateˇcn´ı nastaven´ı parametr˚ u vˇsech restartovac´ıch podm´ınek a vol´an´ı metody initsv´eho pˇredka Metoda setStopConditionParameters nedˇel´a nic, protoˇze tˇr´ıda IPOPCMAESMethodnem´ a ˇz´ adn´e zastavovac´ı podm´ınky, kromˇe jedn´e nadˇrazen´e (kter´a bud’ omezuje ˇcas, nebo mnoˇzstv´ı iterac´ı, ale jej´ı obsluhu m´a plnˇe v kompetenc´ıch volaj´ıc´ı) Metoda optimize se star´ a o vol´an´ı jednoho kroku algoritmu a pˇred´an´ı stavov´ ych promˇenn´ ych pro restartovac´ı podm´ınky. O kontrolu zda, je restartovac´ı podm´ınka splnˇena se star´ a metoda optimize v RestartCMAESMethod pomoc´ı vol´an´ı isRestartConditionsMet. Metoda isRestartConditionsMetvrac´ı but’ true, je-li alespoˇ n jedna ze zm´ınˇen´ ych podm´ınek splnˇena, jinak vrac´ı false. Metoda restart nastavuje stejnˇe jako initvˇsechny restartovac´ı podm´ınky do poˇc´ ateˇcn´ıho stavu .
1.4
Tˇ r´ıda PureCMAESMethod
Tˇr´ıda PureCMAESMethod implementuje abstraktn´ı tˇr´ıdu CMAESMethod, kde sv´emu pˇredkovi implementuje zastavovac´ı podm´ınky, kter´e nem˚ uˇze CMAESMethod implementovat, kv˚ uli restartovac´ım podm´ınk´am. Zbytek chov´an´ı jsem pˇrenechal pˇredkovi
Reference 13
Obr´ azek 3: Z´ akladn´ı tˇr´ıdn´ı hierarchie implmenetace algoritmu CMAES
14
N´ azev promˇenn´e B bestValueInCurrentGeneration C cCumulation chiN consumer countEval cRank1 cSigma currentGeneration D dampingForSigma eigenEval function gaussianGenerator initialSigma
Parametr B(g) (g) x1:λ C(g) cc kN (0, I) k consumer countEval c1 cσ g D(g) dσ eigenEval function N (0, 1) σ (0)
inverseAndSqrtC lambda max min mu muEff N pCumulation pSigma sigma telementry theBestPoint theWorstPoint weights xmean
C− 2 λ max min µ µef f N, n (g) pc (g) pσ (g) σ telemetry theBestPoint theWorstPoint w m(g)
1
(g)
Popis Matice vlastn´ıch vektor˚ u C(g) Nejlepˇs´ı vektor z generace g Kovarianˇcn´ı matice C(g) Kumulaˇcn´ı konstanta Odhad L2 normy N (0, I) Pˇr´ıjemce pr˚ ubˇehu Poˇcet vyhodnocen´ı fitness f Konstakta rank-1-update Konstanta pro v´ ypoˇcet σ (g) St´avaj´ıc´ı generace g Vektor vlastn´ıch ˇc´ısel D(g) Tlum´ıc´ı konstanta dσ Poˇcet rozklad˚ u C(g) Fitness funkce f Gener´ator norm´aln´ıho rozdˇelen´ı Poˇc´ateˇcn´ı hodnota σ (0) 1
(g)
Obr´ azek 4: Popis atribut˚ u tˇr´ıdy CMAESMethod jejich pˇr´ıpadn´e odpov´ıdaj´ıc´ı promˇenn´e algoritmu CMA-ES
15
(g)
C− 2 pro v´ ypoˇcet pσ Velikost populace λ (O) Maxim´aln´ı ∀i ∈ N xi ≤ max (O) Maxim´aln´ı ∀i ∈ N xi ≥ max Poˇcet vybran´ ych jedinc˚ uµ Efektivn´ı hodnota selekce Vstupn´ı rozmˇer funkce f evoluˇcn´ı cesta pro rank-1-update evoluˇcn´ı cesta pro σ (g) Velikost kroku Vˇsichni jedinci z g Nejlepˇs´ı jedinec ze vˇsech generac´ı Nejhorˇs´ı jedinec ze vˇsech generac´ı V´ahy V´aˇzen´a stˇredn´ı hodnota selekce
