Fakulta elektrotechnická. genetického programování

ˇ ´ vysoke ´ uc ˇen´ı technicke ´ v Praze Cesk e ´ Fakulta elektrotechnicka

´ PRACE ´ DIPLOMOVA Simul´ ator vesm´ırn´ e lodi a jej´ı ˇ r´ızen´ı pomoc´ı genetick´ eho programov´ an´ı

Praha, 2013

Autor: Frantiˇ sek Hruˇ ska

i

Podˇ ekov´ an´ı Dˇekuji pˇredevˇs´ım vedouc´ımu diplomové práce a rodiˇc˚ um.

ii

Abstrakt Tato práce si bere za c´ıl vytvoˇrit trojrozmˇernou simulaci vesm´ırného prostˇred´ı inspirovaného hrou Spacewar! a v tomto prostˇred´ı provést experimenty s genetick´ ym programován´ım. C´ılem práce je navrhnout vhodné genetické operátory, termináln´ı a funkˇcn´ı uzly, zp˚ usob interpretace v´ ysledk˚ u program˚ u vyvinut´ ych genetick´ ym programován´ım a navrhnout experimenty vhodné pro simulaci, které nauˇc´ı lod’ ovládat svou rychlost a rotace pˇri pohybu ve dvou rozmˇerném prostˇred´ı, vyh´ ybat se pˇrekáˇzkám a nauˇcit se stˇr´ılet na terˇc. Nakonec jsou navrˇzeny dalˇs´ı moˇzné postupy ˇreˇsen´ı dané problematiky a moˇzná rozˇs´ıˇren´ı projektu do budoucna.

iii

Abstract Goal of this paper is create three-dimensional simulation of the universe inspired by the game called Spacewar! and run here experiments with genetic programming. The main goals are to suggest suitable genetic operators, teminals and funcional nodes, ways to interpret results from trees made by genetic programming and suggest experiments suitable for this simulation, which should teach the ship how to control its speed and rotations in two dimensional space, avoiding obstacles and firing at the targets. There are sugested some other approaches to solve this problem and some extensions to the future.

iv

Obsah Seznam obr´ azk˚ u

ix

Seznam tabulek

xi

´ 1 Uvod

1

2 Genetick´ e programov´ an´ı

3

2.1

Reprezentace program˚ u v GP . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2

Inicializace populace . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.3

Fitness funkce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.4

Parametry GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.5

Selekce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.6

Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.7

Mutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.8

Reprodukce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.9

Bloat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.9.1

Kontrola bloatu v praxi . . . . . . . . . . . . . . . . . . . . . . .

11

2.10 Automatically defined functions . . . . . . . . . . . . . . . . . . . . . . .

12

2.11 Strongly typed GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.12 Grammatical tree-based GP . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.13 Paraleln´ı GP

15

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Simulace prostˇ red´ı 3.1 3.2

17

Rotace ve 3D prostˇred´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.1.1

Rotaˇcn´ı matice . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

Pohyb tˇeles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.2.1

Zákon setrvaˇcnosti . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.2.2

Zákon s´ıly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

v

3.2.3 3.3

3.4

3.5

Aktualizace polohy a rychlosti . . . . . . . . . . . . . . . . . . . .

20

Gravitaˇcn´ı s´ıla a zrychlen´ı . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.3.1

N-Body Problem . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.3.2

Simulace N-Body problému . . . . . . . . . . . . . . . . . . . . .

22

3.3.2.1

Particle - Particle . . . . . . . . . . . . . . . . . . . . . .

22

3.3.2.2

Particle - Mesh . . . . . . . . . . . . . . . . . . . . . . .

23

3.3.2.3

Particle - Particle, Particle - Mesh . . . . . . . . . . . .

23

Detekce koliz´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.4.1

Reprezentace objekt˚ u a poˇc´ıtán´ı koliz´ı . . . . . . . . . . . . . . .

24

3.4.2

Sn´ıˇzen´ı ˇcasové nároˇcnosti detekce koliz´ı . . . . . . . . . . . . . . .

24

Lines of sight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

4 Implementace 4.1

27

Knihovny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.1.1

Grafické knihovny . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.1.2

Knihovny pro genetické programován´ı . . . . . . . . . . . . . . .

28

4.2

Pohyb tˇeles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

4.3

Implementace GP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

4.3.1

Evoluce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.3.2

Terminály a funkce . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.3.3

Genetické operátory . . . . . . . . . . . . . . . . . . . . . . . . .

35

4.4

Ovládán´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

4.5

Soubory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

4.5.1

Vstupn´ı soubory . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

4.5.2

V´ ystupn´ı soubory . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

Moˇznosti nastaven´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

4.6.1

Nastaven´ı vizualizace . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.6.2

Nastaven´ı pro lodˇe . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.6.3

Konstanty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.6.4

Nastaven´ı pro GP . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.6.5

Nastaven´ı v´ ystup˚ u . . . . . . . . . . . . . . . . . . . . . . . . . .

42

Menu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.7.1

Main menu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.7.2

Genetic programming menu . . . . . . . . . . . . . . . . . . . . .

43

4.7.3

Best evolved individual menu . . . . . . . . . . . . . . . . . . . .

43

4.6

4.7

vi

4.8

Screenshoty ze hry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Experimenty a diskuse

43 47

5.1

Nastaven´ı simulaˇcn´ıho prostˇred´ı . . . . . . . . . . . . . . . . . . . . . . .

47

5.2

Experimenty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

5.2.1

Zastaven´ı bez rotac´ı . . . . . . . . . . . . . . . . . . . . . . . . .

49

5.2.1.1

V´ ysledky . . . . . . . . . . . . . . . . . . . . . . . . . .

50

Stˇrelba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

5.2.2.1

V´ ysledky . . . . . . . . . . . . . . . . . . . . . . . . . .

53

Pronásledován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

5.2.3.1

V´ ysledky . . . . . . . . . . . . . . . . . . . . . . . . . .

56

Pohyb v gravitaˇcn´ım poli . . . . . . . . . . . . . . . . . . . . . . .

58

5.2.4.1

V´ ysledky . . . . . . . . . . . . . . . . . . . . . . . . . .

58

Pronásledován´ı v gravitaˇcn´ım poli . . . . . . . . . . . . . . . . . .

61

5.2.5.1

V´ ysledky . . . . . . . . . . . . . . . . . . . . . . . . . .

62

Diskuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.2.2 5.2.3 5.2.4 5.2.5 5.3

6 Z´ avˇ er

71

Literatura

73

A Obsah pˇ riloˇ zen´ eho CD

I

vii

viii

Seznam obr´ azk˚ u 2.1

Syntaktick´ y strom reprezentuj´ıc´ı funkci max(x + x, x + 3 * y) . . . . . .

4

2.2

Generován´ı stromu s maximáln´ı hloubkou 2 metodou full (t = ˇcas) . . .

5

2.3

Generován´ı stromu s maximáln´ı hloubkou 2 metodou grow (t = ˇcas) . . .

5

2.4

Pˇr´ıklad interpretace programu. . . . . . . . . . . . . . . . . . . . . . . . .

6

2.5

One-point crossover s common regionem . . . . . . . . . . . . . . . . . .

8

2.6

Subtree mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.7

Pˇr´ıklad programu se dvˇema ADF a jednou RPB . . . . . . . . . . . . . .

12

2.8

Pˇr´ıklad jedince (derivation tree) vygenerovanáho gramatikou z (2.4) . . .

14

3.1

Grafické znázornˇen´ı tˇr´ı základn´ıch rotac´ı v 3D prostoru. . . . . . . . . . .

18

3.2

Vlevo letadlo bez gimbal locku, vpravo s gimbal lockem.

. . . . . . . . .

18

4.1

Diagram tˇr´ıd pro GP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

4.2

Diagram tˇr´ıd reprezentuj´ıc´ı uzly. . . . . . . . . . . . . . . . . . . . . . . .

31

4.3

Diagram tˇr´ıd reprezentuj´ıc´ı experimenty. . . . . . . . . . . . . . . . . . .

31

4.4

Planety. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.5

Lod’ a meteor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.6

44

4.7

Ukázka pohybu lodi v gravitaˇcn´ım poli bez pouˇzit´ı motor˚ u. . . . . . . . . ´ Uvodn´ ı menu a menu pro nataven´ı parametr˚ u GP. . . . . . . . . . . . . .

5.1

Pr˚ ubˇeh evoluce experimentu Stop2D. . . . . . . . . . . . . . . . . . . . .

51

5.2

Graf závislosti rychlosti lodi na vzdálenosti od c´ıle. . . . . . . . . . . . .

52

5.3

Pr˚ ubˇeh evoluce experimentu Fire2D. . . . . . . . . . . . . . . . . . . . .

54

5.4

Pr˚ ubˇeh evoluce experimentu Persuit2D. . . . . . . . . . . . . . . . . . . .

57

5.5

Trajektorie lodi v experimentu Persuti2D. . . . . . . . . . . . . . . . . .

57

5.6

Trajektorie lodi krouˇz´ıci kolem c´ıle v experimentu GravStop2D. . . . . .

59

5.7

Hvˇezdicovitá trajektorie lodi v experimentu GravStop2D. . . . . . . . . .

60

5.8

Pr˚ ubˇeh evoluce experimentu GravStop2D. . . . . . . . . . . . . . . . . .

61

ix

45

5.9

Pr˚ ubˇeh evoluce experimentu PersuitGrav2D. . . . . . . . . . . . . . . . .

63

5.10 Trajektorie lodi v experimentu PersuitGrav2D. . . . . . . . . . . . . . . .

64


64


65


66


67

x

Seznam tabulek 4.1

Ovládán´ı simulace. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

5.1

Nastaveni experimentu Stop2D. . . . . . . . . . . . . . . . . . . . . . . .

49

5.2

Nastaven´ı experimentu Fire2D. . . . . . . . . . . . . . . . . . . . . . . .

53

5.3

Nastaven´ı experimentu Persuit2D. . . . . . . . . . . . . . . . . . . . . . .

56

5.4

Nastaven´ı experimentu GravStop2D. . . . . . . . . . . . . . . . . . . . .

58

5.5

Struktura individuálu opisuj´ıc´ıho kruhovou trajektorii kolem c´ıle. . . . .

59

5.6

Struktura individuálu opisuj´ıc´ıho hvˇezdicovitou trajektorii kolem c´ıle. . .

60

5.7

Nastaven´ı experimentu PersuitGrav2D. . . . . . . . . . . . . . . . . . . .

62

5.8

Struktura prvn´ıho individálu. . . . . . . . . . . . . . . . . . . . . . . . .

63

5.9

Struktura druhého individálu. . . . . . . . . . . . . . . . . . . . . . . . .

65

5.10 Struktura tˇret´ıho individálu. . . . . . . . . . . . . . . . . . . . . . . . . .

66

xi

xii

Kapitola 1 ´ Uvod Hra Spacewar! 1 byla vytvoˇrena v roce 1977 pro poˇc´ıtaˇc PDP-1 na Massachusetts Institute of Technology. Ve hˇre se vyskytovaly dvˇe ozbrojené lodˇe nazvané “the needle” a “the wedge” a uprostˇred hrac´ı plochy byla hvˇezda p˚ usob´ıc´ı na lodˇe gravitaˇcn´ı silou. Hráˇc mˇel omezen´ y poˇcet raket a paliva a jeho c´ılem bylo sestˇrelit protivn´ıkovu lod’ raketou. Na rakety gravitaˇcn´ı s´ıla nep˚ usobila. Hra se velice rychle rozˇs´ıˇrila mezi ostatn´ı programátory a ti zaˇcali pˇridávat své vlastn´ı modifikace pro hru jako napˇr´ıklad maskován´ı lod´ı, miny, náhodnˇe generované pozad´ı a dokonce i pohled z prvn´ı osoby. Postupem ˇcasu byl kód pˇrepsán i pro jiné typy poˇc´ıtaˇc˚ u a dnes existuje mnoho jej´ıch modifikac´ı pro PC.

1

Java emulator of Spacewar!, http://spacewar.oversigma.com/

1

2

´ KAPITOLA 1. UVOD

Kapitola 2

Genetick´ e programov´ an´ı

Tato kapitola pojednává o základech genetického programován´ı (GP)[1]. Je v n´ı rozebrána reprezentace program˚ u (2.1), inicializaˇcn´ı techniky (2.2), fitness funkce (2.3), technika selekce rodiˇc˚ u z populace (2.5), operátory kˇr´ıˇzen´ı (2.6) mutace (2.7) a reprodukce(2.8) a bloat (2.9). Dále pak kapitola seznamuje se základn´ımi druhy genetického programován´ı (2.10, 2.11, 2.12) a s paraleln´ım genetick´ ym programován´ım (2.13).

2.1

Reprezentace program˚ u v GP

Ve vˇetˇsinˇe pˇr´ıpad˚ u se programy nereprezentuj´ı jako ˇra´dky kódu, ale jako stromy. Vezmˇeme si jako pˇr´ıklad max(x+x,x+3*y) (obr. 2.1). Symboly v pˇr´ıkladu m˚ uˇzeme rozdˇelit na terminály obsahuj´ıc´ı konstanty a promˇenné (v pˇr´ıkladu ˇc´ıslo tˇri a promˇenné x y) a na funkce obsahuj´ıc´ı vnitˇrn´ı uzly (max, *, +). Terminál m˚ uˇze b´ yt i funkce bez argument˚ u, jako napˇr´ıklad funkce random(), vracej´ıc´ı náhodnˇe vygenerované ˇc´ıslo. 3

´ PROGRAMOVAN ´ Í KAPITOLA 2. GENETICKE

4

Obrázek 2.1: Syntaktick´ y strom reprezentuj´ıc´ı funkci max(x + x, x + 3 * y)

V literatuˇre zab´ yvaj´ıc´ı se genetick´ ym programován´ım jsou stromy obvykle v prefixovém zápisu. Tento zp˚ usob zápisu umoˇzn ˇuje lépe sledovat vztahy mezi (pod)v´ yrazy a jejich odpov´ıdaj´ıc´ımi (pod)stromy. Pˇr´ıklad z pˇredchoz´ıho odstavce zapsan´ y prefixovˇe je:

(max (+ x x) (+ x (∗ 3 y)))

2.2

Inicializace populace

Jedinci v populaci jsou pˇri inicializaci generováni náhodnˇe. Nejstarˇs´ımi a nejjednoduˇsˇs´ımi metodami inicializace populace jsou metody grow a full a jejich velmi ˇcasto pouˇz´ıvaná kombinace zvaná Ramped half-and-half metoda. Obˇe metody maj´ı definovanou maximáln´ı inicializaˇcn´ı hloubku generovaného stromu. Hloubka stromu je hloubka nejhlubˇs´ıho listu. V metodˇe full se uzly v hloubce menˇs´ı neˇz je maximáln´ı hloubka generuj´ı z funkˇcn´ı mnoˇziny a v maximáln´ı hloubce jsou uzly generovány z mnoˇziny terminál˚ u. Na obr. 2.2 je vidˇet postupné generováni stromu s hloubkou 2 metodou full. Velikost strom˚ u (poˇcet uzl˚ u) generovan´ ych full metodou závis´ı pouze na aritˇe funkˇcn´ıch uzl˚ u (poˇcet pˇr´ım´ ych potomk˚ u uzlu).

2.2. INICIALIZACE POPULACE

5

Obrázek 2.2: Generován´ı stromu s maximáln´ı hloubkou 2 metodou full (t = ˇcas)

