Vysok´ e uˇ cen´ı technick´ e v Brnˇ e Fakulta informaˇcn´ıch technologi´ı
ˇ ´IKOVY ´ PROJEKT ROCN
Zbyˇ sek Gajda
kvˇeten 2004
Abstrakt Pˇredkl´adan´a pr´ace se zab´ yv´a evoluˇcn´ım umˇen´ım. K tomu jsou vyuˇzity techniky genetick´eho programov´an´ı, kter´e umoˇzn ˇ uje generovat a modifikovat syntaktick´ y strom. Takov´ yto vygenerovan´ y syntaktick´ y strom je pak pˇretransformov´an, s vyuˇzit´ım znalost´ı o frakt´alech a dynamick´ ych syst´emech v komplexn´ı rovinˇe, v obraz s frakt´alem. Pro interakci s umˇelcem slouˇz´ı grafick´e uˇzivatelsk´e rozhran´ı zobrazen´e ve webov´em prohl´ıˇzeˇci. Kl´ıˇ cov´ a slova Evoluce, evoluˇcn´ı algoritmy, genetick´e programov´an´ı, syntaktick´ y strom, evoluˇcn´ı n´avrh, frakt´al, frakt´al v komplexn´ı rovinˇe, grafick´e uˇzivatelsk´e rozhran´ı.
Podˇ ekov´ an´ı R´ad bych na tomto m´ıstˇe podˇekoval vedouc´ımu sv´eho roˇcn´ıkov´eho projektu Ing. Luk´aˇsi Sekaninovi, Ph.D. za jeho cenn´e rady a za zap˚ ujˇcenou literaturu.
Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto pr´aci vypracoval samostatnˇe pod veden´ım Ing. Luk´aˇse Sekaniny, Ph.D. a ˇze jsem uvedl vˇsechny liter´arn´ı prameny a publikace, ze kter´ ych jsem ˇcerpal.
V Brnˇe dne 11. kvˇetna 2004
Zbyˇsek Gajda
Obsah ´ 1 Uvod 2 Evoluˇ cn´ı n´ avrh 2.1 Biologick´a evoluce . . . . . . . 2.2 Evoluˇcn´ı algoritmy . . . . . . . 2.2.1 Genetick´e algoritmy . . 2.2.2 Genetick´e programov´an´ı 2.2.3 Evoluˇcn´ı strategie . . . 2.2.4 Evoluˇcn´ı programov´an´ı 2.3 Evoluˇcn´ı n´avrh . . . . . . . . . 2.3.1 Evoluˇcn´ı umˇen´ı . . . . .
2 . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
3 Frakt´ aly ´ 3.1 Uvod do teorie frakt´al˚ u . . . . . . . . . 3.2 Typy frakt´al˚ u . . . . . . . . . . . . . . . 3.2.1 L-syst´emy . . . . . . . . . . . . . 3.2.2 Syst´em iterovan´ ych funkci (IFS) 3.2.3 Dynamick´e syst´emy . . . . . . . 3.2.4 Nepravideln´e (n´ahodn´e) frakt´aly
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . .
3 3 3 3 4 6 6 6 7
. . . . . .
8 8 9 10 10 10 11
4 Syst´ em Gefra 12 4.1 Popis syst´emu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Zp˚ usob implementace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 Z´ avˇ er
15
A Uˇ zivatelsk´ a pˇ r´ıruˇ cka
18
B Uk´ azky vygenerovan´ ych obr´ azk˚ u
20
1
Kapitola 1
´ Uvod Pˇred nˇekolika lety se obecnˇe poˇc´ıtaˇce pˇri n´avrhu pouˇz´ıvali jen jako n´ahrada r´ ysovac´ıho prkna. V souˇcasnosti se vˇsak zaˇc´ın´a prosazovat n´avrh s vyuˇzit´ım poznatk˚ u o evoluci. N´avrh´aˇr uˇz nemus´ı sv´e n´avrhy vym´ yˇslet a pak je pˇren´aˇset do poˇc´ıtaˇce, n´avrh´aˇr dnes m˚ uˇze nechat nov´ y n´avrh ”vymyslet” pˇr´ımo poˇc´ıtaˇc, podle pravidel stanoven´ ych n´avrh´aˇrem. Pak uˇz z´aleˇz´ı jen na n´avrh´aˇri ˇci c´ılov´e skupinˇe, jestli se mu n´avrh l´ıb´ı nebo nel´ıb´ı. Pˇrekl´adan´a pr´ace se zab´ yv´a evoluˇcn´ım umˇen´ım, kter´e je jedno z odvˇetv´ı evoluˇcn´ıho n´avrhu, a jeho implementac´ı do syst´emu zobraziteln´eho na webov´e str´ance. Syst´emy evoluˇcn´ıho n´avrhu s oblibou a t´emˇeˇr v´ yhradnˇe vyuˇz´ıvaj´ı pro evoluci tzv. evoluˇcn´ı algoritmy, kter´e principy evoluce dobˇre popisuj´ı a vyuˇz´ıvaj´ı. K n´avrhu obraz˚ u s frakt´aly bylo v´ yhodnˇe pouˇzito konkr´etnˇe genetick´e programov´an´ı. Algoritmy toto typu pracuj´ı obecnˇe se syntaktick´ ym stromem, s jehoˇz vhodnou definic´ı se d´a frakt´al nejl´epe popsat. Takov´ yto syntaktick´ y strom se pak d´a s vyuˇzit´ım poznatk˚ u o dynamick´ ych syst´emech zobrazit jako obraz s frakt´alem. K uplatˇ nov´an´ı evoluˇcn´ıch princip˚ u poslouˇz´ı n´avrh´aˇri grafick´e uˇzivatelsk´e rozhran´ı implementovan´e v jazyce, kter´ y umoˇzn ˇ uje interakci pˇr´ımo z webov´e str´anky.
2
Kapitola 2
Evoluˇ cn´ı n´ avrh Kapitola o evoluˇcn´ım n´avrhu pˇribliˇzuje pˇredevˇs´ım r˚ uzn´e evoluˇcn´ı algoritmy, kter´e se v oblasti evoluˇcn´ıch n´avrh˚ u mohou uplatnit.
2.1
Biologick´ a evoluce
V pˇr´ırodˇe jedinci jedn´e populace mezi sebou soutˇeˇz´ı o pˇreˇzit´ı a o moˇznost reprodukce na z´akladˇe toho, jak jsou pˇrizp˚ usobeni prostˇred´ı, ve kter´em ˇzij´ı. V pr˚ ubˇehu mnoha generac´ı se mˇen´ı struktura dan´e populace na z´akladˇe Darwinovy teorie o pˇrirozen´em v´ ybˇeru, tj. ˇze pˇreˇz´ıvaj´ı jen ti nejpˇrizp˚ usobenˇejˇs´ı jedinci. Reprodukc´ı nejpˇrizp˚ usobenˇejˇs´ıch jedinc˚ u (jedinc˚ u, kteˇr´ı pˇreˇzili do reproduktivn´ıho vˇeku) vznikaj´ı jedinci s vysokou pravdˇepodobnost´ı k pˇreˇzit´ı. Do reprodukce nav´ıc vstupuje nahodile mutace, kter´a nahodile ovlivˇ nuje (pozitivnˇe ˇci negativnˇe) genetick´ y materi´al populace jedinc˚ u.
2.2
Evoluˇ cn´ı algoritmy
Evoluˇcn´ı algoritmy jsou jedny ze z´akladn´ıch optimalizaˇcn´ıch metod zaloˇzen´ ych na Darwinovˇe evoluˇcn´ı teorii. Jako jejich hlavn´ı v´ yhoda b´ yv´a ˇcasto oznaˇcov´ana schopnost produkovat kvalitn´ı ˇreˇsen´ı v relativnˇe kr´atk´e dobˇe, a to i v pˇr´ıpadˇe znaˇcn´e rozlehlosti vstupn´ıch parametr˚ u a v´ ystupn´ıch ˇreˇsen´ıch. Proto evoluˇcn´ı algoritmy nach´azej´ı uplatnˇen´ı v nejr˚ uznˇejˇs´ıch optimalizaˇcn´ıch probl´emech. Evoluˇcn´ı algoritmy m˚ uˇzeme obecnˇe rozdˇelit na ˇctyˇri hlavn´ı skupiny: • genetick´e algoritmy, • genetick´e programov´an´ı, • evoluˇcn´ı strategie a • evoluˇcn´ı programov´an´ı.
2.2.1
Genetick´ e algoritmy
Genetick´ y algoritmus (GA) patˇr´ı mezi z´akladn´ı stochastick´e optimalizaˇcn´ı algoritmy s v´ yrazn´ ymi evoluˇcn´ımi rysy. V souˇcasnosti je GA pravdˇepodobnˇe nejpouˇz´ıvanˇejˇs´ı evoluˇcn´ı 3
algoritmus a to pˇredevˇs´ım v oblasti hled´an´ı ˇreˇsen´ı vysoce multimod´aln´ıch funkc´ı. Algoritmus vymyslel v 70. letech John Holland se z´amˇerem vysvˇetlit adaptivn´ı procesy pˇrirozen´ ych syst´em˚ u, a navrhnout inteligentn´ı syst´emy zaloˇzen´e na tˇechto procesech. Z´akladn´ı principy GA jsou obdobou vˇseobecn´ ych princip˚ u evoluce. Jedinec je v GA zak´odov´an do chromozomu, jako napˇr. bitov´ y ˇretˇezec, kde kaˇzd´ y bit pˇredstavuje jeden gen. Nad chromozomem je definov´an oper´ator mutace (v angl. mutation). Tento oper´ator n´ahodnˇe vybere gen z chromozomu a zmˇen´ı jej. D´ale je nad dvˇema chromozomy definov´an oper´ator kˇr´ıˇzeni (v angl. crossover ). Oper´ator kˇr´ıˇzen´ı typicky n´ahodnˇe vybere pozici ve dvou chromozomech, tzv. bod kˇr´ıˇzen´ı (v angl. crossover point), v t´eto pozici jsou chromozomy rozdˇeleny na dvˇe ˇca´sti, levou a pravou. Lev´e ˇca´sti jsou ponech´any beze zmˇeny a prav´e ˇca´sti jsou mezi sebou zamˇenˇeny. Pot´e jsou lev´e ˇca´sti a prav´e ˇca´sti k sobˇe opˇet pˇripojeny.
Obr´azek 2.1: Chov´an´ı oper´atoru mutace nad chromozomem.
Obr´azek 2.2: Chov´an´ı oper´atoru kˇr´ıˇzen´ı nad chromozomy. Svisl´a ˇca´ra oznaˇcuje bod kˇr´ıˇzen´ı. Na poˇca´tku je nahodile vygenerov´ana populace. Jedinci populace jsou ohodnoceni tzv. fitness funkc´ı, kter´a vrac´ı hodnotu v rozmez´ı 0 aˇz 100, kde vˇetˇs´ı hodnota znamen´a vˇetˇs´ı fitness, vˇetˇs´ı schopnost pˇreˇz´ıt. Jedinci proch´az´ı selekˇcn´ım tlakem, tj. jedinci s vhodnou fitness (vˇetˇs´ı nˇeˇz stanoven´a mez) jsou vyb´ır´ani jako kandid´ati pro reprodukci. Tento proces se naz´ yv´a selekce. Uˇzit´ım oper´ator˚ u kˇr´ıˇzen´ı a mutace jedinc˚ u s pˇrijatelnou fitness je vytvoˇrena nov´a populace (star´a populace zanik´a), doch´az´ı k tzv. reprodukci. Proces selekce a reprodukce se opakuje dokud nen´ı z´ısk´an jedinec s poˇzadovan´ ymi vlastnostmi.
2.2.2
Genetick´ e programov´ an´ı
Genetick´e programov´an´ı (GP) je speci´aln´ı formou genetick´eho algoritmu, kde jsou chromozomy pevn´e d´elky nahrazeny sloˇzitˇejˇs´ımi strukturami – syntaktick´ ymi stromy promˇenn´e
4
d´elky. GP vymyslel na pˇrelomu 80. a 90. let John Koza, kter´ y se pokouˇsel vytvoˇrit poˇc´ıtaˇcov´ y program, kter´ y by umˇel vyvinout poˇc´ıtaˇcov´e programy. Chromozom u GP, jak jiˇz bylo zm´ınˇeno dˇr´ıve, je reprezentov´an syntaktick´ ym stromem (viz. obr.2.3). Uzly u chromozomu pˇredstavuj´ı un´arn´ı, bin´arn´ı ˇci tern´arn´ı operace a listy termin´aln´ı symboly. Takov´ y chromozom m˚ uˇze pˇredstavovat aritmetick´ y v´ yraz, funkci nebo program.
Obr´azek 2.3: Pˇr´ıklad jedince v genetick´em programov´an´ı. Nad chromozomem je definov´an oper´ator mutace. Tento oper´ator n´ahodnˇe vybere podstrom, odstran´ı jej, a m´ısto nˇej vygeneruje nov´ y podstrom. D´ale je nad dvˇema chromozomy definov´an oper´ator kˇr´ıˇzen´ı. Oper´ator kˇr´ıˇzen´ı vybere n´ahodnˇe dva podstromy, kaˇzd´ y z jin´eho chromozomu, a ty se mezi sebou zamˇen´ı.
ˇ Obr´azek 2.4: Chov´an´ı oper´atoru mutace nad chromozomem. Srafovanˇ e vyznaˇcen´ y podstrom se smaˇze a nahrad´ı nov´ ym.
Obr´azek 2.5: Chov´an´ı oper´atoru kˇr´ıˇzen´ı nad chromozomy. Zakrouˇzkovan´e uzly se vymˇen´ı i se sv´ ymi podstromy.
5
GP programov´an´ı podobnˇe jako GA pracuje ve tˇrech f´az´ıch. V prvn´ı f´azi prob´ıh´a inicializace poˇca´teˇcn´ı populace, ve kter´e jsou generov´ani jedinci na z´akladˇe omezuj´ıc´ı podm´ınek, napˇr. maxim´aln´ı ˇc´ı minim´aln´ı poˇcet uzl˚ u. V druh´e f´azi doch´az´ı k selekci a k reprodukci. Ve tˇret´ı f´azi je vybr´an nejlepˇs´ı program. Selekce Selekce jedince prob´ıh´a na z´akladˇe jeho fitness (vhodnosti). Vhodnost se v GP vyjadˇruje jako schopnost ˇreˇsit dan´ y probl´em. J. Koza uv´ad´ı ˇctyˇri druhy vhodnosti 1 : Raw fitness, Standardized fitness, Adjusted fitness a Normalized fitness. Pro reprodukci mohou b´ yt 2 vyb´ır´ani kandid´ati pomoc´ı tˇr´ı zp˚ usob˚ u : Fitness proportionate selection, Tournament selection a Random selection.
2.2.3
Evoluˇ cn´ı strategie
Evoluˇcn´ı strategie (ES) patˇr´ı mezi prvn´ı u ´ spˇeˇsn´e stochastick´e metody. ES vynalezli v Nˇemecku v 60. letech Bienert, Rechenberg a Schwefel. ES vych´az´ı stejnˇe jako GA ze vˇseobecn´ ych pˇredstav pˇrirozen´eho v´ ybˇeru, avˇsak na rozd´ıl od GA je jej´ı pˇr´ıstup v´agnˇejˇs´ı. Jej´ı promˇenn´e nejsou reprezentov´any bin´arnˇe, ale jako re´aln´e hodnoty. Nejzn´amˇejˇs´ı ES je strategie (1+1) – jeden rodiˇc a jeden potomek. Pouˇz´ıv´a jedin´ y oper´ator – mutaci a pouze jedno ˇreˇsen´ı v populaci s maxim´alnˇe dvˇema jedinci (rodiˇc a potomek).
2.2.4
Evoluˇ cn´ı programov´ an´ı
Evoluˇcn´ı programov´an´ı (EP) patˇr´ı mezi stochastick´e optimalizaˇcn´ı algoritmy, kter´e mohou b´ yt ch´ap´any jako jednoduch´e zobecnˇen´ı horolezeck´eho algoritmu 3 . Pˇrestoˇze jsou si EP a ES bl´ızk´e, byly vyvinuty nez´avisle v 60. letech Lawrencem Fogelem. Algoritmus byl p˚ uvodnˇe vyvinut pro pˇredpov´ıd´an´ı nov´ ych stav˚ u a ud´alost´ı. K tomu byly pouˇzity koneˇcn´e automaty. Na rozd´ıl od GP, algoritmus EP pouˇz´ıv´a jen oper´ator mutace. Princip soutˇeˇzen´ı spoˇc´ıv´a ve v´ ybˇeru jen nejlepˇs´ıch rodiˇc˚ u a potomk˚ u. Z kaˇzd´eho vybran´eho jedince se vyrob´ı nov´ y potomek do dalˇs´ı populace.
2.3
Evoluˇ cn´ı n´ avrh
Evoluˇcn´ı n´avrh m´a sv´e koˇreny v poˇc´ıtaˇcov´e vˇedˇe, n´avrhu a evoluˇcn´ı biologii. Je to skupina evoluˇcn´ıch v´ ypoˇct˚ u, kter´a rozˇsiˇruje a kombinuje CAD a analytick´ y software, a vyuˇz´ıv´a ideje biologick´e evoluce. Uˇz´ıv´an´ı evoluˇcn´ıch v´ ypoˇct˚ u pro n´avrh zaˇcalo z rozliˇcn´ ych d˚ uvod˚ u v 80. letech. N´avrh´aˇri optimalizovali urˇcit´e ˇca´sti sv´ ych n´avrh˚ u uˇzit´ım evoluce, umˇelci uˇz´ıvali evoluci pro generov´an´ı esteticky pˇr´ıjemn´ ych forem, architekti vyv´ıjeli nov´e pl´any budov, poˇc´ıtaˇcov´ı vˇedci vyv´ıjeli morfologie a ˇr´ıd´ıc´ı syst´emy pro umˇel´ y ˇzivot (v angl. artificial life). Dnes 1
Funkce fitness pro GP podrobnˇeji uv´ ad´ı J. Koza [3]. Zp˚ usoby selekce u GP jsou podrobnˇeji uvedeny [3]. 3 Podrobnˇeji jsou horolezeck´e algoritmy rozebr´ any v [4].
2
6
m˚ uˇzeme rozdˇelit evoluˇcn´ı n´avrh na ˇctyˇri hlavn´ı kategorie 4 : evolutionary desing optimisation, creative evolutionary design, evolutinary art (evoluˇ cn´ı umˇ en´ı) a evolutionary artificial life forms.
2.3.1
Evoluˇ cn´ı umˇ en´ı
Evoluˇcn´ı umˇen´ı je pravdˇepodobnˇe nej´ uspˇeˇsnˇejˇs´ı komerˇcn´ı uˇzit´ı evoluˇcn´ıho n´avrhu [2], aˇckoli akademick´ y v´ yzkum v t´eto oblasti je menˇs´ı nˇeˇz v ostatn´ıch oblastech evoluˇcn´ıho n´avrhu. Vˇetˇsina syst´em˚ u evoluˇcn´ıho umˇen´ı je si velice podobn´a. Vˇsechny generuj´ı na zaˇca´tku poˇca´teˇcn´ı n´ahodnou populaci vzork˚ u (napˇr. obr´azky). Umoˇzn ˇ uj´ı n´avrh´aˇri (umˇelci) nastavit fitness jedinc˚ u populace podle jejich estetick´eho c´ıtˇen´ı. Populace jedinc˚ u takov´eho syst´emu b´ yv´a mal´a (okolo 10 jedinc˚ u), aby mohla b´ yt posouzena umˇelcem velmi rychle. Uˇzivatelsk´e rozhran´ı je vˇetˇsinou jednoduch´e, skl´adaj´ıc´ı se z mˇr´ıˇzky jedinc˚ u populace, kter´ ym nastavuje umˇelec fitness klik´an´ım myˇs´ı.
Obr´azek 2.6: Pˇr´ıklad stolu vyvinut´eho syst´emem evoluˇcn´ıho umˇen´ı. Obr´azek pˇrevzat z [2].
R˚ uzn´e zdroje informac´ı o evoluˇcn´ım umˇen´ı jsou pˇr´ıstupn´e, z web str´anek: • http://evonet.lri.fr/, EvoNet, sekce EvoArt, • http://www.genarts.com/karl, Karl Sims, GenArts, Inc. a • http://www.gaga.demon.co.uk/evoart.htm, Evolutionary Art Using Cartesian Genetic Programming. Syst´em Sarte umoˇznuj´ıc´ı evoluˇcn´ı n´avrh barevn´ ych obraz˚ u je pˇr´ıstupn´ y z URL: http://ass.cis.vutbr.cz/art/galerie/.
4
Kategorie evoluˇcn´ıho n´ avrhu jsou pops´ any v [2].
7
Kapitola 3
Frakt´ aly Frakt´aly jsou pˇrekr´asn´e a fascinuj´ıc´ı konstrukce nekoneˇcn´ ych a sloˇzit´ ych struktur. Pojem frakt´al je odvozen s latinsk´eho slovesa frangere, coˇz v pˇrekladu znamen´a rozl´amat, vytvoˇrit nepravideln´e u ´ lomky. Frakt´al je geometricky nepravideln´ y u ´ tvar, ze kter´eho po 1 jeho rozdˇelen´ı vznikne nˇekolik sobˇepodobn´ ych u ´ tvar˚ u. Frakt´aly jsou tedy matematick´e u ´ tvary, jejichˇz detailn´ı struktura se nemˇen´ı v z´avislosti na pˇribl´ıˇzen´ı ˇci zvˇetˇsen´ı. Podrobnˇeji se frakt´al˚ um vˇenuj´ı [9, 10, 12].
3.1
´ Uvod do teorie frakt´ al˚ u
Pro pˇribl´ıˇzen´ı teorie frakt´al˚ u je nezbytn´e osvˇetlit nˇekolik pojm˚ u, kter´e se v souvislosti s frakt´aly vyskytuj´ı.
Geometricky hladk´ eu ´tvary Geometricky hladk´a tˇelesa (bod, kˇrivka, plocha, prostor), kter´a jsou zn´ama z klasick´e geometrie lze charakterizovat podle urˇcit´eho poˇctu parametr˚ u (napˇr. d´elka, plocha, objem). Tyto parametry m˚ uˇzeme urˇcit i pro sloˇzitˇejˇs´ı u ´ tvary jako B´ezierova nebo Fergasonova kˇrivka. U kaˇzd´eho u ´ tvaru m˚ uˇzeme urˇcit velikost dimenze (poˇcet rozmˇer˚ u) danou cel´ ym ˇc´ıslem. Tuto dimenzi naz´ yv´ame topologickou.
Nekoneˇ cnˇ eˇ clenit´ eu ´tvary Nekoneˇcnˇe ˇclenit´e u ´ tvary jsou u ´ tvary, pro kter´e topologick´a dimenze nedostaˇcuje. B´ yvaj´ı to u ´ tvary, se kter´ ymi se setk´av´ame v pˇr´ırodˇe (napˇr. mraky, stromy, hory). Zn´am´ ym pˇr´ıkladem je d´elka pobˇreˇz´ı ostrova (napˇr. Velk´e Brit´anie). T´ımto probl´emem se zab´ yval Richardson a Mandelbrot. Richardson zjistil, ˇze d´elka pobˇreˇz´ı je z´avisl´a na d´elce tyˇce, kterou pro mˇeˇren´ı pouˇz´ıv´ame, a odvodil vztah: K = N ∗ e D , kde K je d´elka pobˇreˇz´ı, N je poˇcet u ´ seˇcek nutn´ ych k aproximaci a e je d´elka u ´ seˇcky (tyˇce). D´elka pobˇreˇz´ı je z´avisl´a na konstantˇe D. Souvislost t´eto konstanty a Hausdorffovy dimenze dok´azal aˇz Mandelbrot. 1
Sobˇepodobnost bude vysvˇetlena pozdˇeji.
8
Sobˇ epodobnost Kter´akoliv ˇca´st frakt´alu je pˇresnou kopi´ı p˚ uvodn´ıho motivu. Vyskytuje se pouze u ˇcistˇe ’ matematick´ ych struktur, nebot v pˇr´ırodˇe jsme omezeni fyzik´aln´ımi z´akony.
Sobˇ epˇ r´ıbuznost Kter´akoliv ˇca´st je si velice podobn´a s p˚ uvodn´ım tˇelesem. Vyskytuje se v pˇr´ırodˇe (napˇr. mraky, koˇreny stromu, hory).
Hausdorffova dimenze Topologick´a dimenze, napˇr. hladk´e kˇrivky, je rovna jedn´e. Existuj´ı vˇsak kˇrivky, kter´e v rovinˇe zab´ıraj´ı v´ıce m´ısta (napˇr. d´elka pobˇreˇz´ı ostrova). Pˇri mˇeˇren´ı d´elky takov´ ychto kˇrivek se zmenˇsuj´ıc´ım mˇeˇr´ıtkem se st´av´a jejich d´elka nekoneˇcn´a, kdeˇzto u hladk´e kˇrivky jej´ı d´elka ovlivnˇena mˇeˇr´ıtkem nen´ı. Pro takov´ y druh kˇrivek by byla potˇreba dimenze mezi 1 a 2. Hodnota t´eto dimenze ud´av´a, s jakou rychlost´ı d´elka tˇechto kˇrivek roste do nekoneˇcna nebo t´eˇz m´ıru nepravidelnosti. Takov´eto neceloˇc´ıseln´e dimenzi se ˇr´ık´a frakt´aln´ı nebo Hausdorffova.
Atraktor Atraktor je mnoˇzina bod˚ u v prostoru, kter´a odpov´ıd´a ust´alen´emu stavu. Atraktorem m˚ uˇze b´ yt bod nebo nˇejak´ y opakuj´ıc´ı se cyklus. Pˇri zkoum´an´ı atraktoru byl objeven tˇret´ı typ traktoru – tzv. podivn´ y atraktor. Kaˇzd´ y takov´ yto atraktor je frakt´alem.
Matematick´ a definice Matematick´a definice frakt´alu dle Benoita Mandelbrota zn´ı: ”Frakt´al je mnoˇzina, jej´ıˇz hodnota Hausdorffovy dimenze pˇresahuje hodnoty dimenze topologick´e.”
3.2
Typy frakt´ al˚ u
Kv˚ uli systematiˇcnosti se po urˇcit´em ˇcase zaˇcaly rozliˇsovat jednotliv´e typy frakt´al˚ u. Jednotliv´e typy se od sebe liˇs´ı jak vhodnost´ı k ˇreˇsen´ı urˇcit´eho okruhu probl´em˚ u, tak i zp˚ usobem vytv´aˇren´ı (generov´an´ı). Frakt´aly m˚ uˇzeme obecnˇe rozdˇelit na ˇctyˇri skupiny: • L-syst´emy, • syst´em iterovan´ ych funkc´ı (IFS), • dynamick´e syst´emy a • nepravideln´e frakt´aly.
9
3.2.1
L-syst´ emy
L-syst´emy (Lindenmayerovy syst´emy) jsou skupinou frakt´al˚ u definovan´ ych pomoc´ı ˇ pˇrepisovac´ıch gramatik. Zelva (kresl´ıc´ı zaˇr´ızen´ı, pouˇzit´e v programovac´ım jazyce LOGO) je definov´ano stavem a akcemi, kter´e m´a prov´adˇet. Stav je sloˇzen s polohy a orientace ˇ ˇzelvy. Zelva ˇcte a prov´ad´ı ˇretˇezec pˇr´ıkaz˚ u. Frakt´aly pak vznikaj´ı s pouˇzit´ım rekurze. Tˇemto frakt´al˚ um se nˇekdy ˇr´ık´a graft´ aly. Nejzn´amˇejˇs´ımi frakt´aly v t´eto skupinˇe jsou Kantorovo diskontinuum, vloˇcka Kochov´e a Sierpinsk´eho troj´ uheln´ık.
3.2.2
Syst´ em iterovan´ ych funkci (IFS)
Syst´em iterovan´ ych funkc´ı (IFS) je generativn´ı metodou tvoˇren´ı frakt´al˚ u. U t´eto metody generov´an´ı se pouˇz´ıvaj´ı tzv. afinn´ı transformace (posun, rotace, zmenˇsen´ı). Opakovan´ ym aplikov´an´ım afinn´ıch operac´ı vˇzdy na cel´ y obrazec vznikne frakt´aln´ı struktura. Tato metoda je vhodn´a jak pro generov´an´ı frakt´al˚ u tak i pro tzv. frakt´aln´ı kompresi obrazu. Nejzn´amˇejˇs´ım frakt´alem v t´eto kategorii je Barnsleyho kapradina.
3.2.3
Dynamick´ e syst´ emy
Dynamick´ y syst´em je matematick´ y model, kter´ y je z´avisl´ y na nˇejak´e promˇenn´e (napˇr. ˇcasu). Dynamick´ y syst´em vych´az´ı z poˇca´teˇcn´ıch podm´ınek a je jimi determinov´an. Typick´ ym pˇr´ıkladem jsou dynamick´e syst´emy v komplexn´ı rovinˇe. Nejˇcastˇeji se u bod˚ u v komplexn´ı rovinˇe sleduje u ´ nik od atraktoru v z´avislosti na poˇctu iterac´ı. Dojde-li k u ´ niku bodu, vybarv´ı se tento bod u ´ mˇernˇe poˇctu iterac´ı. Takto vznikaj´ı velmi atraktivn´ı frakt´aly napˇr. Juliovy mnoˇziny nebo Mandelbrotova mnoˇzina. Juliovy mnoˇ ziny Juliovy mnoˇziny objevily bˇehem druh´e svˇetov´e v´alky dva francouzˇst´ı matematikov´e Gaston Julia a Pierre Fatou. Juliovy mnoˇziny jsou d´any iteraˇcn´ım v´ yrazem zn+1 = zn2 + c,
(3.1)
a zvolenou komplexn´ı konstantou c, kter´a urˇcuje Juliovu mnoˇzinu. Pro kaˇzd´ y bod z v komplexn´ı rovinˇe, pak iterac´ı v´ yrazu (3.1), kde poˇca´teˇcn´ı z 0 je nastaveno souˇradnic´ım bodu v komplex. rovinˇe, zjist´ıme, zda bod konverguje k nule ˇci ne. Takov´ y bod je bud’ uvnitˇr ˇci vnˇe Juliovy mnoˇziny. V praxi b´ yv´a nastaven maxim´aln´ı poˇcet iterac´ı. Zda-li ˇc´ıslo konverguje k nule ˇci nikoliv, zjist´ıme na konci v´ ypoˇctu tak, ˇze kdyˇz je jeho vzd´alenost od poˇca´tku menˇs´ı neˇz 2, je uvnitˇr mnoˇziny. Se zvˇetˇsuj´ıc´ım se maxim´aln´ım poˇctem iterac´ı z´ısk´ame detailnˇejˇs´ı strukturu Juliovy mnoˇziny 2 . Mandelbrotova mnoˇ zina Mandelbrotovu mnoˇzinu objevil v roce 1979 Benoit Mandelbrot, jako jak´ ysi katalog Juliov´ ym mnoˇzin. T´ımto katalogem byla mnoˇzina v komplexn´ı rovinˇe, kter´a popisovala v kaˇzd´em sv´em bodˇe Juliovu mnoˇzinu. 2
Podobnˇe jako u mˇeˇren´ı d´elky ostrova se zmenˇsuj´ıc´ı se d´elkou tyˇce.
10
Obr´azek 3.1: Pˇr´ıklad zobrazen´ı Juliovy mnoˇziny.
Obr´azek 3.2: Zobrazen´ı Mandelbrotovy mnoˇziny. Mandelbrotova mnoˇzina je vytv´aˇrena podobnˇe jako Juliova na z´akladˇe stejn´eho vztahu (3.1). Liˇs´ı se vˇsak poˇca´teˇcn´ımi podm´ınkami pro kaˇzd´ y bod v komplexn´ı rovinˇe. U Mandelbrotovy je z0 rovno poˇca´tku a c odpov´ıd´a pozici v komplexn´ı rovinˇe. Z v´ yˇse uveden´eho vypl´ yv´a, ˇze zat´ımco Mandelbrotova mnoˇzina je pouze jedna, Juliov´ ym mnoˇzin je nekoneˇcn´e mnoˇzstv´ı.
3.2.4
Nepravideln´ e (n´ ahodn´ e) frakt´ aly
Nepravideln´e frakt´aly jsou sobˇepˇr´ıbuzn´e. Tyto frakt´aly umoˇzn ˇ uj´ı lepˇs´ı popis pˇr´ırodn´ıch objekt˚ u, protoˇze pˇrid´avaj´ı do frakt´aln´ı geometrie prvek n´ahody. N´ahodn´ y frakt´al m˚ uˇze b´ yt vytvoˇren tˇreba posouv´an´ı stˇredn´ıho bodu. Pˇr´ıkladem tˇechto frakt´al˚ u je Brown˚ uv pohyb.
11
Kapitola 4
Syst´ em Gefra N´azev syst´emu Gefra je odvozen ze slovn´ıho spojen´ı genetick´e frakt´aly. Je to syst´em urˇcen´ y k evoluˇcn´ımu n´avrhu obraz˚ u s frakt´aly s vyuˇzit´ım oper´ator˚ u genetick´eho programov´an´ı. Syntaktick´ y strom (v´ yraz) pˇredstavuje genotyp a obraz s frakt´alem pˇredstavuje fenotyp. Tento syst´em patˇr´ı do kategorie evoluˇcn´ıho umˇen´ı.
4.1
Popis syst´ emu
Pˇri spuˇstˇen´ı syst´emu je vygenerov´ano nˇekolik jedinc˚ u populace, kteˇr´ı jsou zn´azornˇeni jako obrazy s frakt´aly. N´avrh´aˇr (umˇelec) vyb´ır´a obrazy, jejichˇz rysy se mu l´ıb´ı a kter´e by chtˇel m´ıt v dalˇs´ı generaci. N´avrh´aˇr prov´ad´ı selekci populace. Vybran´ı jedinci jsou odliˇsen´ı od ostatn´ıch jedinc˚ u zv´ yraznˇen´ ym okrajem. Vyvol´an´ım akce Generate jsou vybran´ı jedinci reprodukov´ani (zkop´ırov´ani) do dalˇs´ı generace a zbytek populace jedinc˚ u je generov´an kˇr´ıˇzen´ım vybran´ ych jedinc˚ u. D´ale umˇelec m˚ uˇze jedince pozmˇenit mutac´ı nebo m´ısto nˇej vygenerovat nov´eho n´ahodn´eho jedince. Pokud umˇelec nen´ı spojen z celou generac´ı, vygeneruje akc´ı New zcela novou populaci jedinc˚ u. Umˇelec m˚ uˇze, kromˇe uplatˇ nov´an´ı genetick´ ych operac´ı, mˇenit zp˚ usob vykreslov´an´ı frakt´al˚ u. M˚ uˇze mˇenit jak maxim´aln´ı poˇcet iterac´ı (parametrem Iterations), tak barevnou paletu (v´ ybˇerovou liˇstou Colormap) a v neposledn´ı ˇradˇe i podm´ınku u ´ niku bodu v komplexn´ı rovinˇe od atraktoru (v´ ybˇerovou liˇstou Escape). Kombinac´ı tˇechto parametr˚ u umˇelec z´ısk´a zaj´ımav´e tvary i z p˚ uvodnˇe nepˇr´ıliˇs zaj´ımav´eho frakt´alu. Zmˇeny se uplatˇ nuj´ı akc´ı Refresh. Syst´em umoˇzn ˇ uje tak´e zmˇenu pˇribl´ıˇzen´ı frakt´alu, a t´ım nalezen´ı nejzaj´ımavˇejˇs´ı oblasti ve zkouman´em frakt´alu. Jak syst´em vypad´a je patrn´e z obr´azku 4.1.
4.2
Zp˚ usob implementace
Syst´em byl naimplementov´an v jazyce Java (konkr´etnˇe ve verzi Java 2 SDK, Standard Edition 1.4.2), coˇz pˇrineslo nemal´e v´ yhody. Pˇredevˇs´ım schopnost zobrazen´ı tzv. appletu, klientsk´e aplikace, pˇr´ımo na webov´e str´ance, aniˇz by byl zat´ıˇzen webov´ y server. Dalˇs´ı nespornou v´ yhodou je nez´avislost na zobrazovac´ı platformˇe, tedy program pracuje poˇra´d 12
Obr´azek 4.1: Applet syst´emu Gefra. stejnˇe, nez´avisle na pouˇzit´em hardware a software. Programovac´ı jazyk Java je objektovˇe orientovan´ y, umoˇzn ˇ uje dˇedˇen´ı, polymorfismus, ˇcehoˇz bylo vyuˇzito pˇri implementaci syntaktick´ ych strom˚ u. A v neposledn´ı ˇradˇe m´a Java definovan´ y Garbage Collector, kter´ y v´ yraznˇe urychluje v´ yvoj, zvyˇsuje stabilitu a nepˇr´ımo sniˇzuje velikost k´odu.
Genetick´ e programov´ an´ı Syst´em k evoluˇcn´ımu n´avrhu vyuˇz´ıv´a technik genetick´eho programov´an´ı. Chromozom je tvoˇren syntaktick´ ym stromem, kter´ y je implementov´an s vyuˇzit´ım rekurze. Z´akladn´ım stavebn´ım prvkem syntaktick´eho stromu je tˇr´ıda GefraNode (pozn. tˇr´ıda Node je jiˇz standardnˇe rezervov´ana). Ze tˇr´ıdy GefraNode jsou odvozeny tˇr´ıdy NodeLeaf, NodeUnary a NodeBinary. Nad tˇr´ıdami NodeUnary a NodeBinary jsou implementov´any funkce pro pro pˇrid´av´an´ı, pro z´ısk´av´an´ı a pro generov´an´ı podstrom˚ u. Ze tˇr´ıd NodeLeaf, NodeUnary a NodeBinary jsou pak odvozeny konkr´etn´ı tˇr´ıdy (napˇr. NodeZ, NodeSin, NodeAdd) definuj´ıc´ı vyhodnocen´ı podstrom˚ u a sebe sama. Speci´aln´ı tˇr´ıdou je tˇr´ıda NodeRoot, odvozen´a od NodeUnary, nad kterou jsou definov´any genetick´e oper´atory jako generov´an´ı, mutace a kˇr´ıˇzen´ı. Instance t´eto tˇr´ıdy charakterizuje konkr´etn´ı syntaktick´ y strom. Pˇr´ıklad hierarchie tˇr´ıd syntaktick´eho stromu je zn´azornˇena na obr´azku 4.2.
13
Obr´azek 4.2: Hierarchie tˇr´ıd syntaktick´eho stromu.
Obrazy s frakt´ aly Implementovan´e frakt´aly jsou typu dynamick´e syst´emy, konkr´etnˇe dynamick´e syst´emy v komplexn´ı rovinˇe. Frakt´aly jsou zobrazov´any podobnˇe jako Juliovy mnoˇziny (nebo Mandelbrotova mnoˇzina), liˇs´ı se vˇsak od nˇej poˇca´teˇcn´ımi podm´ınkami, tak i pouˇzit´ ym v´ yrazem pro v´ ypoˇcet u ´ niku od atraktoru. Pouˇzit´ y v´ yraz je z´ıskan´ y jako v´ ysledek genetick´ ych operac´ı nad syntaktick´ ym stromem. Takov´ yto syntaktick´ y strom vyuˇz´ıv´a jen operac´ı nad komplexn´ımi ˇc´ısly, kter´e jsou bezpeˇcn´e (nepouˇz´ıvaj´ı se nebezpeˇcn´e operace dˇelen´ı). Poˇca´teˇcn´ı podm´ınky jsou pro kaˇzd´ y bod nastaveny tak, aby v kaˇzd´em bodˇe bylo z 0 a c rovno souˇradnic´ım bodu v komplexn´ı rovinˇe. Touto u ´ pravou se zamez´ı setrv´an´ı bodu v poˇca´tku (napˇr. pˇri zn+1 = zn ∗ c) a hled´an´ı konstanty c. Obraz z´ıskan´ y takovouto u ´ pravou vˇsak neztr´ac´ı na atraktivitˇe. Dalˇs´ıch u ´ prav v´ ysledn´eho obrazu bylo doc´ıleno pouˇzit´ım r˚ uzn´ ych barevn´ ych map, tak i pouˇzit´ım jin´ ych podm´ınek u ´ niku bodu od atraktoru, neˇz jsou implicitnˇe u Juliov´ ych mnoˇzin pouˇzity. Tuto vlastnost umoˇzn ˇ uj´ı tˇr´ıdy odvozen´e od tˇr´ıd Colormap a Escape. Obraz s frakt´alem je tak tvoˇren souhrnem vlastnost´ı jako jsou souˇradnice, pˇribl´ıˇzen´ı, rozliˇsen´ı, iteraˇcn´ı v´ yraz, maxim´aln´ı poˇcet iterac´ı, barevn´a mapa a podm´ınky u ´ niku.
Grafick´ e uˇ zivatelsk´ e rozhran´ı Grafick´e uˇzivatelsk´e prostˇred´ı bylo implementov´ano s poˇzit´ım knihoven AWT a JFC Swing, ktere jsou souˇca´st´ı platformy Java2SE. Tyto knihovn´ y umoˇzn ˇ uj´ı definovat grafick´e prvky (napˇr. tlaˇc´ıtka, ikony, roletov´e menu), jejich vzhled a chov´an´ı. 14
Kapitola 5
Z´ avˇ er Zpracov´an´ı syntaktick´eho stromu definovan´eho rekurz´ı a obecnˇe generov´an´ı obraz˚ u s frakt´aly je na v´ ykon n´aroˇcn´a operace. Rychlost vykreslov´an´ı je z´avisl´a na struktuˇre syntaktick´eho stromu, tak i na maxim´aln´ım poˇctu iterac´ı. Proto je vhodn´e zpoˇca´tku m´ıt nastavenou hodnotu maxim´aln´ıho poˇctu iterac´ı na malou konstantu a po nalezen´ı zaj´ımav´eho obrazu tuto hodnotu zv´ yˇsit a aplikovat ji. Pˇri hled´an´ı zaj´ımav´eho obrazu doch´az´ı po nˇekolika generac´ıch k viditeln´e degeneraci genetick´e v´ ybavy populace, proto je v´ yhodn´e v takov´em pˇr´ıpadˇe vyuˇz´ıt operace mutace a nebo rovnou nahradit nˇejak´eho zdegenerovan´eho jedince zcela nov´ ym. Rozˇs´ıˇren´ım v n´avaznosti na tento projekt je moˇzn´e implementovat evoluˇcn´ı n´avrh barevn´ ych map, kter´e by mohly b´ yt pouˇzit´ y pˇri generov´an´ı obraz˚ u s frakt´aly. D´ale je moˇzn´e implementovat ukl´ad´an´ı a naˇc´ıt´an´ı populace jedinc˚ u, jako i ukl´ad´an´ı a naˇc´ıt´an´ı jedinc˚ u samotn´ ych. To by vˇsak znamenalo urˇcit´a omezen´ı, nebot’ webov´ y applet standardnˇe neumoˇzn ˇ uje manipulovat ze syst´emem soubor˚ u. Implementovan´ y syst´em generoval docela hezk´e a zaj´ımav´e obrazy s frakt´aly, o ˇcemˇz se m˚ uˇze ˇcten´aˇr pˇresvˇedˇcit z pˇriloˇzen´ ych v´ ysledk˚ u v dodatku B.
15
Literatura [1] Corne, D., Bentley, P.: Creative Evolutionary Systems, Morgan Kaufmann, 2001. [2] Bentley, P.: Evolutionary Design By Computers, Morgan Kaufmann, 1999. [3] Koza, J.: Genetic Programming of Computer by Means of Natural Selections., Morgan Kaufmann, 1992. [4] Kvasniˇcka, V., Posp´ıchal, J., Tiˇ no, P.: Evoluˇcn´e algoritmy, STU Bratislava, 2000. [5] Jakˇs´ık, O.: N´ astroje pro genetick´e programov´ an´ı [Roˇcn´ıkov´y projekt], FIT VUT Brno, 2003. [6] Schwarz, J.: Aplikovan´e evoluˇcn´ı algoritmy [Studijn´ı materi´ aly], FIT VUT Brno, 2004. ˇ [7] M¨ uller, T.: Evoluˇcn´ı n´ avrh filtru, FEL CVUT Praha, 2002. [8] Sejnoha, P.: Sarte Dokumentace. Dokument http://ass.cis.vutbr.cz/art/dokumentace.html.
je
dostupn´ y
na
URL:
[9] Tiˇsnovk´ y, P.: Frakt´ aly. Dokument je dostupn´ y na URL: http://www.fit.vutbr.cz/ tisnovpa/fract/uvod.html. [10] Wegner, T., Tyler, B.: Fractal Creations, The Waite Group Press, 1993. [11] Sch´anˇel, P., Hruˇskov´a, J.: Frakr´ aly. Dokument je dostupn´ y http://lide.uhk.cz/home/fim/student/fshrusj1/www/grafika/.
na
URL:
[12] Hinner, M.: Jemn´y u ´vod do frakt´ al˚ u. Dokument http://www.penguin.cz/ mhi/math/Fraktaly/.
na
URL:
je
dostupn´ y
[13] efg’s Computer Lab: Complex Numbers and Functions. Dokument je dostupn´ y na URL: http://homepages.borland.com/efg2lab/Mathematics/Complex/ ˇ e Budˇejovice, 2000. [14] Herout, P.: Uˇcebnice jazyka Java, Nakladatelstv´ı Kopp, Cesk´ [15] Eckel, B.: Thinkig in Java, second edition, Prentice Hall, Inc., 2000. [16] Campione, M., Walrath, K., Huml, A.: The Java(TM) Tutorial, Addison-Wesley Pub Co, 2000. Dokument je dostupn´ y na URL: http://java.sun.com/docs/books/tutorial/index.html.
16
[17] Walrath, K., Campione, M.: The JFC Swing Tutorial, AddisonWesley Pub Co, 1999. Dokument je dostupn´ y na URL: http://java.sun.com/docs/books/tutorial/uiswing/index.html. [18] Sun Microsystems, Inc.: Java 2 SDK, Standard Edition, Documentation. Dokument je dostupn´ y na URL: http://java.sun.com/j2se/1.4.2/docs/index.html.
17
Dodatek A
Uˇ zivatelsk´ a pˇ r´ıruˇ cka Syst´em Gefra funguje ve webov´em prohl´ıˇzeˇci (obr. A.1) s pluginem Java2SE (Java Virtual Machine) verze 1.4.2.
Obr´azek A.1: Syst´em Gefra jako applet ve webov´em prohl´ıˇzeˇci Mozilla/Galeon. Ovl´ad´an´ı syst´emu je intuitivn´ı. Kromˇe zmˇeny maxim´aln´ıho poˇctu iterac´ı, kter´a mus´ı b´ yt zad´ana z kl´avesnice, je vˇetˇsina operac´ı urˇcena s pomoc´ı polohovac´ıho zaˇr´ızen´ı (myˇs´ı). Akˇcn´ı tlaˇc´ıtko je standardnˇe u myˇsi lev´e. Vyj´ımkou je pˇribl´ıˇzen´ı, vzd´alen´ı a v´ ybˇer jedinc˚ u populace v sekci Selections, kde je lev´e tlaˇc´ıtko myˇsi urˇceno pro pˇribl´ıˇzen´ı, prav´e tlaˇc´ıtko myˇsi urˇceno pro vzd´alen´ı a stˇredn´ı tlaˇc´ıtko myˇsi urˇceno pro v´ ybˇer. Stiskem tlaˇc´ıtka New se vytvoˇr´ı nov´a populace. Stiskem tlaˇc´ıtka Generate se vygeneruje
18
dalˇs´ı populace kˇr´ıˇzen´ım jedinc˚ u (minim´alnˇe 2), kteˇr´ı byly jiˇz dˇr´ıve vybr´ani. Stiskem tlaˇc´ıtka Refresh se uplatn´ı proveden´e zmˇeny v nastaven´ı. Tyto akˇcn´ı tlaˇc´ıtka jsou v sekci Tools. Zmˇenou parametru Iterations se nastav´ı maxim´aln´ı poˇcet iterac´ı. V´ ybˇerem z liˇsty Colormap se nastav´ı barevn´a mapa. V´ ybˇerem z liˇsty Escape se nastav´ı podm´ınka u ´ niku bodu od atraktoru. Grafick´e prvky pro zmˇeny jsou v sekci Settings. Pod kaˇzd´ ym vygenerovan´ ym obrazem je speci´aln´ı menu, kter´ ym se vyvol´avaj´ı akce jen pro pˇr´ısluˇsn´ y obraz. Tˇemito akcemi jsou Refresh pro uplatnˇen´ı zmˇen, View pro zobrazen´ı zvˇetˇseniny, New pro vytvoˇren´ı nov´eho jedince a Mutate pro mutaci jedince. V sekci Informations jsou zobrazeny informace o poˇctu generac´ı (populac´ı).
19
Dodatek B
Uk´ azky vygenerovan´ ych obr´ azk˚ u Selekce a kˇ r´ıˇ zen´ı Viz tabulka B.1.
Mutace Viz tabulka B.2.
R˚ uzn´ e barevn´ e mapy Viz tabulka B.3.
R˚ uzn´ e podm´ınky u ´niku bodu od atraktoru Viz tabulka B.4.
Vliv maxim´ aln´ıho poˇ ctu iterac´ı na v´ ysledn´ y obraz Viz tabulka B.5.
Pˇ ribl´ıˇ zen´ı obrazu s frakt´ alem Viz tabulka B.6.
R˚ uzn´ e obrazy s frakt´ aly z´ıskan´ e syst´ emem Gefra Viz tabulka B.7.
20
Tabulka B.1: Uk´azka postupn´e selekce a kˇr´ıˇzen´ı (vybran´ı jedinci jsou s vyznaˇcen´ ym okrajem.) 21
Tabulka B.2: Uk´azka postupn´e mutace jedince pˇredstavuj´ıc´ıho obraz s frakt´alem.
Tabulka B.3: Barevn´e mapy (zleva doprava): Spectrum, Spectrum16, Greyscale a Zebra.
22
Tabulka B.4: Podm´ınky u ´ niku bodu od atraktoru (zleva doprava): Circle, Square, Strip a Half-plane
Tabulka B.5: Vliv r˚ uzn´eho poˇctu iterac´ı u barevn´e mapy Spectrum (zleva doprava): 8, 16, 32 a 64 23
Tabulka B.6: Pˇribl´ıˇzen´ı obrazu s frakt´alem (zleva doprava): x1, x1.5, x2.25, x3.375, x5.0625 a 7.59375
24
Tabulka B.7: Obrazy s frakt´aly z´ıskan´e syst´emem Gefra. 25
