Algoritmy pro spojitou optimalizaci Vladim´ır Biˇc´ık
Katedra poˇc´ıtaˇcu˚ Fakulta elektrotechnicka´ ˇ Cesk e´ vysoke´ uˇcen´ı technicke´ v Praze
10.6.2010
ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
1 / 11
´ Uvod
Spojita´ optimalizace ´ ych parametru˚ Obecna´ minimalizace funkce v prostoru realn´ ´ Mnoho pˇr´ıstupu, ˚ dlouhodobeˇ zkoumano
´ ´ Jadro prace ´ ı ˇrady ruzn´ Nastudovan´ ˚ ych algoritmu˚ ´ ı do jednotneho ´ Pˇrepsan´ rozhran´ı ˇ ´ Cerp ano z ruzn´ ˚ ych zdroju˚ (napˇr. FORTRAN77, C++, Java) ˇ ren´ı na vstupn´ı parametry Sjednocen´y popis algoritmu, ˚ zameˇ JavaDoc dokumentace a odkazy k puvodn´ ım publikac´ım ˚
ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
2 / 11
Aplikaˇcn´ı prostˇred´ı JCool ´ M. Hvizdoˇse Projekt vzniknuvˇs´ı jako v´ysledek diplomove´ prace ´ ı a porovnav ´ an´ ´ ı optimalizaˇcn´ıch metod Testovan´ ˇ ´ Obsahovalo nekolik zakladn´ ıch funkc´ı a 3 optimalizaˇcn´ı metody
ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
3 / 11
Implementovane´ optimalizaˇcn´ı metody Numericke´ optimalizaˇcn´ı metody
Gradientn´ı metody Liˇs´ı se v pouˇzit´ı Hessovy matice: 1 2 3
4 5
Conjugate Gradient: nepouˇz´ıva´ vubec ˚ ´ upravuje Levenberg—Marquardt: pouˇz´ıva´ a dale quasi–Newton: nepouˇz´ıva´ pˇr´ımo, aproximuje
Orthogonal search – optimalizace po dimenz´ıch ´ a´ smery ˇ Powell’s method – vylepˇsen´ı, sklad
Covariance Matrix Adaptation Evolution Strategy ´ ı normaln´ ´ ıho rozdelen´ ˇ ı vektoru v´ıce promenn´ ˇ ych Vzorkovan´ ´ ˇ ych Matice kovariance popisuje zavislosti promenn´
ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
4 / 11
Implementovane´ optimalizaˇcn´ı metody Optimalizaˇcn´ı metody inspirovane´ pˇr´ırodou
Mravenˇc´ı algoritmy ´ ı mravencu˚ (CACO, API) Pˇr´ımo simuluj´ıc´ı chovan´ Rozˇs´ırˇen´ı puvodn´ ıho mravenˇc´ıho algoritmu o diskretizaci (AACA) ˚ ˇ Rozˇs´ıˇren´ı puvodn´ ıho mravenˇc´ıho algoritmu o pravdepodobnostn´ ı ˚ ´ ı (ACO*, DACO) vzorkovan´
Geneticke´ algoritmy ´ ı evoluce (DE, SADE) Diferencialn´ ˇ ´ ı populace (PBIL) Pravdepodobnostn´ ı vektor pro vzorkovan´ Simulace hejna hledaj´ıc´ıho potravu (PSO) Kombinace algoritmu˚ (HGAPSO) ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
5 / 11
Implementovane´ testovac´ı funkce Sada testovac´ıch funkc´ı ´ ı a multimodaln´ ´ ı funkce Unimodaln´ ´ ı funkce, mnoho z nich parametrizovateln´ych V´ıcedimenzionaln´ ´ pˇredpis pro analytick´y gradient a Zpravidla implementovan Hessovu matici ´ ıch minim, vˇcetneˇ jejich pozic Dokumentovane´ hodnoty globaln´
´ ˇ Obrazek: Nekter e´ implementovane´ testovac´ı funkce. ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
6 / 11
Provedene´ experimenty Metodologie
´ ı Zpusob testovan´ ˚ ´ ı, limit 2000 iterac´ı 100 opakovan´ ´ rozsahu Vˇsechny parametry v plnem ´ ˇ snost ˇreˇsen´ı a poˇcet iterac´ı Pozorovana usp ´ eˇ 60 Average number of iterations
Average rate of success
100% 80% 60% 40% 20% 0% 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
50 40 30 20 10 0
0
0.1
0.2
0.3
0.4
Parameter range AC BE BO
BR EA GP
GR HI LA
L3 L5 MA
MI RN RA
0.5
0.6
0.7
0.8
0.9
1
Parameter range RO SH SB
SW DJ TR
WH ZA
AC BE BO
BR EA GP
GR HI LA
L3 L5 MA
MI RN RA
RO SH SB
SW DJ TR
WH ZA
´ ˇ Obrazek: PBIL, pravdepodobnost mutace, krok 0,05 ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
7 / 11
Provedene´ experimenty Doporuˇcene´ parametry implementovan´ych optimalizaˇcn´ıch metod
V´ysledky experimentu˚ Doporuˇcene´ hodnoty parametru˚ metod Ruzn ˚ a´ nasteven´ı pro ruzn ˚ e´ typy funkc´ı 100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0% SADE
c re f de
DE
c re f de
RO SH SB SW DJ
c re f de
PSO-FI PSO-C
c re f de
L5 MA MI RN RA
c re f de
PSO
c re f de
DACO GP GR HI LA L3
c re f de
ACO*
c re f de
AC BE BO BR EA
c re f de
AACA
c re f de
c re f de
c re f de
API
PBIL HGAPSO
TR WH ZA
´ ´ ı puvodn´ Obrazek: Porovnan´ ıch a doporuˇcen´ych parametru˚ ˚ ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
8 / 11
Provedene´ experimenty ´ ´ ı implementovan´ych optimalizaˇcn´ıch metod I Vzajemn e´ porovnan´
Zhodnocen´ı konvergence ´ ı napˇr´ıcˇ numerick´ymi, pˇr´ırodou inspirovan´ymi i vˇsemi Porovnan´ dohromady Doporuˇcene´ pouˇzit´ı metod ´ ı v meta-optimalizaci Naznaˇcen´ı pokraˇcovan´
ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
9 / 11
Provedene´ experimenty ´ ´ ı implementovan´ych optimalizaˇcn´ıch metod II Vzajemn e´ porovnan´
Numericke´ metody ˇ s´ı Mnohem pˇresnejˇ ˇ s´ı Efektivnejˇ ´ ı konvergence Chyb´ı jim globaln´ ˇ ı typu funkce Moˇzno pouˇz´ıt i k zjiˇsten´
Metody inspirovane´ pˇr´ırodou ˇ s´ı, ale zvladnou ´ ˇ zke´ funkce Nepˇresnejˇ i teˇ ´ cnejˇ ˇ s´ı Vyˇzaduj´ı v´ıce iterac´ı, cˇ asoveˇ naroˇ
ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
10 / 11
Shrnut´ı
´ Pˇr´ınosy prace Implementace a popis 7 numerick´ych a 10 pˇr´ırodou inspirovan´ych optimalizaˇcn´ıch algoritmu˚ ´ ruzn´ Sada 32 testovac´ıch funkc´ı pokr´yvaj´ıc´ı sˇ irokou sˇ kalu ˚ ych ´ u˚ problem ´ ı algoritmu˚ v zavislosti ´ ´ parametru˚ Popis chovan´ na hodnotach Sady doporuˇcen´ych parametru˚ metod s ohledem na meta-optimalizaci ´ ı efektivnosti metod, doporuˇcen´ı jejich pouˇzit´ı Porovnan´
ˇ Vladim´ır Biˇc´ık (CVUT Praha)
Algoritmy pro spojitou optimalizaci
10.6.2010
11 / 11