Metoda grow generuje uzly z mnoˇziny vˇsech uzl˚ u (sjednocen´ı mnoˇziny funkc´ı a terminál˚ u). Uzly v maximáln´ı hloubce jsou generovány jen z mnoˇziny terminál˚ u. Tato metoda generuje stromy r˚ uzn´ ych velikost´ı bez ohledu na aritu funkˇcn´ıch uzl˚ u. Generován´ı individuálu metodou grow je znázornˇeno na obr. 2.3. Tato metoda je velmi citlivá na velikosti mnoˇzin funkc´ı a terminál˚ u. Je-li napˇr´ıklad funkˇcn´ı mnoˇzina pˇr´ıliˇs velká oproti mnoˇzinˇe terminál˚ u, chová se podobnˇe jako metoda full a naopak, kdyˇz je velká mnoˇzina terminál˚ u, metoda generuje sp´ıˇse krátké programy.

Obrázek 2.3: Generován´ı stromu s maximáln´ı hloubkou 2 metodou grow (t = ˇcas)


6

Metoda ramped half-and-half generuje polovinu individuál˚ u v populaci metodou grow a druhou polovinu metodou full.

2.3

Fitness funkce

Fitness funkce je nástroj slouˇz´ıc´ı k ohodnocen´ı jednotliv´ ych individuál˚ u v populaci. Napomáhá tak programu upˇresnit, které oblasti prostoru ˇreˇsen´ı má dále prozkoumávat. Fitness funkci lze definovat mnoha zp˚ usoby. Napˇr´ıklad jako odchylku mezi v´ ystupem a oˇcekávan´ ym v´ ystupem, jako ˇcas potˇrebn´ y k dosaˇzen´ı c´ıle, jako vzdálenost chybˇej´ıc´ı k dosaˇzen´ı c´ıle atd. Jelikoˇz GP vyv´ıj´ı programy, k v´ ypoˇctu fitness hodnoty je potˇreba vznikl´ y program interpretovat (provést u ´koly definované ve vˇsech uzlech v poˇrad´ı, které zaruˇcuje, ˇze se neprovede ˇzádn´ y uzel, jehoˇz argumenty jeˇstˇe nejsou známy ) po urˇcit´ y ˇcas a ideálnˇe i na nˇekolika r˚ uzn´ ych konfigurac´ıch prostˇred´ı. Pr˚ uchod stromu pˇri interpretaci programu je vidˇet na obr. 2.4.

Obrázek 2.4: Pˇr´ıklad interpretace programu.

2.4. PARAMETRY GP

2.4

7

Parametry GP

Parametry jsou velmi d˚ uleˇzitou souˇcásti GP a odv´ıj´ı se od nich chován´ı celé evoluce. Je nemoˇzné definovat nˇejaké obecnˇe dobré parametry pro GP. Tradiˇcnˇe se pouˇz´ıvá metoda ramped half-and-half (2.2) pro tvorbu poˇca´teˇcn´ı populace s rozsahem hloubky od 2 do 6 a pravdˇepodobnost kˇr´ıˇzen´ı pˇres 90%. Velmi ˇcasto je velikost populace pˇres 500 jedinc˚ u, jsou ale GP systémy, které pouˇz´ıvaj´ı menˇs´ı populaci. Poˇcet generac´ı b´ yvá v mez´ıch 10 aˇz 50, kdy je pokrok v prohledáván´ı prostoru ˇreˇsen´ı nejvˇetˇs´ı.

2.5

Selekce

Ve vˇetˇsinˇe evoluˇcn´ıch algoritm˚ u se genetické operátory aplikuj´ı na individuály, které jsou vyb´ırány na základˇe hodnoty fitness. Nejˇcastˇejˇs´ı selekˇcn´ı metodou je tournament selection (turnajová selekce). Pˇri tournament selection se vybere nˇekolik jedinc˚ u z populace a tito jedinci jsou mezi sebou porovnáni a nejlepˇs´ı z nich je vybrán jako rodiˇc. Pˇri kˇr´ıˇzen´ı jsou vˇsak potˇreba dva rodiˇce, turnajová selekce se proto dˇelá dvakrát. Tato selekˇcn´ı metoda pouze porovnává, kter´ y z vybran´ ych jedinc˚ u je lepˇs´ı, nezjiˇst’uje o kolik je lepˇs´ı. To vede k efektivn´ımu rozloˇzen´ı tzv. selection pressure (mechanismus selekce, kter´ y urˇcuje, jak moc bude systém upˇrednostˇ novat individuály s lepˇs´ı fitness). Dalˇs´ı metodou selekce je roulette wheel selection nebo také Fitness proportionate selection. Pravdˇepodobnost v´ ybˇeru individuálu i z populace o velikosti N závis´ı na jeho hodnotˇe fitness fi a je rovna: pi =

fi N ∑

(2.1)

fj

j=1

2.6

Crossover

Jedn´ım ze dvou nástroj˚ u, pouˇz´ıvan´ ych k vytvoˇren´ı potomka, je tzv. crossover neboli kˇr´ıˇzen´ı. Jedná se o proces, kdy se vzájemnˇe prohod´ı dva podstromy ze dvou individuál˚ u (rodiˇc˚ u) v populaci. Rodiˇce se vyb´ıraj´ı pomoc´ı selekˇcn´ıch technik (2.5). Pravdˇepodobnost


8

aplikace crossover operátoru je obvykle 90% a vyˇsˇs´ı. Existuje nˇekolik druh˚ u. • Nejstarˇs´ı crossover operator v GP se stromovou strukturou je tzv. one-point crossover. Program nejprve projde oba rodiˇcovské stromy od koˇrenového uzlu a analyzuje jejich strukturu. Crossover point (bod kˇr´ıˇzen´ı) následnˇe vybere jen z tzv. common region (obr. 2.5). V této oblasti maj´ı oba rodiˇcovské stromy stejnou strukturu, tzn. uzly na odpov´ıdaj´ıc´ıch m´ıstech maj´ı stejnou aritu, nemus´ı b´ yt ale stejného typu. Nakonec program prohod´ı podstromy obou crossver point˚ u.

Obrázek 2.5: One-point crossover s common regionem

• Uniform crossover procház´ı stromy v jejich common regionech a u kaˇzdého uzlu se rozhodne, ponechá-li uzel ve stromu nebo ho nahrad´ı odpov´ıdaj´ıc´ım uzlem z druhého rodiˇcovského stromu. Tento operátor zp˚ usobuje vˇetˇs´ı zmˇeny kódu bl´ıˇze u koˇrene stromu. • Context-preserving crossover je podobnˇe jako one-point crossover omezen stejn´ ymi souˇradnicemi, avˇsak nen´ı omezen common regionem. • Size-fair crossover. Crossover point na prvn´ım stromu se vybere náhodnˇe. Následnˇe se spoˇc´ıtá velikost podstromu. Tato velikost je pak pouˇzitá k volbˇe crossover pointu na druhém stromu tak, aby druh´ y podstrom nebyl pˇr´ıliˇs velk´ y.

2.7. MUTACE

2.7

9

Mutace

Druh´ ym nástrojem pouˇz´ıvan´ ym k vytváˇren´ı potomk˚ u je takzvaná mutace. Mutace se pouˇz´ıvá jiˇz od prvn´ıch experiment˚ u s evoluˇcn´ımi programy a dnes je velice rozˇs´ıˇrenou technikou pouˇz´ıvanou v GP. Pravdˇepodobnost mutace je obvykle kolem 1%.Existuje mnoho druh˚ u mutac´ı. V následuj´ıc´ı kapitole pop´ıˇsi nˇekolik z nich. • Subtree mutation, která náhodnˇe vybere podstrom programu a nahrad´ı ho nov´ ym náhodnˇe vygenerovan´ ym podstromem (obr. 2.6). Kinnear definoval podobn´ y mutaˇcn´ı operátor ale s omezen´ım, ˇze nov´ y vygenerovan´ y podstrom nesm´ı b´ yt vˇetˇs´ı o v´ıce neˇz 15%.

Obrázek 2.6: Subtree mutation

• Size-fair subtree mutation se snaˇz´ı zachovávat velikost pozmˇenˇen´ ych podstrom˚ u vzhledem k p˚ uvodn´ım. Velikost nového podstromu je z intervalu [d /2, 3d /2] velikosti nahrazeného podstromu a nebo je jeho velikost odvozená od dalˇs´ıho náhodnˇe vybraného podstromu v programu. Experimentálnˇe bylo zjiˇstˇeno, ˇze druhá moˇznost generuje o mnoho v´ıce redundantn´ıho kódu, tzv. bloat (2.9). • Node replacement mutation (nebo point mutation) nahrad´ı náhodn´ y uzel stromu náhodnˇe vygenerovan´ ym uzlem stejného typu, tzn. uzlem se stejnou aritou. • Hoist mutation vytvoˇr´ı nov´ y individuál, kter´ y je kopi´ı náhodného podstromu rodiˇce. Nov´ y jedinec je menˇs´ı neˇz jeho rodiˇc a má jin´ y koˇrenov´ y uzel.


10

• Shrink mutation nahrad´ı náhodn´ y podstrom programu náhodn´ ym terminálem. Jde se o speciáln´ı pˇr´ıpad subtree-mutation. Spolu s hoist mutation redukuj´ı velikost novˇe generovan´ ych program˚ u. • Permutation mutation vybere náhodn´ y funkˇcn´ı uzel rodiˇce a poté prohod´ı jeho argumenty (podstromy). • Mutating constants at random. Ke konstantˇe se pˇriˇcte náhodná hodnota.

2.8

Reprodukce

Reprodukce zkop´ıruje jedince z rodiˇcovské generace vybraného podle selekˇcn´ıch pravidel 2.5 do dalˇs´ı generace. Pravdˇepodobnost reprodukce se z´ıská tak, ˇze seˇcteme pravdˇepodobnosti aplikace mutace a kˇr´ıˇzen´ı a pokud je tento souˇcet p menˇs´ı neˇz 100%, je pravdˇepodobnost reprodukce rovna 1 - p

2.9

Bloat

Jiˇz v 90.t´ ych letech minulého stolet´ı si vˇedci vˇsimli, ˇze je velikost populace bˇehem v´ yvoje dynamická. Zpoˇcátku se sice chová staticky co se velikosti jedinc˚ u (poˇcet uzl˚ u) t´ yˇce, ale po nˇejakém poˇctu generac´ı se velikost jedinc˚ u zaˇcne rapidnˇe zvˇetˇsovat, coˇz zvyˇsuje ˇcasovou nároˇcnost na v´ ypoˇcet fitness hodnoty (2.3). Na druhou stranu, u sloˇzit´ ych problém˚ u, jako je napˇr´ıklad spojitá symbolická regrese, potˇrebujeme vyv´ıjet velké programy (o mnoho vˇetˇs´ı neˇz programy inicializované v prvn´ı generaci), aby splˇ novaly vˇsechny podm´ınky dané fitness funkc´ı. Proto bloat definujeme jako r˚ ust velikosti programu bez (výrazného) zlepˇsen´ı fitness hodnoty. Operátory kˇr´ıˇzen´ı taktéˇz zp˚ usobuj´ı bloat. Velikost novˇe vloˇzen´ ych podstrom˚ u je zpravidla vˇetˇs´ı neˇz p˚ uvodn´ı podstrom a kˇr´ıˇzen´ı produkuje ˇcasto potomky se stejnou nebo o málo vˇetˇs´ı fitness hodnotou. To vede k nár˚ ustu pr˚ umˇerné velikosti programu. Uzly v GP programu m˚ uˇzeme rozdˇelit na dva druhy: Na aktivn´ı a neaktivn´ı kód. Neaktivn´ı kód je ta ˇca´st programu, která nen´ı nikdy provedena nebo je provedena, ale jej´ı v´ ystup nen´ı nikde pouˇzit. Removal bias theory ˇr´ıká, ˇze neaktivn´ı ˇcásti kódu se vyskytuj´ı v niˇzˇs´ıch ˇcástech stromu, v podstromech menˇs´ıch neˇz je pr˚ umˇerná velikost podstrom˚ u.

2.9. BLOAT

11

Nature of program search space theory ˇr´ıká, ˇze od jisté chv´ıle fitness hodnota neodpov´ıdá velikost´ı programu. Jelikoˇz se v populaci vyskytuje v´ıce dlouh´ ych program˚ u s urˇcitou hodnotou fitness neˇz mal´ ych program˚ u se stejnou fitness hodnotou, v pr˚ ubˇehu evoluce GP vytváˇr´ı stále v´ıce a v´ıce dlouh´ ych program˚ u.

2.9.1

Kontrola bloatu v praxi

Nejjednoduˇsˇs´ı zp˚ usob jak bloat kontrolovat, je omezit programu jeho maximáln´ı hloubku a velikost. Mnoho implementac´ı zavád´ı operátory, které kontroluj´ı poruˇsen´ı tˇechto omezen´ı a pokud jsou poruˇseny, je do nové generace zkop´ırován jeden z rodiˇc˚ u. Tato metoda efektivnˇe omezuje r˚ ust programu, ale do nové generace jsou ˇcasto kop´ırováni jedinci, kteˇr´ı maj´ı tendenci tato omezen´ı poruˇsovat aplikac´ı operátor˚ u kˇr´ıˇzen´ı. Populace je pak naplnˇena jedinci, kteˇr´ı jsou na hranici tˇechto omezen´ı, coˇz si ne vˇzdy pˇrejeme. Dalˇs´ı metodou kontroly bloatu jsou tzv. anti-bloat genetické oper´ atory. Nejˇcastˇeji se pouˇz´ıvaj´ı size-fair crossover (2.6) a size-fair mutation operátory. Dále pak shrink mutation a hoist mutation (2.7). Posledn´ı moˇznost´ı jak kontrolovat bloat, je ovlivnit selekci rodiˇc˚ u. Nejznámˇejˇs´ı metodou je parsimony-pressure method. Ta u kaˇzdého individuálu uprav´ı fitness tak, ˇze od jeho fitness hodnoty odeˇcte hodnotu odpov´ıdaj´ıc´ı jeho velikosti. Vˇetˇs´ımu programu se odeˇc´ıtá vyˇsˇs´ı hodnota, tud´ıˇz tento program bude generovat ménˇe potomk˚ u. Dostáváme tak fitness funkci f (x) − c × l(x) kde l(x) je délka programu x, f(x) je p˚ uvodn´ı fitness hodnota programu a c je tzv. parsimony coefficient, kter´ y slouˇz´ı k tomu, abychom z pozmˇenˇené fitness dostali zpátky origináln´ı fitness. Dalˇs´ı z metod ovlivˇ nuj´ıc´ı selekci rodiˇc˚ u, Tarpeian method, pˇriˇrad´ı nˇekter´ ym rodiˇc˚ um vˇetˇs´ım neˇz je pr˚ umˇerná velikost individuál˚ u v rodiˇcovské populaci ˇspatnou hodnotu fitness s pravdˇepodobnost´ı p = W. To zaruˇc´ı, ˇze tento velk´ y jedinec nebude s velkou pravdˇepodobnost´ı vybrán a taktéˇz nebude provádˇen, tud´ıˇz se urychl´ı bˇeh celé evoluce. Tato metoda je závislá na volbˇe parametru W. Velká hodnota zp˚ usob´ı vyˇrazován´ı vˇetˇs´ıho poˇctu individuál˚ u jeˇstˇe pˇred t´ım, neˇz je spoˇc´ıtána jejich fitness. Malá hodnota zase nevynakládá dostateˇcn´ y tlak na velikost strom˚ u. Nejˇcastˇeji se tak pouˇz´ıvá hodnota W = 0.3.


12

V metodˇe waiting room[2], je individuál pˇred zaˇrazen´ım do populace um´ıstˇe do waiting room, kde ˇceká po dobu u ´mˇerné své velikosti a poté je zaˇrazen do populace. Tento mechanismus umoˇzn´ı menˇs´ım individuál˚ um rychlejˇs´ı ˇs´ıˇren´ı populac´ı.

2.10

Automatically defined functions

