Na tomto míst¥ bude o ciální zadání va²í práce •
Toto zadání je podepsané d¥kanem a vedoucím katedry,
•
musíte si ho vyzvednout na studiijním odd¥lení Katedry po£íta£· na Karlov¥ nám¥stí,
•
v jedné odevzdané práci bude originál tohoto zadání (originál z·stává po obhajob¥ na kated°e),
•
ve druhé bude na stejném míst¥ neov¥°ená kopie tohoto dokumentu (tato se vám vrátí po obhajob¥).
i
ii
eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra po£íta£·
Bakalá°ská práce
Optimaliza£ní algoritmus CMA-ES
Antonín ulc
Vedoucí práce:
Ing. Jan Drchal
Studijní program: Softwarové technologie a management, Bakalá°ský
Obor: Inteligentní systémy
19. kv¥tna 2011
iv
v
Pod¥kování Rád bych touto cestou pod¥koval v²em, kte°í m¥ zasv¥tili do problematiky evolu£ních strategií. Mé velké díky pat°í Ing. Janu Drchalovi, který m¥ seznámil s celou problematikou, dále pak Ing. Petru Po²íkovi, Ph.D., který mi v rámci p°edm¥tu Aplikace um¥lé inteligence vysv¥tlil podstatu celých evolu£ních výpo£t· a poskytl obecný rámec informací a rovn¥º za to, ºe si na m¥ vºdy na²el £as, pokud jsem cht¥l cokoli konzultovat. Dále pak RNDr. Petru Ol²ákovi, který pohotov¥ odpovídal na v²echny mé dotazy ohledn¥ matematických problém· souvisejících s algoritmem. Potom své rodin¥ a blízkým p°átel·m a svému zam¥stnavateli Ing. Martinu Rehákovi, Ph.D. , kte°í se mi snaºili pomoci, kdyº jsem za£al poci´ovat £asovou krizi.
vi
vii
Prohlá²ení Prohla²uji, ºe jsem práci vypracoval samostatn¥ a pouºil jsem pouze podklady uvedené v p°iloºeném seznamu. Nemám závaºný d·vod proti uºití tohoto ²kolního díla ve smyslu 60 Zákona £. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zm¥n¥ n¥kterých zákon· (autorský zákon).
Praze dne 27. 5. 2011
.............................................................
viii
Abstract Translation of Czech abstract into English.
Abstrakt Abstrakt práce by m¥l velmi stru£n¥ vystihovat její podstatu. Tedy £ím se práce zabývá a co je jejím výsledkem/p°ínosem. O£ekávají se cca 1 2 odstavce, maximáln¥ p·l stránky.
ix
x
Obsah 1 Úvod
1
1.1
Evolu£ní algoritmy, techniky a výpo£ty . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
Vlastnosti a popis
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.2
Operátory genetických algoritm· a evolu£ních strategií . . . . . . . . .
2
1.1.2.1
Selekce
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.2.2
K°íºení, rekombinace . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2.3
Mutace
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Evolu£ní strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.1
5
1.2
D¥lení evolu£ních strategií . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1.1 1.2.1.2 1.2.1.3 1.2.1.4 1.2.1.5
1.3
(µ, λ)-ES . (µ + λ)-ES (µ/%, λ)-ES (1 + λ)-ES (1 + 1)-ES
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3.1
Newtonova metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3.2
Matice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3
Vlastní £ísla a vlastní vektory matic
. . . . . . . . . .
10
1.3.4
Normální rozd¥lení . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Matematický aparát
1.3.3.1
. . . . . . . . . . . . . . . . . . .
De nice vlastních £ísel a vlastních vektor·
2 Analýza algoritmu CMA-ES 2.0.5
9 10
15
Podrobný popis krok· algoritmu
. . . . . . . . . . . . . . . . . . . . .
16
2.0.5.1
Generování . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.0.5.2
Vyhodnocení
. . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.0.5.3
Selekce a rekombinace . . . . . . . . . . . . . . . . . . . . . .
17
2.0.5.4
Výpo£et
2.0.5.5
Výpo£et
2.0.5.6
Výpo£et kovarian£ní matice
2.0.5.7
Výpo£et hodnoty
pσ pc
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
σ
C
. . . . . . . . . . . . . . . . .
20
. . . . . . . . . . . . . . . . . . . . . . .
22
2.0.6
Vlastnosti algoritmu CMA-ES . . . . . . . . . . . . . . . . . . . . . . .
23
2.0.7
Zastavovací kritéria . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.1
Vlastnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.2
Varianty CMA-ES
2.1.0.1
Vztah s Hessovou maticí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xi
24 25
xii
OBSAH
2.2.1
IPOP-CMA-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.2.2
σ -m-IPOP-CMA-ES
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.2.3
LS-CMA-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.2.4
ACTIVE-CMA-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3 Implementace algoritmu CMA-ES do knihovny JCool 3.1
3.2
29
Knihovna JCool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.1.1
Základní rozhraní knihovny JCool
. . . . . . . . . . . . . . . . . . . .
29
3.1.2
Implementace algoritm· v knihovn¥ JCool . . . . . . . . . . . . . . . .
29
Implementace do knihovny JCool . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.2.1
Základní t°ída CMAESMethod
. . . . . . . . . . . . . . . . . . . . . .
33
3.2.1.1
Obecn¥ k implementaci t°ídy CMAESMethod . . . . . . . . .
33
3.2.1.2
Integrace t°ídy CMAESMethod do knihovny JCool . . . . . .
34
3.2.1.3
Inicializa£ní krok ve t°íde CMAESMethod . . . . . . . . . . .
34
3.2.1.4
Optimaliza£ní krok ve t°íde CMAESMethod
. . . . . . . . .
36
3.2.2
T°ída RestartCMAESMethod . . . . . . . . . . . . . . . . . . . . . . .
40
3.2.2.1
. . . .
40
3.2.3
T°ída IPOPCMAESMethod . . . . . . . . . . . . . . . . . . . . . . . .
41
3.2.4
T°ída PureCMAESMethod
. . . . . . . . . . . . . . . . . . . . . . . .
42
3.2.5
Implementace zastavovacích podmínek . . . . . . . . . . . . . . . . . .
44
3.2.5.1
Podmínka NoEectAxis . . . . . . . . . . . . . . . . . . . . .
44
3.2.5.2
Podmínka NoEectCoord . . . . . . . . . . . . . . . . . . . .
44
3.2.5.3
Podmínka EqualFunValues
3.2.5.4
Podmínka ConditionCov
3.2.5.5
Podmínka TolX
3.2.5.6
Podmínka TolFunHistory
Obecn¥ k implementaci t°ídy RestartCMAESMethod
. . . . . . . . . . . . . . . . . . .
45
. . . . . . . . . . . . . . . . . . . .
46
. . . . . . . . . . . . . . . . . . . . . . . . .
46
. . . . . . . . . . . . . . . . . . . .
4 Experimenty 4.1
47
49
Informace k experiment·m . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
4.1.1
Získávání infomrací o pr·b¥hu p°i porovnávání s ostatními metodami .
49
4.1.2
Diskuze o výsledcích experiment· . . . . . . . . . . . . . . . . . . . . .
49
4.1.3
Získávání informací o pr·b¥hu výpo£tu algoritmu CMA-ES
. . . . . .
50
4.2
Kroky algoritmu pro vybrané funkce
. . . . . . . . . . . . . . . . . . . . . . .
67
4.3
P°íloha A: Porovnání dal²ích variant s algoritmem CMA-ES . . . . . . . . . .
85
4.3.1
Porovnání s algoritmem LS-CMA-ES . . . . . . . . . . . . . . . . . . .
85
4.3.2
Porovnání s algoritmem ACTIVE-CMA-ES
87
. . . . . . . . . . . . . . .
5 P°íloha B: Pouºité zkratky a jejich vysv¥tlení
89
6 P°íloha C: Popis atribut· t°ídy CMAESMethod
91
7 P°íloha D: Grafy vybraných testovacích funkcí
93
8 Záv¥r
103
A Testování zapln¥ní stránky a odsazení odstavc·
107
xiii
OBSAH
B Pokyny a návody k formátování textu práce
111
B.1
Vkládání obrázk· . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
B.2
Kreslení obrázk·
B.3
Tabulky
B.4
Odkazy v textu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
B.4.1
Odkazy na literaturu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
B.4.2
Odkazy na obrázky, tabulky a kapitoly . . . . . . . . . . . . . . . . . . 114
B.5
Rovnice, centrovaná, £íslovaná matematika . . . . . . . . . . . . . . . . . . . . 115
B.6
Kódy programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
B.7
Dal²í poznámky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 B.7.1
eské uvozovky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
C Seznam pouºitých zkratek
117
D UML diagramy
119
E Instala£ní a uºivatelská p°íru£ka
121
F Obsah p°iloºeného CD
123
xiv
OBSAH
Seznam obrázk· (µ/%, λ)
1.1
Pr·b¥h multirekombinace pro
. . . . . . . . . . . . . . . . . . . .
4
1.2
Jedno a dvoubodové k°íºení v GA . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Ukázka k°íºení u GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.4
Newton·v sm¥r. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.5
Newton·v sm¥r i gradient
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.6
Geometrická interpretace rozkladu na vlastní £ísla a vektory. . . . . . . . . . .
12
1.7
Vizualizace normálních rozd¥lení
13
2.1
Váhy
wi
ES
. . . . . . . . . . . . . . . . . . . . . . . . .
pro váºení jedinc· v selekci a rekombinaci. Na ose x je po°adí vah,
p°i£emº první váha je váha pro nejsiln¥j²ího jedince . . . . . . . . . . . . . . .
18
2.2
Ukázky dvou evolut£ních cest
. . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.3
Vliv rozdílu st°edních hodnot
. . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.4
Odhad konvergence algoritmu CMA-ES
2.5
Ukázka výpo£tu parametr· algoritmu
. . . . . . . . . . .
26
3.1
T°ídy Consumer, Producer a Solver . . . . . . . . . . . . . . . . . . . . . . . .
30
3.2
Hierarchie t°íd pro telemetrie
31
3.3
Hierarchie t°íd, zapouzd°ující tness funkci.
. . . . . . . . . . . . . . . . . . .
32
3.4
Základní t°ídní hierarchie implmenetace algoritmu CMA-ES . . . . . . . . . .
43
4.1
Pr·b¥h tness pro Ackleyovu funkci
. . . . . . . . . . . . . . . . . . . . . . .
52
4.2
Pr·b¥h tness pro Bealeho funkci . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.3
Pr·b¥h tness pro Bohachevskyho funkci
. . . . . . . . . . . . . . . . . . . .
53
4.4
Pr·b¥h tness pro Booth funkci . . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.5
Pr·b¥h tness pro Branin funkci
. . . . . . . . . . . . . . . . . . . . . . . . .
54
4.6
Pr·b¥h tness pro Colville funkci . . . . . . . . . . . . . . . . . . . . . . . . .
54
4.7
Pr·b¥h tness pro Dixon-Priceovu funkci
. . . . . . . . . . . . . . . . . . . .
55
4.8
Pr·b¥h tness pro Easomovu funkci
. . . . . . . . . . . . . . . . . . . . . . .
55
4.9
Pr·b¥h tness pro Goldstein-Price funkci
. . . . . . . . . . . . . . . . . . . . .
σ -m-IPOP-CMA-ES
. . . . . . . . . . . . . . . . . . . . . . . . . . .
22
. . . . . . . . . . . . . . . . . . . .
56
4.10 Pr·b¥h tness pro Griewangkovu funkci
. . . . . . . . . . . . . . . . . . . . .
56
4.11 Pr·b¥h tness pro Hartmannovu funkci
. . . . . . . . . . . . . . . . . . . . .
57
4.12 Pr·b¥h tness pro Himmelblauovu funkci
. . . . . . . . . . . . . . . . . . . .
57
4.13 Pr·b¥h tness pro Langermannovu funkci
. . . . . . . . . . . . . . . . . . . .
58
4.14 Pr·b¥h tness pro Levyho 3 funkci . . . . . . . . . . . . . . . . . . . . . . . .
58
4.15 Pr·b¥h tness pro Levyho 5 funkci . . . . . . . . . . . . . . . . . . . . . . . .
59
4.16 Pr·b¥h tness pro Levy funkci
59
. . . . . . . . . . . . . . . . . . . . . . . . . .
xv
xvi
SEZNAM OBRÁZK
4.17 Pr·b¥h tness pro Matyas funkci . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.18 Pr·b¥h tness pro Michalewicz funkci
. . . . . . . . . . . . . . . . . . . . . .
60
. . . . . . . . . . . . . . . . . . . . . . . . . .
61
4.19 Pr·b¥h tness pro Perm funkci
4.20 Pr·b¥h tness pro Powellovu funkci
. . . . . . . . . . . . . . . . . . . . . . .
61
4.21 Pr·b¥h tness pro kvadratickou funkci . . . . . . . . . . . . . . . . . . . . . .
62
4.22 Pr·b¥h tness pro Ranaovu funkci
. . . . . . . . . . . . . . . . . . . . . . . .
62
4.23 Pr·b¥h tness pro Rastrigin funkci . . . . . . . . . . . . . . . . . . . . . . . .
63
4.24 Pr·b¥h tness pro Rosenbrockovu funkci . . . . . . . . . . . . . . . . . . . . .
63
4.25 Pr·b¥h tness pro Schwefelovu funkci
. . . . . . . . . . . . . . . . . . . . . .
64
4.26 Pr·b¥h tness pro Shekelovu funkci . . . . . . . . . . . . . . . . . . . . . . . .
64
4.27 Pr·b¥h tness pro Shubertovu funkci . . . . . . . . . . . . . . . . . . . . . . .
65
4.28 Pr·b¥h tness pro Sphere funkci
. . . . . . . . . . . . . . . . . . . . . . . . .
65
4.29 Pr·b¥h tness pro Tridovu funkci . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.30 Pr·b¥h tness pro Whitleyovu funkci . . . . . . . . . . . . . . . . . . . . . . .
66
4.31 Pr·b¥h tness pro Zakharov funkci . . . . . . . . . . . . . . . . . . . . . . . .
67
4.32 Pr·b¥h algoritmu pro Ackleyovu funkci ve dvou rozm¥rech . . . . . . . . . . .
68
4.33 Pr·b¥h algoritmu pro Bealeho funkci ve dvou rozm¥rech . . . . . . . . . . . .
69
4.34 Pr·b¥h algoritmu pro Bohachevskyho funkci prvního druhu ve dvou rozm¥rech 70 4.35 Pr·b¥h algoritmu pro Booth funkci ve dvou rozm¥rech . . . . . . . . . . . . .
71
4.36 Pr·b¥h algoritmu pro Braninovu funkci ve dvou rozm¥rech . . . . . . . . . . .
72
4.37 Pr·b¥h algoritmu pro konstantní funkci ve dvou rozm¥rech
. . . . . . . . . .
73
4.38 Pr·b¥h algoritmu pro Dixon-Priceovu funkci ve dvou rozm¥rech . . . . . . . .
74
4.39 Pr·b¥h funkce pro Easomovu funkci ve dvou rozm¥rech
. . . . . . . . . . . .
75
4.40 Pr·b¥h algoritmu pro Goldstein-Priceovu funkci ve dvou rozm¥rech . . . . . .
76
4.41 Pr·b¥h algoritmu pro Himmelblauovu funkci ve dvou rozm¥rech . . . . . . . .
77
4.42 Pr·b¥h algoritmu pro Humpovu funkci ve dvou rozm¥rech . . . . . . . . . . .
78
4.43 Pr·b¥h algoritmu pro Matyasovu funkci ve dvou rozm¥rech
. . . . . . . . . .
79
. . . . . . . . .
80
4.45 Pr·b¥h algoritmu pro Rosenbrockovu funkci ve dvou rozm¥rech . . . . . . . .
81
4.46 Pr·b¥h algoritmu pro Schwefelovu funkci ve dvou rozm¥rech . . . . . . . . . .
82
4.47 Pr·b¥h algoritmu pro kvadratickou funkci ve dvou rozm¥rech
4.44 Pr·b¥h algoritmu pro Rastriginovu funkci ve dvou rozm¥rech
. . . . . . . . .
83
4.48 Pr·b¥h algoritmu pro Tridovu funkci ve dvou rozm¥rech . . . . . . . . . . . .
84
4.49 Pr·b¥h algoritmu pro Zakharovovu funkcui ve dvou rozm¥rech
. . . . . . . .
86
. . . . . . . . . . . . . . . . . . . . .
88
4.50 Porovnání algoritmu ACTIVE-CMA-ES 6.1
Popis atribut· t°ídy CMAESMethod jejich p°ípadné odpovídající prom¥nné algoritmu CMA-ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
7.1
Ackleyova funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . . . . .
94
7.2
Bealeho funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . . . . . .
94
7.3
Bohachevskyho funkce prvního druhu ve dvou rozm¥rech . . . . . . . . . . . .
95
7.4
Bootheho funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . . . . .
95
7.5
Braninova funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . . . . .
96
7.6
Konstatní funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . . . . .
96
7.7
Dixon-Priceova funkce ve dvou rozm¥rech
7.8
Easomova funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . .
97
. . . . . . . . . . . . . . . . . . . . . . .
97
xvii
SEZNAM OBRÁZK
7.9
Goldstein-Priceova funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . .
98
. . . . . . . . . . . . . . . . . . . .
98
. . . . . . . . . . . . . . . . . . . . . . .
99
7.12 Matyasova funkce ve dvou rozm¥rech . . . . . . . . . . . . . . . . . . . . . . .
99
7.10 Himmelblauova funkce ve dvou rozm¥rech 7.11 Humpova funkce ve dvou rozm¥rech
7.13 Rastriginova funkce ve dvou rozm¥rech . . . . . . . . . . . . . . . . . . . . . . 100 7.14 Rosenbrockova funkce ve dvou rozm¥rech . . . . . . . . . . . . . . . . . . . . . 100 7.15 Schwefelova funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . . . . 101
7.16 Kvadratická funkce ve dvou rozm¥rech
. . . . . . . . . . . . . . . . . . . . . . 101
7.17 Tridova funkce ve dvou rozm¥rech . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.18 Zakharovova funkce ve dvou rozm¥rech . . . . . . . . . . . . . . . . . . . . . . 102 F.1
Seznam p°iloºeného CD p°íklad
. . . . . . . . . . . . . . . . . . . . . . . . 123
xviii
SEZNAM OBRÁZK
Seznam tabulek 4.1
Testovací funkce, nad nimiº byli provedeny expermenty.
xix
. . . . . . . . . . . .
51
xx
SEZNAM TABULEK
Kapitola 1
Úvod 1.1
Evolu£ní algoritmy, techniky a výpo£ty
De nice Evolu£ní algoritmy, techniky a výpo£ty: Jsou metaheuristické optimaliza£ní algoritmy, jenº jsou podoblastí um¥lé inteligence. Evolu£ní algoritmy jsou tvo°eny populací, nad níº jsou de novány operátory selekce, k°íºení a mutace. Kaºdý prvek z populace p°edstavuje jedno z moºných °e²ení.
1.1.1
Vlastnosti a popis
Jak bylo °e£eno v de nici, tak evolu£ní algoritmus (dále jen EA) je tvo°en populací o jedincích, nad nimiº probíhá adaptace a evoluce v kaºdé generaci
g.
n
.Úkolem je najít glo-
bální optimum. Protoºe se jedná o metaheuristiku, není zaru£eno, ºe toto vybrané °e²ení
xi
je optimální. EA vytvo°ili mezistupe¬ mezi deterministickými gradientními technikami a
technikami náhodného prohledávání.
input : Fitness funkce f : Df → R. output: Metaheuristický odhad nejlep²í hodnoty funkce f g := 0; (∀xi = rand ()) ∈ X(0) ; (0) ; vyhodno´ kvalitu f (xi ) ∀xi ∈ X
while not stop condition do met (g)
Xselekce = selekce X(g) ⊆ X(g) ; (g)
(g)
Xoperatory = operatory Xselected
;
(g) vyhodno´ kvalitu f (xi ) ∀xi ∈ Xoperatory ; (g) X(g+1) = vyber_nejlepsi Xoperatory ;
g := g + 1;
end
Algoritmus 1: Základní genetický algoritmus 1
2
KAPITOLA 1.
ÚVOD
Jedinec je ur£itou reprezentací, pro kterého jsme schopni vyhodnotit jeho kvalitu. Reprezentace kaºdého jedince je genotyp (sloºený z atomických gen· ) a reprezentuje ur£itý fenotyp.
Nejznám¥j²í EA jsou:
•
Genetický algoritmus (dále jen GA), v kaºdé generaci jsou jedinci, kte°í jsou reprezentováni binárním genotypem. Obecný GA je popsán v algoritmu 1.
•
Genetické programování
, v kaºdé generaci jsou jedinci, kte°í jsou reprezentací
jednoho z moºných postup· (nap°. struktura, popis atp.) v °e²ení daného problému. Jejich kvalitu m¥°í schopnost °e²it daný problém.
•
Evolu£ní programování , je velmi podobné genetickému programování s tím rozdílem, ºe reprezentace jednoho jedince viz. [
•
? ].
x
je pevn¥ daná. M¥ní se pouze jeho parametry
Evolu£ní strategie (dále jen ES), v kaºdé generaci jsou jedinci reprezentováni vektory, ale na rozdíl od GA je genotyp p°ímou reprezentací (fenotypem) hodnoty vstupující do tness funkce
f.
Vlastnosti nových jedinc· v populaci jsou p°eváºn¥ navzájem
korelované s p·vodní populací a s ohledem na jejich kvalitu. U ES m·ºe být pouºito k°íºení, zatímco mutace vybraných jedinc· probíhá vºdy.
1.1.2
Operátory genetických algoritm· a evolu£ních strategií
V následujícím pojednání se pokusím vysv¥tlit principy a postupy operátor· pouºívaných v EA. Genetické operátry nelze zobecnit pro v²echny algortimy. Kaºdý operátor je charakteristický tím, ºe vybírá z populace (selekce), vytvá°í novou informaci v populaci (mutace) nebo sdílí informaci mezi jedinci (k°íºení, rekombinace).
1.1.2.1 Selekce De nice Selekce: Je operátor, jenº vybírá jedince z populace, na neº bude pouºit genetický operátor
Selek£ní operátory vybírají lep²í jedince s vy²²í pravd¥podobností.
?
Nap°íklad u GA existuje operátor selekce ruletovým kolem [
]. Tento selek£ní operá-
tor set°ídí populaci a ke kaºdému jedinci vypo£te pom¥r jeho kvality v·£i celkové kvalit¥ populace. Tento pom¥r tvo°í pom¥r výse£e na tzv. ruletovém kole. Následn¥ se na tomto ruletovém kole vybere náhodné místo, které ukazuje na vybraného jedince. N¥kdy m·ºe být výb¥r i deterministický, jako nap°. u ES, která je zaloºená na adaptaci kovarian£ních matic (dále jen CMA-ES). Selek£ní operátor z celé populace vybere mnoºinu o velikosti
µ
nejlep²ích jedinc· a z nich vypo£te váºenou st°ední hodnotu.
1.1.
3
EVOLUNÍ ALGORITMY, TECHNIKY A VÝPOTY
1.1.2.2 K°íºení, rekombinace De nice K°íºení, rekombinace: Je, je n-nární operátor, který provádí nad dv¥ma genotypy vzájemnou vým¥nu informace mezi jedinci.
Nejb¥ºn¥j²í operátor k°íºení je jednobodové k°íºení v GA. Termín jednobodové k°íºení nad dv¥ma chromozomy délky
N
si lze p°edstavit tak, ºe zvolím náhodný bod
0 < r < N,
r-tého
genu nahradí
p°i£emº v²echny geny v reprezentaci jednoho jedince se od prvního do
r-tého
geny druhého jedince a geny druhého jedince se od
do posledního (N -tého) genu
nahradí geny na odpovídajících pozicích chromosomu prvního jedince. Výsledkem jsou dva chromozomy, dva noví jedinci. Geometricky si lze jednobodové k°íºení p°edstavit tak, ºe nov¥ vytvo°ení jedinci z k°íºení se mohou nacházet na hlavních osách kaºdého z jedinc·. Princip je na obrázku 1.1.2.2 a na obrázku 1.1.2.2 kde je geometrická interpretace. K°íºení lze samoz°ejm¥ zobecnit na
m-bodové
k°íºení, mezi
n
jedinci. Nejb¥ºn¥ji pouºívaný v GA je
ov²em binární jedno-aº-dvou bodový operátor k°íºení. V p°ípad¥, ºe je ES ozna£ena jako
(µ/%, λ)
nebo
(µ/% + λ)
a hodnota parametru
%
je
v¥t²í neº 2, m·ºe docházet k tzv. multirekombinaci. N¥kdy se také multirekombinaci °íká diskrétní k°íºení [
? ]. Multirekombinace je operátor, kde do k°íºení vstupuje % jedinc· z µ
vybraných jedinc·. Multirekombinace probíhá tak, ºe z poulace selekcí vybere z nichº se náhodn¥ vybere
%
µ
jedinc·,
jedinc·. Následn¥ z této mnoºiny vybere operátor kaºdý gen
náhodn¥ (prvek vektoru reprezentace)
1
aº
N
K°íºení probíhá u v²ech ES, které mají
z
%
jedinc·. Proces ilustruje obrázek 1.1.2.2.
% ≥ 2,
pokud
% > 2
mluvíme o tzv. multire-
kombinaci. Podstatným rozdílem operátoru k°íºení u GA a ES je, ºe výsledkem k°íºení jsou op¥t dva jedinci, zatímco u ES vygenerujeme nového jedince pouze jednoho nebo více, ale s podobnými vlastnostmi. Podstatný je fakt, ºe do k°íºení vstupuje generace p°edchozí, která p°edá £áste£n¥ svou informaci generaci nové.
1.1.2.3 Mutace De nice Mutace: Je u GA operátor náhodné zm¥ny hodnoty genu v genotypu. V p°ípad¥ ES je to nahrazení celého genotypu genem podobným. U mutace vzniká nová, potenciáln¥ vhodná informace.
!!! ES? zkratka de novana? P°íkladem mutace u GA je prohození genu/gen· v daném genotypu. Geometricky si lze p°edstavit mutaci nad binárním genotypem po p°evodu na fenotyp podle obrázku 2. Jedi-
{0, 1}. (1, 0, 0, 0; 1, 0, 0, 0) a nachází se na sou°adnicích
nec je reprezentován chromozomem, kde kaºdý gen m·ºe být reprezentován binárn¥ Výchozí jedinec je reprezentován genotypem
(8, 8).
Prohozením libovlného bitu docílíme ve dvou rozm¥rech translaci jedince do jednoho
ze sm¥r· hlavních os sou°adného systému (viz obrázek 1.1.2.2).
4
KAPITOLA 1.
ÚVOD
(x11 , x12 , x13 , . . . x1n ) (x21 , x22 , x23 , . . . x2n ) Celá populace
λ
jedinc·
X=
(x31 , x32 , x33 , . . . x3n ) . . .
(xλ1 , x12 , x13 , . . . xλn )
⇓ Selekce µ jedinc· ⇓ (x11 , x12 , x13 , . . . x1n ) (x21 , x22 , x23 , . . . x2n ) (x31 , x32 , x33 , . . . x3n ) µ jedinc·
. . .
. . .
(xµ1 , x12 , x13 , . . . xµn ) ⇓ Náhodný výb¥r % jedinc· ⇓ (x11 , x12 , x13 , . . . x1n ) (x21 , x22 , x23 , . . . x2n ) (x31 , x32 , x33 , . . . x3n ) % jedinc·
Vygeneruj
(x%1 , x12 , x13 , . . . x%n ) ⇓ náhodn¥ pro kaºdý gen (0, n) náhodný chromosom ⇓ Nový jedinec, sloºený z £ástí populace % x%
Obrázek 1.1: Pr·b¥h multirekombinace pro
(µ/%, λ)
z
%
jedinc·
ES
Obrázek 1.2: Jedno a dvoubodové k°íºení v GA
? ] Levý :Jednobodové k°íºení, Pravý :Dvoubodové k°íºení. Crossover point k°íºení, tedy náhodnou hodnotu 0 < r < N . [? ]
[
ozna£uje bod
1.2.
5
EVOLUNÍ STRATEGIE
Bit−flip mutace pro dvourozmerny prostor
Jednobodove krizeni
10
10 x2
15
x2
15
5
5 (g) (g)
x1 ,x2
x(g)
cross(x(g) ,x(g) ) 1 2
mut(x(g)) 0
0
5
10
15
0
0
5
x1
10
15
x1
Obrázek 1.3: Ukázka k°íºení u GA Levý : Mutace jednoho bitu u jedince reprezentovaným binárním °et¥zcem o délce 8 bit·, Pravý : Jednobodové k°íºení u jedinc· reprezentovaných binárním °et¥zcem o délce 8 bit·
V ES je p°ístup pon¥kud jiný. ES reprezentují jedince pomocí vektr· reálných £ísel a genotyp je zárove¬ i fenotyp. V p°ípad¥ mutace ES se vyuºívá podmnoºiny, p°ípadn¥ celé populace, z níº vytvo°ím novou populaci, £áste£n¥ korelovanou s p·vodní. V p°ípad¥ CMA-ES probíhá mutace tak, ºe stávající populace jedinc· je pln¥ nahrazena novými, normáln¥ rozd¥lenými jedinci, p°i£emº parametry pro normální rozd¥lení bere ze stávající populace speciálním výpo£tem kovarian£ní matice a její st°ední hodnoty (st°ední hodnota, jak jsem jiº zmínil je parametr selekce ). Obdobn¥ jako u k°íºení, resp. rekombinace nelze popis zobecnit, nebo´ se li²í strategie od strategie. Obecným rysem mutace je, ºe vná²í novou náhodnou sloºku do stávající populace, která m·ºe být n¥kdy výhodná pro lep²í prohledání stavového prostoru.
1.2
Evolu£ní strategie
Evolu£ní strategie, je dal²í z kategorií evolu£ních výpo£t·. ES se li²í od GA tím, ºe vyuºívá stávající reprezentaci jedinc· k tomu, aby mohla vygenerovat populaci novou pomocí normálního rozd¥lení. Populace jako celek tvo°í reprezentaci n¥jakého stavu v prostoru °e²ení a vlastností celku nebo její podmnoºiny. Vyuºije p°i tom operátory k vytov°ení nové populace. Podstatným rysem v¥t²iny ES je, ºe vyuºívá normální rozd¥lení. Navzájem se od sebe ES mohou li²it r·znými p°ístupy k výpo£t·m parametr· normálního rozd¥lení.
1.2.1
D¥lení evolu£ních strategií
Jelikoº práce s populací lze u ES zobecnit, byla vytvo°ena metodika ozna£ování kategorií. Ozna£ení nic ne°íká o velikostech populace, ale co je vstupem a výstupem jednoho kroku (jedné generace) dané ES. Symbolem nových jedinc·
λ.
µ
zna£íme populaci, jenº byla vybrána k vytvo°ení
6
KAPITOLA 1.
1.2.1.1
ÚVOD
(µ, λ)-ES
Z populace se vybere
µ
jedinc·, kte°í vytvo°í
λ
jedinc· do populace nové.
µ → (µ, λ)-ES → λ
1.2.1.2
(1.1)
(µ + λ)-ES
Z populace se vybere
µ
jedinc·, která vytvo°í
λ
jedinc· a výsledkem je slou£ení
µ
a
λ.
(worst) jedinc· Pro udrºení konstantní velikosti populace v generacích je resp. m·ºe být λ odstran¥no.
1.2.1.3
µ → (µ + λ)-ES → µ + λ & µ %
(1.2)
(µ/%, λ)-ES
Z populace se vybere
µ
jedinc·, kte°í vytvo°í
λ
jedinc· do populace nové. V pr·b¥hu ES je
pouºit i operátor rekombinace, který je provád¥n nad
%
jedinci.
µ → (µ/%, λ)-ES → λ P°íkladem m·ºe být základní algoritmus CMA-ES, který je ozna£ován jako £ímº °íká, ºe do rekombinace vstupuje skriptu
W ).
µ
(1.3)
(µ/µW , λ)-ES,
jedinc·, kte°í jsou váºení jistou váhou (podle sub-
V p°ípad¥ algoritmu CMA-ES ozna£ení °íká, ºe k°íºení probíhá nad
µW = µ
jedinci. Znakem
% nemusíme zna£it mutirekombinaci, nicmén¥ informace za lomítkem je nositelem
informace o tom, co se d¥je v k°íºení. Coº by m¥lo u odpovídající ES blíºe speci kováno.
1.2.1.4
(1 + λ)-ES
Z populace se vybere jeden jedinec, který vytvo°í
λ
jedinc· do nové populace.
1 → (1 + λ)-ES → 1 + λ & 1 %
1.2.1.5
(1.4)
(1 + 1)-ES
Z populace se vybere jeden jedinec, který vytvo°í jednoho jedince do nové populace.
1 → (1 + 1)-ES → 1 + 1 & 1 %
(1.5)
Ve své podstat¥ je tato ES tzv. hill-climbing technikou, nebo´ ve své jedné generaci vytvo°í nového jedince. Ten se p°idá do stávající populace a bu¤ zvít¥zí a z·stane, nebo, je-li lep²í, bude odstran¥n.
1.3.
7
MATEMATICKÝ APARÁT
1.3 1.3.1
Matematický aparát Newtonova metoda
Newtonova metoda, jak ukáºi pozd¥ji, má velmi blízko k algoritmu CMA-ES. Metoda je zaloºena na vlastnostech inverzní Hessovy matice, která je práv¥ algoritmem CMA-ES aproximována. Je to iterativní metoda pro hledání ko°en· rovnic. Lze ji ov²em pouºít i pro hledání in exních bod· funkcí, které mají druhou derivaci. Takºe hledáme poblíº lokální optima.
f : R → R, která má spojité druhé derivace, x0 a hledám in exní bod x∗ (první derivace je v bod¥ x∗ nulová). Budu f Taylorovým polynomem druhého stupn¥:
Budu p°edpokládat, ºe mám zadanou funkci zadaný výchozí bod aproximovat funkci
f (x + ∆x) = f (x) +
df 1 d2 f (x) ∆x2 (x) ∆x + dx 2 dx2
(1.6)
∆x je krok algoritmu, resp. délka kroku. Hledám takové ∆x, které je co nejmen²í, nejlépe ∆x a vznikne:
nula p°ímo. Toto získám zderivováním výrazu 1.6 podle 2
df dx
(x) + ddxf2 (x) ∆x = 0 df d2 f dx (x) + dx2 (x) (xn − xn−1 ) = 0 df
(xn )
xn − xn−1 = − ddx 2f xn = xn−1 −
(1.7)
(xn ) dx2 df (xn ) dx d2 f (xn ) dx2
? ]. Oby£ejné gradientní
vy°e²ím-li tuto rovnici, odvodím rovnici pro Newtonovy metody [
metody berou v potaz pouze okamºitou hodnotu gradientu v ur£itém bod¥, tzn. sm¥r kolmý na te£nu vrstevnice. U Newtonovy metody, pokud se bod, ze kterého vycházíme nachází poblíº optima, sm¥°uje Newton·v sm¥r p°ímo ve sm¥ru optima. Na obrázku 1.3.1 je ukázka ideálního !sm¥ru Newtonova algoritmu pro kvadratickou funkci s nesymetrickou maticí
1 1 1 3
A=
pro dvourozm¥rný p°ípad.
Obrázek 1.3.1 ukazuje °ezy po 0.1 krocích kvadratickou funkcí. Uvedl jsem výpo£et pro jednorom¥rný p°ípad. Pro vícerozm¥rný p°ípad je nahrazena první derivace gradientem
5f
a
d2 x dx2
−1
inverzním Hessiánem
H−1
funkce
f
a pro víceroz-
m¥rný p°ípad rovnice vypadá následovn¥:
xn = xn−1 − H−1 5 f (xn−1 )
(1.8)
Obecn¥ lze samoz°ejm¥ aproximovat libovolnou funkci. Pro ukázku jsem na obrázcích pouºil kvadratickou funkci, která není symetrická podle hlavních os. Pokud rozloºím matici na vlastní £ísla a vlastní vektory, transformuje matice
H−1
parabolu na parabolu se stejnou
velikostí ve v²ech hlavních osách, pro níº je práv¥ gradient shodný s Newtonovým sm¥rem (transformuji nesymetrické osy k optimální hodnot¥).
xAxT
na symetrické
xxT , pro níº je má gradient p°ímo sm¥r
8
KAPITOLA 1.
ÚVOD
Newtonuv smer na elipse 4 Kvadraticka forma xAxT pro A=[1 1;1 3] Newtonuv smer
3
2
y
1
0 −1 −2 −3
−4 −1.5
−1
−0.5
0 x
0.5
1
1.5
Obrázek 1.4: Newton·v sm¥r. Hledáme-li ! nejmen²í hodnotu pro kvadratickou funkci
1 1 1 3
xAxT
charakterizovanou
A =
. ervenou barvou je vyzna£en Newton·v sm¥r a £ím sv¥tlej²í £erná, tím men²í
hodnota.
Gradient i Newtonuv smer 1 Kvadraticka funkce xxT Newtonuv smer i gradient
0.8 0.6 0.4
y
0.2 0 −0.2 −0.4 −0.6 −0.8
−1
−0.5
0 x
0.5
1
Obrázek 1.5: Newton·v sm¥r i gradient mají pro
xxT
stejný sm¥r, na obrázku hledáme nejmen²í hodnotu. ervenou barvou je vy-
zna£en Newton·v sm¥r a záporný gradient a £ím sv¥tlej²í £erná, tím men²í hodnota.
1.3.
9
MATEMATICKÝ APARÁT
Povinnost existence druhé derivace metod¥ výrazn¥ omezuje pouºití, nebo´ ne vºdy je funkce spojitá. Dal²í v¥cí je samotný výpo£et inverzního Hessiánu, který je výpo£etn¥ náro£ný.
1.3.2
Matice
V následující tabulce vyjád°ím n¥kolik podstatných vlastností, které budu pouºívat p°i úpravách matic nebo se na n¥ budu odkazovat. Symbolem £tvercovou matici,
B
A
budu ozna£ovat libovolnou reálnou
matici vlastních vektor· k odpovídajcí matici,
p°ípad¥ diagonální matici vlatních £ísel odpovídající matici a je
I
D
diagonální matici,
matice identity. Takto
ozna£ených symbol· se budu drºet i ve zbytku mé práce, pokud neuvedu n¥co jiného. Název
Zna£ení
Diagonální matice
diag (d1 , . . . , dn )
Podstatná vlastnost Platí báze
DT = D, je I
Pozitivn¥ de nitní
B=I AD = DAT AT = A B = B−1 BBT = I ∀x ∈ Rn xAxT > 0
matice
Vlastní £ísla jsou > 0
Pozitivn¥ semide nitní
∀x ∈ Rn xAxT ≥ 0 Vlastní £ísla jsou ≥ 0
Vlastní vektory
Symetrická matice Ortonormální báze
matice
? ].
P°edchozí vlastnosti vychází z [
De nice
H je hessova £tvercová matice typu (n, n) parciálních f (x1 , x2 , x3 , . . . xn ) je li funkce dvakrát spojit¥ derivovatelná podle
Hessova matice: Matice
derivací skalární funkce
kaºdé ze svých argument·
H=
∂2f ∂x21 ∂2f ∂x2 x1 . . .
∂2f ∂xn x1
∂2f ∂x1 x2 ∂2f ∂x22
··· ···
. . .
..
∂2f ∂xn x2
···
.
∂2f ∂x1 xn ∂2f ∂x2 xn . . .
∂2f ∂x2n
(1.9)
De nuji podmínku symetrie Hessovy matice, která vychází ze Schwarzovy v¥ty (upravená de nice podle [
De nice
? ]):
Schwarzova v¥ta: Jsou-li parciální derivace funkce
f
podle argument·
∂2f spojité a derivovatelné na otev°ené mnoºin¥ je parciální derivace totoºná pro ∂xi xj
Jestliºe funkce
f
xi a xj ∂2f = ∂x j xi
spl¬uje Schwarzovu v¥tu, je Hessova matice symetrická. Nyní je²t¥ de nuji
kovarian£ní matici:
10
KAPITOLA 1.
ÚVOD
De nice Kovarian£ní matice: Matice C je kovarian£ní matice typu (n, n), kde na kaºdém prvku
i, j
matice je kovariance náhodného vektoru i-tého a
ozna£uji kovarianci náhodných jev·
X1
a
X2
a
D(X)
j -tého jevu. Symbolem C(X1 , X2 )
varianci jevu:
D(X1 ) C(X1 , X2 ) · · · C(X1 , Xn ) C(X , X ) D(X2 ) · · · C(X2 , Xn ) 2 1
C=
. . .
. . .
..
. . .
.
C(Xn , X1 ) C(Xn , X2 ) · · ·
(1.10)
D(Xn )
Kovarian£ní matice udává tvar a sm¥r funkce hustoty vícerozm¥rného normálního roz-
N o C (X2 , X1 )
d¥lení
1.3.3
níº se zmíním více v kapitole o normálním rozd¥lení. Jelikoº platí
C (X1 , X2 ) =
je matice symetrická a navíc pozitivn¥ semide nitní.
Vlastní £ísla a vlastní vektory matic
Vlastnosti vlastních £ísel jsou pro algoritmus CMA-ES podstatné, proto zde de nuji vlastní £ísla a následn¥ vysv¥tlím jejich vlastnosti, které úzce souvisí s adaptací kovarian£ních matic. Pro zjednodu²ení budu p°edpokládat, ºe jsou matice reálné.
1.3.3.1 De nice vlastních £ísel a vlastních vektor· De nice Vlastní £ísla a vlastní vektory: Nech´ C je £tvercová pozitivn¥ de nitní matice typu (n, n). íslo d2 ∈ R b ∈ Rn takový, ºe:
Vektor
b,
se nazývá vlastním £íslem matice
A,
pokud existuje nenulový vektor
Cb = d2 b
(1.11)
který spl¬uje uvedenou rovnost, se nazývá vlastní vektor matice
A
p°íslu²ný
2 vlastnímu £íslu d .
Je-li matice
C
pozitivn¥ de nitní, jsou v²echna vlastní £ísla v¥t²í neº 0.
Pro zjednodu²ení zna£ení budu pouºívat maticové zna£ení, kde matice
h
B = bT1 , . . . , bTn
i
p°edstavuje matici vlatních vektor· a kaºdý sloupec p°edstavuje vlastní vektor se°azený v klesající posloupnosti podle jejich odpovídajících vlatních £ísel. Vlastní £ísla budu reprezento-
d2i
vat
a pro mnoºinu vlastních £ísel budu pouºívat diagonální matici
D = diag (d1 , . . . , dn ),
kde odpovídající pozice na diagonále odpovídá její velikosti od nejv¥t²ího do nejmen²ího vlastního £ísla. Rozvedu vlastnosti vlastních £ísel z rovnice 1.11 v de nici . Podle [
? ] p°edpokládám, ºe
C je symetrická a pozitivn¥ de nitní matice, která má ortonormální bázi tvo°enou vlastními vektory B = [b1 , . . . , bn ] s odpovídajícími vlastními £ísly D = diag (d1 , . . . , dn )
C = BD2 BT = Bdiag d21 , . . . , d2n BT Od této chvíle budu symbolem a
B
matici vlastních vektor·.
(1.12)
D ozna£ovat odpovídající diagonální matici vlastních £ísel
1.3.
11
MATEMATICKÝ APARÁT
B jsou navzájem ortonormální. Kdyº B = B−1 (viz. de nice ortonormality) do-
Rovnice 1.3.3.1 platí, protoºe vektory v matici vynásobím rovnici inverzní maticí pro níº platí
stanu rovnost z de nice pro vlastní £ísla a vlastní vektory. Pomocí rovnosti lze nalézt velmi elegantn¥ inverzní matici
C
C−1 =
BD2 BT
−1
= B−1 D−2 BT = BD−2 BT druhá odmocina z
C
je 1
C2
Dokáºi tvrzení v 1.14. Hledám takové vztah
= =
BD2 BT BDBT
−1
(1.13)
1 2
(1.14)
1
1
1
C 2 , aby platilo C = C 2 C 2
T . Pouºiji de novaný
?? upravím jej s vlastností komutativity násobení diagonálních matic, tedy ºe platí
BD = BT D.
1
1
C = C2 C2 T T = B DB | {z } B | {zD} B = BD
DB
2 B BD | {z } BB =
=
D2 BT BD2 BT B B
=
| {z }
(1.15)
=
I
BD2 BT
= Výsledkem násobení dokázal platnost zvrzení
1
1
C2 C2
T je op¥t kovarian£ní matice
1 2
C = BDBT .
C = BD2 BT ,
£ímº jsem
Vztah 1.14 pouºiji p°i výpo£tu jednoho parametru
algoritmu CMA-ES, proto jej zde uvádím. Na obrázku 1.3.3.1 je zobrazená jednotková kruºnce ([sin t, cos t] pro je zobrazena na matici
C.
t = h0, 2πi),
která
Z obrázku je zjevné, ºe ve sm¥ru vlastních vektor· s nejv¥t²ím
resp. nejmen²ím vlastním £íslem
d2
mají hodnoty
x
nejv¥t²í resp. nejmen²í nár·st. Dal²í
vlastností je pak, ºe vlastní vektory nejsou rotovány maticí
C,
coº plynne p°ímo z de nice,
nebo´ kaºdý sou£in vlastního vektoru a jeho odpovídající matice je násobek vlastního vektoru a jeho vlastního £ísla. V p°ípad¥ první matice identity, jejíº vlastní £ísla jsou
d21 = d22 = 1,
nedochází ke zm¥n¥,
zkrátka jedná se o identické ! zobrazení, coº odpovádá levému obrázku 1.3.3.1. V p°ípad¥ matice
C=
0.5 0 0 0.75
, která má vlastní £ísla
d21 = 0.75
a
d22 = 0.5
dochází ke zmen²ení
B = I,
jsou vlastní vektory
ve sm¥ru odpovídajících vlasntích vektor·. A protoºe je matice
ve sm¥ru hlavních os, takºe zobrazení zm¥ní velikost, ale neoto£í kruºnici, coº odpovídá 1.3.3.1. A v posledním p°ípad¥ se celé zobrazení oto£í ve sm¥ru nejv¥t²ího vlastního vektoru s nejv¥t²ím vlastním £íslem.
12
KAPITOLA 1.
A=[1 0;0 1]
A=[0.5 0;0 0.75]
1
4 x Ax
x Ax
0.5
2
0
0
0
−1 −1
y
0.5
y
y
A=[2 1;1 3]
1 x Ax
−0.5
−0.5
−0.5
0 x
0.5
1
ÚVOD
−2
−1 −1
−0.5
0 x
0.5
−4 −5
1
0 x
5
Obrázek 1.6: Geometrická interpretace rozkladu na vlastní £ísla a vektory. Modrá kruºnice p°edstavuje sou°adnice jednotkové kruºnice a £ervená zobrazení jednotkové na matici
A
Levý : Ukázka rozkladu na vlastní £ísla
x1 (1, 0), x2 = (0, 1) d11
= 0.75
2 a d2
= 0.5
matice
!
1 0 0 1
d21 = 1
d22 = 1
a vlastní vektory
, Prost°ední : Ukázka rozkladu na vlastní £ísla
x1 (1, 0), x2 = (0, 1)
a vlastní vektory
Ukázka rozkladu na vlastní £ísla
d21 ≈ 3.6180
a
matice
d22 ≈ 1.3820
x1 ≈ (0.5257, 0.8507), x2 ≈ (−0.8507, 0.5257)
1.3.4
a
matice
0.5 0 0 0.75
! , Pravý :
a vlastní vektory
2 1 1 3
!
Normální rozd¥lení
S normálním rozd¥lením pracuje algoritmus CMA-ES, vysv¥tlím a rozvedu n¥kolik postatných vlastností. Náhodný vektor s normálním rozd¥lením budu zna£it
N (m, C). N (m, C)
abych udrºel
konzistentní notaci s v¥t²inou literatury na problematiku adaptace kovarian£ních matic.
?
Normální rozd¥lení má n¥kolik podstatných vlastností, které nyní rozvedu. Podle [ platí
??:
]
N (m, C) ≡ m + N (0, C) 1 ≡ m + C 2 N (0, I) ≡ m + BD BT N (0, I) |
{z
N (0,I)
}
(1.16)
≡ m + B DN (0, I) |
≡ m+ Symbolem
≡
{z
}
N (0,D2 ) BN 0, D2
°íkám, ºe vztahy si jsou de ni£n¥ ekvivalentní.
Rovnice 1.16 °íká v jednotlivých °ádcích n¥kolik podstatných vlastností, které mají vztah s rozkladem na vlastní £ísla. Postupn¥ je podrobn¥ rozepí²i 1. P°edpokládejme, ºe máme normální rozd¥lení s nulovou st°ední hodnotou a symetrickou a pozitivn¥ de nitní matici 2. Kovarian£ní matice
C
C
je druhá odmocnina zobrazení do normálního rozd¥lení
N (0, I)
1.3.
13
MATEMATICKÝ APARÁT
4
3 N(0,C) C
10
2
2
5 1
0
0
0
−1 −2
−5 −2
−4 −4
−2
0
2
−3 −4
4
15
N(0,C) C −2
0
N(0,C) C
2
−10 −5
4
12
0
5
15
5
8
Occurences
Occurences
Occurences
10 10
6 4
10
5
2 0 −4
−2
0 Number
2
4
0 −4
−2
0 Number
2
4
0 −10
−5
0 Number
5
10
Obrázek 1.7: Vizualizace normálních rozd¥lení pro dva rozm¥ry v p°ípad¥ r·zných kovarian£ních matic
C
s nulovou st°ední hodnotou. Na
dolních grafech jsou odpovídající histogramy k danému rozd¥lení. Levý : Normální rozd¥lení pro kovarian£ní matici
C = I2 ,
Prost°ední :Normální rozd¥lení pro symetrickou pozitivn¥
de nitní kovarian£ní matici
C=
0.5 0 0 0.75
!
nesymetrickou pozitivn¥ de nitní kovarian£ní matici
, Pravý :Normální rozd¥lení pro
C=
2 1 1 3
! . Z histogram· je dále
vid¥t, ºe pravd¥podobnost daného jevu klesá se vzdáleností od st°ední hodnoty
m=0
14
KAPITOLA 1.
3. Matice
1
C2
4. Protoºe
má odpovídající rozklad
BT
BDBT
je ortonormální, platí pro ni
ÚVOD
podle rovnice 1.14.
BBT = BT B = I
takºe pokud p°esuneme
B
do normálního rozd¥lení (tzn. vynásobíme sebe samou v transpozici) vznikne matice
TN
identity (B
5. P°esuneme-li
(0, I) = N 0, BT B = N (0, I))
D do pozice kovarian£ní matice, tak stejn¥ jako se kovarian£ní matice od-
mocnila p°i p°esunu z pozice kovariance v normálním rozd¥lení, tak vynásobím matici
D
sebe samou (DN
6. Matice
B
(0, I) = N 0, DDT = N 0, D2
.
pooto£í rozd¥lení podle vlastních vektor· kovarian£ní matice normálního
rozd¥lení, které bude osov¥ soumerné s hlavními osami s ohledem na velikost vlastních £ísel (nebo´
D = diag d21 , . . . d2n
Kapitola 2
Analýza algoritmu CMA-ES
Algoritmus CMA-ES je stochastická ES, pro optimalizaci nelineárních a nekonvexních problém·. V této ES je populace navzorkována podle mnoharozm¥rného normálního rozd¥lení, kterou ur£ují kovarian£ní matice
C
a st°ední hodnota
m,
které jsou podle kvality populace
adaptovány. Vzájemné vlastnosti jsou modelované kovarian£ní maticí. Algoritmus prokázal velmi dobré výsledky na v¥t²in¥ vícerozm¥rných funkcí oproti svým velmi silným konkurent·m a má velkou podporu v komunit¥ zabyvající se optimalizací i p°es to, ºe se jedná o pom¥rn¥ nový algoritmus [
?]
Snaºil jsem se, aby v¥t²ina symbol·, jimiº ozna£uji prom¥nnné algoritmu byli shodné
?
se £lánekm [
], ze kterého jsem algoritmus p°edev²ím zkoumal. V popisu algoritmu. Pro
15
16
KAPITOLA 2.
ANALÝZA ALGORITMU CMA-ES
(g+1)
zlep²ení £itelnosti popisu algoritmu pouºiji substituci
yi:λ =
xi:λ
−m(g) σ (g)
Inicializace:
m = rand ()n σ = 12 λ = 4 + blog (3 log N )c µ = b λ2 c ln( λ +0.5)−ln i 2 ∀i = 1 . . . µ:wi = Pµ ln ( λ2 +0.5)−ln j j=1 PN
µef f = PNi=1
wi
w2 i=1 i
(cc , cσ , c1 , cµ ) =
µef f N µ f N +4+2 ef N
4+
q
dσ = 1 + 2 max 0,
µef f −1 n+1
2(µef f −2+ 21 ) µef f +2 2 , , 2 N +µef f +5 (n+1.3) +µef f (N +2)2 +µef f
,
− 1 + cσ
pc = pσ (0, . . . 0)T 1 C 2 = C = B = diag (1, 1, . . . 1) D = diag (1, . . . , 1) eigeneval = 0
while not zastavovací kritérium spln¥no do Generování λ jedinc· normáln¥ rozd¥lených N (m, C) Vyhodnocení tness kaºdého jedince f (xi ) ∀1 P ≤i≤λ Selekce a rekombinace z µ jedinc· m(g+1) = µi=1 wi xi:λ s q − 1 (g+1) −m(g) (g) Výpo£et p(g+1) = (1 − cσ ) pσ + cσ (2 − cσ ) µef f C(g) 2 m σ(g) σ (g+1)
(g)
pc
= (1 − cc ) pc +
C(g+1)
= (1 − c1 − cµ
q
cc (2 − cc ) µef f m
) C(g)
(g+1) −m(g)
σ (g)
T c1 p(g+1) p(g+1) c c
+
|
{z
}
rank−one−update
σ (g+1) = σ (g) e g ←g+1
end
2.0.5
cσ dσ
+cµ
µ X
(g+1)
wi yi:λ
yi:λ T
{z
}
i=1
|
rank−µ−update
(g+1) kpσ k −1 EkN (0,I)k
Algoritmus 2: Základní algoritmus (µ/µW , λ) CMA-ES Podrobný popis krok· algoritmu
2.0.5.1 Generování V prvním kroku algoritmu se vygeneruje populace podle normálního rozd¥lení o velikosti podle kovarian£ní matice
(g+1)
xk Symbolem
≈
C
a hodnoty
λ
m.
≈ σ (g) N m(g) , C(g) ≈ m(g) + σ (g) N 0, C(g)
∀k = 1 . . . λ
(2.1)
zna£ím generování náhodného vektoru podle odpovádajícího normálního
rozd¥lení. V p°ípad¥, ºe se jedná o první krok populace se vygeneruje podle kovarian£ní
17
matice, tak aby bylo rozd¥lení normální a jednotkové násobenné odpovídá levému p°ípadu na obrázku
??.
σ (0) = 0.5.
M·ºe nastat n¥kolik situací rozd¥lení v závilosti na kovarian£ní matici
Cg
=
B(g) D2 B(g)
•
Je-li
C(g) = I
tedy
T
B(g) = B(g) = D2 = I,
Tento p°ípad
C.
Rozloºím-li
pak rozd¥lení odpovídá levému rozd¥lení
na obrázku 1.16. Rozd¥lení má stejnou prav¥podobnost ve v²ech sm¥rech se stejnou vzdáleností od st°edu. Tomuto stavu odpovídá po£áta£ní stav.
•
Je-li
B(g) = B(g)
T
= I,
pak rozd¥lení odpovídá prost°ednímu rozd¥lení na obrázku
1.16. Rozd¥lení má v¥t²í pravd¥podobnost ve sm¥ru té hlavní osy, která má nejv¥t²í vlastní £íslo.
•
Je-li
B(g) 6= I
a
T
B(g) 6= I,
pak rozd¥lení odpovdá pravému rozd¥lení na obrázku 1.16.
Rozd¥lení má v¥t²í pravd¥podobnost ve sm¥ru vlastních vektor·
2 nejv¥t²ím vlastním £íslem dii
(g)
bi
s odpovídajícím
2.0.5.2 Vyhodnocení Vyhodnotí se kvalita v²ech posloupnost
xi:λ ,
λ
takových ºe
jedinc· nov¥ vygenerované populace. Takºe máme set°ídenou
f (x1:λ ) ≤ f (x2:λ ) ≤ . . . f (xλ:λ ),
hledáme-li minimum.
2.0.5.3 Selekce a rekombinace Ze set°íd¥né populace vybereme
µ
nejlep²ích a z nich spo£ítáme váºenou st°ední hodnotu.
m(g+1) =
µ X
(g+1)
wi xi:λ
.
(2.2)
i=1 Hodnota váhy je doporu£ována volit, tak aby nejv¥t²í váhu m¥li nejlep²í jedinci a postupn¥ se sniºovala a p°itom byl její sou£et vah je nap°.
ln( λ +0.5)−ln i wi = Pµ 2 λ j=1
ln( 2 +0.5)−ln j
1.
Jedna z pouºitých funkcí pro výpo£et vektoru
, na obrázku 2.1 je graf jednotlivých vah pro stodimen-
zionální p°ípad (µ je v tomto p°ípad¥ 8). St°ední hodnota, nebo p°esn¥ji váºená st°ední hodnota z
µ
jedinc· udává, kde bude
nejv¥t²í pravd¥podobnost výskytu jedinc· v nové generaci. Výpo£et
m(g+1)
reprezentuje
selekci.
2.0.5.4 Výpo£et pσ σ , tedy velikost kroku algoritmu . P°ímo výpo£tu C se prom¥nná pσ , ale ovliv¬uje velikost σ , která udává velikost násobku normáln¥ vygenerovaných hodnot, neboli tzv. step-size. Parametrem σ regulujeme velikost normálního rozd¥lení, nebo´ parametery C a m neudávají velikost, ale pouze pozici a sm¥r. Rovnice 2.3 po£ítá (g+1) novou hodnotu pσ Hodnota
pσ
slouºí k výpo£tu hodnoty
18
KAPITOLA 2.
ANALÝZA ALGORITMU CMA-ES
Vahy pro prumer v selekci pro 100 dimenzi 0.35
0.3
0.25
wi
0.2
0.15
0.1
0.05
0
1
2
3
4
5
6
7
8
i
Obrázek 2.1: Váhy
wi
pro váºení jedinc· v selekci a rekombinaci. Na ose x je po°adí vah,
p°i£emº první váha je váha pro nejsiln¥j²ího jedince
p(g+1) = (1 − cσ ) p(g) σ σ +
q
cσ + (2 − cσ ) µef f C(g)
− 21
m(g+1) − m(g) (g) σ{z | }
(2.3)
evolution path Na za£átku je hodnota
(0)
pσ
nulová. V kaºdém dal²ím kroku se m¥ní podle velikosti
vzdálenosti hodnot mezi sou£asnou generací
m(g+1)
(g) D(g) −1 B(g) T £ímº p°epsat dále podle 1.14 na B
• B(g)
T
• D(g) • B(g)
zobrazí
−1
m(g+1) −m(g) na bázi σ (g)
a p°edchozí
m(g) .
1
Hodnota
C(g) 2
lze
C(g)
zm¥ní velikosti v hlavních osách sou°adného systému, tak aby byli st¥jn¥ velké
oto£í
Násobením
m(g+1) −m(g) do p·vodního sou°adného systému (protoºe platí σ (g)
C− 2 1
dosáhneme toho, ºe hodnoty
pσ
BBT = I)
budou nezávislé na velikosti kovarian£ní
matice Vysv¥tlím nejd°íve co znamená evolu£ní cesta (p°eklad z angl. evolution path ). V pr·b¥hu výpo£tu algoritmu se p°esouvá postupn¥ st°ední hodnota z
m(g)
do
m(g+1) ,
udává, jakou cestu algoritmus v pr·b¥hu generací urazil. A pokud se hodnoty
která p°ibliºn¥
m(g)
a
m(g+1)
pohybují v generacích p°ibliºn¥ v okolí stejné hodnoty, tak se vyru²ují s ohledem na uchovávání p°edchozích hodnot
(g)
1 − cσ )pc
, coº °íká, ºe algoritmus se pohybuje kolem n¥jakého
bodu a je dobrý d·vod zmen²it hodnotu
σ (g+1) < σ (g)
v dal²í generaci. P°íklad takové evo-
lu£ní cesty je na obrázku 2.2 nalevo. Druhý opa£ný p°ípad, který m·ºe nastat je, ºe cesty mají p°ibliºn¥ stejný sm¥r, takºe se nevyru²ují a je naopak dobrý d·vod zv¥t²it hodnotu
σ (g+1) > σ (g) ,
coº ilustuje obrázek 2.2 napravo.
19
σ(g+1)<σ(g)
σ(g+1)>σ(g)
7
3
10
2.5
9 2
2
6
8
1.5
7
16
5
6
0.5
4
5 1
0
3
4
−0.5
3
3 5
−1
2
2
−1.5
1
−2 −2
−1
0
4 1
01 0
2
1
2
3
4
Obrázek 2.2: Ukázky dvou evolut£ních cest st°edních hodnot v n¥kolika generacích. Na levém obrázku je vid¥t, ºe se st°ední hodnoty
m(g+1
a
m(g)
pohybují v svém okolí a navzájem se vyru²ují, takºe velikost
σ (g+1)
by m¥la
být zmen²ena, £ímº se zmen²í i ²í°ka normálního rozd¥lení p°i generování nové populace. Zatímco na pravém obrázku mají st°ední hodnoty
m(g+1)
a
m(g)
podobný sm¥r a navzájem
(g+1) by m¥la být zv¥t²ena. se nevyru²ují, takºe velikost σ m(g+1) −m(g) je pouºito p°i generování populace jako násobek normální σ (g) (g) , C(g) rozd¥lení z výrazu 2.1, £ímº hodnotu rozdíl· normalizuji na N m D¥lení
σ (g)
rozdílu
Pro uchování vztahu s hodnotami
pσ
v p°edchozích generacích je pouºito tzv. expo-
neciální vyhlazování (p°eklad z angl. exponential smoothing ) s p°edchozími hodnotami. Za
µef f = 1 (tzn. za p°edpokladu, ºe sou£et v²ech vah v selekci dává 1) je hodnota 2 (1 − cσ ) + cσ (2 − cσ ) = 1. Pro cσ = 1 si neuchovává ºádou historii a pro cσ < 1 p°i£ítá historii um¥rn¥ se zmen²ováním cσ . Pro cσ = 0 bere v potaz pouze historii, coº je nep°ípustná p°edpokladu
2
p
hodnota. Volba konstanty je
cσ
je doporu£ena jako
Je dokázáno, ºe hodnota má rozd¥lení, jako
(g+1)
pσ
cσ =
µef f +2 N +µef f +5
má za p°edpokladu náhodné selekce hodnot
m(g) a m(g+1)
N (0, I).
2.0.5.5 Výpo£et pc (0)
pσ
(0)
= 0. Hodnota pc slouºí k tzv. (g+1) (g+1) T rank-one-update výpo£tu a výpo£et se nazývá tak nebo´ pc pc má hodnost matice
Obdobn¥ jako
platí, ºe na za£átku je hodnota
pc
1.
p(g+1) = (1 − cc ) p(g) c c +
q
cc (2 − cc ) µef f
m(g+1) − m(g) (g) σ{z } |
(2.4)
evolution path Ve výrazu pro výpo£et
(g+1)
pc
zlomek
m(g+1) −m(g) σ (g)
udává jeden ze sm¥r·, jakým se nová
kovarian£ní matice má sm¥rovat, resp. v jakém sm¥ru zvý²it pravd¥podobnost výskytu (p°i£tení
(g+1) (g+1) T pc p°idá nový vlastní vektor ke kovarian£ní matici).
pc
20
KAPITOLA 2.
ANALÝZA ALGORITMU CMA-ES
Interpretací toho, ºe znaménko ve výsledné hodnot¥
(g+1) hodnotu pc p°i výpo£tu
(g+1)
pc
C(g+1) jako sou£in dvou vektor·
není podstatné je, ºe vyuºívám
(g+1) (g+1) T pc pc , takºe se znamená
vyru²í.
m(g+1) −m(g) p°idává setrva£nost cesty ke kovarian£ní σ (g) (g+1) (g+1) T (g+1) tak, aby se ve sm¥ru rozdílu matici .Pomocí sou£inu pc pc zm¥ní tvar (a sm¥r) C (g+1) posunula. zvý²ila pravd¥podobnost t¥ch hodnot, kam kam se nová st°ední hodnota m Rozdíl vzdáleností st°edních hodnot
Je dokázáno, ºe hodnota a velikost vektoru stejné rozd¥lení, jako
pc
má za p°edpokladu
cc = 1
a
N (0, C)
µef f = 1 (g)
C(g) na hodnoty kpc k g hodnota kpσ k je na velikosti
Na obrázku 2.3 je vid¥t rozdíl vlivu normy kovarian£ní matice a
(g)
pσ
. Zatímco pokles normy
C(g)
ovlivní velikost
(g)
kpc k,
tak
kovarian£ní matice nezávislá.
2.0.5.6 Výpo£et kovarian£ní matice C C
Výsledek výpo£tu kovarian£ní matice
udává sm¥ry v¥t²ích hustot pravd¥podobností nor-
málního rozd¥lení které ur£uje sm¥r kam bude sm¥°ovat dal²í generace. Tvar normálního rozd¥lení je ur£ován rozkladem na vlastní £ísla, kde po rozkladu na vlastní £ísla a vlastní vektory bude mít oproti ostatním v¥t²í pravd¥podobnost vygenerování nového jedince ve sm¥ru vlastního vektoru s nejv¥t²ím vlastním £íslem a nejmen²í pravd¥podobnost vlastní vektor s nejmen²ím vlastním £íslem. Pro lep²í £itelnost výrazu pouºiji substituci
T
µ X
}
i=1
C(g+1) = (1 − c1 − cµ ) C(g) + c1 p(g+1) p(g+1) +cµ c c |
{z
rank−one−update
(g+1)
yi:λ
(g+1)
=
xi:λ
(g+1) (g+1) (g+1)
y1:λ yi:λ {z
|
−m(g)
σ (g)
(2.5)
}
rank−µ−update Výpo£et
pc
neboli rank-one-update jsem popsal v p°edchozím odstavci, nyní vysv¥tlím
interpretaci druhého £lenu rank-µ-update ve výrazu 2.5. Obdobn¥ jako v p°íapd¥ rank-one-update, kde one udává, ºe hodnost této operace je 1, tak rank-µ-update udává hodnost
min (µ, n)
váºeného sou£tu sou£in· výsledku.
Budu p°edpokládat, ºe kovarian£ní matici po£ítám pouze z akuální populace podle vzorce
C(g+1) µ
=
µ X
(g+1)
wi xi:λ
− m(g)
(g+1)
xi:λ
− m(g)
T (2.6)
i=1 pokud mám dostate£n¥ velkou populaci vybraných jedinc·, tak pomocí rovnice 2.6 mohu odhadovat hodnotu kovarian£ní matice. Tento odhad je na obrázku tvo°a 300 jedinci, z nichº je vybráno
µ = 100
??,
kde populace je
jedinc· podle jejich tness funkce
f.
Vyvstává
ale problém s historií, nebo´ v p°ípad¥ rovnice 2.6 zahazuji v kaºdé nové generaci p°edchozí hodnoty
C(g) , coº m·ºe zp·sobit p°íli² rychlou konvergenci k lokálnímu optimu, nebo naopak
p°íli² velkou divergenci (slepé prohledávání stavového prostoru, ztráta pozitivní de nitnovsti
C),
proto ve vzorci 2.6 zohledním historii, p°i£emº v¥t²í váhu bude mít ta nedávná.
C(g+1) =
(g+1) 1 2 Cµ σ (g) P (g+1) (g+1) T cµ µi=1 wi yi:λ yi:λ
(1 − cµ ) C(g) + cµ
= (1 − cµ ) C(g) +
(2.7)
21
pc 2.5
(g+1)
||pc
||2
(g+1)
|m
(g)T
−m
(g)
/σ |
g+1
trace(C
)
1.5
1
c
2
||p(g+1)|| /m(g11)−m(g)T/σ(g)/C
2
0.5
0
0
5
10
15
20
25 30 Generace
35
40
45
50
pσ 3
||p(g+1) ||2 σ |m(g+1)−m(g)T/σ(g)| trace(Cg+1)
2
1.5
1
||p
(g+1) (g+1) (g)T (g) || /|m −m /σ |/C σ 2
2.5
0.5
0
PN
(g)
m(g+1)−m i=1 σ
0
5
10
15
20
25 30 Generace
35
40
45
50
Obrázek 2.3: Vliv rozdílu st°edních hodnot
(g) na hodnotu normy kp k a kp k pro funkci aC c c (g) p°edchozích hodnot pc a pσ (tzn. cc = 1, cσ = 1).
f (x) = xxT
p°i ignorování
22
KAPITOLA 2.
ANALÝZA ALGORITMU CMA-ES
f(x)=x2+y2
f(x)=−x−y 10
5
45
4
40
0 3 −10
35
2
30
1
−20 y
25 0 20
−30
−1 15
−2
−40
10
−3 −50
5
−4
−20
−10 x
0
−5 −5
−60
10
0 x
0
5
Obrázek 2.4: Odhad konvergence algoritmu CMA-ES pokud po£ítáme kovarian£ní matici podle vzorce 2.6. Hledáme minima dvou funkcí, které jsou na obrázku charakterizované stupn¥m ²edi. Modrou barvou vizualizuji kovarian£ní matici v dané generaci a £ervenou odpovadící st°ední hodnotu Pravý : Funkce
m
Levý : Funkce
f (x, y) = −x − y
f (x + y) = x2 + y 2
cµ je kritická, nebo´ v p°ípad¥ malých hodnot m·ºe kovarian£ní matice konvergovat cµ zanedbávat nov¥ vypo£tené sm¥ry. 2(µef f −2+ 12 ) . Empiricky je hodnota doporu£ená jako cµ (N +2)2 +µ Volba
p°íli² pomalu, nebo naopak p°i velkých hodnotách
ef f
Vlastnosti rank-µ-update p°idávají tedy k výpo£tu
C(g+1)
vlastnosti celé
µ
populace.
Spojením rank-one-update a rank-µ-update zíkáme dobré vlastnosti ze stávající populace s uchováním £ásti informace s historii, z £ehoº vznikne rovnice 2.5
2.0.5.7 Výpo£et hodnoty σ σ (g+1) udává ²í°i rozd¥lení v nové generaci. Primární veli£ina, jenº ovliv¬uje velikost (g+1) kpσ k v pom¥ru k Eukleidovské norm¥ o£ekávané hodnoty rozd¥lení kN (0, I) k. Eukleidovská norma o£ekávané hodnoty rozd¥lení je ur£ena podle [? ] √ jako kN (0, I) k = n + O n1 . Hodnota
σ (g+1) je Eukleidovská norma
(g+1)
k = kN (0, I) k
bude hodnota
σ (g+1) = σ (g)
(g+1)
k > kN (0, I) k
bude hodnota
σ (g+1) > σ (g)
(g+1)
k < kN (0, I) k
bude hodnota
σ (g+1) < σ (g)
•
Pro
kpσ
•
Pro
kpσ
•
Pro
kpσ
Konstanta
dσ
je ur£ena empiricky jako
dσ = 1 + 2 max 0,
q
µef f −1 n+1
− 1 + cσ
23
2.0.6
Vlastnosti algoritmu CMA-ES
2.0.7
Zastavovací kritéria
Krom¥ klasických zastavovacích kritérií, jako po£et vyhodnocení prom¥nných, po£et krok· algoritmu, nebo dosaºení poºadované tness m·ºe algoritmus zastavit i n¥kolik jiných kritérií, které vycházejí z jeho prom¥nných.
?
V²echna zastavovací kritéria vycházející z vlastností algoritmu podle £lánku [
] jsem
implementoval do knihovny. Následující podmínky jsou nezávislé na problému
•
NoEectAxis - Zastav jestliºe 0.1 sm¥rodatné odchylky v n¥které z komponent C(g) p°i£tené k
•
m(g)
nezm¥ní jeho hodnotu
NoEectCoord - Zastav jestliºe p°i£tení 0.2 sm¥rodatné odchylky v n¥jaké i-té osy nezm¥ní hodnotu
m(g)
v dané sou°adnici
(g)
mi
•
EqualFunValues - Zastav jestliºe 10 + d 30n λ e generacích je hodnota f (x1:λ ) rovna 0
•
ConditionCov κ=
- Zastav jestliºe £íslo podmín¥nosti kovarian£ní matice je v¥t²í neº
1014
a mají parametr, který se m·ºe resp. musí m¥nit v závilosti na °e²eném problému
•
TolFun - Zastav jestliºe 10 + d 30n λ e generacích je hodnota f (x1:λ ) men²í, nebo rovna TolFun
•
TolX
- Zastav jestliºe sm¥rodatná odchylka normálního rozd¥lení je ve v²ech osách
men²í neº hodnota
Podmínku kde
(g)
dii
je
TolX a jestliºe hodnota σ(g) p(g) c je ve v²ech osách men²í neº TolX
(g) NoEectAxis lze vyjád°it jako m(g) = m(g) +0.1d(g) ii bi kde i = (gmodn)+1,
i-té
vlastní £íslo a
(g)
bi
jeho odpovídající vlastní vektor,
i
Tuto podmínku jsem implementoval jako potomka abstraktní t°ídy
NoEffectAxisStopCondition. Podmínku
NoEectCoord lze vyjád°it jako m(g) = 0.2σ(g)
√
se v opakovan¥ st°ídá.
StopCondition
D(g) ,
kde
D(g)
t°ídou
diagonální
matice vlastních £ísel. Tuto podmínku jsem implementoval jako potomka abstraktní t°ídy
StopCondition Podmínka t°ídou
t°ídou
NoEffectCoordStopCondition.
EqualFunValues je implementována ve t°íd¥ jako potomek StopCondition
EqualFunValuesStopCondition.
Podmínku
ConditionCov
lze vyjád°it jako
(g)
(g)
d11 > κdnn .
Ve výrazu je
(g)
d11
nejv¥t²í
(g) vlastní £íslo a dnn nejmen²í vlastní £íslo £íslo. Pokud tedy tato podmínka platí, znamená to, ºe podín¥nost kovarian£ní matice je v¥t²í neº t°ídu
ConditionCovStopCondition.
κ.
Tuto podmínku jsem implementoval jako
24
KAPITOLA 2.
2.1
ANALÝZA ALGORITMU CMA-ES
Vlastnosti
Algoritmus CMA-ES je vhodný pro optimaliza£ní problémy, kde klasické metody druhého °ádu (quasi-Newton metoda, metoda sdruºených gradeitn·), které mohou selhat n¥kterých funkcích. The CMA-ES is an attractive option for non-linear optimization, if classical search methods, e.g. quasi-Newton methods (BFGS) and/or conjugate gradient methods, fail due to a non-convex or rugged search landscape (e.g. sharp bends, discontinuities, outliers, noise, and local optima). Learning the covariance matrix in the CMA-ES is analogous to learning the inverse Hessian matrix in a quasi-Newton method. In the end, any convex-quadratic (ellipsoid) objective function is transformed into the spherical function fsphere. This can improve the performance on ill-conditioned and/or non-separable problems by orders of magnitude. The CMA-ES overcomes typical problems that are often associated with evolutionary algorithms.
2.1.0.1 Vztah s Hessovou maticí CMA-ES je úzce svázán s aproximací inverzní Hessovy matice, resp. kovarian£ní matice CMA-ES aproximuje inverzní hessián, který je optimální pro problémy, její tvar funkce vhodn¥ aproximovatelný Taylorovým polynomem druhého stupn¥ a v tomto p°ípad¥ dosahuje podobných výsledk·, jako jiº zmín¥ná Newtonova metoda.
f (x) = xxT . Podle [? ] je matice identity optimální kovarian£ní matice pro hledání optima funkce f a konverguje v (1, λ)-ES. Dále T hledám minimum funkce která má tvar paraboly fE (x) = xHx a budu p°edpokládat, ºe H je symetrická a pozitivn¥ de nitní matice. Budu p°edpokládat, ºe hledám minimum funkce
Rozloºím-li matici
H = BD2 BT
na vlastní £ísla a vlastní vektory podle 1.3.3.1 budu
mít ortonormální matici vlastních vektor·
B
(tzn. spl¬ující
B = B−1 )
a diagonální matici
2 vlastních £ísel D .
fE
Dále pak p°ed dosazením hodnot budu do
transformovat hodnoty
x
xE = D−1 Bx £ímº nejd°íve oto£ím hodnoty
x
ve sm¥ru
B
jako (2.8)
a následn¥ velikosti hlavních os zmen²ím tak,
ºe si budou v²echny rovny, takºe bude platit následující rovnost
fE (x) = f (xE ) Tvrzení dokáºu. Dosadím-li do
fE
místo
x
transformaci
xE
a upravím
T xE HxE
fE (xE ) = =
−1 2 T −1 T T D B x} | {zBx} BD B D {z | xE
|
{z
D− 2
{z
|
= D−1 D−1 =
(2.9)
T }
}
H
xT E
T T T D2 BB | {z } xx BB | {z } I
xxT
I
(2.10)
2.2.
25
VARIANTY CMA-ES
p°i úprav¥ jsem p°esouval po°adí násobení matic
D, protoºe v tomto p°ípad¥ je maticové
násobení komutativní (D je diagonální) Budu-li vycáhzet z p°edpokladu, ºe pro bude ideální rozd¥lení
N
Uvedená transofmrace
0, H−1 xE
xxT
je ideální rozd¥lení
N (0, I),
tak pro
xHxT
provádí v podstat¥ to samé, co provádí Newtonova metoda,
která funkci, kterou aproximuje nahradí polynomem druhého stupn¥, který transofmuje na symetrickou parabolu, pro níº je sm¥r gradientu sm¥r p°ímý k optimu. Algoritmus CMA-ES provádí stejnou transformaci, s ohledem na to co jsem °ekl v p°edchozím odstavci, proto se ob¥ metody chovají podobn¥ a CMA-ES aproximuje kovarian£ní matici hessiánu
2.2
H−1
C hodnotu inverzního
Varianty CMA-ES
K £istému algoritmu CMA-ES existje n¥kolik variant roz²i°ujících jeho funkcionalitu. Standardní variantu lze obecn¥ ozna£it jako L-CMA-ES, kde po£áta£ní písmeno zna£í Local search, takºe od algoritmu o£ekáváme mén¥ robustní prohledávání, které poblíº n¥jakého
optima dosahuje rychlých a kvalitních výsledk·. Dal²í obecnou variantou je G-CMA-ES, pro níº o£ekáváme, kde po£áte£ní písmeno zna£í Global search, takºe od algoritmu o£ekáváme robustn¥j²í prohledávání na úkor rychlosti (a
mnohdy i výpo£etní náro£nosti).
2.2.1
IPOP-CMA-ES
Jedna z variant CMA-ES je náhrada klasického algoritmu tím, ºe p°i dosaºení ur£itých podmínek dojde k restartování v²ech parametr· algortimu do po£áte£ního stavu. Výsledkem toho m·ºe být robustn¥j²í prohledávání prostoru nebo´ s novým restartem algoritmus znovu inicializuje v²echny parametry na nové, náhododné hodnoty. Roz²í°enou a pouºívanou va-
? ], kdy p°i kaºdém restartu
riantou je i restart s nár·stem popualce tzv. IPOP-CMA-ES [ dochází k nár·stu násobku populace p·vodní.
Podmínky pro restart vycházejí ze zastavovacích podmínek. IPOP-CMA-ES se restartuje a zv¥t²í populaci v okamºiku, kdy dosáhne n¥které z podmínek, které pouºívá CMA-ES k zastavování. Z toho zárove¬ plynne, ºe zastavení IPOP-CMA-ES nem·ºeme °ídit zastavovacími kritérii klasického CMA-ES. Výraznou výhodou oproti klasickému CMA-ES je, ºe ES má mnohem lep²í výsledky pro multimodální funkce. Ve své podstatn¥ se ale jedná o velmi so skovaný random search, protoºe p°i kaºdém restartu náhodn¥ inicializuji v²echny parametry na po£áte£ní hodnoty. Jakmile se algoritmus ocitne poblíº n¥jakého optima, p°ibliºuje se k n¥mu, stejn¥ jako CMAES a kdyº p°íli² moc ryhcle konverguje, zrestartuje se, nebo´ o toto optimum prozkoumal a zkusí nalézt nové. Implementace algoritmu IPOP-CMA-ES je sou£ástí mé implementace CMA-ES do knihovny JCool.
26
KAPITOLA 2.
ANALÝZA ALGORITMU CMA-ES
σ−m−IPOP−CMAES a vypocet hodnot σ a m po restartu −0.3
−0.4 xbest −0.5
x2
σ(0) −0.6
m(0)
−0.7
σ(0)
xworst
−0.8
−0.9
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
x1
Obrázek 2.5: Ukázka výpo£tu parametr· algoritmu
σ -m-IPOP-CMA-ES
T funkce f (x) = xx p°i restartu. Polovina Eukleidovské vzdálenosti (polovina modré £áry) (0) a nová st°ední hodnota mezi nejlep²í xbest a nejhor²í xworst hodntou slouºí k výpo£tu σ (0) m po restartu pr·m¥r nejlep²í a nejhor²í hodnoty.
2.2.2
σ -m-IPOP-CMA-ES
Je varianta IPOP-CMA-ES, kterou jsem roz²í°il o nastavení po£áta£ní st°ední hodnoty po restartu jako pr·m¥r nejhor²ího a nejlep²ího jedince, tedy
m(0) =
a hodnotu
σ
xbest + xworst 2
(2.11)
po restartu jako polovinu Eukleidovské vzdálenosti mezi nejlep²ím a nejhro-
²ím jedincem, tedy
σ (0) =
kxbest − xworst k 2
(2.12)
Algoritmus se ukázal jako ryhclej²í neº jeho p·vodní varianta IPOP-CMA-ES, ale v p°ípad¥, ºe má funkce mnoho stejných lokálních optim uvázne a osciluje mezi mezi nimi a permanentn¥ se restartuje a zvy²uje populaci, £ímº i výpo£etní náro£nost. Výhodou je, ºe si pamatuje oproti IPOP-CMA-ES i ta dobrá °e²ení, proto neustále konverguje k t¥m lep²ím i po restartu, coº se o IPOP-CMA-ES °íci nedá. Dále bych dokonce doporu£il dávat men²í po£et krok·, nebo´ strategie výsledky p°i prohledávání, ale má velmi malé úsp¥chy p°i konvergenci k optim·m, pokud n¥jaké najde, práv¥ na úkor globálního prohledávání. A poslední výsledek není jako v v¥t²inou bývá v p°ípad¥ CMA-ES ten nejlep²í, ale v pr·b¥hu nalezne mnohdy velmi atraktivní °e²ení. Implementace algoritmu knihovny JCool. 3
σ -m-IPOP-CMA-ES
je sou£ástí mé implementace CMA-ES do
2.2.
27
VARIANTY CMA-ES
2.2.3
LS-CMA-ES
Dal²í ze znám¥j²ích variant je LS-CMA-ES [
? ], která vylep²uje stávající implementaci CMA-
ES o p°ímý výpo£et invezního Hessiánu v p°ípad¥, ºe je algoritmus ve vhodném stavu (je vohdné tness aproximovat kvadratickou funkcí). Lze za°adit do t°ídy LS-CMA-ES Algoritmus, jak by se dalo o£ekávat je vhodný pro funkce, které mají eliptický tvar, kde konverguje k nejlep²ím °e²ením v n¥koliknásobn¥ mén¥ iteracích, neº CMA-ES, resp. rychlost konvergence ke globálnímu optimu je p°ímo£árá. Výsledky algoritmu LS-CMA-ES v porovnání s CMA-ES ukazuje pro r·zné testovací funkce tabulka 4.3.1 (podle [
? ]) v p°íloze.
Z výsledk· v tabulce je vid¥t, ºe pro problémy, které mají tvar elipsy má algoritmus LS-CMA-ES výrazn¥ lep²í výsledky, h·°e na tom je kdyº je problém ²patn¥ aproximovatelný kvadaratickou funkcí, jako nap°íkald Rosenbrockova funkce, u níº mnohdy algoritmus nedosáhl optima.
2.2.4
ACTIVE-CMA-ES
Poslední varianta o níº se zmíním je algoritmus aktivní varianta CMA-ES, která vychází ze £lánku [
? ]. V²echny doposud zmín¥né implementace zohlednují ve výpo£tu pouze µ nej-
lep²ích jedinc·, ale algoritmus ACTIVE-CMA-ES vyuºívá k p°edcházení ²patným sm¥r·m i nejhor²í jedince. Existují dv¥ varianty jak zohled¬ovat nejhor²í jedince, jedna je zna£n¥ zjednodu²ená a m·ºe zp·sobit problémy u n¥kterých funkcí a docílí aktivního výpo£tu na-
λ − µ jedinc·m a druhá varianta ode£ítá u výpo£tu rank-µ-update λ−µ záporn¥ váºených jedinc·. Výpo£et rank-µ-update v tomto p°ípad¥ vypadá podle
stavením záporných vah t¥chto
rovnice 2.13
µ X i=1
|
(g+1) (g+1) (g+1)
y1:λ yi:λ
− {z
λ 1 X yk:λ yk:λ T µ k=λ−µ+1
(2.13)
}
rank−µ−update P°ínos algoritmu spo£ívá v men²ím mnoºství iterací, resp. podle sloupcového grafu 4.50 je mnoºství generací nutných k dosaºení poºadované hodnoty tness men²í pro v²echny funkce, v£etn¥ kvadratické funkce (funcke sphere v grafu) na které to moºná není na první pohled vid¥t.
28
KAPITOLA 2.
ANALÝZA ALGORITMU CMA-ES
Kapitola 3
Implementace algoritmu CMA-ES do knihovny JCool 3.1
Knihovna JCool
JCool je open-source knihovna pro jazyk Java pro optimalizaci spojitých funkcí. Implemetuje jak numerické (Gradient, Sdruºený gradient, Quasi-Newton,...) a p°írodou inspirované (Evolu£ní, PSO, ACO) algoritmy. Sou£ástí knihovny je sada testovacích funkcí.
3.1.1
Základní rozhraní knihovny JCool
P°edávání výsledk· a práce s výsledky o²t°ují rozhraní
Consumer
a
Producer.
Producer má
na starosti vytvá°ení výsledk·, zatímco Consumer informace p°íjímá. Volání a p°edávání výsledk· do t°ídy konzumenta má na starosti odpovídající potomek t°ídy
OptimizationMethod
. T°ídy
Consumer
a
Producer
m·ºe obsluhovat jeden z potomk· rozhraní
Solver. Solver
pracuje s producentem i konzumenetem a stará se o °ádné volání producenta a p°edávání vý-
BasicSolver,TimeoutSolvera StepSolver. Solver získat p°es metodu getResults, která vrací instanci OptimizationMethod. Potomci t°ídy Solver výsledky z výpo£tu algoritmu p°edávají jako instanci t°díy Synchronization. T°ída OptimizationMethod zapouzd°uje informace o zastavovacích podmínkách, po£et iterací algoritmu, výsledné °e²ení (potomek t°ídy Telemetry) a statistické informace t°ídy Statistics. sledk· konzumentovi. K dispozici jsou t°i t°ídy Výsledky lze ze t°ídy
3.1.2
Implementace algoritm· v knihovn¥ JCool
P°edek generické t°ídy
OptimizationMethod
, generická t°ída
Producer
slouºí k p°edávání
dosavadních výsledk· daného algoritmu. V²echny instance této t°ídy jsou producenty. T°ída má dv¥ abstraktní metody a to:
void addConsumer(Consumer consumer); T getValue();
29
30
KAPITOLA 3.
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
Obrázek 3.1: T°ídy Consumer, Producer a Solver
první metoda p°idává nové instance p°íjemc· informací o stavu algoritm·, tedy instancí abstraktní t°ídy Consumer. Pro tyto ú£ely v²ichni potomci musí implementovat metody, addConsumer , který slouºí k nastavení objektu konzumenta, kam se budou odesílat výsledky daného algoritmu. K získávání výsledk· je getValue, která vrací výsledky. Výsledky mohou být instance potomk· abstraktní generické t°ídy Telemetry, tedy
• ValueTelemetry
- uchovává stávající hodnotu
• ValuePointTelemetry hodnoty value = f (x).
value
uchovává stávající hodnotu
tness funkce
value
f.
tness funkce
f
a pozici
• ValuePointTelemetryList - uchovává stávající hodnoty valuei tness funkce f odpovídající pozice xi hodnoty valuei = f (xi ).
x
a jejich
• ValuePointTelemetryList - uchovává stávající hodnoty valuei tness 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²í z celého seznamu). na obrázku 3.2 je UML diagram t°ídy Dále má knihovna JCool rozhlaní
Telemetry
a jeho potomk·.
OptimizationMethod
, od níº jsou odvozené v²echny
t°ídy implementující algoritmy pro optimalizaci. Rozhraní má t°i metody, které musí potomek implementovat
void init(ObjectiveFunction function); StopCondition[] getStopConditions(); void optimize();
3.1.
31
KNIHOVNA JCOOL
Obrázek 3.2: Hierarchie t°íd pro telemetrie
první metoda
init
slouºí k inicializaci dané optimaliza£ní metody v potomkovi a p°e-
dání dané tness funkce
getStopConditions
f,
ObjectiveFunction. Druhá metoda StopConditions, coº je seznam zastavovacích pod-
která je potomkem t°ídy
vrací pole instancí
mínek dané metody. T°ída, která pracuje s optimaliza£ními algoritmy má potom na starosti obsluhu zastavení algoritmu, tedy volá cyklicky v²echny zastavovací podmínky, které vrátí v poli a metoda
isConditionMet t°ídy StopCondition a vrátí v závislosti na stavu, zda se má optimizezapouzd°uje slouºí svým
algoritmus zastavit, £i ne. A poslední abstraktní metoda
potomk·m k implementaci jednoho kroku optimaliza£ního algoritmu. Jedno volání metody
optimize
odpovídá jedné iteraci daného algoritmu.
To jak by m¥l m¥la vypadat obsluha obecného optimaliza£ního algoritmu v knihovn¥ JCool pomocí abstraktního p°edka
OptimizationMethodje
podrobn¥ji popsáno v níºe uve-
deném algoritmu. Algoritmy vyhodnocují svou kvalitu na základ¥ tness funkce v knihovn¥ rozhraním
Function.
f,
která je reprezentována
Pokud má tness funkce ur£ený gradient, druhou derivaci
(Hessián), nebo je n¥jak omezená, je moºné odvodit implementaci funkce kvality od t°íd
FunctionGradient, FunctionHessian, nebo FunctionBounds. V²echna tato rozhraní v sob¥ sjednocuje rozhraní ObjectiveFunction, která je i p°edávána jako parametr p°i volání funkce init odvozených t°íd od OptimizationMethod. Ne v²echny tness funkce mají známý gradient, Hessián, nebo omezení, pro tento ú£el
BaseObjectiveFunction,která v sob¥ zast°e²uje obecnou funkci a zárove¬ je ObjectiveFunction. Pokud má funkce gradient, Hessián, nebo omezení vyvolá odpovídající metodu p°edka, jinak vyvolá vyjímku. Instance t°ídy BaseObjectiveFunction slouºí k p°edávání instance tness funkce v metod¥ init.
exituje t°ída potomkem
32
KAPITOLA 3.
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
input : Instance optimaliza£ní metody method while true do
method.optimize() stopConditions = method.getStopConditions() foreach stopCondition in stopConditions do if stopCondition. isConditionMet() is true then Break;
end end end Algoritmus 3: Obsluha optiamliza£ních metod pomocí abstraktní t°ídy OptimizationMethod
Obrázek 3.3: Hierarchie t°íd, zapouzd°ující tness funkci. Potomci a p°edci t°ídy ObjectiveFunction.
3.2.
33
IMPLEMENTACE DO KNIHOVNY JCOOL
3.2
Implementace do knihovny JCool
Na za£átku jsem p°edpokládal, ºe budu implementovat pouze základní algoritmus CMAES, takºe základní my²lenka byla koncipována tak, ºe neubudu d¥dit ºádnou dal²í t°ídu z hlavní t°ídy
CMAESMethod. Ale je²t¥ p°ed tím, neº jsem za£al implementovat jsem se rozhod,
ºe doimplementuji i dal²í variantu IPOP-CMA-ES, takºe celá koncepce se roz²í°ila o dal²í t°ídu, která se mírn¥ odchylovala od výpo£tu klascikého algoritmu CMA-ES. Návrh jsem tedy roz²í°il o dal²í £ty°i t°ídy, které mají hierarchii, která je znázorn¥na na obrázku 3.4. V metod¥ je zna£né mnoºství maticových operací i z pokro£ilej²í algebry, proto jsem pro maticové operace pouºil knihovnu
java-commons-math
verze 2.1, která pln¥ vyhovovala k
algebraickým výpo£t·m a zárove¬ je u této knihovny zaru£eno, ºe se jedná o velmi stabilní, dlouhodob¥ testovanou a efektivní knihovnu. Z knihovny jsem vyuºil velké mnoºství funkcí pro operace nad maticemi a vektory, rozklad na vlastní £ísla a vlastní vektory a implementaci generátoru vektor· s normálním rozd¥lením podle kovarin£ní matice. V²echny instance
RealMatrix, RealVector
jsou t°ídy knihovny
java-commons-math.
Díky pouºití maticové
knihonvy jsem dosáhl efektivní a p°edev²ím p°ehledné implementace, nebo´ p°edpokládám, ºe ve vývoji se je²t¥ bude pokra£ovat i po obhajob¥.
3.2.1 T°ída
Základní t°ída CMAESMethod
CMAESMethod
je koncipována jako abstraktní p°edek v²ech mnou implenetovaných
variant a t°íd algoritmu CMA-ES. T°ída je abstraktní, takºe implementace £istého algoritmu CMA-ES je p°enchána t°íd¥
PureCMAESMethod.
3.2.1.1 Obecn¥ k implementaci t°ídy CMAESMethod CMAESMethod implementuje n¥které základní výpo£ty, které jsou obecné pro v²echny metody jako je výpo£et hodnot pc , pσ , σ a C, tyto základní výpo£ty jsou rozd¥leny do separátních metod, tak aby se kaºdá £lenská metoda mohla jmenovat podle toho jakou prom¥nnou po£ítá a p°ípadn¥ bylo moºné od ní odvodit pat°i£nou t°ídu, která m·ºe výpo£et provád¥t jinak. Dále pak t°ída implementuje základní podmínky pro zastavení, jako konvergence k °e²ení. Zbývající zastavovací podmínky jsem p°enechal na jejich potomcích, protoºe potomci
RestartCMAESMethod
vyuºívají tyto zastavovací podmínky jako podmínky pro restart algo-
ritmu. Celý algoritmus potom provádí metoda
optimize, která sjednocuje základní výpo£ty
hodnot jedné metody. P°edch·dce, generická t°ída
OptimizationMethod
, a jako generický parametr p°edka
jsem dal typ ValuePointListTelemetry, protoºe mám populaci více jedinc· (ValuePointListTelemetry obsahuje seznam ValuePoint instancí) K implementaci jsem pouºil jako p°edlohu £lánek [
? ] a p°edev²ím p°edlohovou variantu
algoritmu v jazyce Matlab. K porovnání jsem pouºil referen£ní kód v jazyce Matlab ze zdroje
? ]. Pokud jsem pot°eboval podrobn¥j²í a p°edev²ím aktuáln¥j²í informaci, pouºil jsem plnou ? ].
[
implementaci [
Výslednou implementaci jsem ov¥°oval porovnáváním hodnot v jednotlivých krocích p°i
?] ConditionCov.
generování stejných náhodných hodnot v·£i implementaci [ nemá v¥t²inu zastavovacích podmínek, krom¥
jejíº kód je zjednodu²en a
34
KAPITOLA 3.
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
Seznam v²ech atribut· t°ídy
CMAESMethod
s popisem a jeho ekvivaltentem v anaýze a
popisu algoritmu je v tabulce 6.1
3.2.1.2 Integrace t°ídy CMAESMethod do knihovny JCool Abstraktní p°edch·dci t°ídy
CMAESMethod,
t°ída
OptimizationMethod
a
Producer
mají 5
abstraktních metod, které implemetuji
• addConsumer
pouze nastavuje konzumenta výsledk· algoritmu. T¥lo metody tedy
nastavuje pouze £lenský
consumer
atribut.
• getValue, jenº vrací typ ValuePointListTelemetry, který jsem de noval jako generický parametr p°edchodce OptimizationMethod . • init, v níº volám metodu initializeDefaultParameters, která mi nastavuje v²echny hodnoty do iniciálního stavu, nastavím v parametru p°edanou tness funkci a n¥které její parametry.
• getStopConditions,
vrací prázdné pole instancí StopCondition
• optimize, je metoda která implementuje v n¥kolika metodách základní kroky algoritmu CMA-ES t°ída má jedinou abstraktní metodu,
setStopConditionParameters, v níº by její potomci
m¥li nastavit parametry pro zastavovací podmínky.
3.2.1.3 Inicializa£ní krok ve t°íde CMAESMethod O inicializaci algortimu se stará metoda t°ídy
ObjectiveFunction.
init, které ten kdo jí volá p°edá parametrem instanci
V inicializa£ní £ásti metody se nastavují atributy daného pro-
blému, inicializace prom¥nných algoritmu je implementovaná v metod¥
initializeDefaultParameters.
D·vodem pro£ mám rozd¥lenou inicializa£ní £ást algoritmu na dv¥ £ásti je kv·li implementacím zaloºených na restartech. Implementace CMA-ES zaloºené na restartech vyºadují inicializaci v¥t²iny atribut· na po£áte£ní hodnoty. Metoda
init
je zde p°edev²ím
pro p°edání informací o °e²eném problému z jiného kódu. Takºe metoda init sice volá initializeDefaultParameters,ale rovn¥º jí volají potomci t°ídy RestartCMAESMethod. Stejný d·vod, jako je rozd¥lení init na dv¥ metody má i rozd¥lení prom¥nné σ na dva atributy sigma a initialSigma. Pokud totiº obsluha algoritmu nastaví, ºe chce n¥jakou po£áte£ní hodnotu atributu sigma, tak jej algoritmus v pr·b¥hu výpo£tu modi kuje a p·vodní po£áte£ní hodnotu a v p°ípad¥ strategiích zloºených na restartech nemáme nikde op£áte£ní hodnotu. Metoda
initnastavuje
atribut tness funkce
function
,p°ípadn¥ nastavuje minimální,
resp. maximální meze dané funkce a nastavuje atribut nejlep²í hodnoty ve v²ech generacích
theBestPoint na hodnotu pozici s nulovými sou°adnicemi (statická metoda Point.getDefault()) a tness na Double.MAX_VALUE a naopak theWorstPoint s nejlep²í tness -Double.MAX_VALUE se stejnými sou°adnicemi jako theBestPoint aby v první generaci nahradili hodnoty theBestPoint a theWorstPoint inicializované hodnoty. Nyní popí²u mírn¥ zobecn¥nou metodu initializeDefaultParameters, °ádek po °ádku.
3.2.
1-5
35
IMPLEMENTACE DO KNIHOVNY JCOOL
Inicializuji vektor
xmeannáhodnými
hodnotami s rovnom¥rným rozd¥lením v kruhu o
pr·m¥ru rozdílu maximální a minimální moºné hodnoty tness funkce
6
initialSigma.
po£áte£ní hodnotu
8 9
sigma,
Nastavím po£áte£ní hodnoty step-size parametru
Nastavím velikost populace, prom¥nnou
λ,
tedy atribut
tedy
σ (0)
function.
na p°edem nastavenou
lambda.
Nastavím velikost velikost selektované populace, rom¥nnou
µ, tedy atribut \verbmu. Atri-
but by m¥l být p°ibliºn¥ polovina celkového mnoºství populace.
11-19
Nastavení vah selekce, podle vzorce z teorie. Nejd°íve nainicializuji hodnoty jako
rostoucí posloupnost od 0 do
21 22
µ,
potom váhy zlograritmji dekadickým logaritmem.
Vypo£ítám maximovou normu váhového vektoru Vypo£ítám efektivní hodnoty selekce
µef f
weight
pro výpo£et atributu
muEff.
jako pom¥r druhé mocniny normy k norm¥
druhé mocniny.
24
cc , tedy atribut cCumulation. Po£ítá se podle ur£eného
Vypo£ítám kumula£ní konstantu
? ].
vzorce podle z [
25
σ
Vypo£ítám konstantu pro historii
? ].
prom¥nnou
cσ ,
tedy atribut
cSigma. Po£ítá se podle
ur£eného vzorce z [
26
Vypo£ítám konstantu pro rank-1-update ného vzorce z [
27
Vypo£ítám konstantu pro rank-µ-update ného vzorce z [
28
? ].
? ].
Vypo£ítám tlumící konstantu
σ
c1 ,
tedy atribut
cRank1.
Po£ítá se podle ur£e-
cµ ,
tedy atribut
cRankMu.
Po£ítá se podle ur£e-
prom¥nnou
? ].
dσ ,
tedy atribut
dampingForSigma.
Po£ítá
se podle ur£eného vzorce z [
30
Nastavím vektor kumulace cesty atribut
31
pCumulation
z [
? ].
(0)
pc
pro výpo£et rank-1-update na nulový vektor, tedy
Nastavím vektor normalizované kumulace cesty vektor, tedy atribut
33-34
pSigma
z [
? ].
(0)
pc
pro výpo£et step-size
Nastavím sou°adné systémy pro normální rozd¥lení na kruºnici, resp.
matici identity, stejn¥ jako vektor
D
B
σ
na nulový
nastavím na
nastavím na jednotkový, takºe normální rozd¥lení
bude mít tvar kruºnice, takºe body stejn¥ vzdálené od st°ední hodnoty budou mít stejnou pravd¥podobnost.
35
Nastavím matici
C(0) ,
tedy atribut
kladu na vlastní £ísla
D
C
na matici identity. Hodnoty
a vlastní vektory
B,
1 (0)
po£ítám podle roz-
abych p°ede²el problém·m s nejednozna£-
ností rozkladu, kdybych volil jiné po£áte£ní hodnoty
36
C
D
a
B.
C− 2 , tedy atribut inverseAndSqrtC na matici identity. Hodnoty invserseAndSqrtC po£ítám podle rozkladu ze stejného d·vodu, jako po£ítám atribut C.
Nastavím matici
36
KAPITOLA 3.
38
Vypo£ítám odhad
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
L2
normy normálního rozd¥lení
N (0, I)
podle [
?]
3.2.1.4 Optimaliza£ní krok ve t°íde CMAESMethod Nyní popí²u mírn¥ zobecn¥nou metodu
optimize,
°ádek po °ádku. Metoda je implemento-
vána tak, aby m¥la minimum lokáních prom¥nných a v¥t²inu prom¥nných ukládala do svých atribut·, aby je p°ípadn¥ mohla sdílet se svými potomky.
1
Vytvo°ím novou populaci pomocí normálního rozd¥lení z parametr· vypo£tených z p·vodní generace (p°ípadn¥ inicializa£ních parametr·). Metoda
generatePopulation
vrací pole instancí ValuePoint, tedy novou ohodnocenou mno-
ºinu jedinc·.
2
Uloºím si p·vodní st°ední hodnotu z p·vodní generace, nebo´ bude pot°eba p°i výpo£tu n¥kterých dal²ích parametr·.
3
Set°ídím celou populaci. Protoºe je t°ída ValuePoint potomkem rozhraní Comparable, set°ídí se mi populace vzestupn¥.
4
Uloºím nejlep²ího a nejhor²ího jedince pro v²echny generace pokud takový existuje v nov¥ vytvo°ené generaci.
5
Pomocí metody
createMatrixFromPopulationvytvo°ím instanci nejlep²ích vybraných (µ)
jedinc· t°ídy RealMatrix z instancí ValuePoint, tak, ºe kaºdý sloupec p°edstavuje jednoho jedince. Instance t°ídy RealMatrix má
7
N
°ádk·
Kaºdý sloupec vynásobím hodnotou na odpovídajícím indexu vektoru vah
weight. Touto
operací ud¥lám ze st°ední hodnoty vybrané popualce váºenou, coº odpovádá výpo£tu prom¥nné
m(g+1)
8
Výpo£et hodnoty atributu
9
Výpo£et hodnoty
hσ
(g+1)
pSigmapσ
pomocí metody
pomocí metody
calculatePSigma.
calculateHSigma. Hodnota hσ
slouºí k udrºení
(g)
pc
,
(g) jestliºe kpσ k nabývá velkých hodnot. Tato hodnota se vyuºívá p°i výpo£tu prom¥n(g+1) (g+1) , tedy v metodách calculatePCumulation a calculateCovariance, ných pc aC kde se p°edají v parametrech.
10
Vypo£tu hodnoty prom¥nné
(g+1)
pc
pCumulationpomocí metody caculatePCumulation. xold a hodnotu hSigma, která reguluje zda bude hod-
, tedy atributu
P°edáme starou st°ední hodnotu
nota zm¥n¥na, nebo ne. Tento výpo£et pozd¥ poslouºí v kovarian£ní matici k rank-1update.
11-12
Vypo£tu vzdálenost nejlep²ích
tou
mu jedinc· z populace od st°ední hodnoty d¥lené hodn-
sigma. Výsledek bude op¥t instance t°ídy RealMatrix, tak, ºe kaºdý sloupec p°edT . yi:λ
stavuje jednoho jedince. Kaºdý sloupec odpovídá výpo£tu
3.2.
37
IMPLEMENTACE DO KNIHOVNY JCOOL
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· 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£en normalizovaných vah pro výpo£et
µef f
Norm = this.weights.getNorm (); this.muE = Math.pow (Norm, 2) / this.weights.mapPow (2).getNorm (); // inicializace koe cient· adapace
cc , cσ , c1 , cµ , dσ
// dynamické parametry strategie
pc 0), pσ , B( 0), D(0) , C(0)
this.cCumulation = (4 + this.muE / this.N) / (this.N + 4 + 2 * this.muE / 2); this.cSigma = (this.muE + 2) / (this N + this.muE + 5); this.cRank1 = 2 / (Math.pow (this.N + 1.3, 2) + this.muE ); this.cRankMu = 2 * (this.muE - 2 + 1 / this.muE ) / (Math.pow (this.N + 2, 2) + this.muE ); this.dampingForSigma = 1 + 2 * Math.maximum (0, Math.sqrt ((this.muE - 1) / (this.N + 1)) - 1) + this.cSigma; (
this.pCumulation =RealVector (this.N); this.pSigma =RealVector (this.N);
(0)
a
1 (0)
C− 2
// de nuje sou°adný systém
this.B = MatrixUtils.createRealIdentityMatrix (this.N); this.D = RealVector (this.N, 1); this.C = B.mapMultiply (MatrixUtils.createRealDiagonalMatrix (this.D.mapPow (2).toArray ())).mapMultiply (this.B.transpose ()); this.inverseAndSqrtC = this.B.mapMultiply (MatrixUtils.createRealDiagonalMatrix (this.D.toArray ())).mapMultiply (this.B.transpose ()); // odhad normy kN (0, I) k pro výpo£et dσ this.chiN = Math.sqrt (N) * (1 - 1 / (4 * N)) + (1 / (21 * Math.pow (N, 2))));
Algoritmus 4: Jeden krok metody initializeDefaultParametes t°ídy CMAESMethod
38
KAPITOLA 3.
15
Vypo£tu novou hodnotu atributu
17
Vypo£tu novou hodnotu
18
Rozklad na vlastní £ísla a vlastní matice pomocí metody
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
C,
tedy kovarian£ní matice
C(g+1)
pomocí metody
calculateCovariance. V²echny prom¥nné, které jsou nutné k výpo£tu krom¥ hSigmaa muDifferenceFromOldMean(které p°edstavují ve výpo£tu rank-1-update ) jsou atributy t°ídy CMAESMethod. sigma,
tedy step-size parametr
σ (g+1) .
calculateEigendecomposition, D(g+1) . Dále pak 1 inverseAndSqrtC,tedy prom¥nné C− 2 , která slouºí
(g+1) a diagonální matice vlastních £ísel tedy ortonormální matice B metoda po£ítá hodnotu atributu k transofrmaci
(g+1)
pSigma,tedy pσ
19
Inkrementace £íta£e po£tu generací
20
Uloºení nejlep²ího jedince do atributu
21
Nastavení atributu
(g) x1:λ
telemetrypro
bestValueInCurrentGeneration,coº
je hodnota
p°edání výsledk·. Protoºe se jedná o instanci t°ídy
ValuePointListTelemetry, p°edáváme celou populaci.
22,23,24
consumer.
P°edání výsledk· daného generace instanci
Prom¥nná
hSigmaje lokální, protoºe neuchovává svou historii, ani není pouºitelný v rámci
jiných implementací, stejn¥ Výpo£et hodnoty
hσ
je 1 jestliºe platí rovnice
(
kpσ g)k
q
1 − (1 − cσ )2(g+1)
<
√
??, jinak je rovna 0.
1 1 + n 1− 4N 21N 2
(3.1)
Metody, které po£ítají prom¥nné algoritmu:
• initializeDefaultParameters
- nastavuje v²echny prom¥nné, které algoritmus po-
ºívá k výpo£t·m na po£áte£ní hodnotu
• generatePopulation
λ prvních s normálním roz¥lením. Generování je provád¥no pomocí t°ídy CorrelatedRandomVectorGenerator z knihovny java-commons-math. - generuje novou populaci o
• calculateEigendecomposition - po£ítá rozklad na vlastní £ísla a vlastní vektory (g+1) . Rozklad je provád¥n pomocí t°ídy EigenDecomposition kovarian£ní matice C knihovny java-commons-math. • calculateCovariance • calculatePSigma-
- po£ítá novou kovarian£ní matici
po£ítá novou hodnotu
• calculatePCumulation• calculateHSigma-
(g+1)
pσ
po£ítá novou hodnotu
po£ítá hodnotu
hσ
(g+1)
pc
C(g+1)
z z
3.2.
IMPLEMENTACE DO KNIHOVNY JCOOL
population = generatePopulation () xold = xmean Arrays.sort (population) storeTheBestAndWorst (population) muBestIndividuals = createMatrixFromPopulation (population, this.Mu, this.N) // výpo£et nové váºené st°ední hodnoty
m(g+1)
this. xmean = muBestIndividuals.operate (weights) calculatePSigma (xold) hSigma = calculateHSigma () calculatePCumulation (hSigma,xold) // výpo£et y pro rank-µ-update
muDierenceVectorsFromOldMean =
calculateMuDifferenceFromOldMean (muBestIndividuals,this.xold, this.N, this.Mu,
this.stepSize)
// výpo£et nové kovarian£ní matice
C(g+1)
calculateCovariance (hSigma,muDierenceVectorsFromOldMean) (g+1) // výpo£et nové hodnoty σ calculateSigma () calculateEigendecomposition ()
this.currentGeneration =this.currentGeneration +1 bestValueInCurrentGeneration = population [0].getValue (); telemetry = Arrays.asList (population); if consumer!= null then consumer.notifyOf (this)
end Algoritmus 5: Jeden krok v kódu metody optimize t°ídy CMAESMethod
39
40
KAPITOLA 3.
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
• calculateSigma-
po£ítá novou hodnotu
σ (g)
V jednotlivých metodách probíhají zna£n¥ komplikované maticové operace. Pomocné metody, které slouºí k výpo£t·m prom¥nných algoritmu:
(g) T
(g) T
• calculateMuDifferenceFromOldMean - po£ítá vzdálenost matice populace x1:λ , . . . xµ:λ od st°ední hodnoty
m(g)
σ (g) . Statická (g+1) . matice C
d¥lené stepsize atributem
po£tu rank-µ-update p°i po£ítání kovarian£ní
metoda pomáhá vý-
• createMatrixFromPopulation - vytvá°í z µ
(g) T (g) T vybraných jedinc· matici x1:λ , . . . xµ:λ .
Statická metoda pomáhá p°i celkovém zjednodu²ování výpo£t·.
• triu
toTriu. Statická metoda computeEigendecomposition v níº zaru£uje symetrii (g+1) = B(g+1) D2 (g+1) B(g+1) T rozkladu na C
- vrací horní troj·helníkovou matici ze zadané matice
se pouºívá p°i výpo£tu v metod¥ kovarian£ní matice p°i jejím
zbývající nepopsané metody jsou jiº popsané a slouºí k nastavování parametr· z GUI, nebo k informování o výsledcích a jiº jsem je d°íve popsal.
3.2.2 T°ída
T°ída RestartCMAESMethod
RestartCMAESMethod
je koncipována jako abstraktní p°edek v²ech mnou implemen-
tovaných variant a t°íd algoritmu CMA-ES zaloºených na restartech. Takºe obsahuje implementace obsluh restart· algoritmu. Odvozená t°ída musí implementovat podmínky pro restart a novou hodnotu výpo£tu prom¥nné po restartu
λ,
protoºe práv¥ tyto dv¥ v¥ci jsou
podstatou restartovacího algoritmu.
3.2.2.1 Obecn¥ k implementaci t°ídy RestartCMAESMethod T°ída
RestartCMAES
roz²i°uje abstraktního p°edka
CMAESMethodo
následující metody:
abstract void calculateLambda(); abstract boolean isRestartConditionsMet(); void restart(); public void optimize(); int getRestartCounter() p°i£emº roz²i°uje chování metody
optimize
o kontrolu, zda nebyla v práv¥ prob¥hlé
iteraci spln¥na n¥která z restartovacích podmínek. Vyvolání restartu ssebou obná²í volání metod
CMAESMethod(viz.
initializeDefaultParametersp°edka
popis) , která inicializuje v²echny prom¥nné pro výpo£et algoritmu na
λ po restartu (IPOP-CMA-ES po násobek increasePopulationMultiplier)
po£áte£ní hodnotu a metodu pro p°epo£et parametru restartu zvy²uje mnoºství populace o n¥jaký
calculateLambda.
3.2.
IMPLEMENTACE DO KNIHOVNY JCOOL
41
To, zda jsou restartovací podmínky spln¥ny je pln¥ na benevolenci potomk·, nebo´ im-
isRestartConditionMet. PodrobIPOPCMAESMethod, která tuto metodu implemenimplementovat zm¥nu populace λ po restartu, tedy metodu
plementace této metody je startosí potomk· v metod¥ n¥ji rozeberu tuto metodu u popisu t°ídy tuje. Stejn¥ tak potomek musí
calculateLambda. getRestartCounter, metody restart).
Poslední metoda je (tedy po£et volání
restartCounter
která vrací mnoºství jiº provedených restart·
restartCounter +1
+=
calculateLambda() initializeDefaultParameters()
Algoritmus 6: Obsluha jednoho restartu restartovací strategie
super.optimize()
if
isRestartConditionsMet() restart()
then
end Algoritmus 7: Obsluha jednoho optimaliza£ního kroku instance restartovací strategie 3.2.3
T°ída IPOPCMAESMethod
T°ída IPOPCMAESMethod implementuje abstraktní t°ídu CMAESMethod, kde svému p°edkovi implementuje restartovací podmínky, které jsou shodné s podmínkami pro zastavení t°ídy
PureCMAESMethod.
Jedná se o tyto podmínky:
•
NoEectAxis v instanci noEffectToAxisStopCondition t°ídy NoEffectAxisStopCondition.
•
NoEectCoord v instanci noEffectToAxisStopCondition t°ídy NoEffectAxisStopCondition.
•
EqualFunValues v instanci equalFunValuesStopCondition t°ídy EqualFunValuesStopCondition.
•
ConditionCov v instanci conditionCovStopCondition t°ídy ConditionCovStopCondition.
•
TolFun v instanci tolFunStopCondition t°ídy TolFunStopCondition.
•
TolX v instanci tolXStopCondition t°ídy TolXStopCondition.
•
instance t°ídy
SimpleStopCondition,
coº je obecná zastavovací podmínka která dete-
kuje konvergenci tness .
increasePopulationMultiplier, která udává násobek λ calculateLambda, která je volána p°i restart.
T°ída má jednu prom¥nnou
po restartu. Tento atribut pouºit p°i volání metody kaºdém restartu metodou
Metody jsou následující
42
KAPITOLA 3.
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
void init(ObjectiveFunction function) void setStopConditionParameters() void optimize() boolean isRestartConditionsMet() void restart() void calculateLambda() init se stará pouze o správné po£áte£ní nastavení parametr· v²ech restartovacích podmínek a volání metody initsvého p°edka. Metoda setStopConditionParameters ned¥lá nic, protoºe t°ída IPOPCMAESMethodnemá Metoda
ºádné zastavovací podmínky, krom¥ jedné nad°azené (která bu¤ omezuje £as, nebo mnoºství iterací, ale její obsluhu má pln¥ v kompetencích volající). Metoda
optimize
se stará o volání jednoho kroku algoritmu a p°edání stavových pro-
m¥nných pro restartovací podmínky. O kontrolu zda, je restartovací podmínka spln¥na se
optimize v RestartCMAESMethod pomocí volání isRestartConditionsMet. Metoda isRestartConditionsMetvrací bu´ true, je-li alespo¬ jedna ze zmín¥ných podmínek spln¥na, jinak vrací false. Metoda restart nastavuje stejn¥ jako initv²echny restartovací podmínky do po£áte£-
stará metoda
ního stavu .
3.2.4 T°ída
T°ída PureCMAESMethod
PureCMAESMethod
CMAESMethod, kde svému p°edkovi CMAESMethod implementovat, kv·li restartova-
implementuje abstraktní t°ídu
p°idává zastavovací podmínky, které nem·ºe
cím podmínkám (jakmile by byla spln¥na restartovací podmínka, byla by spln¥na i podmínka
CMAESMethod by mohl výpo£et zastavit) . Zbytek chování jsem p°enechal PureCMAESMethod implementuje následující meteody:
zastavovací a p°edek p°edkovi. T°ída
void init(ObjectiveFunction function) void optimize() void setStopConditionParameters() CMAESStopCondition[] getStopConditions() T°ída implementuje v²echny známé zastavovací podmínky, které jsou:
•
NoEectAxis v instanci noEffectToAxisStopCondition t°ídy NoEffectAxisStopCondition.
•
NoEectCoord v instanci noEffectToAxisStopCondition t°ídy NoEffectAxisStopCondition.
•
EqualFunValues v instanci equalFunValuesStopCondition t°ídy EqualFunValuesStopCondition.
•
ConditionCov v instanci conditionCovStopCondition t°ídy ConditionCovStopCondition.
•
TolFun v instanci tolFunStopCondition t°ídy TolFunStopCondition.
•
TolX v instanci tolXStopCondition t°ídy TolXStopCondition.
3.2.
IMPLEMENTACE DO KNIHOVNY JCOOL
43
Obrázek 3.4: Základní t°ídní hierarchie implmenetace algoritmu CMA-ES
•
instance t°ídy
SimpleStopCondition,
coº je obecná zastavovací podmínka která dete-
kuje konvergenci tness .
Metoda
init se stará pouze o správné po£áte£ní nastavení parametr· v²ech zastavovacích initsvého p°edka.
podmínek a volání metody
optimize se stará o volání jednoho kroku algoritmu. Metoda volá svého potomka CMAESMethod a následn¥ nastavuje parametry zastavovacích podmínek po výpo£tu voláním metody setStopConditionParameters. Metoda
ve t°íd¥
Metoda
setStopConditionParameters nastavuje v²echny zastavovací podmínky po prooptimize).
vedení jednoho kroku algoritmu (volání metody Metoda
getStopConditions
vrací pole v²ech zastavovacích podmínek uvedené na p°ed-
chozím vý£tu, tak aby volající mohl ov¥°it, zda n¥jaká z nich nebyla spln¥na (metoda
isConditionMet).
44
KAPITOLA 3.
3.2.5
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
Implementace zastavovacích podmínek
? ], který po-
P°i implementaci zastavovacích podmínek jsem vycházel p°edev²ím z £lánku [ dorbn¥ vysv¥tluje kaºdou zastavovací podmínku. U podmínek jsem pouºil známou vycházel z implementace [
NoEffectAxis a NoEffectCoord
? ], kde jsou podmínky velmi dob°e popsané.
V²echny mnou implementované zastavovací podmínky jsou potomky rozhraní
CMAESStopCondition,
aby nebyli zam¥n¥ny s jinými zastavovacícmi podmínkami.
use,kterým m·ºu danou zastavovací podvypnout, nebo zapnout. P°i volání metody isConditionMet se ov¥°uje p°ed vyhodkritéria zda není hodnota use nastavena na true.
V²echny zastavovací podmínky mají atribut mínku nocení
3.2.5.1 Podmínka NoEectAxis Zastavovací podmínku NoEectAxis jsem implementoval t°ídou Podmínka pracuje s vlastnostmi prom¥nných p°edávám v metod¥
D(g) , B(g) , m(g)
NoEffectAxisStopCondition. g . V²echny tyto prom¥nné
a
setValues.
De nice Zastavovací podmínka NoEectAxis: Zastav jestliºe 0.1 sm¥rodatné odchylky v n¥které z komponent
C(g)
p°i£tené k
m(g)
nezm¥ní jeho hodnotu
Je nutné, aby se postupn¥ st°ídali v²echny komponenty, £ehoº lze docílit tím, ºe spo£ítám zbytek po d¥lení z této generace po vyd¥lení po£tu moºných komponent. Podmínku lze vyjád°it tak, ºe porovnánáme aktuální st°ední hodnotu se sou£tem st°ední hodnoty s vybraným vlastním vektorem po tom, co vynásobíme 0.1 odmocniny z vlastního £ísla. Matematicky lze vyjád°it výpo£et sm¥rodatné odchylky podle rovnice 3.2:
(g)
(g)
mstddev = m(g) + 0.1bi takºe lze
NoEffectAxisvyjád°it
q
(g)
dii
(3.2)
kódem jako:
eigenIndex = currentGeneration mod N; xmeanAfterAddingStdDev = xmean.add ( B.getColumnVector (eigenIndex).mapMultiply ( standardDeviationRatio * Math.sqrt ( D.getEntry (eigenIndex)))); if xmean.equals ( xmeanAfterAddingStdDev) then return true;
end return false; Algoritmus 8: Implementace zastavovací podmínky NoEectAxis
3.2.5.2 Podmínka NoEectCoord Zastavovací podmínku NoEectCoord jsem implementoval t°ídou
(g) , m(g) , a Podmínka pracuje s vlastnostmi prom¥nných D dávám v metod¥
setValues.
NoEffectCoordStopCondition.
σ (g) . V²echny tyto prom¥nné p°e-
3.2.
45
IMPLEMENTACE DO KNIHOVNY JCOOL
De nice Zastavovací podmínka NoEectCoord: Zastav jestliºe p°i£tení 0.2 sm¥rodatné odchylky v n¥jaké
i-té
osy nezm¥ní hodnotu
m(g)
v dané sou°adnici
(g)
mi
Podmínku lze vyjád°it podobn¥ jako v p°ípad¥ NoEectAxis porovnáním výpo£tu odmocniny vektoru vlastních £ísel násobených
0.2σ (g) .
Matematicky lze výpo£et p°i£tení sm¥-
rodatné odchylky podle rovnice 3.3:
p
(g)
mstddev m(g) + 0.2σ (g) D(g) takºe lze
NoEffectCoordvyjád°it
(3.3)
kódem v Jav¥ jako:
if D.mapSqrt().mapMultiply ( atrributeSigma * 0.2).add ( xmean).equals ( xmean) then return true; end return false; 3.2.5.3 Podmínka EqualFunValues Zastavovací podmínku EqualFunValues jsem implementoval t°ídou
Podmínka pracuje hodnotami
f
(g) x1:λ
EqualFunValuesStopCondition.
30n v 1 . . . 10 + d λ e generacích. Fitness hodnoty nejlep-
²ích jedinc· v generacích jsem ukládal to instance
ArrayList
a zárove¬ jsem p°i£í-
tal p°idávanou hodnotu tness k prom¥nné, tak abych zabránil nutnosti s£ítat celý seznam uloºených
10 + d 30n λ e
De nice
Zastavovací podmínka EqualFunValuesStopCondition: Zastav jestliºe
generacích je hodnota
tness.
f (x1:λ )
rovna 0
currentGeneration
V atributu
10 + d 30n λ e
uchávávám práv¥ probíhající generaci a jeho hodnotu
setValues. Dále pak atribut historyDepth, v 30n 10+d 30n e . Atribut currentSumOfHisotry ukládá sou£et 10+d λ λ e posledních generací, nebo men²í po£et generací. Seznam history pouºívám k uchovávání v²ech hodnot p°edaných metodou setValuesa pouºívám tento atribut k ode£ítání historie 30n pokud po£et generací p°esko£í 10 + d λ e. inkrementuji pokaºdé, kdyº volám metodu
nemº uchovávám hodnotu
setValuesp°edá metoda setStopConditionParameters tness nejlep-
P°i volání metody
(g) x1:λ
30n f v generaci g . Pokud je g < 10+d λ e (tzn. podmínka currentGeneration≤ historyDepth ) sta£í pouze p°idat hodnotu na seznam history a p°i£íst k atributu currentSumOfHistoryh (g) f x1:λ . Pokud je ov²em po£et generací v¥t²í, ode£tu od hodnoty currentSumOfHistoryprvní ²ího jedince
hodnotu v seznamu Podmínku
historya
p°i£tu hodnotu
EqualFunValueslze
(g)
f x1:λ
.
vyjád°it kódem v Jav¥ jako:
46
KAPITOLA 3.
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
if currentGeneration <= historyDepth then
history.add (currentBestFitness); currentSumOfHisotry += currentBestFitness;
end else
currentSumOfHisotry += currentBestFitness- history.get ((currentGeneration- 1) mod historyDepth); history.set (currentGeneration mod historyDepth, currentBestFitness);
end
3.2.5.4 Podmínka ConditionCov Poslední ze statických zastavovacích podmínek je ve t°íd¥
ConditionCovStopCondition.
De nice
ConditionCov, jejíº implementace se skrývá
Zastavovací podmínka ConditionCov: Zastav jestliºe £íslo podmín¥nosti kovari-
an£ní matice je v¥t²í neº
κ = 1014
Pokud známe nejmen²í a nejv¥t²í vlastní £íslo matice n¥nosti nap°. podle [
κ,
κ.
d11 > κdnn men²í neº κ
Pokud platí
neplatí-li pomín¥nost je
Podmínku
nemusíme po£ítat £íslo podmí-
? ], ale sta£í porovnat nejv¥t²í vlastní £íslo s nejmen²ím vlastním £íslem
vynásobeným hodnotou v¥t²í, neº
C,
ConditionCovlze
je £íslo podmín¥nosti matice
C(g)
také
vyjád°it kódem v Jav¥ jako:
Arrays.sort (eigenvalues); if eigenvalues [0] > maxMultiplyOfMinEigenvalue
then return true; end return false;
*
eigenvalues [ eigenvalues.length-
1]
3.2.5.5 Podmínka TolX TolXnení obecn¥ platná pro v²echny funkce, ale m·ºe být závislá na problému. tolXje proto nutné nastavit na n¥jakou poºadovanou hodnotu. Podmínka je implementována ve t°íd¥ TolXStopCondition.
Podmínka
Její atribut
De nice Zastavovací podmínka TolX: Zastav jestliºe sm¥rodatná odchylka normálního roz(g) p(g) je ve v²ech osách d¥lení je ve v²ech osách men²í neº hodnota TolX a jestliºe hodnota σ c men²í neº TolX První kritérium, tedy zda je sm¥rodatná odchlka ve v²ech osách men²í neº hodnota
TolX
lze matematicky vyjád°it tak, ºe jsou-li v²echny prvky na hlavní diagonále kovarian£ní matice
C(g)
vynásobené step-size v dané generaci
σ (g)
men²í neº
TolX podmnka je spln¥na
3.2.
47
IMPLEMENTACE DO KNIHOVNY JCOOL
Podmínku
TolXlze
vyjád°it kódem v Jav¥ jako:
pcAndSigma = pc.mapMultiply (attributeSigma).getData();
for i=1 to N do if pcAndSigma [] > tolX then return false; end end
stdDevDistribution = diagC.mapMultiply (attributeSigma).getData(); for i=0 to
do
N
if stdDevDistribution [i] > tolX then return false; end return true; end 3.2.5.6 Podmínka TolFunHistory Podmínka
TolFunHistoryje
TolXplatná pro v²echny funkce, ale být závislá na EqualFunValuesStopCondition s rozdílem, ºe sou£et
stejn¥ jako
problému. Podmínka je identická s
10 + d 30n λ e generacích m·ºe být r·zný od 0 a podmínka je spln¥na pokud je sou£et mén¥ neº atribut tolFun.
48
KAPITOLA 3.
IMPLEMENTACE ALGORITMU CMA-ES DO KNIHOVNY JCOOL
Kapitola 4
Experimenty 4.1
Informace k experiment·m
Na algoritmu jsem provedl °adu experiment·. První experimenty spo£ívali v porovnání algoritmu CMA-ES pro v²echny dostupné metody v knihovn¥ JCool, které ke dni 11. kv¥tna 2011 byli v dispozici a to samé platí pro dostupné funkce, kterých bylo celkem 35 a jsou uvedeny v prvním sloupci tabulky 4.1. Druhá série experiment· spo£ívala v zji²t¥ní pr·b¥hu u vybraných funkcí algoritmu CMA-ES.
4.1.1
Získávání infomrací o pr·b¥hu p°i porovnávání s ostatními metodami
Pro získávání informací o pr·b¥hu jednotlivých metod není explicitn¥ vytvo°ena ºádná t°ída,
StepSolver, který StepStorage, která slouºila k
Solver
takºe jsem si vytvo°il vlastní solver
implementoval rozhraní
zárove¬ d¥dil od mé t°ídy
uchovávání mezivýsledk· o nejlep-
a
²ích a nejhor²ích jedincích v jednotlivých generacích (pokud se jednoalo o metodu, která pouºívala více jak jednu hodnotu k výpo£tu resp. m¥la
ValuePointListColoredTelemetry
ValuePointListTelemetry,
nebo
telemetrii), nebo jako nejhro²ího a zárove¬ nejlep²ího
jedince (pokud se jednalo o metodu, která naopak pouºívá jednu hodnotu k výpo£tu, resp. m¥la
ValuePoint
telemetrii). Ve t°íd¥
StepSolverjsem
implementoval metodu
solve
tak,
aby si v kaºdém kroku uloºila pr·b¥h metody a zárove¬ ov¥°ila, zda nebyl p°ekro£en maximální po£et 1000 iterací. P°i výpo£tech selhala funkce Hump, která selhala na výpo£tu optimaliza£ní metody
LevenbergMarquardtMethod,
proto pro ní nemám graf o pr·b¥hu.
Nár·st populace po restartu
4.1.2
∆λ
je pro IPOP-CMA-ES algoritmus nastavena na 2.
Diskuze o výsledcích experiment·
Ve v¥t²in¥ testovacích funkcí dosáhl algoritmus CMA-ES lep²ích výsledk· neº jeho konkurentni. Místy se sice stalo, ºe algoritmus uvázl v lokálním minimu, jako nap°íklad v p°ípad¥ Levyho 3 a Levyho 5 funkce, kde algoritmus CMA-ES skon£il výpo£et po 20 iteracích protoºe byla spln¥na zastavovací podmínka
EqualFunValues,
49
ale algoritmus IPOP-CMA-ES
50
KAPITOLA 4.
EXPERIMENTY
jeho hor²í výsledky vykompenzoval hned po prvním restartu, kdy se dostal do globálního optima kde prob¥hlo pro Levyho 3 funkci 7 restart· a pro Levyho 5 funkci 6 restart·. Na v¥t²in¥ pr·b¥h· je vid¥t, kdy se algoritmus IPOP-CMA-ES restartoval. Restart se m·ºe projevit náhlým nár·stem, resp. poklesem pr·b¥hu tness funkce. Velmi dob°e je to vid¥t nap°íklad na Langermannov¥ funkci, kde prob¥hlo velmi rychle za sebou po cca. 10 generacích 7 restart·, ale po restartu se algoritmus vrátil k p·vodnímu globálnímu optimu a jediná metoda, která podává stejn¥ dobré výsledky je API. Naopak u n¥kterých metod m¥l IPOP-CMA-ES problémy s velkým po£tem restart·, coº ukazuje Shekelova funkce kde u 20 generace zna£né mnoºství restart· a algoritmus hodn¥ osciluje. I p°es to, ºe metoda je metoda vhodná spí²e na funkce unimodální, výsledky ukazují, ºe nemá problémy ani s multimodálními funkcemi, jako je Ackleyova nebo Rastriginova funkce.
4.1.3
Získávání informací o pr·b¥hu výpo£tu algoritmu CMA-ES
4.1.
51
INFORMACE K EXPERIMENTM
Funkce
f (x)
Pr·b¥h
f (x)
Pr·b¥h CMA-ES
Pr·b¥h tness s ostatními algoritmy
Ackley
7.1
4.32
4.1
Beale
7.2
4.33
4.2
Bohachevsky
7.3
4.34
4.3
Booth
7.4
4.35
4.4
Branin
7.5
4.36
4.5
DixonPrice
?? ??
Easom
7.8
Colville
?? ??
4.39
Hartmann
?? ?? ??
Himmelblau
7.10
4.41
Hump
7.11
4.42
GoldsteinPrice Griewangk
Levy5
?? ?? ?? ??
Matyas
7.12
Langermann Levy Levy3
4.6 4.7 4.8
?? ?? ??
4.10 4.12
?? ?? ?? ??
4.43
4.11 4.13 4.16 4.14 4.15 4.17
Rana
?? ?? ?? ?? ??
Rastrigin
7.13
4.44
4.23
Rosenbrock
7.14
4.45
4.24
Schwefel
7.15
4.46
4.25
Michalewicz Perm Powell PowerSum
?? ?? ?? ?? ??
4.9
4.19 4.20 4.21 4.22
Shubert
?? ??
Sphere
7.16
4.47
4.28
Trid
4.29
Shekel
?? ??
4.17
4.26 4.27
7.17
??
4.48
Whitley Zakharov
7.18
4.49
4.31
Constant
7.6
4.37
-
??
4.30
Tabulka 4.1: Testovací funkce, nad nimiº byli provedeny expermenty. V prvním sloupci je název odpovídající funkce, ve druhém sloupci je £íslo obrázku na nemº je zanesen pr·b¥h funkce, na t°etím £íslo obrázku na nemº je vyzna£en pr·b¥h výpo£tu algoritmu prom¥nných algoritmu v pr·b¥hu výpo£tu a ve t°etím sloupci porovnání v²ech dostupných algoritm· v knihovn¥ na odpovídající testovací funkci. V p°ípad¥, ºe je v tabulce - znamená to, ºe výpo£et byl zbyte£ný, nebo se pr·b¥hu vyskytla n¥jakýá chyba
52
KAPITOLA 4.
EXPERIMENTY
Ackley 25 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
20
Fitness f(x)
15
10
5
0
−5
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.1: Pr·b¥h tness pro Ackleyovu funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
6
14
ValuePoint)
nebo jediného
v²ech metod v knihovn¥ JCool.
Beale
x 10
AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
12
10
Fitness f(x)
ValuePointList),
8
6
4
2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.2: Pr·b¥h tness pro Bealeho funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.1.
53
INFORMACE K EXPERIMENTM
Bohachevsky 250 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
200
Fitness f(x)
150
100
50
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.3: Pr·b¥h tness pro Bohachevskyho funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Booth 700 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
600
Fitness f(x)
500
400
300
200
100
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.4: Pr·b¥h tness pro Booth funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
54
KAPITOLA 4.
EXPERIMENTY
Branin 300 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
250
Fitness f(x)
200
150
100
50
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.5: Pr·b¥h tness pro Branin funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
5
12
ValuePoint)
nebo jediného
v²ech metod v knihovn¥ JCool.
Colville
x 10
AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
10
8
Fitness f(x)
ValuePointList),
6
4
2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.6: Pr·b¥h tness pro Colville funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.1.
55
INFORMACE K EXPERIMENTM
5
2
DixonPrice
x 10
AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
1.8
1.6
1.4
Fitness f(x)
1.2
1
0.8
0.6
0.4
0.2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.7: Pr·b¥h tness pro Dixon-Priceovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Easom 0.4 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
0.2
Fitness f(x)
0
−0.2
−0.4
−0.6
−0.8
−1
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.8: Pr·b¥h tness pro Easomovu funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
56
KAPITOLA 4.
7
GoldsteinPrice
x 10
18
AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
16
14
12
Fitness f(x)
EXPERIMENTY
10
8
6
4
2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.9: Pr·b¥h tness pro Goldstein-Price funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Griewangk 2 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
1.8
1.6
1.4
Fitness f(x)
1.2
1
0.8
0.6
0.4
0.2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.10: Pr·b¥h tness pro Griewangkovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.1.
57
INFORMACE K EXPERIMENTM
Hartmann 0 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
−0.5
−1
Fitness f(x)
−1.5
−2
−2.5
−3
−3.5
−4
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.11: Pr·b¥h tness pro Hartmannovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Himmelblau 180 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
160
140
Fitness f(x)
120
100
80
60
40
20
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.12: Pr·b¥h tness pro Himmelblauovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
58
KAPITOLA 4.
EXPERIMENTY
Langermann 0.8 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
0.6
0.4
0.2
Fitness f(x)
0
−0.2
−0.4
−0.6
−0.8
−1
−1.2
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.13: Pr·b¥h tness pro Langermannovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Levy3 100 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
50
Fitness f(x)
0
−50
−100
−150
−200
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.14: Pr·b¥h tness pro Levyho 3 funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.1.
59
INFORMACE K EXPERIMENTM
Levy5 200 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
150
100
Fitness f(x)
50
0
−50
−100
−150
−200
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.15: Pr·b¥h tness pro Levyho 5 funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Levy 1.4 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
1.2
Fitness f(x)
1
0.8
0.6
0.4
0.2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.16: Pr·b¥h tness pro Levy funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
60
KAPITOLA 4.
EXPERIMENTY
Matyas 0.7 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
0.6
Fitness f(x)
0.5
0.4
0.3
0.2
0.1
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.17: Pr·b¥h tness pro Matyas funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Michalewicz 0.5 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
0
Fitness f(x)
−0.5
−1
−1.5
−2
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.18: Pr·b¥h tness pro Michalewicz funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.1.
61
INFORMACE K EXPERIMENTM
Perm 1200 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
1000
Fitness f(x)
800
600
400
200
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.19: Pr·b¥h tness pro Perm funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Powell 350 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
300
Fitness f(x)
250
200
150
100
50
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.20: Pr·b¥h tness pro Powellovu funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
62
KAPITOLA 4.
4
14
PowerSum
x 10
AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
12
10
Fitness f(x)
EXPERIMENTY
8
6
4
2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.21: Pr·b¥h tness pro kvadratickou funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
8
1
ValuePoint)
nebo jediného
v²ech metod v knihovn¥ JCool.
Rana
x 10
AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
0
−1
−2 Fitness f(x)
ValuePointList),
−3
−4
−5
−6
−7
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.22: Pr·b¥h tness pro Ranaovu funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.1.
63
INFORMACE K EXPERIMENTM
Rastrigin 45 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
40
35
Fitness f(x)
30
25
20
15
10
5
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.23: Pr·b¥h tness pro Rastrigin funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Rosenbrock 300 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
250
Fitness f(x)
200
150
100
50
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.24: Pr·b¥h tness pro Rosenbrockovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
64
KAPITOLA 4.
7
0.5
Schwefel
x 10
AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
0
−0.5
−1
Fitness f(x)
EXPERIMENTY
−1.5
−2
−2.5
−3
−3.5
−4
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.25: Pr·b¥h tness pro Schwefelovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Shekel 0 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
−2
Fitness f(x)
−4
−6
−8
−10
−12
−14
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.26: Pr·b¥h tness pro Shekelovu funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.1.
65
INFORMACE K EXPERIMENTM
Shubert 250 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
200
150
Fitness f(x)
100
50
0
−50
−100
−150
−200
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.27: Pr·b¥h tness pro Shubertovu funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList
), nebo jediného
v²ech metod v knihovn¥ JCool.
Sphere 2.5 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
2
Fitness f(x)
1.5
1
0.5
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.28: Pr·b¥h tness pro Sphere funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
66
KAPITOLA 4.
EXPERIMENTY
Trid 4 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
3
Fitness f(x)
2
1
0
−1
−2
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.29: Pr·b¥h tness pro Tridovu funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Whitley 350 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
300
Fitness f(x)
250
200
150
100
50
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.30: Pr·b¥h tness pro Whitleyovu funkci nejlep²ího jedince
(g)
x1:λ
(pokud metoda pouºívá telemetrii
jedince (pokud metoda pouºívá telemtrii
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
4.2.
67
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
Zakharov 12 AACA ACO API CACO CMAES DACO DifferentialEvolution HGAPSO OrthogonalSearch PALDifferentialEvolution PBIL Powell PSO QuasiNewton Random SADE SteepestDescent PureCMAES IPOPCMAES
10
Fitness f(x)
8
6
4
2
0
0
20
40
60 Generace (g)
80
100
120
Obrázek 4.31: Pr·b¥h tness pro Zakharov funkci
(g) nejlep²ího jedince x1:λ (pokud metoda pouºívá telemetrii jedince (pokud metoda pouºívá telemtrii
4.2
ValuePoint)
ValuePointList),
nebo jediného
v²ech metod v knihovn¥ JCool.
Kroky algoritmu pro vybrané funkce
68
KAPITOLA 4.
EXPERIMENTY
ackley
5 4
x2
3 2 1 0 −1 −1
0
1
2
3
4
5
3
4
5
x1
5 4
x2
3 2 1 0 −1 −1
0
1
2
3
3
2
2
||σ(g)||
(g)
||C ||
x1
1 0
0
500 Generace (g)
1000
1 0
0
500 Generace (g)
1000
Obrázek 4.32: Pr·b¥h algoritmu pro Ackleyovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
4.2.
69
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
beale
3 2.5
x
2
2 1.5 1 0.5 0 0
0.5
1
1.5
2
2.5
3
2
2.5
3
x1
3 2.5
x
2
2 1.5 1 0.5 0 0
0.5
1
1.5 x1 2 1.5
1
||σ(g)||
||C(g)||
1.5
0.5 0
1 0.5
0
500 Generace (g)
1000
0
0
500 Generace (g)
1000
Obrázek 4.33: Pr·b¥h algoritmu pro Bealeho funkci ve dvou rozm¥rech Globální minimum je
x∗ = (3, 0.5), f (x∗ ) = 0. ervenou barvou je vyzna£ena váºená st°ední σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
70
KAPITOLA 4.
EXPERIMENTY
bohachevsky 1 0 −1
x2
−2 −3 −4 −5 −6 −7 −8 −8
−7
−6
−5
−4
−3 x1
−2
−1
0
1
−7
−6
−5
−4
−3 x1
−2
−1
0
1
1 0 −1
x2
−2 −3 −4 −5 −6 −7
3
6
2
4
||σ(g)||
(g)
||C ||
−8 −8
1 0
0
500 Generace (g)
1000
2 0
0
500 Generace (g)
1000
Obrázek 4.34: Pr·b¥h algoritmu pro Bohachevskyho funkci prvního druhu ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x) = 1. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
4.2.
71
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
booth 6 5
x2
4 3 2 1 1
2
3
4
5
6
4
5
6
x1 6 5
x2
4 3 2 1 1
2
3 x1 2 1.5
1
||σ(g)||
||C(g)||
1.5
0.5 0
1 0.5
0
500 Generace (g)
1000
0
0
500 Generace (g)
1000
Obrázek 4.35: Pr·b¥h algoritmu pro Booth funkci ve dvou rozm¥rech Globální minimum je
x∗ = (1, 3), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
72
KAPITOLA 4.
EXPERIMENTY
branin 8 6
x2
4 2 0 −2 −4 −4
−2
0
2 x1
4
6
8
−4
−2
0
2 x1
4
6
8
8 6
x2
4 2 0 −2
2
4
1.5
3 ||σ(g)||
||C(g)||
−4
1 0.5 0
2 1
0
500 Generace (g)
1000
0
0
500 Generace (g)
1000
Obrázek 4.36: Pr·b¥h algoritmu pro Braninovu funkci ve dvou rozm¥rech Globální minimum je
x∗1 = (−π, 12.275), x∗2 = (π, 2.275), x∗3 = (9.42478, 2.475), f x∗1,2,3 =
0.397887. ervenou barvou je vyzna£ena váºená st°ední hodnota m(g) (g) C(g) . matice σ
a modrou kovarian£ní
4.2.
73
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
constant 16
1
14
0.9
12
0.8 0.7
10
0.6 x2
8 0.5 6 0.4 4
0.3
2
0.2
0
0.1
−2 −12
−10
−8
−6
−4 x1
−2
0
2
4
0
16
1
14
0.9
12
0.8 0.7
10
0.6 x2
8 0.5 6 0.4 4
0.3
2
0.2
0
0.1 −10
−8
−6
−4 x1
−2
0
1.5
3000
1
2000
||σ(g)||
(g)
||C ||
−2 −12
0.5 0
0
500 Generace (g)
2
4
0
1000
1000
0
0
500 Generace (g)
1000
Obrázek 4.37: Pr·b¥h algoritmu pro konstantní funkci ve dvou rozm¥rech Globální minimum je
x ∈ R2 , ∀x ∈ R2 f (x) = 0. ervenou barvou je vyzna£ena váºená σ (g) C(g) . Protoºe je vypnutná zastavovací
(g) a modrou kovarian£ní matice st°ední hodnota m
podmínka EqualFunValues algoritmus se zastaví aº po ur£eném po£tu iterací 1000.
74
KAPITOLA 4.
EXPERIMENTY
dixonprice
5 4
x2
3 2 1 0 −1 −1
0
1
2 x1
3
4
5
−1
0
1
2 x1
3
4
5
5 4
x2
3 2 1 0 −1
2 1.5
2
||σ(g)||
(g)
||C ||
3
1 0
1 0.5
0
500 Generace (g)
1000
0
0
500 Generace (g)
1000
Obrázek 4.38: Pr·b¥h algoritmu pro Dixon-Priceovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
4.2.
75
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
easom 3 2 1
x2
0 −1 −2 −3 −4 −5 −5
−4
−3
−2
−1 x1
0
1
2
3
−5
−4
−3
−2
−1 x1
0
1
2
3
3 2 1
x2
0 −1 −2 −3 −4
2
4
1.5
3 ||σ(g)||
||C(g)||
−5
1 0.5 0
2 1
0
500 Generace (g)
1000
0
0
500 Generace (g)
1000
Obrázek 4.39: Pr·b¥h funkce pro Easomovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (π, π), f (x) = −1. ervenou barvou je vyzna£ena váºená st°ední σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
76
KAPITOLA 4.
EXPERIMENTY
10
goldsteinprice
x 10 10
0.4
9 0.2
8 7
0
6
−0.2 x
2
5 −0.4
4
−0.6
3 2
−0.8 1 −1
0 −1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
x1
10
x 10 10
0.4
9 0.2
8 7
0
6 −0.2 x
2
5 −0.4
4
−0.6
3 2
−0.8 1 −1
0 −1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
x1 1
1
||σ(g)||
||C(g)||
1.5
0.5 0
0
500 Generace (g)
1000
0.5
0
0
500 Generace (g)
1000
Obrázek 4.40: Pr·b¥h algoritmu pro Goldstein-Priceovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0, 1), f (x) = 3. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
4.2.
77
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
himmelblau 160
x
2
3
140
2.5
120
2
100 80
1.5
60
1
40
0.5
20 0 0
0.5
1
1.5 x1
2
2.5
3 160
x
2
3
140
2.5
120
2
100 80
1.5
60
1
40
0.5
20 0 0
0.5
1
1.5 x1
2
2 ||σ(g)||
||C(g)||
3
1.5
1.5 1 0.5 0
2.5
0
500 Generace (g)
1000
1 0.5 0
0
500 Generace (g)
1000
Obrázek 4.41: Pr·b¥h algoritmu pro Himmelblauovu funkci ve dvou rozm¥rech
x∗ = (−0.270844, −0.923038), f (x) = 181.616. ervenou (g) a modrou kovarian£ní matice σ (g) C(g) . st°ední hodnota m
Globální minimum je vyzna£ena váºená
barvou je
78
KAPITOLA 4.
EXPERIMENTY
hump 3000
0 −0.5
2500 −1 2000
−1.5 2
−2
x
1500 −2.5 1000
−3 −3.5
500 −4 −4
−3.5
−3
−2.5
−2
−1.5
−1
−0.5
0
x1 3000
0 −0.5
2500 −1 2000
−1.5 2
−2
x
1500 −2.5 1000
−3 −3.5
500 −4 −4
−3.5
−3
−2.5
−2
−1.5
−1
−0.5
0
x1 1
2
||σ(g)||
(g)
||C ||
3
1 0
0
500 Generace (g)
1000
0.5
0
0
500 Generace (g)
1000
Obrázek 4.42: Pr·b¥h algoritmu pro Humpovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0.0898, −0.7126), x∗2 = (−0.0898, 0.7126), f x∗1,2 = 0.
(g) a modrou kovarian£ní matice nou barvou je vyzna£ena váºená st°ední hodnota m
erve-
σ (g) C(g) .
4.2.
79
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
matyas 25
0 −0.5
20
−1 −1.5
15
x
2
−2 −2.5
10
−3 −3.5 −4
5
−4.5 −5 −5
−4
−3
−2
−1
0
x1 25
0 −0.5
20
−1 −1.5
15
x
2
−2 −2.5
10
−3 −3.5 −4
5
−4.5 −5 −5
−4
−3
−2
−1
0
1.5
3
1
2
||σ(g)||
||C(g)||
x1
0.5 0
0
500 Generace (g)
1000
1 0
0
500 Generace (g)
1000
Obrázek 4.43: Pr·b¥h algoritmu pro Matyasovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
80
KAPITOLA 4.
EXPERIMENTY
rastrigin 40 35 1 30 0.5 x
2
25 20
0
15 −0.5
10 5
−1 −1
−0.5
0
0.5
1
x1 40 35 1 30 0.5 x
2
25 20
0
15 −0.5
10 5
−1 −1
−0.5
0
0.5
1
x1 2
1.5 ||σ(g)||
||C(g)||
1.5 1 0.5 0
0
500 Generace (g)
1000
1 0.5 0
0
500 Generace (g)
1000
Obrázek 4.44: Pr·b¥h algoritmu pro Rastriginovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
4.2.
81
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
8
rosenbrock
x 10 3 2.5
6
2
4
1.5
2
1
0
0.5
x2
8
−2
0 −2
0
2
4
6
8
x1
8
x 10 3 2.5
6
2
4
1.5
2
1
0
0.5
x2
8
−2
0 −2
0
2
4
6
8
x1 400 300
1
||σ(g)||
(g)
||C ||
1.5
0.5 0
200 100
0
500 Generace (g)
1000
0
0
500 Generace (g)
1000
Obrázek 4.45: Pr·b¥h algoritmu pro Rosenbrockovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (1, 1), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
82
KAPITOLA 4.
EXPERIMENTY
schwefel 836 6
835.5
5.5
835
5
834.5
4.5
834 833.5
x
2
4
833
3.5
832.5
3
832
2.5
831.5
2
831
1.5
830.5
1 1
2
3
4
5
6
x1 836 6
835.5
5.5
835
5
834.5
4.5
834 833.5
x
2
4
833
3.5
832.5
3
832
2.5
831.5
2
831
1.5
830.5
1 1
2
3
4
5
6
x1 2
15 ||σ(g)||
||C(g)||
1.5 1 0.5 0
0
500 Generace (g)
1000
10 5 0
0
500 Generace (g)
1000
Obrázek 4.46: Pr·b¥h algoritmu pro Schwefelovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (1, 1), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
4.2.
83
KROKY ALGORITMU PRO VYBRANÉ FUNKCE
sphere 60 55
5
50 45
4
40 3 x2
35 30
2
25 20
1
15 10
0
5 −1 −1
0
1
2
3
4
5
x1 60 55
5
50 45
4
40 3 x2
35 30
2
25 20
1
15 10
0
5 −1 −1
0
1
2
3
4
5
x1 2
3 ||σ(g)||
||C(g)||
1.5 1 0.5 0
0
500 Generace (g)
1000
2 1 0
0
500 Generace (g)
1000
Obrázek 4.47: Pr·b¥h algoritmu pro kvadratickou funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
84
KAPITOLA 4.
EXPERIMENTY
trid 18 2.5
16
2
14
1.5
12
1
10 8
0
6
−0.5
4
−1
2
−1.5
0
x
2
0.5
−1.5
−1
−0.5
0
0.5 x1
1
1.5
2
2.5 18
2.5
16
2
14
1.5
12
1
10 8
0
6
−0.5
4
−1
2
−1.5
0
x
2
0.5
−1.5
−1
−0.5
0
0.5 x1
1
2.5
1.5
2 1 0
2
2 ||σ(g)||
(g)
||C ||
3
1.5
1 0.5
0
500 Generace (g)
1000
0
0
500 Generace (g)
1000
Obrázek 4.48: Pr·b¥h algoritmu pro Tridovu funkci ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x) = −2. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
4.3.
PÍLOHA A: POROVNÁNÍ DALÍCH VARIANT S ALGORITMEM CMA-ES
4.3
85
P°íloha A: Porovnání dal²ích variant s algoritmem CMAES
4.3.1
Porovnání s algoritmem LS-CMA-ES
Testovací funkce m¥li dimenzi algoritmu vyd¥lených
104
n = 20.
Hodnoty v jednotlivých bu¬kách je po£et iterací
nutných k dosaºení hodnoty men²í neº
4 - zna£í, ºe algoritmus nedosáhl ani po 10 iteracích minima
10−10 .
10−10
LS-CMA-ES Funkce
Pn
106
i−1
x2i
n−1 felli = i=1 2 2 fros = i=1 100 x1 − xi+1 + (xi − 1)2 P 4 x2 + 108 x2 fcigtab = x2i + n−1 n i i=1 10 P 6 2 ftablet = 10 x1 + n2 x2i P fcigar = x21 + n2 106 x2i
Pn−1
Pn
i−1 2+10 n−1
fdif f −pow = i=1 |xi | 2 fexp = ekxk − 1
Hodnoty se znakem
CMA-ES
min
max
min
max
0.51
0.72
2.05
2.26
0.98
1.4
2.3
0.53
0.70
1.45
1.5
0.42
0.56
1.61
1.78
0.45
0.57
0.90
1.01
1.53
3.66
1.18
1.5
0.22
0.31
0.27
0.3
86
KAPITOLA 4.
EXPERIMENTY
zakharov 2500 2 1 2000 0
x2
−1
1500
−2 −3
1000
−4 −5
500
−6 −7 −6
−4
−2 x1
0
2 2500
2 1 2000 0
x2
−1
1500
−2 −3
1000
−4 −5
500
−6 −7 −6
−4
−2 x1
0
2
3 ||σ(g)||
||C(g)||
1.5 1 0.5 0
2
0
500 Generace (g)
1000
2 1 0
0
500 Generace (g)
1000
Obrázek 4.49: Pr·b¥h algoritmu pro Zakharovovu funkcui ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0. ervenou σ (g) C(g) .
(g) a modrou kovarian£ní matice hodnota m
barvou je vyzna£ena váºená st°ední
Literatura 4.3.2
Porovnání s algoritmem ACTIVE-CMA-ES
87
88
LITERATURA
Obrázek 4.50: Porovnání algoritmu ACTIVE-CMA-ES
? ]. Na ose generací je vyná²en medán
s algoritmem £istým algoritmem CMA-ES z £lánku [
deseti opakování výpo£et po£tu generací algoritmu nutných k dosaºení tness men²í, neº hodnota
fstop = 10−10
Kapitola 5
P°íloha B: Pouºité zkratky a jejich vysv¥tlení
EA
Evolu£ní algoritms
GA
Genetický algoritmus
ES
Evolu£ní strategie
CMA-ES
Evolu£ní strategie adapatace ovarian£ních matic
IPOP-CMA-ES
Restartovací evolu£ní strategie zaloºená na CMA-ES
89
90
KAPITOLA 5.
PÍLOHA B: POUITÉ ZKRATKY A JEJICH VYSV
TLENÍ
Kapitola 6
P°íloha C: Popis atribut· t°ídy CMAESMethod
91
92
KAPITOLA 6.
PÍLOHA C: POPIS ATRIBUT TÍDY CMAESMETHOD
Název prom¥nné
Parametr
B bestValueInCurrentGeneration C cCumulation chiN consumer countEval cRank1 cSigma currentGeneration D dampingForSigma eigenEval function gaussianGenerator initialSigma
B(g) (g) x1:λ C(g) cc kN (0, I) k
inverseAndSqrtC lambda max min mu muEff N pCumulation pSigma sigma telementry theBestPoint theWorstPoint weights xmean
Popis
C(g) Nejlep²í vektor z generace g (g) Kovarian£ní matice C
Matice vlastních vektor·
Kumula£ní konstanta Odhad
consumer countEval
c1 cσ g D(g) dσ eigenEval function
N (0, 1) σ (0) − 12 (g)
C
λ max min
µ µef f N, n (g) pc (g) pσ σ (g) telemetry
L2
normy
N (0, I)
P°íjemce pr·b¥hu Po£et vyhodnocení tness
f
Konstakta rank-1-update Konstanta pro výpo£et
σ (g)
g (g) Vektor vlastních £ísel D Tlumící konstanta dσ (g) Po£et rozklad· C Fitness funkce f Stávající generace
Generátor normálního rozd¥lení
σ (0)
Po£áte£ní hodnota
− 12 (g)
C
(g)
pσ Velikost populace λ (O) Maximální ∀i ∈ N xi ≤ max (O) Maximální ∀i ∈ N xi ≥ max Po£et vybraných jedinc· µ pro výpo£et
Efektivní hodnota selekce Vstupní rozm¥r funkce
f
evolu£ní cesta pro rank-1-update evolu£ní cesta pro
σ (g)
Velikost kroku V²ichni jedinci z
g
theBestPoint
Nejlep²í jedinec ze v²ech generací
theWorstPoint
Nejhor²í jedinec ze v²ech generací
w m(g)
Váhy Váºená st°ední hodnota selekce
Obrázek 6.1: Popis atribut· t°ídy CMAESMethod jejich p°ípadné odpovídající prom¥nné algoritmu CMA-ES
Kapitola 7
P°íloha D: Grafy vybraných testovacích funkcí Pro úplnost jsem vykreslil v²echny grafy funkcí, pro n¥º jsem zobrazoval pr·b¥h algoritmu. Skripty, jenº jsem vytvo°il na základ¥ [ funkce jsou v rozsahu v obou osách
?
x1 i x2
] a jsou na p°iloºeném CD. V²echny vykreslené v rozsahu
pouºil Matlab.
93
h−10, 10i. Pro generování obrázk· jsem
94
KAPITOLA 7.
PÍLOHA D: GRAFY VYBRANÝCH TESTOVACÍCH FUNKCÍ
ackley
20
f(x1,x2)
15
10
5
0 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.1: Ackleyova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0.
beale
7
x 10 12 10
f(x1,x2)
8 6 4 2 0 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.2: Bealeho funkce ve dvou rozm¥rech Globální minimum je
x∗ = (3, 0.5), f (x∗ ) = 0.
95
bohachevsky
300 250
f(x1,x2)
200 150 100 50 0 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.3: Bohachevskyho funkce prvního druhu ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x) = 1.
booth
3000 2500
1 2
f(x ,x )
2000 1500 1000 500 0 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.4: Bootheho funkce ve dvou rozm¥rech Globální minimum je
x∗ = (1, 3), f (x∗ ) = 0.
96
KAPITOLA 7.
PÍLOHA D: GRAFY VYBRANÝCH TESTOVACÍCH FUNKCÍ
branin
2500
2000
f(x1,x2)
1500
1000
500
0 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.5: Braninova funkce ve dvou rozm¥rech Globální minimum je
0.397887.
constant
1
f(x1,x2)
0.5
0
−0.5
−1 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.6: Konstatní funkce ve dvou rozm¥rech Globální minimum je
x∗1 = (−π, 12.275), x∗2 = (π, 2.275), x∗3 = (9.42478, 2.475), f x∗1,2,3 =
x ∈ R2 , ∀x ∈ R2 f (x) = 0.
97
dixonprice
4
x 10 4.5 4 3.5
f(x1,x2)
3 2.5 2 1.5 1 0.5 0 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.7: Dixon-Priceova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0.
easom
0.4 0.2
f(x1,x2)
0 −0.2 −0.4 −0.6 −0.8 −1 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.8: Easomova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (π, π), f (x) = −1.
98
KAPITOLA 7.
PÍLOHA D: GRAFY VYBRANÝCH TESTOVACÍCH FUNKCÍ
goldsteinprice
17
x 10 14 12
f(x1,x2)
10 8 6 4 2 0 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.9: Goldstein-Priceova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (0, 1), f (x) = 3
himmelblau
4
x 10 2.5
2
f(x1,x2)
1.5
1
0.5
0 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.10: Himmelblauova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (−0.270844, −0.923038), f (x) = 181.616.
99
hump
5
x 10 4 3.5 3
f(x1,x2)
2.5 2 1.5 1 0.5 0 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.11: Humpova funkce ve dvou rozm¥rech Globální minimum je
matyas
180 160 140
f(x1,x2)
120 100 80 60 40 20 0 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.12: Matyasova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (0.0898, −0.7126), x∗2 = (−0.0898, 0.7126), f x∗1,2 = 0.
x∗ = (0, 0), f (x∗ ) = 0.
100
KAPITOLA 7.
PÍLOHA D: GRAFY VYBRANÝCH TESTOVACÍCH FUNKCÍ
rastrigin
250
200
f(x1,x2)
150
100
50
0 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.13: Rastriginova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0.
rosenbrock
7
x 10 4 3.5 3
f(x1,x2)
2.5 2 1.5 1 0.5 0 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.14: Rosenbrockova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (1, 1), f (x∗ ) = 0.
101
schwefel
846 844 842
f(x1,x2)
840 838 836 834 832 830 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.15: Schwefelova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (1, 1), f (x∗ ) = 0.
sphere
200
f(x1,x2)
150
100
50
0 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.16: Kvadratická funkce ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0.
102
KAPITOLA 7.
PÍLOHA D: GRAFY VYBRANÝCH TESTOVACÍCH FUNKCÍ
trid
350 300 250
f(x1,x2)
200 150 100 50 0 −50 10 10
5 5
0 0 −5
−5 −10
x2
−10
x1
Obrázek 7.17: Tridova funkce ve dvou rozm¥rech
globální minimum je
x∗ = (0, 0), f (x) = −2.
zakharov
12000 10000
f(x1,x2)
8000 6000 4000 2000 0 10 10
5 5
0 0 −5 x2
−5 −10
−10
x1
Obrázek 7.18: Zakharovova funkce ve dvou rozm¥rech Globální minimum je
x∗ = (0, 0), f (x∗ ) = 0.
Kapitola 8
Záv¥r •
Zhodnocení spln¥ní cíl· DP/BP a vlastního p°ínosu práce (p°i formulaci je t°eba vzít v potaz zadání práce).
•
Diskuse dal²ího moºného pokra£ování práce.
103
104
KAPITOLA 8.
ZÁV
R
Literatura
105
106
LITERATURA
P°íloha A
Testování zapln¥ní stránky a odsazení odstavc· Tato p°íloha nebude sou£ástí va²í práce. Slouºí pouze jako p°íklad formátování textu.
Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili?
107
108
PÍLOHA A.
TESTOVÁNÍ ZAPLN
NÍ STRÁNKY A ODSAZENÍ ODSTAVC
Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která
109
se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká
110
PÍLOHA A.
TESTOVÁNÍ ZAPLN
NÍ STRÁNKY A ODSAZENÍ ODSTAVC
p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili? Ur£it¥ existuje n¥jaká p¥kná latinská v¥ta, která se k tomuhle testování pouºívá, ale co mají d¥lat ti, kte°í se nikdy latinsky neu£ili?
P°íloha B
Pokyny a návody k formátování textu práce Tato p°íloha samoz°ejm¥ nebude sou£ástí va²í práce. Slouºí pouze jako p°íklad formátování textu.
AT X. Existuje velké mnoºství voln¥ p°ístupné Pouºívat se dají v²echny p°íkazy systému L E dokumentace, tutoriál·, p°íru£ek a dal²ích materiál· v elektronické podob¥. Výchozím bo-
? ]. Tam najdete
dem, krom¥ Googlu, m·ºe být stránka CSTUG (Czech Tech Users Group) [
odkazy na dal²í materiály. Vet²inou dosta£ující a p°ehledn¥ organizovanou elektronikou dokumentaci najdete nap°íklad na [
? ] nebo [? ].
AT X, které výrazn¥ usnadní psaní textu Existují i r·zné nadstavby nad systémy TEX a L E zejména za£áte£ník·m. Velmi roz²í°ený v Linuxovém prost°edí je systém Kile.
B.1
Vkládání obrázk·
Obrázky se umís´ují do plovoucího prost°edí (\caption) a
figure. Kaºdý obrázek by m¥l obsahovat název
náv¥²tí (\label). Pouºití p°íkazu pro vloºení obrázku
\includegraphics je podmín¥no \usepackage{graphicx}.
aktivací (na£tením) balíku graphicx p°íkazem
Budete-li zdrojový text zpracovávat pomocí programu p°íponou
*.pdf1 ,
pouºijete-li k formátování
latex,
pdflatex,
o£ekávají se obrázky s
o£ekávají se obrázky s p°íponou
*.eps.2
P°íklad vloºení obrázku:
\begin{figure}[h] \begin{center} \includegraphics[width=5cm]{figures/LogoCVUT} \caption{Popiska obrazku} \label{fig:logo} pd atex umí také formáty PNG a JPG. Vzájemnou konverzi mezi snad v²emi typy obrazku v£etn¥ zm¥n vekostí a dal²ích vymoºeností vám m·ºe zajistit balík ImageMagic (http://www.imagemagick.org/script/index.php). Je dostupný pod Linuxem, Mac OS i MS Windows. D·leºité jsou zejména p°íkazy convert a identify. 1 2
111
112
PÍLOHA B.
POKYNY A NÁVODY K FORMÁTOVÁNÍ TEXTU PRÁCE
\end{center} \end{figure} B.2
Kreslení obrázk·
Z°ejm¥ kaºdý z vás má n¥jaký oblíbený nástroj pro tvorbu obrázk·. Jde jen o to, abyste dokázali obrázek uloºit v poºadovaném formátu nebo jej do n¥j konvertovat (viz p°edchozí kapitola). Je z°ejm¥ vhodné kreslit obrázky vektorov¥. Celkem oblíbený, na ovládání celkem jednoduchý a p°itom dostate£n¥ mocný je nap°íklad program Inkscape.
? ], který dokáºe do obrázku vkládat
Zde stojí za to upozornit na kreslící programe Ipe [
komentá°e p°ímo v latexovském formátu (vzroce, stejné fonty atd.). Podobné v¥ci umí na Linuxové platform¥ nástroj X g. Za pozornost je²t¥ stojí schopnost editoru Ipe importovat obrázek (jpg nebo bitmap) a krelit do n¥j latexovské popisky a komentá°e. Výsledek pak umí exportovat p°ímo do pdf.
B.3
Tabulky
Existuje více zp·sob·, jak sázet tabulky. Nap°íklad je moºno pouºít prost°edí je velmi podobné prost°edí
figure.
table,
Z
\begin{table} \begin{center} \begin{tabular}{|c|l|l|} \hline \textbf{DTD} & \textbf{construction} & \textbf{elimination} \\ \hline $\mid$ & \verb+in1|A|B a:sum A B+ & \verb+case([_:A]a)([_:B]a)ab:A+\\ &\verb+in1|A|B b:sum A B+ & \verb+case([_:A]b)([_:B]b)ba:B+\\ \hline $+$&\verb+do_reg:A -> reg A+&\verb+undo_reg:reg A -> A+\\ \hline $*,?$& the same like $\mid$ and $+$ & the same like $\mid$ and $+$\\ & with \verb+emtpy_el:empty+ & with \verb+emtpy_el:empty+\\ \hline R(a,b) & \verb+make_R:A->B->R+ & \verb+a: R -> A+\\ & & \verb+b: R -> B+\\ \hline \end{tabular} \end{center} \caption{Ukázka tabulky} \label{tab:tab1} \end{table} \begin{table}
které
B.4.
113
ODKAZY V TEXTU
B.4 B.4.1
Odkazy v textu Odkazy na literaturu
Jsou realizovány p°íkazem
\cite{odkaz}.
Seznam literatury je dobré zapsat do samostatného souboru a ten pak zpracovat programem bibtex (viz soubor
reference.bib). Zdrojový soubor pro bibtex vypadá nap°íklad
takto:
@Article{Chen01, author = "Yong-Sheng Chen and Yi-Ping Hung and Chiou-Shann Fuh", title = "Fast Block Matching Algorithm Based on the Winner-Update Strategy", journal = "IEEE Transactions On Image Processing", pages = "1212--1222", volume = 10, number = 8, year = 2001, } @Misc{latexdocweb, author = "", title = "{\LaTeX} --- online manuál", note = "\verb|http://www.cstug.cz/latex/lm/frames.html|", year = "", } ...
Pozor: Sazba názv· odkaz· je dána BibTEX stylem
(\bibliographystyle{abbrv}). BibTEX tedy obvykle vysází velké pouze po£áte£ní písmeno z názvu zdroje, ostatní písmena z·stanou malá bez ohledu na to, jak je napí²ete. P°esn¥ji °e£eno, styl m·ºe zvolit pro kaºdý typ publikace jiné konverze. Pro £asopisecké £lánky t°eba vý²e uvedené, jiné pro monogra e (u nich £asto bývá naopak velikost písmen zachována). Pokud chcete BibTEXu napov¥d¥t, která písmena nechat bez konverzí (viz
"{\LaTeX} --- online manuál"
title =
v p°edchozím p°íkladu), je nutné p°íslu²né písmeno (zde
celé makro) uzav°ít do sloºených závorek. Pro p°ehlednost je proto vhodné celé parametry uzavírat do uvozovek (author
= "..."),
nikoliv do sloºených závorek.
Odkazy na literaturu ve zdrojovém textu se pak zapisují:
Podívejte se na \cite{Chen01}, dal²í detaily najdete na \cite{latexdocweb} *.tex a *.bib zajistíte p°íkazem \bibliography{} v souboru *.tex. V na²em p°ípad¥ tedy zdrojový dokument thesis.tex obsahuje p°íkaz \bibliography{reference}. Vazbu mezi soubory
114
PÍLOHA B.
POKYNY A NÁVODY K FORMÁTOVÁNÍ TEXTU PRÁCE
Zpracování zdrojového textu s odkazy se provede postupným voláním program·
pdflatex <soubor> (p°ípadn¥ latex <soubor>), bibtex <soubor> pdflatex <soubor>.3
a op¥t
Níºe uvedený p°íklad je p°evzat z d°íve existujících pokyn· student·m, kte°í d¥lají svou diplomovou nebo bakalá°skou práci v Gra cké skupin¥.
4 Zde se praví:
... j) Seznam literatury a dal²ích pouºitých pramen·, odkazy na WWW stránky, ... Pozor na to, ºe na ve²keré uvedené prameny se musíte v textu práce odkazovat -- [1]. Pramen, na který neodkazujete, vypadá, ºe jste ho vlastn¥ nepot°ebovali a je uveden jen do po£tu. P°íklad citace knihy [1], £lánku v £asopise [2], stati ve sborníku [3] a html odkazu [4]: [1] J. ára, B. Bene²;, and P. Felkel. Moderní po£íta£ová grafika. Computer Press s.r.o, Brno, 1 edition, 1998. (in Czech). [2] P. Slavík. Grammars and Rewriting Systems as Models for Graphical User Interfaces. Cognitive Systems, 4(4--3):381--399, 1997. [3] M. Haindl, . Kment, and P. Slavík. Virtual Information Systems. In WSCG'2000 -- Short communication papers, pages 22--27, Pilsen, 2000. University of West Bohemia. [4] Knihovna grafické skupiny katedry po£íta£·: http://www.cgg.cvut.cz/Bib/library/ . . . abychom vý²e citované odkazy skute£n¥ na²li v (automaticky generovaném) seznamu
? ], £lánek v £asopisu
literatury tohoto textu, musíme je nyní alespo¬ jednou citovat: Kniha [
? ], p°ísp¥vek na konferenci [? ], www odkaz [? ].
[
Je²t¥ p°idáme dal²í ukázku citací online zdroj· podle £eské normy. Odkaz na wiki o
? ] a ORM [? ]. Pouºití viz soubor reference.bib. V seznamu literatury by
frameworcich [
nyní m¥ly být ºivé odkazy na zdroje. V
reference.bib
je zcela nový typ publikace. Detaily
dohledal a dodal Petr Dlouhý v dubnu 2010. Podrobnosti najdete ve zdrojovém souboru tohoto textu v komentá°i u p°íkazu
B.4.2
•
\thebibliography.
Odkazy na obrázky, tabulky a kapitoly
Ozna£ení místa v textu, na které chcete pozd¥ji £tená°e práce odkázat, se provede p°íkazem
\label{navesti}.
Lze pouºít v prost°edích
figure
a
table,
ale téº za názvem
kapitoly nebo podkapitoly.
•
Na náv¥²tí se odkáºeme p°íkazem
\ref{navesti}
nebo
\pageref{navesti}.
První volání pdflatex vytvo°í soubor s koncovkou *.aux, který je vstupem pro program bibtex, pak je pot°eba znovu zavolat program pdflatex (latex), který tentokrát zpracuje soubory s p°íponami .aux a .tex. Informaci o p°ípadných nevy°e²ených odkazech (cross-reference) vidíte p°ímo p°i zpracovávání zdrojového souboru p°íkazem pdflatex. Program pdflatex (latex) lze volat vícekrát, pokud stále vidíte nevy°e²ené závislosti. 4 N¥kolikrát jsem byl upozorn¥n, ºe web s t¥mito pokyny byl zru²en, proto jej zde p°ímo necituji. Nicmén¥ p°íklad sám o sob¥ dokumentuje obecn¥ p°ijímaný konsensus ohledn¥ citací v bakalá°ských a diplomových pracích na KP. 3
B.5.
115
ROVNICE, CENTROVANÁ, ÍSLOVANÁ MATEMATIKA
B.5
Rovnice, centrovaná, £íslovaná matematika
Jednoduchý matematický výraz zapsaný p°ímo do textu se vysází pomocí prost°edí resp. zkrácený zápis pomocí uzav°ení textu rovnice mezi znaky Kód
$ S = \pi * r^2 $
bude vysázen takto:
S=π∗
$.
math,
r2 .
Pokud chcete ne£íslované rovnice, ale umíst¥né centrovan¥ na samostatné °ádky, pak lze pouºít prost°edí znaky
$$.
Zdrojový
displaymath, resp. zkrácený zápis pomocí uzav°ení textu kód: |$$ S = \pi * r^2 $$| bude pak vysázen takto:
rovnice mezi
S = π ∗ r2 Chcete-li mít rovnice £íslované, je t°eba pouºít prost°edí
eqation.
Kód:
\begin{equation} S = \pi * r^2 \end{equation} \begin{equation} V = \pi * r^3 \end{equation} je potom vysázen takto:
B.6
S = π ∗ r2
(B.1)
V = π ∗ r3
(B.2)
Kódy programu
Chceme-li vysázet nap°íklad £ást zdrojového kódu programu (bez formátování), hodí se prost°edí
verbatim:
(* nickname2 *) Lego> Refine in1 (do_reg (nickname1 h)); Refine by in1 (do_reg (nickname1 h)) ?4 : pcdata ?5 : pcdata (* surname2 *) Lego> Refine surname1 h; Refine by surname1 h ?5 : pcdata (* email2 *) Lego> Refine undo_reg (email1 h); Refine by undo_reg (email1 h) *** QED ***
116
B.7 B.7.1
PÍLOHA B.
POKYNY A NÁVODY K FORMÁTOVÁNÍ TEXTU PRÁCE
Dal²í poznámky eské uvozovky
V souboru
k336_thesis_macros.tex
uzav°ený do £eských uvozovek.
je p°íkaz
\uv{}
pro sázení £eských uvozovek. Text
P°íloha C
Seznam pouºitých zkratek 2D
Two-Dimensional
ABN
Abstract Boolean Networks
ASIC
Application-Speci c Integrated Circuit
. . .
117
118
PÍLOHA C.
SEZNAM POUITÝCH ZKRATEK
P°íloha D
UML diagramy Tato p°íloha není povinná a z°ejm¥ se neob jeví v kaºdé práci. Máte-li ale v¥t²í mnoºství podobných diagram· popisujících systém, není nutné v²echny umís´ovat do hlavního textu, zvlá²t¥ pokud by to sniºovalo jeho £itelnost.
119
120
PÍLOHA D.
UML DIAGRAMY
P°íloha E
Instala£ní a uºivatelská p°íru£ka Tato p°íloha velmi ºádoucí zejména u softwarových implementa£ních prací.
121
122
PÍLOHA E.
INSTALANÍ A UIVATELSKÁ PÍRUKA
P°íloha F
Obsah p°iloºeného CD Tato p°íloha je povinná pro kaºdou práci. Kaºdá práce musí totiº obsahovat p°iloºené CD. Viz dále. M·ºe vypadat nap°íklad takto. Vá² seznam samoz°ejm¥ bude odpovídat typu va²í práce. (viz [
? ]):
Obrázek F.1: Seznam p°iloºeného CD p°íklad
Na GNU/Linuxu si strukturu p°iloºeného CD m·ºete snadno vyrobit p°íkazem:
$ tree . >tree.txt Ve vzniklém souboru pak sta£í pouze doplnit komentá°e.
123
124
PÍLOHA F.
Z
OBSAH PILOENÉHO CD
README.TXT (p°ípadne index.html apod.) musí být rovn¥º z°ejmé, jak programy
instalovat, spou²t¥t a jaké poºadavky mají tyto programy na hardware. Adresá°
text musí obsahovat soubor s vlastním textem práce v PDF nebo PS formátu,
který bude pozd¥ji pouºit pro prezentaci diplomové práce na WWW.