Automatically defined functions (ADF) jsou ˇcasté opakuj´ıc´ı se ˇcásti kódu. Maj´ı stejn´ y tvar stromu ale mohou m´ıt jiné argumenty. Program s ADF se skládá z nˇekolika sloˇzek. Jednak z ADF a dále z jedné nebo nˇekolika tzv. main result-producing branches (RPB), jak znázorˇ nuje obr. 2.7. RPB je program, kter´ y je provádˇen pˇri kaˇzdém vyhodnocován´ı jedince. RPB m˚ uˇze volat ADF a ADF mohou volat samy sebe. Jedna ADF muˇze b´ yt RPB volána i nˇekolikrát.

Obrázek 2.7: Pˇr´ıklad programu se dvˇema ADF a jednou RPB

Vezmˇeme si jako pˇr´ıklad následuj´ıc´ı individuál skládaj´ıc´ı se z jedné ADF a jedné RPB: RBF = ADF (ADF (ADF (x)))

(2.2)

ADF = arg0 × arg0

(2.3)

Rovnice (2.3) je jednoduchá druhá mocnina argumentu arg0 ale jej´ı nˇekolikanásobná kombinace v RPB (2.2) vrac´ı x8 a to v mnohem pˇrehlednˇejˇs´ım zápisu. Tento pˇr´ıklad je jednoduch´ y a ADF se pouˇz´ıvaj´ı na mnohem sloˇzitˇejˇs´ı vˇeci. M˚ uˇze se vˇsak stát, ˇze ADF je zavolána jen jednou za cel´ y bˇeh programu, nebo ˇze ADF obsahuje jen jeden uzel, tedy je to jen jin´ y název pro terminál. V tˇechto pˇr´ıpadech ztrác´ı ADF na v´ yznamu.

2.11. STRONGLY TYPED GP

13

Rekurze s ADF vede ve vˇetˇsinˇe pˇr´ıpad˚ u k zacyklen´ı. Existuje zp˚ usob jak zacyklen´ı obej´ıt a to pˇridán´ım index˚ u i a j. ADFi pak m˚ uˇze volat ADFj jen za pˇredpokladu, ˇze i < j. Pˇri kˇr´ıˇzen´ı (2.6) lze nahradit strom z ADFi pouze jin´ ym stromem taktéˇz z ADFi . John Koza navrhl dalˇs´ı automatically-evolved programs: Automatomatically defined iterations (ADI), Automatically defined loops (ADL) a Automatically defined recursion(ADR).

2.11

Strongly typed GP

Strongly typed GP je GP, v nˇemˇz maj´ı vˇsechny uzly definovan´ y návratov´ y datov´ y typ a funkˇcn´ı uzly maj´ı definovan´ y i datov´ y typ vˇsech argument˚ u. Vezmˇeme si jako pˇr´ıklad funkci IF FOOD AHEAD(test, option1, option2). Tato funkce má tˇri argumenty. Prvn´ı argument, test, vrac´ı datov´ y typ boolean, zbylé dva mohou b´ yt napˇr´ıklad typu void, tzn. nevrac´ı ˇza´dnou hodnotu (ale mohou provést nˇejakou akci, napˇr´ıklad GO AHEAD). Cel´ y uzel m˚ uˇze m´ıt pak návratovou hodnotu typu void.

2.12

Grammatical tree-based GP

Gramatická evoluce je GP, které pouˇz´ıvá pro tvorbu individuál˚ u gramatiku a zajiˇst’uje, ˇze vzniklé programy jsou ”gramaticky správné”. Vezmˇeme si jako pˇr´ıklad gramatiku v (2.4) tree ::= E × sin (E × t)

(2.4)

E ::= var|(EopE) op ::= +| − | × |÷ var ::= x|y|z Kaˇzdé z pravidel v (2.4) lze povaˇzovat za tzv. production rule nebo rewrite rule. Prvky, které nelze pˇrepsat ˇzádn´ ym pravidlem naz´ yváme termin´ aly gramatiky a prvky z lev´ ych stran pravidel naz´ yváme netermin´ aln´ımi symboly. Strom vytvoˇren´ y z gramatiky (2.4) zobrazuje obr. 2.8. Program reprezentovan´ y t´ımto stromem y × sin (x + z) × t


14

z´ıskáme tak, ˇze pˇreˇcteme listy stromu zleva doprava. Jedn´ım ze zaj´ımav´ ych GP pˇr´ıstup˚ u vyuˇz´ıvaj´ıc´ıch gramatiku je grammatical evolution (GE), ˇcesky gramatická evoluce. GE nevyuˇz´ıvá k reprezentaci individuál˚ u stromy ale sekvence cel´ ych ˇc´ısel o r˚ uzn´ ych délkách. Pravidla gramatiky na pravé stranˇe jsou indexována od 0. K vygenerován´ı programu se pak vybere pravidlo, které je urˇceno zbytkem po dˇelen´ı ˇc´ısla v genu ˇc´ıslem znaˇc´ıc´ım poˇcet pravidel na pravé stranˇe pravidla. Uvaˇzujme jedince ve tvaru (2.5) 39, 7, 2, 83, 66, 92, 57, 80, 47, 94 a gramatiku (2.4).

Obrázek 2.8: Pˇr´ıklad jedince (derivation tree) vygenerovanáho gramatikou z (2.4)

Postup vytváˇren´ı stromu na obr. 2.8 (rozv´ıjej´ıc´ı neterminály jsou podtrˇzené): tree → (39 mod 1 = 0, tzn. je zde jen jedna moˇznost) E ×sin(E × t) → (7 mod 2 = 1, tzn. vybereme druhou moˇznost) (E op E ) ×sin(E × t) → (2 mod 2 = 0, tzn. vybereme prvn´ı moˇznost) (var op E ) ×sin(E × t) → (83 mod 3 = 2, tzn. vybereme tˇret´ı moˇznost) (z op E ) ×sin(E × t)

(2.5)

2.13. PARALELNÍ GP

15

→ (66 mod 4 = 2, tzn. vybereme tˇret´ı moˇznost) (z op E ) ×sin(E × t) ... (z × x) × sin(x × t)

2.13

Paraleln´ı GP

Paralelizace GP v´ yraznˇe urychluje bˇeh programu a mˇen´ı chován´ı evoluce. Existuj´ı dva zp˚ usoby jak paralelizovat GP: Prvn´ı z nich, Master-slave model, rozdˇel´ı v´ ypoˇcty na nˇekolik jader. Takto lze paralelizovat v´ ypoˇcet hodnoty fitness ale i selekci, genetické operátory a inicializaci. Druh´ ym zp˚ usobem, inspirovan´ ym pˇr´ırodou, je Island model. Princip spoˇc´ıvá v ˇ od rozdˇelen´ı populace na nˇekolik menˇs´ıch sub-populac´ı a ty vyv´ıjet nezávisle na sobˇe. Cas ˇcasu si mezi sebou mohou sub-populace vymˇenit nˇejaké individuály. Tyto sub-populace mohou konvergovat rychleji a mohou naj´ıt r˚ uzná lokáln´ı optima.

16


Kapitola 3 Simulace prostˇ red´ı 3.1

Rotace ve 3D prostˇ red´ı

V dvourozmˇerném prostˇred´ı, v nˇemˇz si vystaˇc´ıme s rotac´ı kolem jedné osy, lze rotace reprezentovat pomoc´ı Eulerových u ´hl˚ u. Tato metoda v trojrozmˇerném prostˇred´ı, v nˇemˇz rozliˇsujeme tˇri druhy rotac´ı roll (kolem osy x), pitch (kolem osy y) a yaw (kolem osy z) (obr. 3.1), vede k nˇekolika problém˚ um: • Rotace r1 a r2 nejsou asociativn´ı. To znamená, ˇze plat´ı: r1 .r2 ̸= r2 .r1 V d˚ usledku této nerovnosti z´ıskáme r˚ uzné v´ ysledné polohy tˇelesa pro r˚ uzná poˇrad´ı aplikac´ı rotac´ı. Jako pˇr´ıklad si vezmˇete dlaˇ n. Palec je osa x, nataˇzené prsty jsou osa y a osa z procház´ı dlan´ı. Ted’ proved’te postupnˇe rotace kolem osy x a osy y o 30 stupˇ n˚ u a zapamatujte si v´ ysledek. Následnˇe proved’te rotace v opaˇcném poˇrad´ı. Dostanete se k jinému v´ ysledku. Obecnˇe plat´ı, ˇze ˇc´ım vˇetˇs´ı je u ´hel rotace, t´ım vˇetˇs´ı je i odchylka v celkové orientaci tˇelesa v prostoru. • Gimbal Lock - Namapován´ı jedné osy na jinou (3.2). Tento efekt nastává pˇri rotac´ıch o 90 stupˇ n˚ u. Opˇet jako pˇr´ıklad poslouˇz´ı dlaˇ n. Po rotaci kolem osy x (palec) o 90 stupˇ n˚ u je osa y shodná s osou z a rotace kolem tˇechto dvou os se chovaj´ı stejnˇe. Eulerovy u ´hly tedy nejsou vhodné pro reprezentován´ı rotac´ı v trojrozmˇerném prostˇred´ı. Naˇstˇest´ı existuj´ı i jiné metody jako axis-angle representation, quaterniony a v poˇc´ıtaˇcové grafice velice rozˇs´ıˇrené rotaˇcn´ı matice[3]. 17

ˇ Í KAPITOLA 3. SIMULACE PROSTRED

18

Obrázek 3.1: Grafické znázornˇen´ı tˇr´ı základn´ıch rotac´ı v 3D prostoru.

Obrázek 3.2: Vlevo letadlo bez gimbal locku, vpravo s gimbal lockem.

3.1.1

Rotaˇ cn´ı matice

V poˇc´ıtaˇcové grafice jsou rotace velmi ˇcasto reprezentovány pomoc´ı tzv.rotaˇcn´ı matice o velikosti 3x3 (3.1). Matematick´ y základ rotaˇcn´ı matice je celkem jednoduch´ y a snadno se implementuje. Matice se skládá z tˇechto prvk˚ u: 

tx2 + c

txy + sz txz − sy



   txy − sz ty 2 + c tyz + sx    txz + sy tyz − sx tz 2 + c kde (x, y, z)T

(3.1)

ˇ 3.2. POHYB TELES

19

je osa rotace, c = cosΘ, s = sinΘ, t = 1 − cosΘ a Θ je u ´hel. Jednotlivé rotaˇcn´ı matice rotac´ı roll (3.2), pitch (3.3) a yaw (3.4) vypadaj´ı následovnˇe: Matice rotace kolem osy x o u ´hel α: 

 0

0

0

   Rx (α) =  0 cos(α) −sin(α)   0 sin(α) cos(α)

(3.2)

Matice rotace kolem osy y o u ´hel β:   Ry (β) =  

 cos(β) 0

0 sin(β) 1

0

−sin(β) 0 cos(β)

  

(3.3)

Matice rotace kolem osy z o u ´hel γ: 



cos(γ) −sin(γ) 0    Rz (γ) =  sin(γ) cos(γ) 0   0 0 1

(3.4)

Rotaˇcn´ı matice je souˇcást´ı projekˇcn´ı matice o velikosti 4x4. Tato matice obsahuje u ´daje i o posunut´ı tˇelesa od poˇcátku soustavy souˇradnic. Pro správnou simulaci rotac´ı je nutné provést rotace v poˇca´tku soustavy souˇradnic. Proto se tˇeleso pˇred aplikac´ı rotac´ı posune zpˇet do poˇca´tku soustavy souˇradnic (hodnoty v posledn´ım sloupci projekˇcn´ı matice jsou nulové). Po rotaci se tˇeleso posune zpˇet do p˚ uvodn´ı polohy.

3.2

Pohyb tˇ eles

[4] Vˇetˇsina fyzikáln´ıch simulac´ı je zaloˇzena na Newtonových pohybových zákonech, které simuluj´ı pohyb tzv.hmotných bod˚ u (tˇelesa, která maj´ı hmotnost, ale jejichˇz velikost je nulová). K simulaci jejich pohybu je zapotˇreb´ı znát jejich polohu p = (px , py , pz )T , rychlost v = (vx , vy , vz )T , zrychlen´ı a = (ax , ay , az )T a prvn´ı dva Newtonovy zákony (tˇret´ı zákon, zákon akce a reakce, nen´ı v této simulaci potˇreba). • Zákon setrvaˇcnosti (prvn´ı Newton˚ uv zákon): Jestliˇze na tˇeleso nep˚ usob´ı ˇza´dné vnˇejˇs´ı s´ıly nebo je v´ yslednice sil nulová, pak tˇeleso setrvává v klidu nebo v rovnomˇerném pˇr´ımoˇcarém pohybu.


20

• Zákon s´ıly (druh´ y Newton˚ uv zákon): Jestliˇze na tˇeleso p˚ usob´ı s´ıla, pak se tˇeleso pohybuje se zrychlen´ım, které je pˇr´ımo u ´mˇerné p˚ usob´ıc´ı s´ıle a nepˇr´ımo u ´mˇerné hmotnosti tˇelesa. a=

3.2.1

F m

Z´ akon setrvaˇ cnosti

Tento zákon ˇr´ıká, ˇze pokud na tˇeleso nep˚ usob´ı ˇzádné s´ıly, tˇeleso se pohybuje konstantn´ı rychlost´ı a jeho poloha se mˇen´ı pouze v závislosti na velikosti rychlosti. V reálném svˇetˇe ale neexistuje situace, kdy by na tˇeleso nep˚ usobila ˇzádná s´ıla (vˇzdy na tˇeleso p˚ usob´ı nˇejaká, byt’ malá, s´ıla, jako napˇr´ıklad gravitaˇcn´ı s´ıla, tˇren´ı, ...). Proto se v nˇekter´ ych simulac´ıch zavád´ı promˇenná damping, která urˇcuje procentuáln´ı z˚ ustatek velikosti rychlosti tˇelesa v dalˇs´ım ˇcasovém okamˇziku. Hodnota 0 ˇr´ıká, ˇze v dalˇs´ım kroku bude rychlost nulová, hodnota 1 naopak naznaˇcuje, ˇze je rychlost konstantn´ı. V naˇs´ı simulaci je hodnota damping rovna jedné.

3.2.2

Z´ akon s´ıly

Druh´ y Newton˚ uv zákon (rovnice 3.5) ˇr´ıká, ˇze pokud chceme zmˇenit pohyb tˇelesa, mus´ıme na tˇeleso p˚ usobit silou (zmˇena zrychlen´ı tˇelesa). Tento zákon se ˇcasto simuluje pˇr´ım´ ym nastaven´ım zrychlen´ı tˇelesa F = ma = mp¨

(3.5)

Po u ´pravˇe rovnice 3.5, dostáváme rovnici pro v´ ypoˇcet samotného zrychlen´ı ¨= p

3.2.3

1 F m

(3.6)

Aktualizace polohy a rychlosti

Pˇri simulaci pohybu se mus´ı v kaˇzdém ˇcasovém okamˇziku aktualizovat poloha tˇelesa p a jeho rychlost p. ˙ Pro aktualizaci polohy se pouˇz´ıvá rovnice 3.7: ˙ + pnew = pold + pt

1 2 ¨ pt 2

(3.7)

ˇ Í SÍLA A ZRYCHLENÍ 3.3. GRAVITACN

21

a pro základn´ı aktualizaci rychlosti se pouˇz´ıvá rovnice 3.8. ¨ p˙ new = p˙ old + pt

(3.8)

V kapitole 3.2.1 byl popsán mechanismus pro sniˇzován´ı rychlosti v kaˇzdém ˇcasovém okamˇziku pomoc´ı promˇenné damping. Pokud je hodnota damping menˇs´ı neˇz jedna, vynásob´ı se touto hodnotou vektor rychlosti. ¨ p˙ new = p˙ old d + pt

(3.9)

V pˇr´ıpadˇe, ˇze je ˇcasov´ y interval h mezi dvˇema ˇcasov´ ymi okamˇziky konstantn´ı, je tato rovnice dostaˇcuj´ıc´ı. V opaˇcném pˇr´ıpadˇe, pˇri kol´ısán´ı ˇcasového intervalu h, se m˚ uˇze pohybuj´ıc´ı tˇeleso “zadrhávat”. To vyˇreˇs´ı u ´prava rovnice 3.9 zaˇclenˇen´ım ˇcasu do ˇca´sti rovnice s damping parametrem, ¨ p˙ new = p˙ old dt + pt

3.3

(3.10)

Gravitaˇ cn´ı s´ıla a zrychlen´ı

Gravitaˇcn´ı s´ıla je s´ıla, kterou se vˇsechna tˇelesa navzájem pˇritahuj´ı. Jej´ı intenzita klesá se ˇctvercem vzdálenost´ı od jej´ıho zdroje a jej´ı dosah je nekoneˇcn´ y. Oblast p˚ usoben´ı graˇ vitaˇcn´ı s´ıly od jednoho tˇelesa se naz´ yvá gravitaˇcn´ı pole. Casto se za hranici gravitaˇcn´ıho pole udává oblast, kde jiˇz nen´ı gravitaˇcn´ı s´ıla od tˇelesa mˇeˇritelná. Gravitaˇcn´ı s´ılu nejlépe popisuje obecn´ a teorie relativity, ale v klasické fyzice (tˇelesa pohybuj´ıc´ı se rychlostmi znaˇcnˇe menˇs´ımi neˇz je rychlost svˇetla) si vystaˇc´ıme s Newtonovým gravitaˇcn´ım zákonem. Ten ˇr´ıká, ˇze dvˇe hmotná tˇelesa m1 , m2 , která lze aproximovat hmotn´ ymi body, se ve vzdálenosti r pˇritahuj´ı silou Fg jeˇz se spoˇc´ıtá podle rovnice 3.11. Fg = G

m1 m2 r2

(3.11)

kde G je gravitaˇcn´ı konstanta, jej´ıˇz hodnota je 6, 67 · 10−11 m3 kg −1 s−2 , m1 a m2 jsou hmotnosti prvn´ıho a druhého tˇelesa a r je vzdálenost mezi tˇelesy. Pro v´ ypoˇcet v´ ysledné gravitaˇcn´ı s´ıly p˚ usob´ıc´ı na tˇeleso v soustavˇe s v´ıce neˇz tˇremi tˇelesy se pouˇz´ıvá metoda N-Body problem[5].


22

3.3.1

N-Body Problem

N-Body Problem má za u ´kol odhadnout dráhu tˇeles, která se vzájemnˇe gravitaˇcnˇe ovlivˇ nuj´ı. Motivac´ı k vyˇreˇsen´ı této u ´lohy byla snaha porozumˇet pohybu Slunce, planet a ostatn´ıch hvˇezd ve vesm´ıru. V˚ ubec prvn´ı matematické ˇreˇsen´ı publikoval Isaac Newton v roce 1687 ve svém d´ıle Principia. Analyticky byl N-Body problem vyˇreˇsen pro N=2, a pro nˇekteré speciáln´ı symetrické pˇr´ıpady s N=3, napˇr´ıklad pro 3 pohybuj´ıc´ı se tˇelesa leˇz´ıc´ı na pˇr´ımce nebo ve vrcholech rovnostranného troj´ uheln´ıka. V ostatn´ıch pˇr´ıpadech lze problém ˇreˇsit pomoc´ı numerického ˇreˇsen´ı diferenciáln´ıch rovnic. Nˇekdy lze N-Body problem zjednoduˇsit vypuˇstˇen´ım tˇelesa s malou hmotnost´ı, které gravitaˇcnˇe neovlivˇ nuje alespoˇ n jedno dalˇs´ı tˇeleso. Napˇr´ıklad pˇri ˇreˇsen´ı pohybu soustavy tˇeles Slunce-Zemˇe-Mˇes´ıc lze vypustit Mˇes´ıc, kter´ y prakticky neovlivˇ nuje pohyb Slunce kolem spoleˇcného tˇeˇziˇstˇe soustavy. Vˇsechny tyto metody uvaˇzuj´ı vesm´ırná tˇelesa jako dokonale tuhé a sféricky symetrické koule a lze je povaˇzovat za hmotné body. Matematicky lze zapsat N-Body problem pro N tˇeles s poˇcáteˇcn´ımi pozicemi qj (0) a rychlostmi q˙j (0) (j = 1,...,n), kde qj (0) ̸= qk (0) pro vˇsechny dvojice tˇeles, jako: mj q¨j = G

∑ mj mk (qk − qj ) k̸=j

|qk − qj |2

, j = 1, ..., n

(3.12)

kde m1 , m2 , ..., mn jsou konstanty reprezentuj´ıc´ı hmotnost tˇeles 1 aˇz n, q1 , q2 ,...,qn jsou vektory pozic tˇeles v ˇcase t a G je gravitaˇcn´ı konstanta. Levá strana je souˇcin hmotnosti a zrychlen´ı tˇelesa s indexem j a vyjadˇruje druhý Newton˚ uv zákon. Pravá strana je pak sumou sil p˚ usob´ıc´ıch na tˇeleso j ostatn´ımi tˇelesy a popisuje Newton˚ uv gravitaˇcn´ı zákon.

3.3.2

Simulace N-Body probl´ emu

Simulace N-Body problému je ˇcasovˇe a v´ ypoˇcetnˇe velice nároˇcná. Existuje nˇekolik metod simulace[6] od r˚ uzn´ ych autor˚ u. V této kapitole pop´ıˇsi nˇekolik z nich. 3.3.2.1

Particle - Particle

Jde o nejjednoduˇsˇs´ı avˇsak ˇcasovˇe nejnároˇcnˇejˇs´ı metodu simulace. Funguje na principu v´ ypoˇctu interakce kaˇzdého tˇelesa s ostatn´ımi v systému. Pro N tˇeles tedy provád´ı N (N − 1) operac´ı, coˇz je kvadratická sloˇzitost O(N 2 ). Jelikoˇz je zjevné, ˇze metoda Particle-Particle poˇc´ıtá kaˇzdou s´ılu dvakrát, je moˇzné jednoduchou u ´pravou sn´ıˇzit poˇcet operac´ı na polovinu. Algoritmus vylepˇsené verze je následuj´ıc´ı:

3.4. DETEKCE KOLIZÍ

23

Algorithm 1 Algoritmus zjednoduˇsené verze metody Particle-Particle for i = 1 → N do for j = i + 1 → N do Fi = Fi + Fij Fj = Fj − Fij end for end for Poˇcet operac´ı vylepˇseného algoritmu je

N (N − 1) 2

, sloˇzitost z˚ ustává nadále kvadra-

tická. Particle-Particle je nejpˇresnˇejˇs´ı metodou, chyba vzniká jen pˇri numerické integraci, napˇr´ıklad pˇri velkém ˇcasovém kroku. 3.3.2.2

Particle - Mesh

Metoda zaloˇzená na aproximaci polohy tˇelesa v prostoru do mˇr´ıˇzky a poˇc´ıtán´ı jeho gravitaˇcn´ıho potenciálu. Z potenciálu urˇceného mˇr´ıˇzkou se pak vypoˇc´ıtá gravitaˇcn´ı s´ıla p˚ usob´ıc´ı na okoln´ı tˇelesa. Existuje nˇekolik druh˚ u pˇridˇelovan´ı tˇeles k bod˚ um mˇr´ıˇzky, napˇr´ıklad Nearest-Grid-Point, v nˇemˇz je tˇeleso pˇriˇrazeno k nejbliˇzˇs´ımu bodu mˇr´ıˇzky nebo sloˇzitˇejˇs´ı metoda Cloud-In-Cell, v n´ıˇz m˚ uˇze ˇcástice souˇcasnˇe patˇrit do nˇekolika bod˚ u mˇr´ıˇzky. Slabinou metody Particle-Mesh je konstantn´ı velikost mˇr´ıˇzky, která v oblastech s velkou hustotou tˇeles zp˚ usobuje velkou odchylku. Tento nedostatek lze vyˇreˇsit pomoc´ı ˇ pˇr´ıdavn´ ych jemnˇejˇs´ıch mˇr´ıˇzek. Casov´ a sloˇzitost je O(N log N ). 3.3.2.3

Particle - Particle, Particle - Mesh

Tato metoda eliminuje nedostatek Particle-Mesh metody (3.3.2.2), a to odchylku v oblastech s velkou hustotou tˇeles. Pro vzdálené tˇelesa pouˇz´ıvá metodu Particle-Mesh a pro bl´ızˇ ká tˇelesa metodu Particle-Particle (3.3.2.1). Casov´ a sloˇzitost je stejná jako u ParticleMesh a to O(N log N ).

3.4

Detekce koliz´ı

D˚ uleˇzitou souˇca´st´ı simulace je detekce koliz´ı. Jedná se o v´ ypoˇcetnˇe nároˇcnou operaci, pˇri n´ıˇz se kontroluje vzájemná poloha vˇsech tˇeles. Pro N tˇeles je tˇreba provést N (N − 1) operac´ı a ˇcasová sloˇzitost je O(N 2 ). Poˇcet operac´ı lze sn´ıˇzit na polovinu, tj. N (N2 −1) , ˇ jelikoˇz vzájemná pozice dvou tˇeles se poˇc´ıtá dvakrát pro kaˇzdou dvojici. Casov´ a sloˇzitost z˚ ustává kvadratická.


24

3.4.1

Reprezentace objekt˚ u a poˇ c´ıt´ an´ı koliz´ı

Pro jednoduˇsˇs´ı poˇc´ıtán´ı koliz´ı jsou planety, meteority a vesm´ırné lodˇe reprezentovány jako koule a stˇrely jsou reprezentovány jako body. Tato forma reprezentace umoˇzn ˇuje rychlou a efektivn´ı detekci koliz´ı poˇc´ıtán´ım vzdálenosti d mezi dvˇema tˇelesy o1 , o2 podle rovnice (3.13). d=

√ (o1 .x − o2 .x)2 + (o1 .y − o2 .y)2 + (o1 .z − o2 .z)2

(3.13)

Jestliˇze je vzdálenost d menˇs´ı neˇz souˇcet polomˇer˚ u obou tˇeles, dojde ke kolizi.

3.4.2

Sn´ıˇ zen´ı ˇ casov´ e n´ aroˇ cnosti detekce koliz´ı

Problémem detekce koliz´ı je jednak velké mnoˇzstv´ı dvojic, pro které se kolize kontroluj´ı a také samotná ˇcasová nároˇcnost algoritmu pro kontrolu koliz´ı. Proto se detekce koliz´ı dˇel´ı do dvou ˇcást´ı: • V prvn´ı ˇcásti se vyberou pouze ta tˇelesa, u nichˇz je sráˇzka moˇzná. K tomu se pouˇz´ıvaj´ı r˚ uzné heuristiky a datové struktury jako napˇr´ıklad Bounding Volume Hierarchy, Grid, Multi-Resulution Maps, Quad-Trees a Oct-Trees, • Druhá ˇca´st se zab´ yvá samotnou detekc´ı koliz´ı mezi páry tˇeles, které byly vybrány v prvn´ı ˇcásti v prvn´ı ˇca´sti.

3.5

Lines of sight

Podobn´ y mechanismus jako u detekce koliz´ı lze vyuˇz´ıt i pro v´ ypoˇcet tzv. Lines of sight. Jedná se o algoritmus, kter´ y zjist´ı, zda na sebe dvˇe tˇelesa “vid´ı”, neboli zda mezi nimi nen´ı ˇza´dná pˇrekáˇzka. Jedin´ y rozd´ıl je v tom, ˇze se pˇri tom poˇc´ıtá vzd´ alenost bodu X od roviny ρ. Postup ˇreˇsen´ı je následuj´ıc´ı: • Z´ıskáme smˇerov´ y vektor u pˇr´ımky p na n´ıˇz leˇz´ı obˇe tˇelesa, tj. rozd´ıl pozic obou tˇeles (3.14) u = (o1 .x − o2 .x, o1 .y − o2 .y, o1 .z − o2 .z)

(3.14)

Tento smˇerov´ y vektor je souˇcasnˇe normálov´ ym vektorem roviny ρ kolmé na pˇr´ımku p

3.5. LINES OF SIGHT

25

• Urˇc´ıme pr˚ useˇc´ık E pˇr´ımky p a roviny ρ. • Spoˇc´ıtáme vzdálenost d = |XE| podle vzorce (3.15):

d=

|nx Xx + ny Xy + nz Xz | √ , n2x + n22 + n2z

(3.15)

kde nn jsou jednotlivé sloˇzky normálového vektoru roviny ρ a Xn jsou sloˇzky polohy bodu X. Nakonec zb´ yvá podle (3.16) zkontrolovat, zda se kolizn´ı tˇeleso p nacház´ı mezi tˇelesy o1 , o2 , pro nˇeˇz se lines of sight poˇc´ıtaj´ı. Mus´ı platit: o1 .n ≤ p.n ≤ o2 .n ∥ o1 .n ≥ p.n ≥ o2 .n, kde n jsou jednotlivé sloˇzky polohového vektoru tˇelesa.

(3.16)

26


Kapitola 4 Implementace Hlavn´ım u ´ˇcelem simulace je v´ yvoj program˚ u pomoc´ı GP a jejich testován´ı v simulaˇcn´ım prostˇred´ı. Jelikoˇz je urˇcena hlavnˇe k pˇresnému v´ ypoˇctu pohybu tˇeles, jedná se o simulaci, která uvaˇzuje konstantn´ı ˇcasový interval h mezi dvˇema ˇcasov´ ymi okamˇziky (volán´ı metody pro fyzikáln´ı v´ ypoˇcty). Tzn. mezi dvˇema ˇcasov´ ymi okamˇziky ubˇehne v simulaci vˇzdy jedna ˇcasová jednotka. Simulace pouˇz´ıvá grafickou knihovnu JOGL (4.1.1) a je optimalizovaná pro dvou jádrov´ y procesor. Jedno vlákno se stará o grafiku a druhé vlákno obstarává fyzikáln´ı v´ ypoˇcty. Pˇri spuˇstˇeném GP je aktivn´ı pouze jedno vlákno (fyzikáln´ı v´ ypoˇcty prob´ıhaj´ı v jin´ y ˇcas neˇz samotné GP). Grafika a fyzika jsou psané pro trojrozmˇerné prostˇred´ı (4.2) a slouˇz´ı hlavnˇe k vizualizaci v´ ysledk˚ u. Pro u ´spˇeˇsné spuˇstˇen´ı simulace je potˇreba nˇekolik vstupn´ıch soubor˚ u (4.5) a program m˚ uˇze generovat nˇekolik soubor˚ u s informacemi o pohybu vesm´ırn´ ych tˇeles nebo o pr˚ ubˇehu evoluce. Program vyuˇz´ıvá vlastn´ı implementaci GP (4.3) inspirovanou knihovnou JGAP (4.1.2), s moˇznost´ı pouˇz´ıt r˚ uzné genetické operátory (4.3.3). Kaˇzd´ y uzel má návratovou hodnotu double, která se pouˇz´ıvá pro interpretaci v´ ysledku programu, vyvinutém pomoc´ı GP. Pˇred spuˇstˇen´ım samotné simulace, lze nastavit parametry vizualizace a GP pomoc´ı menu (4.7) nebo v souboru Settings.java (4.6).

4.1 4.1.1

Knihovny Grafick´ e knihovny

V´ ybˇer grafické knihovny je omezen programovac´ım jazykem, v nˇemˇz je dan´ y program psan´ y. Jelikoˇz program Universe3D je napsán v jazyce Java, pˇripadaj´ı v u ´vahu tyto 27

28

KAPITOLA 4. IMPLEMENTACE

knihovny: • JOGL1 je open source knihovna, která umoˇzn ˇuje pouˇz´ıvat grafickou knihovnu OpenGL[7] v jazyce Java. Umoˇzn ˇuje pˇr´ıstup k funkc´ım tˇr´ıd GL a GLU. Naopak neumoˇzn ˇuje pˇr´ıstup k funkc´ım tˇr´ıdy GLUT, ale vyuˇz´ıvá javovské AWT a Swing systémy. • Java3D2 je plnˇe objektová grafická knihovna, vyv´ıjená pˇr´ımo pro platformu Java. Je postavena na základech OpenGL nebo DirectX. Jej´ı nev´ yhodou je vˇetˇs´ı pamˇet’ová nároˇcnost neˇz u JOGL. • jMonkeyEngine33 je relativnˇe nová knihovna (2010) zaloˇzená na OpenGL.

4.1.2

Knihovny pro genetick´ e programov´ an´ı

Existuje nˇekolik knihoven, implementuj´ıc´ıch r˚ uzné druhy genetického programován´ı a mnoho z nich je psáno pro Javu, uvedu nˇekteré z nich: • JGAP4 - Velice rozsáhlá knihovna, která ovládá jak genetické algoritmy, tak i genetické programován´ı. Nab´ız´ı hned nˇekolik tutoriál˚ u a kvalitn´ı dokumentaci. Fungován´ı JGAP je velice jednoduché. Nev´ yhodou je sloˇzitost zaˇclenˇen´ı do vlastn´ıho programu. • ECJ5 - Dalˇs´ı rozsáhlá knihovna, která um´ı strongly-typed GP s moˇznost´ı paralelizace. • JGProg6 - Knihovna pro strongly-typed GP. Jej´ı v´ yvoj se bohuˇzel zastavil v roce 2000.

4.2

Pohyb tˇ eles

Pohyb tˇeles je ˇreˇsen mechanismem, popsan´ ym v kapitole 3.2. V simulaci se vyskytuj´ı dva druhy zrychlen´ı: zrychlen´ı e generované motory lodi, a gravitaˇcn´ı zrychlen´ı g. Celkové 1

Java Binding For OpenGL, http://jogamp.org/jogl/www/ http://www.oracle.com/technetwork/java/javase/tech/index-jsp-138252.html 3 http://jmonkeyengine.com/ 4 Java Genetic Algorithms Package, http://jgap.sourceforge.net/ 5 http://cs.gmu.edu/ eclab/projects/ecj/ 6 http://jgprog.sourceforge.net 2

4.3. IMPLEMENTACE GP

29

zrychlen´ı a je rovno souˇctu tˇechto dvou vektor˚ u. a = e + g;

(4.1)

• Motory - Zrychlen´ı e generované motory lodi je nastavované pˇr´ımo a jeho hodnota je 0.0035 délkov´ ych jednotek za druhou mocninu ˇcasu. Smˇer zrychlen´ı je stejn´ y s orientac´ı lodi. Stejn´ y mechanismus je pouˇzit pro zpomalen´ı. • Gravitaˇcn´ı zrychlen´ı - V simulaci se m˚ uˇze nacházet ˇrádovˇe des´ıtky tˇeles a proto se hodnota g poˇc´ıtá základn´ı metodou Particle-Particle (N-Body Problem kapitola 3.3.2.1). Kaˇzdá rotace a zmˇena rychlosti spotˇrebuj´ı urˇcité mnoˇzstv´ı paliva.

4.3

Implementace GP

Implementace GP je inspirovaná knihovnou JGAP (4.1.2). Kaˇzd´ y strom (individuál) je uloˇzen jako ArrayList jednotliv´ ych uzl˚ u a koˇren je uzel s indexem nula. Celá populace je uloˇzena v poli ArrayLit˚ u o velikosti populace. Strom je procházen pomoc´ı rekurzivn´ıho prohledáván´ı do hloubky od koˇrene. Tˇr´ıdy pro GP se nacházej´ı v bal´ıku gp: • Node - Abstraktn´ı tˇr´ıda reprezentuj´ıc´ı uzel stromu a metody pro interakci mezi uzly. Uzly se dˇel´ı na terminály a funkce a kaˇzd´ y druh uzlu je reprezentován vlastn´ı tˇr´ıdou. • Tree - Tˇr´ıda reprezentuj´ıc´ı strom jako ArrayList uzl˚ u. Obsahuje metody pro inicializaci a u ´pravy stromu. • Forest - Les skládaj´ıc´ı se z nˇekolika strom˚ u (podle typu experimentu). Tato tˇr´ıda reprezentuje individuál v populaci a je Comparable, kv˚ uli porovnáván´ı a ˇrazen´ı individuál˚ u v populaci podle jejich hodnoty fitness. • Population - Pole individuál˚ u (les˚ u), neboli populace. Tˇr´ıda se stará o generován´ı populace a jej´ı v´ yvoj za pomoci genetick´ ych operátor˚ u. • BestIndividual - Nejlepˇs´ı individuál, vytvoˇren´ y pomoc´ı GP. Obsahuje metodu pro interpretaci v´ ysledk˚ u z jednotliv´ ych strom˚ u v závislosti na druhu experimentu.

30

KAPITOLA 4. IMPLEMENTACE • Mutation, Crossover a Selection - Statické tˇridy obsahuj´ıc´ı implementaci genetick´ ych operátor˚ u.

Diagramy tˇr´ıd pro GP v programu Universe3D jsou znázornˇeny na obrázc´ıch 4.1, 4.2 a 4.3.

Obrázek 4.1: Diagram tˇr´ıd pro GP.


Obrázek 4.2: Diagram tˇr´ıd reprezentuj´ıc´ı uzly.

Obrázek 4.3: Diagram tˇr´ıd reprezentuj´ıc´ı experimenty.

31

32


4.3.1

Evoluce

Program rozliˇsuje evoluci s crossover operátorem (algoritmus 2) a bez nˇej (algoritmus 3). Je to proto, ˇze pˇri mal´ ych rozmˇerech strom˚ u docház´ı ke kˇr´ıˇzen´ı v jejich koˇrenech a nebo v uzlech a v´ ysledn´ı potomci jsou kopiemi rodiˇc˚ u. To vede k velmi rychlé konvergenci populace a je tedy tˇreba odliˇsn´ y algoritmus. Pˇri pouˇzit´ı crossoveru operátoru jsou do následuj´ıc´ı generace potomk˚ u (offsprings) vˇzdy vybráni dva nejlepˇs´ı individuálové ze ˇctveˇrice (o1 , o2 , p1 , p2 ). Pokud crossover operátor nen´ı pouˇzit, je pcross = 0 a pmut = 1 a mutaˇcn´ı operátor je subtree mutation. Algorithm 2 Pr˚ ubˇeh v´ yvoje jedné generace bez crossover operátoru Vstup: velikost populace N P arents ← initP opulaci(N ); Execute(P arents); while c´ılové podm´ınky nesplnˇeny do for i = 0 → N do p ← Selection(P arents); o ← M utation(p); o.f itness ← 0.0; if kontrola bloatu povol´ı o then o.f itness ← vyhodnot(o); end if Of f springs.add(o); end for Sort(Of f springs); P arents = vyberN ejlepsi(P arents, Of f springs); end while

4.3.2

Termin´ aly a funkce

Vˇsechny uzly pouˇz´ıvané v GP maj´ı návratov´ y typ double a kaˇzd´ y druh uzlu má vlastn´ı specifickou tˇr´ıdu, urˇcuj´ıc´ı jeho název, aritu a návratovou funkci. Arita funkˇcn´ıch uzl˚ u je r˚ uzná, maximálnˇe vˇsak rovna ˇctyˇrem. Mnoˇziny terminál˚ u a funkc´ı lze nastavit bud’ v menu pro genetické programován´ı (4.7.2) a nebo v souboru Settings.java.


Algorithm 3 Pr˚ ubˇeh v´ yvoje jedné generace s crossover operátorem Vstup: velikost populace N P arents ← initP opulaci(N ); Execute(P arents); for i = 0 → N/2 do (p1 , p2 ) ← Selection(P arents); if M ath.random() < pcross then (o1 , o2 ) ← Crossover(p1 , p2 ); end if if M ath.random() < pmut then (o1 , o2 ) ← M utation(o1 , o2 ); end if if o1 .equals(p1 )∥∥o1 .equals(p2 ) then o1 ← SubT reeM utation(o1 ); o2 ← SubT reeM utation(o2 ); end if o1 .f itness ← 0.0; o2 .f itness ← 0.0; if kontrola bloatu povol´ı o1 then o1 .f itness ← vyhodnot(o1 ); end if if kontrola bloatu povol´ı o2 then o2 .f itness ← vyhodnot(o2 ); end if (b1 , b2 ) ← vyberN ejlepsi(o1 , o2 , p1 , p2 ); Of f springs.add(b1 ); Of f springs.add(b2 ); P arents ← Of f rings end for

33

34


Mnoˇzina funkc´ı se skládá ze základn´ıch matematick´ ych operac´ı a funkc´ı a dále dvou funkc´ı implementuj´ıc´ıch podm´ınku: • Add: (a + b). • Sub: (a - b). • Mul: (a * b). • Div: if (b == 0) return 1 else return (a / b). Tzv. protected divide. • Sin: Math.sin(a). • Atan: Math.atan(a). • Log: Math.log(a). • Abs: Math.abs(a). • Sqrt: Math.sqrt(a). • YnaryMinus: a*(-1). • IfCollide: if (tˇeleso je na kolizn´ım kurzu s planetou) return a else return b. Pozn´ amka: Pokud je lod’ od planety daleko (trojnásobek jej´ıho pr˚ umˇeru), kolizn´ı kurz se nepoˇc´ıtá.

2

• Iflet: if (a ̸= b) return c else return d. • Min: Math.min(a, b). • Max: Math.max(a, b). Mnoˇzina terminál˚ u: • Constant: Náhodnˇe generovaná konstanta. • Speed: Rychlost tˇelesa. Kromˇe u ´lohy Fire2D, v n´ıˇz je tento uzel roven rychlosti terˇce, vrac´ı rychlost lodi. • Distance: Vzdálenost dvou tˇeles. • Gravitation: Velikost vektoru gravitaˇcn´ıho zrychlen´ı p˚ usob´ıc´ı na tˇeleso.


35

• One: Vrac´ı hodnotu jedna. • PI: Math.PI. ´ • AngleDiff: Uhel mezi smˇerov´ ym vektorem tˇelesa a pˇr´ımkou, danou polohou tˇelesa a terˇce. Podle znaménka návratové hodnoty lze zjistit, která rotace zmenˇs´ı tento u ´hel. Záporná hodnota ˇr´ıká, ˇze tˇeleso je potˇreba natoˇcit doprava. Tento uzel je funkˇcn´ı jen pro dvourozmˇerné prostˇred´ı. ´ • CollisionAngle: Uhel pro natoˇcen´ı lodi od kolizn´ıho tˇelesa. Tento uzel je funkˇcn´ı jen pro dvourozmˇerné prostˇred´ı. • NearestPlanet: Vrát´ı index planety, která je k lodi nejbl´ıˇze.

4.3.3

Genetick´ e oper´ atory

V programu si lze vybrat z nˇekolika jiˇz implementovan´ ych genetick´ ych operátor˚ u um´ıstˇen´ ych ve statick´ ych tˇr´ıdách Mutation, Crossover a Selection. Jednoduˇse lze pˇripsat dalˇs´ı statickou metodu pro nov´ y genetick´ y operátor. Mutace: • Subtree mutation - Mutace nahrad´ı zvolen´ y podstrom nov´ ym, náhodnˇe vygenerovan´ ym stromem. Nov´ y strom je vˇzdy generován metodou grow (2.2). Omezen´ım maximáln´ı hloubky stromu je zaruˇceno, ˇze tento operátor nezp˚ usob´ı r˚ ust individuál˚ u nad maximáln´ı stanovenou velikost. • Node replacement mutation - Mutace nahrad´ı náhodnˇe zvolen´ y uzel stromu za jin´ y náhodnˇe vygenerovan´ y uzel se stejnou aritou. Tato mutace nezp˚ usobuje zmˇenu velikosti stromu. Crossover: • One-point crossover - Crossover pointy obou strom˚ u vybere z common regionu (2.6) a prohod´ı podstromy. • Common crossover - Crossover pointy jsou na obou stromech zvoleny náhodnˇe. Tento operátor m˚ uˇze vytvoˇrit strom, kter´ y pˇresáhne maximáln´ı povolenou hloubku. Selekce:

36

KAPITOLA 4. IMPLEMENTACE • Tournament selection - Náhodnˇe vybere N individuál˚ u z nichˇz poté vybere nejlepˇs´ı. Velikost N lze nastavit promˇennou TOURNAMENT SIZE v souboru Settings.java • Roulette wheel selection - Pravdˇepodobnost v´ ybˇeru individuálu je závislá na jeho fitness hodnotˇe 2.5. • Random selection - Individuál je vybrán náhodnˇe.

4.4

Ovl´ ad´ an´ı

Pohyb lodi a kamery a nˇekteré dalˇs´ı funkce simulace lze ovládat z klávesnicového vstupu. ↑↓

Zrychlen´ı.

←→

Yaw rotace.

Z, X

Pitch rotace.

C, V

Roll rotace.

G

Stˇrelba.

Q, E

Kamera zoom in/out.

L

Zobrazován´ı LOS.

T

Vykreslován´ı trajektorie lod´ı.

I

Vypne/zapne pohled z prvn´ı osoby. Kamera zamˇeˇrena na lod’ s indexem nula.

K

Vypne/zapne pohled ze tˇret´ı osoby. Kamera zamˇeˇrena na lod’ s indexem nula.

J

Vypne/zapne pohled ze tˇret´ı osoby. Kamera zamˇeˇrena na lod’ s indexem nula.

R

Restart simulace.

P

Náhodn´ y restart simulace.

M, N

Zv´ yˇsen´ı/sn´ıˇzen´ı poˇctu polygon˚ u tvoˇr´ıc´ıch planety, meteory a terˇce. Tabulka 4.1: Ovládán´ı simulace.

4.5

Soubory

Simulace potˇrebuje ke svému bˇehu nˇekolik vstupn´ıch soubor˚ u a zároveˇ n jsou schopny generovat nˇekolik soubor˚ u v´ ystupn´ıch.

4.5. SOUBORY

4.5.1

37

Vstupn´ı soubory

K bˇehu programu Universe3D jsou potˇreba tˇri soubory: ships.txt, meteors.txt, planets.txt, které definuj´ı tˇelesa, vyskytuj´ıc´ı se v simulaci a uˇzivatel m˚ uˇze mˇenit jejich poˇcet i nastaven´ı. Bez tˇechto soubor˚ u se program nespust´ı. Pro kaˇzd´ y soubor plat´ı, ˇze jedno tˇeleso je definováno na jednom ˇra´dku. Zakonˇcovac´ı znak je znak pro nov´ y ˇra´dek. Za komentáˇr se povaˇzuje kaˇzd´ y ˇra´dek, kter´ y zaˇc´ıná znakem ’#’. Jako konec souboru je brán prázdný ˇr´ adek. Pokud chce uˇzivatel pro zpˇrehlednˇen´ı souboru um´ıstit prázdn´ y ˇrádek do textu, je ˇ ısla jsou oddˇelena nutné zapsat ho jako komentáˇr, tzn. ˇra´dek obsahuj´ıc´ı jen znak ’#’. C´ mezerou. Je tˇreba dodrˇzovat tato pravidla spolu s formátován´ım pro dané tˇeleso jinak dojde k chybˇe v parsován´ı a program se ukonˇc´ı! Formáty vstupn´ıch soubor˚ u jsou následuj´ıc´ı: • soubor ships.txt – Tˇri ˇc´ısla typu double pro polohov´ y vektor lodi. – Tˇri ˇc´ısla typu double pro u ´hly rotac´ı roll, pitch a yaw. – Tˇri ˇc´ısla typu double pro vektor poˇcáteˇcn´ı rychlosti lodi. • soubor meteors.txt – Tˇri ˇc´ısla typu double pro polohov´ y vektor meteoru. – Tˇri ˇc´ısla typu double pro vektor poˇcáteˇcn´ı rechlosti meteoru. – Celé ˇc´ıslo pro pr˚ umˇer meteoru (km). – Hmotnost meteoru (kg 1024 ). – Název textury meteoru. • soubor planets.txt – Index planety typu integer. Index planety nesm´ı pˇresáhnout hodnotu N-1, kde N je poˇcet planet v simulaci. – Tˇri ˇc´ısla typu double pro polohov´ y vektor planety. – Tˇri ˇc´ısla typu double pro vektor poˇcáteˇcn´ı rychlosti planety. – Pr˚ umˇer planety (km). – Hmotnost planety (kg 1024 ).

38

KAPITOLA 4. IMPLEMENTACE – Index mateˇrské planety typu integer, kolem n´ıˇz bude tato planeta ob´ıhat. Pokud je hodnota rovna -1 nebo je index shodn´ y s indexem planety, znamená to, ˇze planeta nemá definovanou svou mateˇrskou planetu. – Název textury.

4.5.2

V´ ystupn´ı soubory

Informace o pr˚ ubˇehu simulace a GP lze ukládat do v´ ystupn´ıch soubor˚ u. Tvorbu nˇekter´ ych v´ ystupn´ıch soubor˚ u lze zakázat, jiné se naopak vytvoˇr´ı pˇri kaˇzdém bˇehu simulace. • Trajektorie lod´ı - Soubor ve formátu pro MatLab nacházej´ıc´ı se ve sloˇzce ShipRoutes, kter´ y má uloˇzené informace o pozici lodi a jej´ı rychlosti. Dále obsahuje script, kter´ y vrát´ı trojrozmˇern´ y graf s trajektori´ı lodi. Tento v´ ystupn´ı soubor je nepovinn´ y a lze jej zakázat pomoc´ı promˇenné WRITE SHIP POSITIONS INTO FILE v souboru Setting.java. • Pr˚ ubˇeh evoluce - Soubor pro MatLab obsahuj´ıc´ı informace o v´ yvoji nejlepˇs´ı fitness a pr˚ umˇerné fitness celé populace spolu se scripty na zobrazen´ı r˚ uzn´ ych statistik do grafu. Soubor se vygeneruje vˇzdy, kdyˇz je spuˇstˇeno GP. • Seznam individuál˚ u v populaci Povinné soubory (pokud je zapnuté GP). Pro kaˇzdou generaci je urˇcen jeden textov´ y soubor, kter´ y obsahuje nastaven´ı parametr˚ u a operátor˚ u GP a v´ yˇcet individuál˚ u v populaci spolu s jejich fitness hodnotou. Tyto soubory lze vyuˇzit k naˇcten´ı populace a pokraˇcovat v evoluci. • Nejlepˇs´ı individuál - Povinné soubory (pokud je zapnuté GP), které obsahuj´ı informace o nejlepˇs´ıch individuálech nalezen´ ych bˇehem evoluce. Tyto soubory lze opˇetovnˇe naˇc´ıst jako program ovládaj´ıc´ı lod’.

4.6

Moˇ znosti nastaven´ı

Program nab´ız´ı mnoho moˇzn´ ych nastaven´ı pro vizualizaci, vlastnost´ı lodi i genetického programován´ı. Toto nastaven´ı se nacház´ı ve tˇr´ıdˇe Universe3D.Settings. Mnoho moˇznost´ı lze nastavit pˇr´ımo z menu (4.7) pˇred spuˇstˇen´ım samotné simulace.

ˇ 4.6. MOZNOSTI NASTAVENÍ

4.6.1

39

Nastaven´ı vizualizace

Toto nastaven´ı se projev´ı pouze tehdy bude-li program spuˇstˇen vizualizac´ı. • boolean VISUALISATION - Moˇznost pustit program s vizualizac´ı. Vizualizace je dobrá pro shlédnut´ı v´ ysledk˚ u genetického programován´ı. Naopak pro samotné GP nen´ı potˇreba a jen zpomaluje jeho bˇeh. • int GRAPHIC QUALITY - Poˇcet polygon˚ u, z nichˇz se skládá kaˇzdá koule v simulaci. Toto ˇc´ıslo velice ovlivˇ nuje rychlost vizualizace. • boolean FIND OPTIMAL RESOLUTION - Program nalezne optimáln´ı hodnotu promˇenné GRAPHIC QUALITY na základˇe hodnoty FPS. • boolean DRAW SHIP ROUTES - Vykreslován´ı trajektorie lod´ı. • boolean SHOW FPS - Zobrazován´ı poˇctu vykreslen´ ych scén za vteˇrinu. • boolean SHOW LOS - Moˇznost zobrazovat spojnice mezi vˇsemi dvojicemi lod´ı, pokud se mezi dvojic´ı lod´ı nevyskytuje ˇza´dná pˇrekáˇzka.

4.6.2

Nastaven´ı pro lodˇ e

• int VISIBLE DISTANCE - Vzdálenost, pro kterou se poˇc´ıtaj´ı LOS (3.5). • int WEAPONS RANGE - Dolet stˇrely. • double SHOT SPEED - Rychlost stˇrel. ˇ • double SHOOTING FREQUENCY - Casov´ a prodleva mezi dvˇema v´ ystˇrely. ´ • double SHIP ROTATION STEP - Uhel pootoˇcen´ı za jeden krok. • double SHIP SPEED STEP - Maximáln´ı zmˇena tahu motor˚ u lodi mezi dvˇema ˇcasov´ ymi okamˇziky. • double SHIP MAX SPEED - Maximáln´ı moˇzná rychlost lodi, dosaˇzitelná pomoc´ı motor˚ u. P˚ usoben´ım gravitaˇcn´ıch sil na lod’ m˚ uˇze b´ yt tato hodnota pˇrekroˇcena.

40


4.6.3

Konstanty

Konstanty jsou v programu zavedeny proto, aby simulace byla rychlejˇs´ı a odehrávala se v menˇs´ım prostoru. Jejich nastaven´ı je v´ ysledkem experiment˚ u a prostˇred´ı je na jejich zmˇenu velice citlivé, proto se nedoporuˇcuje jejich hodnoty mˇenit. • int SIZE SCALE - Tato konstanta upravuje velikost tˇeles. Jelikoˇz je velikost tˇelesa zadávána jako pr˚ umˇer koule v kilometrech (u planet se velikosti pohybuj´ı ˇrádovˇe v tis´ıc´ıch kilometr˚ u), je tˇreba toto ˇc´ıslo zmenˇsit tak, aby byla v´ ysledná velikost tˇeles vhodná pro grafické prostˇred´ı. • double DISTANCE SCALE - Konstanta upravuj´ıc´ı vzdálenost. • double WEIGHT SCALE - Upravuje váhu objekt˚ u. • double SATELITE GRAVITY SCALE - Konstanta upravuj´ıc´ı velikost gravitaˇcn´ı s´ıly, kterou p˚ usob´ı planeta na sv˚ uj pˇr´ırodn´ı satelit.

4.6.4

Nastaven´ı pro GP

Nejd˚ uleˇzitˇejˇs´ı promˇenné v programu, t´ ykaj´ıc´ı se nastaven´ı parametr˚ u pro GP. Vˇetˇsinu tˇechto promˇenn´ ych lze nastavit v u ´vodn´ım menu programu. • boolean GENETIC PROGRAMMING - Promˇenná urˇcuje, bude-li spuˇstˇeno GP. Pokud je tato hodnota promˇenné true, doporuˇcuje se promˇennou VISUALISATION (4.6.1) nastavit na false kv˚ uli rychlosti bˇehu samotného GP. • int POPULATION SIZE - Velikost populace. • boolean INITIAL GROW METHOD - Pˇri generován´ı nov´ ych individuál˚ u bude pouˇzitá metoda grow (2.2). • boolean INITIAL FULL METHOD - Pˇri generován´ı nov´ ych individuál˚ u bude pouˇzitá metoda full. Pozn´ amka: Pokud maj´ı obˇe promˇenné INITIAL GROW METHOD a INITIAL FULL METHOD hodnotu false, je pˇri generován´ı individuál˚ u pouˇzita metoda Ramped half-and-half. • int NUMBER OF GENERATIONS - Poˇcet generac´ı, po kter´ y GP pobˇeˇz´ı.

2

ˇ 4.6. MOZNOSTI NASTAVENÍ

41

• int GP MIN DEPTH - Minimáln´ı hloubka individuál˚ u. • int GP MAX DEPTH - Maximáln´ı hloubka individuál˚ u. • boolean SUBTREE MUTATION - Mutaˇcn´ı operátor bude subtree mutation (2.7). • boolean NODE REPLACEMENT MUTATION - Mutaˇcn´ı operátor bude node replacement mutation. Pozn´ amka: Nelze pouˇz´ıt v´ıce mutaˇcn´ıch operátor˚ u pˇri bˇehu GP, tj. právˇe jedna z promˇenn´ ych NODE REPLACEMENT MUTATION a SUBTREE MUTATION mus´ı m´ıt hodnotu true, ostatn´ı pak hodnotu false, jinak vznikne chyba a program se ukonˇc´ı.

2

• boolean TOURNAMENT SELECTION - Jako selekˇcn´ı operátor bude pouˇzita turnajová selekce (2.5) • boolean ROULETTE SELECTION - Jako selekˇcn´ı operátor bude pouˇzita roulette wheel selection. • boolean RANDOM SELECTION - Individuál pro aplikován´ı genetick´ ych operátor˚ u bude vybrán náhodnˇe. • boolean DETERMINISTIC SELECTION - Bˇehem evoluce jedné generace bude vybrán kaˇzd´ y rodiˇcovsk´ y individuál právˇe jednou. Pozn´ amka: Nelze pouˇz´ıt pˇri bˇeˇehu GP nˇekolik selekˇcn´ıch operátor˚ u najednou, tj. právˇe jedna z promˇenn´ ych TOURNAMENT SELECTION, ROULETTE SELECTION, RANDOM SELECTION a DETERMINISTIC SELECTION mus´ı m´ıt hodnotu true, ostatn´ı pak hodnotu false, jinak vznikne chyba a program se ukonˇc´ı.

2

• int TOURNAMENT SIZE - Poˇcet individuál˚ uu ´ˇcastn´ıc´ıch se turnajové selekce. • boolean TARPEIAN METHOD - Kromˇe kontroly hloubky individuál˚ u bude pro kontrolu bloatu (2.9) pouˇzita i Tarpeian metoda. • double TARPEIAN PROB - Pravdˇepodobnost s niˇz Tarpeian metoda vylouˇc´ı individuál, jehoˇz velikost je vˇetˇs´ı neˇz pr˚ umˇerná velikost individuál˚ u v populaci. • boolean [jmeno] NODE - Napˇr´ıklad ADD NODE, SUB NODE,... urˇcuj´ı, zda bude konkrétn´ı uzel pouˇzit pˇri GP.

42

KAPITOLA 4. IMPLEMENTACE • boolean USE INDIVIDUAL - Naˇcte jiˇz vytvoˇren´ y ˇr´ıdic´ı program pomoc´ı GP a t´ımto program bude ovládaná lod’. Pozn´ amka: Pokud je tato promˇenná true, nesm´ı b´ yt souˇcasnˇe true promˇenná GENETIC PROGRAMMING.

2

• String BEST INDIVIDUAL - Cesta k uloˇzenému ˇr´ıdic´ımu programu.

4.6.5

Nastaven´ı v´ ystup˚ u

• boolean WRITE SHIP POSITIONS INTO FILE - Trajektorie lod´ı bude zapsaná do souboru. • boolean PRINT SIMULATION INFORMATION - Vypisuje informace o dˇen´ı v simulaˇcn´ım prostˇred´ı. • boolean PRINT GENETIC INFORMATION - Vypisuje informace o pr˚ ubˇehu genetického programovan´ı.

4.7

Menu

Program Universe3D obsahuje menu pro nastaven´ı r˚ uzn´ ych parametr˚ u. U tlaˇc´ıtek se nacházej´ı popisky, které ukazuj´ı aktuáln´ı nastaven´ı dané poloˇzky. Po spuˇstˇen´ı simulace parametry nelze mˇenit. Menu se skládá z nˇekolika ˇca´st´ı: main menu (4.7.1), genetic programming menu (4.7.2) a best evolved individual menu (4.7.3). Kaˇzdá z nich je reprezentovaná vlastn´ı tˇr´ıdou a je dˇelená na nˇekolik podtˇr´ıd.

4.7.1

Main menu

V hlavn´ım menu se nacházej´ı tyto volby: • Visualisation - Moˇznost vypnout nebo zapnout vizualizaci instance programu Universe3D. • Genetic programming - Vypne nebo zapne genetické programován´ı. Pˇri povolen´ı genetického programován´ı se zpˇr´ıstupn´ı poloˇzka Genetic programming settings.

4.8. SCREENSHOTY ZE HRY

43

• Genetic programming settings - Otevˇre menu pro nastaven´ı parametr˚ u genetického programován´ı (4.7.2). • Use evolved individual - Vesm´ırná lod’ bude ovládaná pomoc´ı programu, vytvoˇreného genetick´ ym programován´ım. Pokud je zvolena tato moˇznost, nelze zapnout genetické programován´ı! • Load evolved individual - Menu pro naˇcten´ı programu ovládaj´ıc´ıho lod’. • Start program - Spust´ı samotnou simulaci. • Exit program - Ukonˇc´ı program.

4.7.2

Genetic programming menu

Toto menu slouˇz´ı k nastaven´ı parametr˚ u pro genetické programován´ı. • Genetic task - V´ ybˇer mezi jednotliv´ ymi u ´lohami pro genetické programován´ı. • Population size - Nastaven´ı velikosti populace. • Evolution parameters - Nastaven´ı ostatn´ıch parametr˚ u jako: maximáln´ı hloubka strom˚ u, inicializaˇcn´ı metoda, operátory kˇr´ıˇzen´ı a mutace a jejich pravdˇepodobnost pouˇzit´ı a metoda pro kontrolu bloatu. • Select nodes - V´ ybˇer termináln´ıch a funkˇcn´ıch symbol˚ u. • Load evulution - Naˇcte uloˇzenou populaci i s parametry ze souboru.

4.7.3

Best evolved individual menu

Toto menu umoˇzn ˇuje nahrát uloˇzen´ y individuál, vytvoˇren´ y pomoc´ı genetického programován´ı. Pomoc´ı tohoto individuálu bude ovládaná lod’ s indexem nula.

4.8

Screenshoty ze hry

V této kapitole jsou grafické ukázky programu Universe3D.

44


Obrázek 4.4: Planety.

Obrázek 4.5: Lod’ a meteor.

Obrázek 4.6: Ukázka pohybu lodi v gravitaˇcn´ım poli bez pouˇzit´ı motor˚ u.

4.8. SCREENSHOTY ZE HRY

´ Obrázek 4.7: Uvodn´ ı menu a menu pro nataven´ı parametr˚ u GP.

45

46


Kapitola 5 Experimenty a diskuse V této kapitole je popsáno nastaven´ı simulaˇcn´ıho prostˇred´ı pro GP (5.1) a dále jsou zde v´ ysledky a diskuse nad jednotliv´ ymi experimenty (5.2).

5.1

Nastaven´ı simulaˇ cn´ıho prostˇ red´ı

Vˇsechny experimenty se provádˇej´ı pˇri stejném nastaven´ı simulaˇcn´ıho prostˇred´ı, které je uvedeno v následuj´ıc´ım seznamu: • Konstanty – WEIGHT SCALE = 300.10−3 – SIZE SCALE = 1000 – DISTANCE SCALE = 11e11 – SATELITE GRAVITY SCALE = 10e18 • Lod – SHIP ROTATION STEP = 0.7◦ – SHIP SPEED STEP = 0.0035km.s−2 – SHIP MAX SPEED = 1.0km.s−1 – SHOOTING FREQUENCY = 0.2 – SHOT SPEED = 2.0km.s−1 47

48

KAPITOLA 5. EXPERIMENTY A DISKUSE – VISIBLE DISTANCE = 100 km – WEAPONS RANGE = 100 km

Pozn´ amka: Pro konverzi jednotek berme kilometr jako vzdálenost jedna v simulaˇcn´ım prostˇred´ı a vteˇrinu jako interval mezi dvˇema ˇcasov´ ymi okamˇziky.

5.2

2

Experimenty

Jelikoˇz je pohyb v trojrozmˇerném prostoru d´ıky rotac´ım matematicky sloˇzit´ y, rozhodl jsem se postupovat od jednoduch´ ych u ´loh ke sloˇzitˇejˇs´ım. Kaˇzd´ y individuál je testován a vyhodnocován na nˇekolika instanc´ıch, po urˇcitou dobu nebo do nˇejaké urˇcité události (sráˇzka tˇeles). U vˇsech u ´loh se maximalizuje fitness hodnota a, pokud to druh u ´lohy umoˇzn ˇuje, minimalizuje souˇcet spotˇrebovaného paliva a ˇcasu (poˇcet ˇcasov´ ych okamˇzik˚ u) potˇrebného k dosaˇzen´ı c´ıle. Minimalizace tˇechto poloˇzek nen´ı souˇcásti vzorce fitness funkce ale je pouˇz´ıvaná pˇri seˇrazován´ı individuál˚ u jak je znázornˇeno v algoritmu 4. ˇ Algorithm 4 Razen´ ı individuál˚ u Vstup: Individuál i1, i2; Vstup: Podobnostn´ı konstanta C = 0.1; V´ ystup: lepˇs´ı z obou individuál˚ u; if M ath.abs(i1.f itness − i2.f itness) > C then if i1.f itness < i2.f itness then return i2; else return i1; end if else if i1.f uel + i1.time ≤ i2.f uel + i2.time then return i1; else return i2; end if end if

5.2. EXPERIMENTY

49

Doba bˇehu evoluce je omezena poˇctem generac´ı nebo konvergenc´ı populace potomk˚ u. Bˇehem evoluce se ukládaj´ı informace o v´ yvoji fitness hodnoty nejlepˇs´ıho individuálu a pr˚ umˇerné fitness populace a potomk˚ u v závislosti na poˇctu v´ ypoˇct˚ u fitness hodnoty nebo na poˇctu generac´ı. Fitness funkce se poˇc´ıtá pro kaˇzd´ y test zvláˇst’ a po ukonˇcen´ı testován´ı je tato hodnota zpr˚ umˇerovaná. Minimáln´ı hodnota fitness je rovna nule. Ve vˇsech experimentech je jako mutaˇcn´ı operátor pouˇzita subtree-mutation a selekce je typu roulette wheel. Crossover a bloat control operátory nejsou pouˇzity.

V experimentech se pracuje s nˇekolika druhy strom˚ u: Strom slouˇz´ıc´ı k ovládán´ı rychlosti lodi, rotaˇcn´ı strom a strom pro stˇrelbu.

5.2.1

Zastaven´ı bez rotac´ı Název experimentu

Stop2D

Velikost populace

100

Poˇcet generaci

500

Maximáln´ı hloubka stromu

2

Poˇcet strom˚ u

1 (rychlost)

Poˇcet testovac´ıch instanc´ı

3

Ukonˇcovac´ı podm´ınky testu

500 ˇcasov´ ych okamˇzik˚ u, jedna vteˇrina, dva po sobˇe jdouc´ı ˇcasové okamˇziky s nulovou rychlost´ı lodi

Pouˇzité terminály

Distance (vzdálenost lod’-c´ıl), Speed (velikost rychlosti lodi)

Pouˇzité funkce Fitness funkce F

+, -, *, /, Abs, Log, Sin, Atan, Sqrt { 0 je-li N D ≥ 100, F = 100 − N D jinak. ND = vzdálenost lodi od c´ıle na konci testu

Tabulka 5.1: Nastaveni experimentu Stop2D.

Velice jednoduchá u ´loha, kdy je lod’ nasmˇerovaná na terˇc a jej´ım u ´kolem je doletˇet a zastavit co nejbl´ıˇze u terˇce. V této u ´loze se nepouˇz´ıvaj´ı rotace ani stˇrelba. Nasta-

50

KAPITOLA 5. EXPERIMENTY A DISKUSE

ven´ı GP pro tento experiment je v tabulce 5.1. Interpretace v´ ysledku GP executionResult v závislosti na velikosti rychlosti lodi shipSpeed je ˇr´ızena algoritmem 5. Tento algoritmus je pouˇz´ıván pro interpretaci v´ ysledk˚ u rychlostn´ıch strom˚ u ve vˇsech experimentech.

Algorithm 5 Mechanismus ovládán´ı rychlosti lodi Vstup: executionResult E; Vstup: rychlost lodi S; if E − S > ae then S = S + ae ; else if E − S < −ae then S = S − ae ; else if S < va &&E == 0.0 then S = 0.0; end if end if end if

ae je zmˇena velikosti rychlosti pomoc´ı motor˚ u (4.2).

5.2.1.1

V´ ysledky

umˇerné hodnoty nejlepˇs´ı fitness (modrá), pr˚ umˇerné fitness V grafu 5.1 jsou znázornˇeny pr˚ populace (ˇcervená) a pr˚ umˇerné hodnoty fitness potomk˚ u (zelená) z dvaceti bˇeh˚ u GP. Osa x je pro detailnˇejˇs´ı náhled na poˇcátek evoluce v logaritmickém mˇeˇr´ıtku.

5.2. EXPERIMENTY

51

Obrázek 5.1: Pr˚ ubˇeh evoluce experimentu Stop2D.

V´ ysledky tohoto experimentu z´ıská GP velice rychle a v pokroˇcilejˇs´ı fázi evoluce se uˇz jen minimalizuj´ı hodnoty spotˇrebovaného ˇcasu a paliva. Jedna generace se vytváˇr´ı pˇet aˇz dvacet vteˇrin a populace konverguje do dvaceti minut. Vybrané terminály a funkce dovoluj´ı pouˇz´ıt v´ ysledek i v trojrozmˇerném prostˇred´ı. Zaj´ımavost´ı je, ˇze pˇri nastaven´ı vˇetˇs´ı maximáln´ı hloubky strom˚ u nenajde GP tak dobré v´ ysledky. Velice ˇcast´ ym v´ ysledkem je strom 5.1.

log log DIST AN CE

Graf závislosti rychlosti lodi na vzdálenosti od c´ıle stromu 5.1 je na obr 5.2.

(5.1)

52


Obrázek 5.2: Graf závislosti rychlosti lodi na vzdálenosti od c´ıle.

5.2.2

Stˇ relba

Pˇri tomto experimentu je lod’ stále na stejné pozici a jej´ı smˇerov´ y vektor je d = (1, 0, 0). Dále se v simulaci vyskytuje pohybliv´ y terˇc, kter´ y mus´ı lod’ sestˇrelit. Lod’ zná pr˚ useˇc´ık trajektorie stˇrely a terˇce. Kaˇzdou testovac´ı instanci má k dispozici pouze jednu stˇrelu a pozice lodi, rychlost a smˇer pohybu terˇce v testovac´ıch instanc´ıch jsou r˚ uzné. Jelikoˇz se lod’ nepohybuje, minimalizace paliva a ˇcasu je zbyteˇcná. Nastaven´ı experimentu je v tabulce 5.2.

5.2. EXPERIMENTY

53

Název experimentu

Fire2D

Velikost populace

100

Poˇcet generaci

500

Minimáln´ı hloubka stromu

2


4

Poˇcet strom˚ u

1 (stˇrelba)


18


minut´ı c´ıle

Ukonˇcovac´ı podm´ınka celé evoluce 18 zásah˚ u Pouˇzité terminály

Distance (vzdálenost terˇc-pr˚ useˇc´ık), Speed (velikost rychlosti terˇce)

Pouˇzité funkce

+, -, *, /, Abs, Log, Sin, Atan, Sqrt, Unary Minus

Fitness funkce F

F = (TH * 100) + (100 - ND) ND = vzdálenost stˇrely od terˇce v posledn´ı instanci TH = poˇcet zásah˚ u terˇce Tabulka 5.2: Nastaven´ı experimentu Fire2D.

Interpretace v´ ysledku stromu je dána algoritmem 6 Algorithm 6 Mechanismus ovládán´ı stˇrelby lodi Vstup: executionResult E; Vstup: pr˚ useˇc´ık smˇerového vektoru lodi a trajektorie terˇce PP; Vstup: poloha lodi PL; Vstup: rychlost stˇrely V; Vstup: vzdálenost lodi od pr˚ useˇc´ıku S; Vstup: náboj N = 1; if E ≤ S/V && N > 0 then Stˇrelba(); N–; end if

5.2.2.1

V´ ysledky

Graf 5.3 znázorˇ nuje pr˚ umˇerné v´ ysledky fitness hodnot z dvaceti bˇeh˚ u GP. Osa x je v logaritmickém mˇeˇr´ıtku.

54


Obrázek 5.3: Pr˚ ubˇeh evoluce experimentu Fire2D.

Opˇet GP nalezne v´ ysledek brzy, vˇetˇsinou v prvn´ıch dvaceti generac´ıch. Jedna generace se vyv´ıj´ı tˇricet aˇz padesát vteˇrin a celá evoluce probˇehne do dvaceti minut. Experiment nedosahoval dobr´ ych v´ ysledk˚ u pˇri maximáln´ı hloubce rovné dvˇema, tud´ıˇz je tato hloubka nastavena jako minimáln´ı, aby se neprohledával prostor ˇspatn´ ych ˇreˇsen´ı.

5.2.3

Pron´ asledov´ an´ı

V simulaci se vyskytuj´ı dvˇe lodi, pronásledovatel a pachatel. Pronásledovatel má za u ´kol dopadnout pachatele v co nejkratˇs´ım ˇcase (za dopaden´ı pachatele se povaˇzuje sráˇzka obou lod´ı). Pachatel má danou trajektorii svého pohybu tˇremi body mezi nimiˇz se pˇresunuje dle algoritmu 7.

5.2. EXPERIMENTY

55

Algorithm 7 Algoritmus pro ovládán´ı lodi pachatele Vstup: terˇce[] T Vstup: poˇcet terˇc˚ uN Vstup: aktuáln´ı terˇc n = 0; Vstup: rychlost lodi S while true do if pachatel nem´ıˇr´ı na c´ıl T[n] then Proved’ rotaci o jeden rotaˇcn´ı krok; S = normalise(shipDirection) * 0.6; end if if pachatel dorazil do T[n] then n + +; if n == T.length then break; end if end if end while

Pachatel si udrˇzuje konstantn´ı rychlost ve smˇeru orientace lodi o velikosti 0.6, nep˚ usob´ı na nˇej setrvaˇcnost ani gravitaˇcn´ı s´ıla a lod’ ignoruje veˇskeré kolize mimo kolize dvou lod´ı. Chová se tedy jinak neˇz lod’ ovládaná pomoc´ı GP. Kdyˇz pachatel doraz´ı do posledn´ıho c´ıle, je simulace ukonˇcena. Tento experiment je prvn´ı z ˇrady dalˇs´ıch, kde jsou potˇreba dva stromy. Prvn´ı pro rotace a druh´ y pro rychlost. Interpretace v´ ysledku rotaˇcn´ıho stromu ve vˇsech experimentech je ˇr´ızena algoritmem 8. Nastaven´ı experimentu je v tabulce 5.3. Algorithm 8 Mechanismus ovládán´ı rotace lodi Vstup: executionResult E; Vstup: rotaˇcn´ı krok R = 0.7; Vstup: aktuáln´ı rotace yaw lodi Y; if M ath.abs(E) > R then Y = Y + (E/M ath.abs(E)) ∗ R; else Y =Y +E end if

56

KAPITOLA 5. EXPERIMENTY A DISKUSE Název experimentu

Persuit2D

Velikost populace

100

Poˇcet generaci

500


2

Poˇcet strom˚ u

2 (rotace, rychlost)


3


2000 ˇcasov´ ych okamˇzik˚ u, jedna vteˇrina, sráˇzka obou lod´ı


Distance (vzdálenost lod’-lod’), AngleDiff (´ uhel pootoˇcen´ı na protivn´ıka)

Pouˇzité funkce Fitness funkce F

+, -, *,     F =   

/, Abs, qrt, Atan, Log, Sin, Iflet 0

je-li N D ≥ 100,

100

sráˇzka lod´ı,

100 − N D jinak.

ND = nejbliˇzˇs´ı vzdálenost mezi lodˇemi Tabulka 5.3: Nastaven´ı experimentu Persuit2D.

5.2.3.1

V´ ysledky

Graf 5.4 závislosti fitness hodnoty na poˇctu generac´ı udává pr˚ umˇerné hodnoty z dvaceti bˇeh˚ u GP. Pro lepˇs´ı zobrazen´ı v´ yvoje v prvn´ıch generac´ıch je osa x v logaritmickém mˇeˇr´ıtku.

5.2. EXPERIMENTY

Obrázek 5.4: Pr˚ ubˇeh evoluce experimentu Persuit2D.

Ukázka trajektori´ı pronásledovatele a pachatele je na obrázku 5.5.

Obrázek 5.5: Trajektorie lodi v experimentu Persuti2D.

57

58

5.2.4


Pohyb v gravitaˇ cn´ım poli

V simulaci se nacház´ı lod’, terˇc a planeta. C´ılem je navigace lodi do c´ıle a ideálnˇe jej´ı zastaven´ı co nejbl´ıˇze c´ıly. Tento experiment byl puˇstˇen po tis´ıc generac´ı bez ukonˇcovac´ı podm´ınky konvergence populace. Bˇeh celé evoluce trval ˇrádovˇe des´ıtky hodin. Na základˇe tohoto pozorován´ı byla zavedena ukonˇcovac´ı podm´ınka konvergence populace a to mnohonásobnˇe urychlilo dalˇs´ı experimenty. Nastaven´ı experimentu je v tabulce 5.4. Název experimentu

GravStop2D

Velikost populace

100

Poˇcet generaci

1000


2

Poˇcet strom˚ u



10

Podm´ınka pˇreruˇsen´ı testován´ı individuálu sráˇzka lodi s planetou Ukonˇcovac´ı podm´ınky testu

1500 ˇcasov´ ych okamˇzik˚ u, jedna vteˇrina


Distance (vzdálenost lod’-c´ıl), Speed (rychlost lodi) AngleDiff, CollisionAngle, Konstanta

Pouˇzité funkce

+, -, *, /, Log, IfLet, Max, Min, IfCollide

Fitness funkce F

F = (100 - ND) + (10 * NS) ND = nejbliˇzˇs´ı vzdálenost mezi lodˇemi NS = rychlost, kdyˇz je lod’ nejbl´ıˇze c´ıli Tabulka 5.4: Nastaven´ı experimentu GravStop2D.

5.2.4.1

V´ ysledky

P˚ uvodnˇe byl c´ıl experimentu zamˇeˇren na zastaven´ı lodi co nejbl´ıˇze c´ıli, stejnˇe jako v exusob´ıc´ı na lod’ graperimentu 5.2.1, s t´ım rozd´ılem, ˇze se v simulaci nacház´ı planeta p˚ vitaˇcn´ı silou a lod’ mus´ı vyuˇz´ıt rotac´ı k dosaˇzen´ı c´ıle. Problém nastal u zastavován´ı. Jelikoˇz na lod’ p˚ usob´ı setrvaˇcnost a mechanismus zpomalován´ı (4.2) mˇen´ı rychlost pouze ve smˇeru orientace lodi, rychlost lodi se sice u terˇce sniˇzuje ale sloˇzka rychlosti ze setrvaˇcnosti poté “odtáhne lod’ do strany”, mimo dosah c´ıle. Lod’ se pak pohybuje kolem c´ıle v kruz´ıch (obr. 5.6) jako v pˇr´ıpadˇe individuálu 5.5

5.2. EXPERIMENTY Rotace

59

IfCollide 9.387669342798125 Iflet DISTANCE 10.663324931803926 COLLISION ANGLE ANGLEDIFF

Rychlost

IfCollide Log ANGLEDIFF - DISTANCE 11.551224407391091

Fitness evals 27034 Tabulka 5.5: Struktura individuálu opisuj´ıc´ıho kruhovou trajektorii kolem c´ıle.

Obrázek 5.6: Trajektorie

lodi

krouˇz´ıci

kolem

c´ıle

v

experimentu

GravStop2D.

nebo se opakovanˇe vzdaluje a pˇribliˇzuje k c´ıli a opisuje hvˇezdicovitou trajektorii (obr. 5.7) jako individuál 5.6.

60


Rotace

IfCollide Iflet ANGLEDIFF SPEED COLLISION ANGLE -3.607515549399359 IfCollide -2.3487230349122727 ANGLEDIFF

Rychlost

Iflet / 7.1494131827019345 COLLISION ANGLE Max 9.9335077812971 11.527967427926647 - DISTANCE 8.763741644568235 ANGLEDIFF

Fitness evals 56398 Tabulka 5.6: Struktura individuálu opisuj´ıc´ıho hvˇezdicovitou trajektorii kolem c´ıle.

Obrázek 5.7: Hvˇezdicovitá trajektorie lodi v experimentu GravStop2D.

Pr˚ ubˇeh evoluce je zobrazen na obr. 5.8. Graf zobrazuje pr˚ umˇerné hodnoty z dvaceti bˇeh˚ u GP.

5.2. EXPERIMENTY

61

Obrázek 5.8: Pr˚ ubˇeh evoluce experimentu GravStop2D.

5.2.5

Pron´ asledov´ an´ı v gravitaˇ cn´ım poli

Podobnˇe jako v experimentu Pron´ asledov´ an´ı (5.2.3) se i zde vyskytuj´ı pronásledovatel a pachatel a c´ılem testu je dopadnout pachatele. V simulaci se nav´ıc vyskytuj´ı tˇri planety p˚ usob´ıc´ı na lodˇe gravitaˇcn´ı silou. Pachatel m˚ uˇze skrz tyto planety prolétávat (detekce koliz´ı této lodi s planetami je vypnuta). Algoritmus ˇr´ızen´ı lodi pachatele je stejn´ y jako v experimentu Pronásledován´ı. Nastaven´ı experimentu je v tabulce 5.7.

62


Název experimentu

PersuitGrav2D

Velikost populace

100

Poˇcet generaci

500


2

Poˇcet strom˚ u



3

Podm´ınka pˇreruˇsen´ı testován´ı individuálu sráˇzka lodi s planetou Ukonˇcovac´ı podm´ınky testu

jedna vteˇrina, sráˇzka obou lod´ı


Distance (vzdálenost lod’-lod’), AngleDiff, CollisionAngle, One

Pouˇzité funkce

Abs, Log, Sin, Iflet, Max, Min, IfCollide   je-li N D ≥ 100,   0 F = 100 sráˇzka lod´ı,    100 − N D jinak.

Fitness funkce F

ND = nejbliˇzˇs´ı vzdálenost mezi lodˇemi Tabulka 5.7: Nastaven´ı experimentu PersuitGrav2D.

5.2.5.1

V´ ysledky

Celá evoluce probˇehne do dvou hodin vˇcetnˇe konvergence populace. Ne vˇzdy vˇsak GP nalezne program s fitness hodnotou rovnou stu. V´ yvoj jedné generace trvá zhruba jednu minutu. Pr˚ ubˇeh evoluce je znázornˇen v grafu 5.9.

5.2. EXPERIMENTY

63

Obrázek 5.9: Pr˚ ubˇeh evoluce experimentu PersuitGrav2D.

Trajektorie lod´ı tˇr´ı vybran´ ych individuál˚ u jsou zobrazeny v následuj´ıc´ıch grafech. Prvn´ı, rotaˇcn´ı, strom ˇr´ıd´ı rotace a druh´ y, rychlostn´ı, ˇr´ıd´ı rychlost lodi. Stromy jsou v prefixovém zápisu. Struktura prvn´ıho individuálu je v tabulce 5.8 a trajektorie lodi v r˚ uzn´ ych instanc´ıch na obrázc´ıch 5.10 a 5.11.

Rotace

Iflet Iflet COLLISION ANGLE COLLISION ANGLE DISTANCE DISTANCE 1 ANGLEDIFF IfCollide COLLISION ANGLE ANGLEDIFF

Rychlost

Iflet Abs COLLISION ANGLE Sin ANGLEDIFF 1 DISTANCE

Fitness evals 3289 Tabulka 5.8: Struktura prvn´ıho individálu.

64


Obrázek 5.10: Trajektorie lodi v experimentu PersuitGrav2D.


Struktura druhého individuálu je v tabulce 5.9 a trajektorie lodi v r˚ uzn´ ych instanc´ıch

5.2. EXPERIMENTY

65

na obrázc´ıch 5.12 a 5.13.

Rotace

Iflet Abs COLLISION ANGLE COLLISION ANGLE Min DISTANCE ANGLEDIFF Min COLLISION ANGLE 1

Rychlost

Max Max ANGLEDIFF 1 Abs ANGLEDIFF

Fitness evals 8721 Tabulka 5.9: Struktura druhého individálu.


66



Struktura tˇret´ıho individuálu je v tabulce 5.10 a trajektorie lodi na obrázku 5.14.

Rotace

Iflet Abs 1 Sin COLLISION ANGLE Log ANGLEDIFF IfCollide COLLISION ANGLE ANGLEDIFF

Rychlost

Iflet Sin ANGLEDIFF Abs COLLISION ANGLE Abs DISTANCE IfCollide 1 1

Fitness evals 4328 Tabulka 5.10: Struktura tˇret´ıho individálu.

5.3. DISKUSE

67


5.3

Diskuse

Pˇri psan´ı programu Universe3D, jsem narazil na mnoho moˇznost´ı, jak ˇreˇsit nˇejak´ y problém. Prvn´ım z problém˚ u byla u ´prava v´ ysledku vráceného programem vytvoˇren´ ym pomoc´ı GP. Jako nejlepˇs´ı se ukázalo ponechat v´ ysledek ER v p˚ uvodn´ı hodnotˇe beze zmˇen. V´ ysledek lze vˇsak dále upravovat, aby lépe vyhovoval potˇrebám experimentu. Pokud jde o rychlostn´ı stromy, byly vyzkouˇseny tyto tˇri u ´pravy na u ´kolu Stop2D: • Desetina zbytku po dˇelen´ı deseti ER = (ER % 10.0) \ 10.0 Tato u ´prava umoˇzn ˇuje ER s hodnotami vˇetˇs´ımi neˇz deset ovlivˇ novat rychlost lodi. Rychlost ale velmi ˇcasto kol´ısá a to má za následek vyˇsˇs´ı spotˇrebu paliva a ˇcas potˇrebn´ y k dosaˇzen´ı c´ıle je také delˇs´ı. • Desetina v´ ysledku ER = ER \ 10.0

68

KAPITOLA 5. EXPERIMENTY A DISKUSE ´ Uprava, která nep˚ usob´ı tak ˇcasté zmˇeny rychlosti lodi, coˇz je dobré pro spotˇrebu paliva. Na druhou stranu, reakce lodi nejsou tak rychlé. Ve v´ ysledku tak lod’ pˇrelétává c´ıl a nebo se k c´ıli bl´ıˇz´ı velice pomalu. • V´ ysledek ponechán beze zmˇeny - Pouˇzitá metoda, pˇri které je rychlost reakce lodi na potˇrebu zmˇeny rychlosti dostaˇcuj´ıc´ı. Nev´ yhodou je vyˇsˇs´ı spotˇreba paliva.

V´ ysledek rotaˇcn´ıho stromu je ponechán beze zmˇeny a znamená poˇzadovanou velikost u ´hlu rotace ve stupn´ıch, o kter´ y by se lod’ mˇela natoˇcit. Lze ale vyuˇz´ıt i rotace v radiánech jako je tomu u Evolving Steering Behaviours with Genetic Programming[8]. Dalˇs´ım problémem byla volba termináln´ıch a funkˇcn´ıch uzl˚ u pro GP. Volba byla ovlivnˇena zp˚ usobem interpretace v´ ysledku stromu. Jelikoˇz je návratová hodnota typu double, je lepˇs´ı pouˇz´ıt terminály jako napˇr´ıklad Distance, AngleDiff neˇz napˇr´ıklad uzly ShipPositionX, ShipPositionY a ShipPositionZ vracej´ıc´ı jednotlivé sloˇzky vektoru polohy lodi, protoˇze je pak prostor prohledávan´ y genetick´ ym programován´ım menˇs´ı. Uzel Iflet se ukázal jako neefektivn´ı. Je to jedin´ y uzel s aritou ˇctyˇri, ˇc´ımˇz znaˇcnˇe zvˇetˇsuje velikost individuál˚ u a jeho struktura umoˇzn ˇuje tvoˇrit kód obsahuj´ıc´ı bloat. Napˇr´ıklad u individuálu 5.2 bude strom vracet vˇzdy hodnotu A. Uzly max a min mohou také zp˚ usobovat bloat podobnˇe jako uzel Iflet. if(DIST AN CE <= DIST AN CE) return A else return B

(5.2)

Naopak velmi uˇziteˇcné se ukázaly b´ yt uzly IfCollide, CollisionAngle a AngleDiff, které obstarávaj´ı veˇskeré rotace a s nimi spojené vektorové v´ ypoˇcty. Projekt Evolving Steering Behaviours with Genetic Programming vyuˇz´ıvá jako mnoˇzinu terminál˚ u relativn´ı souˇradnice tˇeles vzhledem k agentovi LOCAL X a LOCAL Y. V´ ysledek, kter´ y vrac´ı strom, je pak u ´hel pootoˇcen´ı lodi v radiánech. Nev´ yhodou této reprezentace jsou vˇetˇs´ı stromy a pomalejˇs´ı bˇeh GP. Pro program Universe3D by bylo potˇreba pˇridat terminály pro nejbliˇzˇs´ı pˇrekáˇzku (planeta, meteor) a nejbliˇzˇs´ı lod’. Nav´ıc v tomto projektu nemá agent stanoven´ y minimáln´ı u ´hel rotace za jeden ˇcasov´ y okamˇzik jak je tomu v programu Universe3D, na agenta nep˚ usob´ı setrvaˇcnost a agent si udrˇzuje konstantn´ı rychlost. Dalˇs´ı moˇznost´ı je pouˇz´ıt funkce typu “if else” a terminály, které rovnou provád´ı akce. Napˇr´ıklad terminály Accelerate, RotateYaw nebo Fire. Odpadá tak problém s interpretac´ı v´ ysledk˚ u strom˚ u. Souˇcasné GP v programu Universe3D lze lehce upravit aby vyhovoval

5.3. DISKUSE

69

tomuto zp˚ usobu, staˇc´ı ignorovat návratové hodnoty a implementovat akce jednotliv´ ym terminál˚ um. V neposledn´ı ˇradˇe by se ovládán´ı lodi mohlo ˇreˇsit pomoc´ı neuronov´ ych s´ıt´ı. ˇ Casovˇ eu ´sporná se ukázala metoda pˇreruˇsován´ı testován´ı individuál˚ u pˇri selhán´ı v nˇekterém z test˚ u. Individuál jehoˇz c´ılem je vyhnout se pˇrekáˇzce a jenˇz neuspˇeje jiˇz v prvn´ım testu a do pˇrekáˇzky naraz´ı, nemá smysl testovat dále. Uˇsetˇr´ı se tak ˇcas, kter´ y je vˇenován na testován´ı slibnˇejˇs´ıch individuál˚ u. Testován´ı individuál˚ u mus´ı b´ yt vˇzdy na stejné sadˇe instanc´ı. Pokud jsou instance náhodnˇe generované, je fitness hodnota zavádˇej´ıc´ı a pˇrevládá prvek náhody nad funkˇcnost´ı vyvinutého programu. Toto plat´ı i pro v´ıce bˇeh˚ u GP.

70


Kapitola 6 Z´ avˇ er Projekt u ´spˇeˇsnˇe simuluje trojrozmˇerné vesm´ırné prostˇred´ı a navrˇzené experimenty dosahuj´ı velmi dobr´ ych v´ ysledk˚ u. Nicménˇe experimenty jsou ˇcasovˇe nároˇcné a je nad s´ıly jednotlivce vyzkouˇset vˇsechny moˇzné postupy s r˚ uzn´ ymi mnoˇzinami uzl˚ u. Lze pouˇz´ıt jinou mnoˇzinu uzl˚ u, klasické GP s terminály, které provádˇej´ı r˚ uzné akce, nebo stronglytyped GP s v´ıce datov´ ymi typy neˇz jen double. Dále je pak moˇzné pˇridat mnoho nov´ ych experiment˚ u jako je tˇreba stˇrelba na nerovnomˇernˇe pohybuj´ıc´ı se terˇc, bitva mezi nˇekolika lodˇemi, nebo pronásledován´ı s jin´ ym algoritmem pro ovládán´ı pachatele. Jelikoˇz je simulace psaná pro trojrozmˇerné prostˇred´ı, lze experimenty rozˇs´ıˇrit o tˇret´ı rozmˇer.

71

72

´ ER ˇ KAPITOLA 6. ZAV

Literatura [1] Poli R., Langdon W.B. and McPhee N.F.: A field guide to genetic programming, Lulu Enterprises Uk Limited (2008). [2] Liviu Panait and Sean Luke: Alternative Bloat Control Methods. [3] Diana Gruber: The Mathematics of the 3D Rotation Matrix [online], publikováno: 30.10.2000. Dostupné z http://www.fastgraph.com/makegames/3drotation/. [4] Millington I.: Game Engine Physics Development Second Edition, Elsevier Inc. (2010). [5] Florin Diacu: Solution of the n-body problem [6] Tancred Lindholm: N-body algorithms (1999) [7] Michal Turek: NeHe OpenGL Tutori´ aly (2004). Dostupné z http://nehe.opengl.cz/. [8] Vogel Daniel.: Evolving Steering Behaviours with Genetic Programming [online], publikováno: záˇr´ı 2004. Dostupné z http://www.nonsequitoria.com/2521/.

73

74

LITERATURA

Pˇ r´ıloha A Obsah pˇ riloˇ zen´ eho CD K této práci je pˇriloˇzeno CD, na kterém jsou uloˇzeny zdrojové kódy. • .\ DP - Sloˇzka obsahuj´ıc´ı text DP. • .\ Experimenty - Sloˇzka s vyvinut´ ymi individuály. • .\ Universe3D - Sloˇzka se zdrojov´ ym kódem projektu Uninverse3D psaném v jazyce Java. • .\ Zadani - Sloˇzka obsahuj´ıci kopii zadán´ı DP.

I

Fakulta elektrotechnická. genetického programování

Recommend Documents