Univerzita Karlova v Praze Matematicko-fyzikální fakulta

Univerzita Karlova v Praze Matematicko-fyzik´aln´ı fakulta

´ RSK ˇ ´ PRACE ´ BAKALA A

ˇ ep´an Henek Stˇ Simulace Mraveniˇstˇ e ´ Ustav form´aln´ı a aplikovan´e lingvistiky

Vedouc´ı bakal´aˇrsk´e pr´ace: RNDr. Ondˇrej Bojar Studijn´ı program: Informatika Studijn´ı obor: Programov´an´ı 2008

Chtˇel bych t´ımto mnohokr´at podˇekovat vedouc´ımu sv´e pr´ace RNDr. Ondˇreji Bojarovi, za jeho rady, n´amˇety, pˇripom´ınky a v˚ ubec vˇsechen ˇcas, kter´y mi vˇenoval.

Prohlaˇsuji, ˇze jsem svou bakal´aˇrskou pr´aci napsal samostatnˇe a v´yhradnˇe s pouˇzit´ım citovan´ych pramen˚ u. Souhlas´ım se zap˚ ujˇcov´an´ım pr´ace a jej´ım zveˇrejˇ nov´an´ım. ˇ ep´an Henek Stˇ

V Praze dne 3. srpna 2008

2

Obsah ´ 1 Uvod 1.1 Napodobovan´e chov´an´ı . . . . . . . . . . . . . . . . . . . . . 1.2 Struktura textu . . . . . . . . . . . . . . . . . . . . . . . . . 2 Popis modelu 2.1 Prostˇred´ı . . . . . . . . . . . . 2.2 J´ıdlo . . . . . . . . . . . . . . . 2.2.1 Kalend´aˇr j´ıdla . . . . . 2.3 Pˇrek´aˇzky . . . . . . . . . . . . . 2.3.1 Kalend´aˇr pˇrek´aˇzek . . . 2.4 Mraveniˇstˇe . . . . . . . . . . . . 2.5 Stavebn´ı materi´al . . . . . . . . 2.6 Feromony . . . . . . . . . . . . 2.7 Mravenec . . . . . . . . . . . . ˇ 2.7.1 Zivotn´ ı cyklus mravence 2.7.2 Hodnocen´ı . . . . . . . 2.7.3 Genetick´a v´ybava . . . 2.7.4 Kalend´aˇr akc´ı . . . . . . 2.7.5 Stavy a tah mravence . 2.7.6 Kˇr´ıˇzen´ı . . . . . . . . . 2.7.7 Pohyb . . . . . . . . . . 2.8 Monitorov´an´ı . . . . . . . . . . 2.8.1 Poˇc´ıtadla . . . . . . . . 2.8.2 Cesty a Skupiny cest . . 2.8.3 Zaj´ımav´e promˇenn´e . . . 2.8.4 Shrnut´ı . . . . . . . . . 2.9 Pr˚ ubˇeh jednoho kola . . . . . . 2.10 Pozn´amky k implementaci . . . 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 7 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 15 19 19 20 20 21 21 21 22 22

2.10.1 2.10.2 2.10.3 2.10.4

Verze Javy . . . . . . . . . . Popis soubor˚ u . . . . . . . . Rozd´ıly mezi GUI a konzol´ı Uˇzit´e datov´e struktury . . .

. . . .

23 23 23 24

3 Uˇ zivatelsk´ a Dokumentace 3.1 Ovl´ad´an´ı pˇres konzoli . . . . . . . . . . . . . . . . . . . . . 3.2 Ovl´ad´an´ı pˇres GUI . . . . . . . . . . . . . . . . . . . . . . .

26 26 32

4 Porovn´ an´ı se skuteˇ cn´ ymi mravenci 4.1 Experiment se skuteˇcn´ymi mravenci 4.1.1 Popis prostˇred´ı . . . . . . . 4.1.2 Popis experiment˚ u . . . . . 4.1.3 V´ysledky pokus˚ u . . . . . . 4.2 Simulace . . . . . . . . . . . . . . . 4.2.1 Popis prostˇred´ı . . . . . . . 4.2.2 Popis simulace . . . . . . . 4.2.3 V´ysledky . . . . . . . . . . 4.3 Srovn´an´ı . . . . . . . . . . . . . . . 4.3.1 Obyˇcejn´a . . . . . . . . . . 4.3.2 Zablokov´an´ı . . . . . . . . . 4.3.3 Zpr˚ uchodnˇen´ı . . . . . . . .

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

40 40 40 40 42 44 44 44 49 49 49 50 50

5 Z´ avˇ er 5.1 Diskuze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Z´avˇer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51 51 52

6 Pˇ r´ılohy 6.1 CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53 53

Literatura

54

4

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

. . . .

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

Seznam obr´ azk˚ u 1.1

Ant Colony Optimization . . . . . . . . . . . . . . . . . . . .

8

2.1

Stavy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4.1 4.2 4.3 4.4 4.5

Prostˇred´ı experimentu . . . V´ysledky re´aln´ych mravenc˚ u Moje prostˇred´ı . . . . . . . V´ysledky A . . . . . . . . . V´ysledky B . . . . . . . . .

41 43 44 47 48

5

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

N´azev pr´ace: Simulace mraveniˇstˇe ˇ ep´an Henek Autor: Stˇ ´ ´ Katedra (Ustav): Ustav form´aln´ı a aplikovan´e lingvistiky Vedouc´ı bakal´aˇrsk´e pr´ace: RNDr. Ondˇrej Bojar e-mail vedouc´ıho: [email protected] Abstrakt: C´ılem pr´ace je navrhnout a implementovat simulaˇcn´ı prostˇred´ı, kter´e bude napodobovat chov´an´ı mravenc˚ u pˇri hled´an´ı potravy. Prostˇred´ı simulace nen´ı po celou dobu statick´e a m˚ uˇze se mˇenit. Zmˇeny mohou b´yt n´ahodn´eho charakteru, s n´ahodn´ym prvkem nebo ˇcistˇe deterministick´e. Mravenci by na tyto zmˇeny mˇeli b´yt schopni zareagovat a pˇrizp˚ usobit se nov´ym podm´ınk´am. Pohyb mravenc˚ u v prostˇred´ı je nedeterministick´y, je ovlivnˇen stavem bezprostˇredn´ıho okol´ı a genetickou v´ybavou kaˇzd´eho jedince. V´ysledn´y model je na z´avˇer porovn´an s chov´an´ım re´aln´ych mravenc˚ u v umˇel´em prostˇred´ı (viz [1]). Kl´ıˇcov´a slova: mravenci, mraveniˇstˇe, simulace, rojov´a inteligence

Title: Ant Colony Simulation ˇ ep´an Henek Author: Stˇ Department: Institute of Formal and Applied Linguistcs Supervisor: RNDr, Ondˇrej Bojar Supervisor’s e-mail address: [email protected] Abstract: The aim of the paper is to design and implement simulation environment, which will imitate the foraging behaviour of the ants. The environment itself is variable. The changes of environment can be purely random, with random element or purely deterministic. Ants should be able to react to these changes and adapt to new conditions. An ant’s movement is nondeterministic influenced by its current surroundings and genetic information. Finally, our model is compared to the behaviour of real ants in artifitial settings (see [1]). Keywords: ant, ant colony, simulation, swarm intelligence

6

Kapitola 1 ´ Uvod V ˇzivoˇciˇsn´e ˇr´ıˇsi se vyskytuje mnoho zv´ıˇrat, jejichˇz chov´an´ı by se dalo napodobit znaˇcnˇe komplexn´ım algoritmem. Postup, jak reagovat na r˚ uzn´e situace, by mˇel jedince pˇripravit na r˚ uzn´a nebezepeˇc´ı, zajistit pravideln´y pˇr´ısun potravy a v neposledn´ı ˇradˇe umoˇznit u ´ spˇeˇsn´emu jedinci, aby rozˇs´ıˇril sv˚ uj genom mezi budouc´ı generace. Popsat kompletnˇe nˇeco tak sloˇzit´eho, je ovˇsem velice obt´ıˇzn´e a u ˇzivoˇcich˚ u na vyˇsˇs´ım stupni v´yvoje takˇrka nemoˇzn´e. V t´eto pr´aci se proto zamˇeˇr´ım na ponˇekud jednoduˇsˇs´ı ˇzivoˇcichy, mravence. Nebudu se zde nav´ıc snaˇzit popsat kompletn´ı model jejich chov´an´ı. P˚ ujde mi pouze o kr´atk´y v´yˇrez z jejich jistˇe sloˇzit´e etologie. Konkr´etnˇe mi p˚ ujde o to, jak napodobit chov´an´ı mravenc˚ u pˇri hled´an´ı cesty ke zdroj˚ um potravy. Tento algoritmus b´yv´a nˇekdy oznaˇcov´an anglickou zkratkou ACO1 a lze jej vyuˇz´ıt napˇr´ıklad pˇri smˇerov´an´ı s´ıt’ov´eho provozu2 .

1.1

Napodobovan´ e chov´ an´ı

Sch´ema je pomˇernˇe jednoduch´e. Mravenec se vyd´av´a na cestu do nezn´ama. Snaˇz´ı se prozkoumat pokud moˇzno co nejvˇetˇs´ı u ´ zem´ı, na kter´em by se mohl vyskytovat nˇejak´y zdroj potravy. Kdyˇz najde j´ıdlo, tak je sebere a zaˇcne odn´aˇset zpˇet do mraveniˇstˇe. Pˇri n´avratu vyluˇcuje feromony, kter´e by mˇely 1 2

Ant Colony Optimalization http://en.wikipedia.org/wiki/Ant colony optimization

7

pˇril´akat ostatn´ı mravence. Postupn´ym nahromadˇen´ım tˇechto l´atek se vytv´aˇr´ı feromonov´a stopa. Mravenci se zaˇc´ınaj´ı pohybovat po stopˇe od mraveniˇstˇe ke zdroji potravy. Kdyˇz se nˇejak´y mravenec dostane k j´ıdlu jinudy, poloˇz´ı pˇri cestˇe zp´atky z´aklad nov´e feromonov´e stopy. Pokud je tato cesta rychlejˇs´ı, tak ji postupnˇe zaˇcne vyuˇz´ıvat st´ale v´ıce mravenc˚ u, protoˇze na udrˇzen´ı urˇcit´e hladiny feromon˚ u na cestˇe staˇc´ı menˇs´ı poˇcet mravenc˚ u. Koncentrace feromon˚ u se na p˚ uvodn´ı cestˇe postupnˇe sn´ıˇz´ı. P˚ uvodn´ı cesta m˚ uˇze zcela zaniknout, pˇr´ıpadnˇe pˇri vˇetˇs´ım poˇctu mravenc˚ u m˚ uˇze slouˇzit jako doplnˇek rychlejˇs´ı cesty. Takto nalezen´e cesty nemus´ı b´yt nejlepˇs´ım ˇreˇsen´ım probl´emu. M˚ uˇzeme je ovˇsem povaˇzovat za jedno lepˇs´ıch, viz Obr´azek 1.1.

Obr´azek 1.1: Ant Colony Optimization - Obr´azek z cs.wikipedia.org

8

1.2

Struktura textu

Prvn´ı kapitola slouˇz´ı jako struˇcn´y u ´ vod a popis toho, o co mi v pr´aci p˚ ujde. V druh´e kapitole se snaˇz´ım pˇribl´ıˇzit implementovan´ y model. Tˇret´ı kapitola pak slouˇz´ı jako uˇzivatelsk´a dokumentace. Ve ˇctvrt´e je navrˇzen´y model porovn´am s re´aln´ymi mravenci. V p´at´e kapitole se nach´az´ı diskuze a z´avˇer. ˇ a kapitola pouze informuje o pˇr´ıloh´ach. Sest´

9

Kapitola 2 Popis modelu 2.1

Prostˇ red´ı

Okoln´ı svˇet1 je reprezentov´an polem o rozmˇerech 200x100. Obsahuje pr´avˇe jeden vchod do mraveniˇstˇe. Mravenci jej vyuˇz´ıvaj´ı, kdyˇz potˇrebuj´ı doplnit energii, pˇr´ıpadnˇe vyloˇzit j´ıdlo nebo stavebn´ı materi´al.

2.2

J´ıdlo

V prostˇred´ı simulace se s urˇcitou pravdˇepodobnost´ı m˚ uˇze objevit v pˇr´ıˇst´ım tahu nov´y zdroj j´ıdla. Tato pravdˇepodobnost se ˇr´ıd´ı exponenci´aln´ım rozdˇelen´ım (viz [2]). J´ıdlo se obyˇcejnˇe objevuje n´ahodnˇe kdekoliv na mapˇe v n´ahodn´em mnoˇzstv´ı (shora i zdola omezen´em), pˇr´ıpadnˇe lze zvolit nˇekolik oblast´ı v´yskytu. Kaˇzd´a z tˇechto oblast´ı m´a nav´ıc svoji d˚ uleˇzitost. V oblastech s vˇetˇs´ı d˚ uleˇzitost´ı se j´ıdlo objev´ı s vˇetˇs´ı pravdˇepodobnost´ı neˇz v tˇech s menˇs´ı. Oblasti jsou reprezentov´any jako ˇctverce vymezen´e dvˇema body. J´ıdlo se objev´ı v libovoln´em m´ıstˇe z vybran´e oblasti. Pokud se na dan´em pol´ıˇcku jiˇz j´ıdlo vyskytuje, tak se jeho kvantita zv´yˇs´ı. Algoritmus se nesnaˇz´ı hledat pole bez j´ıdla. J´ıdlo se m˚ uˇze objevit i na nepˇr´ıstupn´ych pol´ıch. J´ıdlo je pro mravence ˇzivotnˇe d˚ uleˇzit´a surovina. Pokud nebudou m´ıt j´ıdla dostatek, tak se jejich poˇcet zaˇcne redukovat. Aby vˇsichni mravenci nevymˇreli 1

Budeme jej tak´e oznaˇcovat jako mapa.

10

bude zad´an minim´aln´ı poˇcet mravenc˚ u. Tˇemto mravnc˚ um se bude bˇehem simulace postupnˇe generovat v mraveniˇsti j´ıdlo. Pokud je j´ıdla v mraveniˇsti dostateˇcn´e mnoˇzstv´ı dle pˇredem zvolen´eho parametru, tak se mravenci rozmnoˇz´ı (viz 2.7.6).

2.2.1

Kalend´ aˇ r j´ıdla

Simulace umoˇzn ˇ uje za bˇehu pˇrid´av´an´ı a maz´an´ı oblast´ı, kde se objevuje j´ıdlo. O tuto vymoˇzenost se star´a kalend´aˇr j´ıdla. Obsahuje dva typy z´aznam˚ u, jeden oblast pˇrid´a a druh´y ji odstran´ı. Pˇr´ıtomnost z´aznamu o odebr´an´ı nen´ı povinn´a. Pokud neexistuje, tak dan´a oblast nezmiz´ı.

2.3

Pˇ rek´ aˇ zky

V okoln´ım svˇetˇe se vyskytuj´ı pˇrek´aˇzky dvoj´ıho typu : • Pol´ıˇcka, kter´a mravenece zpomal´ı.2 • Pol´ıˇcka, kter´e jsou nepˇr´ıstupn´a. Tato pol´ıˇcka se nav´ıc mohou bˇehem simulace objevit kdekoliv na mapˇe podle pˇredem dan´eho kalend´aˇre pˇrek´aˇzek.

2.3.1

Kalend´ aˇ r pˇ rek´ aˇ zek

Pˇrid´av´an´ı a mazan´ı pˇrek´aˇzek bˇehem simulace je moˇzn´e spravovat pomoc´ı kalend´aˇre. Na rozd´ıl od kalend´aˇre j´ıdla (viz 2.2.1) zde chyb´ı z´aznam o odeb´ır´an´ı a je nav´ıc zad´an typ pr˚ uchodnosti. Tato pr˚ uchodnost je pak v dan´em ˇcase aplikov´ana na celou zvolenou oblast. Pokud se oblast stane nepr˚ uchodnou, tak jsou vˇsichni mravenci z dan´e oblasti pˇresunuti zpˇet do mraveniˇstˇe. 2

Pr˚ uchod trv´a 2, pˇr´ıpadnˇe 3 kola.

11

2.4

Mraveniˇstˇ e

Mraveniˇstˇe je vlastnˇe z´akladna pro mravence. Mravenci tam nos´ı j´ıdlo a stavebn´ı materi´al. Po urˇcit´e dobˇe se mravenec unav´ı (viz 2.7.3). Mus´ı pak navˇst´ıvit mraveniˇstˇe a naj´ıst se. N´avˇstˇeva mraveniˇstˇe m˚ uˇze mravence zdrˇzet na jedno nebo v´ıce kol, dle n´ahodn´e hodnoty, jej´ıˇz rozsah je urˇcen parametrem. Mraveniˇstˇe m´a od zaˇc´atku omezenou kapacitu (tj. maxim´aln´ı poˇcet mravenc˚ u v simulaci). Tato kapacita lze rozˇs´ıˇrit t´ım, ˇze mravenci nanos´ı potˇrebn´e mnoˇzstv´ı stavebn´ıho materi´alu. Kdyˇz se voln´a kapacita bl´ıˇz´ı nule, tak mravenci zaˇcnou nosit do mraveniˇstˇe mimo j´ıdla i stavebn´ı materi´al.

2.5

Stavebn´ı materi´ al

Mravenci potˇrebuj´ı stavebn´ı materi´al k rozˇs´ıˇren´ı sv´eho mraveniˇstˇe. Materi´al se vyskytuje na mapˇe n´ahodnˇe, v pˇredem zadan´em mnoˇzstv´ı. Na jednom pol´ıˇcku je maxim´alnˇe jedna jednotka stavebn´ıho materi´alu. Samovolnˇe nemiz´ı a novˇe se objevuje pouze, kdyˇz mravenec nˇejak´y kus stavebn´ıho materi´alu sebere. D´ıky tomu se bude na mapˇe se vyskytovat vˇzdy konstantn´ı poˇcet pol´ıˇcek se stavebn´ım materi´alem.

2.6

Feromony

Hlavn´ı komunikaˇcn´ı n´astroj mezi mravenci jsou feromony. Mravenci je postupnˇe vyluˇcuj´ı bˇehem cesty3 , aby dali zpr´avu ostatn´ım. Existuj´ı dva typy feromon˚ u – A a B. Feromon A je vyluˇcov´an pˇri hled´an´ı potravy a feromon B pˇri n´avratu s potravou do mraveniˇstˇe. V jin´ych situac´ıch mravenec ˇz´adn´y feromon nevyluˇcuje. Feromony se postupem ˇcasu z pol´ıˇcek vypaˇruj´ı, aˇz se nakonec vytrat´ı u ´ plnˇe. Poˇcet vyluˇcovan´ych jednotek feromon˚ u, maxim´aln´ı poˇcet jednotek na pol´ıˇcku a m´ıra vypaˇrov´an´ı jsou nastaviteln´e. 3

Na pol´ıˇcko, kde stoj´ı a na okoln´ı voln´ a pol´ıˇcka

12

2.7

Mravenec

Mravenec je jedin´a vˇec, kter´a se na mapˇe pohybuje. M´a ˇctyˇri z´akladn´ı u ´ koly. Naj´ıt j´ıdlo a stavebn´ı materi´al, pˇren´est j´ıdlo a stavebn´ı materi´al do mraveniˇstˇe, pokusit se pˇredˇcasnˇe neukonˇcit svoji existenci a ˇs´ıˇrit sv˚ uj genom. V´ykon´av´a pˇritom 4 z´akladn´ı akce: jdi Mravenec se pˇresune z jenoho pole na druh´e. otoˇ c Mravenec se ot´aˇc´ı do poˇzadovan´eho smˇeru. seber Mravenec bere poˇzadovanou surovinu. vyloˇ z Mravenec pokl´ad´a nesnou surovninu.

2.7.1

ˇ Zivotn´ ı cyklus mravence

Mravenec potˇrebuje k ˇzivotu energii. Tu z´ısk´av´a pˇri konzumaci j´ıdla v mraveniˇsti. Pokud energie mravence klesne na nulu mravenec um´ır´a. Pokud nen´ı v mraveniˇsti dostatek potravy, tak se mravenc˚ um, kteˇr´ı maj´ı n´ızk´e hodnocen´ı (viz 2.7.2), zmraz´ı pˇr´ıdˇel potravy. Mravenec nedostane naj´ıst, kdyˇz je v mraveniˇsti poˇcet jednotek j´ıdla niˇzˇs´ı neˇz jeho lepˇs´ı poˇrad´ı v ˇzebˇr´ıˇcku nosiˇc˚ u a ˇzebˇr´ıˇcku objevitel˚ u. napˇr. Je-li mravenec osm´y nejlepˇs´ı nosiˇc a ˇsest´y nejlepˇs´ı objevitel, tak dostane naj´ıst, jen pokud je v mraveniˇsti v´ıce neˇz pˇet jednotek j´ıdla. Mravenec m´a tak´e omezenou dobu ˇzivota. Po jej´ım uplynut´ı um´ır´a a pˇrenech´a sv´e m´ısto mladˇs´ım generac´ım. Tato doba je zad´av´ana jako parametr simulace, vˇsichni mravenci ji maj´ı stejnou a nem˚ uˇze se bˇehem simulace mˇenit.

2.7.2

Hodnocen´ı

Pro u ´ˇcely kˇr´ıˇzen´ı a pˇridˇelov´an´ı potravy se mravenec hodnot´ı podle: 1. Mnoˇzstv´ı j´ıdla, kter´e nanosil do mraveniˇstˇe. (=nosiˇ c) 2. Poˇctu pol´ı bez feromon˚ u, kter´ymi proˇsel. (=objevitel)

13

Aby se mohla budouc´ı generace mravenc˚ u l´epe prosadit, tak je bˇehem kˇr´ıˇzen´ı u vˇsech mravenc˚ u hodnocen´ı sn´ıˇzeno. Z hodnocen´ı dle j´ıdla se dvˇe dod´avky smaˇzou a objevitelsk´e z´asluhy jsou zcela vynulov´any.

2.7.3

Genetick´ a v´ ybava

Genetick´a v´ybava u kaˇzd´eho jedince je udrˇzov´ana v poli GEN. Hodnoty pole GEN jsou re´aln´a ˇc´ısla v rozsahu: GEN[0], GEN[14] ∈ h0, 10) GEN[1], . . . , GEN[13] ∈ h−5, 5)

(2.1) (2.2)

Prvn´ı poloˇzka pole ovlivˇ nuje, kdy se mravenec zaˇcne vracet zpˇet do mraveniˇstˇe. Je to vlastnˇe pˇrechod ze stavu HLEDAT (viz 2.7.5) do stavu VRATIT a z´avis´ı tak´e na souˇcasn´e energii mravence(=em) a parametru simulace zvan´em energetick´a hranice(=eh). Pˇrechod se uskuteˇcn´ı pr´avˇe kdyˇz : em ≤ eh ∗ (1 + GEN[0]/10)

(2.3)

D´ıky tomu m´a genetick´a v´ybava vliv na to, kdy se mravenec zaˇcne vracet. Nav´ıc bylo potˇreba zajistit, aby mravenci se nezaˇcali vracet zpˇet moc pozdˇe/brzy, coˇz zajiˇst’uje parametr eh. Jin´ymi slovy mravenec se m˚ uˇze samovolnˇe zaˇc´ıt vracet kdyˇz: em ∈ heh, 2 ∗ eh)

(2.4)

v z´avislosti na jeho genetick´e v´ybavˇe. Dalˇs´ı poloˇzky tohoto pole maj´ı vliv na v´ybˇer pol´ıˇcka, kam se mravenec pokus´ı pˇresunout pˇri stavu HLEDAT.

2.7.4

Kalend´ aˇ r akc´ı

Mravenci jsou uloˇzeni do kalend´aˇrov´e struktury. Kaˇzd´y mravenec je zde asociov´an s ˇcasem jeho pˇr´ıˇst´ı aktivace. Pˇri aktivaci mravenec vykon´a nˇejakou akci, n´aslednˇe je mu napl´anov´an ˇcas jeho pˇr´ıˇst´ı aktivace.

14

2.7.5

Stavy a tah mravence

Obr´azek 2.1: Stavy mezi kter´ymi m˚ uˇze mravenec pˇrech´azet Mravenec se m˚ uˇze nach´azet v r˚ uzn´ych stavech. Podle tˇechto stav˚ u a stavu 4 okol´ı s jistou pravdˇepodobnost´ı rozhodne co dˇelat v n´asleduj´ıc´ım tahu. Tato pravdˇepodobnost je ovlivnˇena genetickou v´ybavou kaˇzd´eho mravence (viz 2.7.3). Pˇrechod mezi stavy m˚ uˇze nastat pˇri n´avˇstˇevˇe mraveniˇstˇe, pˇri nalezen´ı potravy, pˇri nalezen´ı stavebn´ıho materi´alu, pˇri nalezen´ı pˇrek´aˇzky na cestˇe a samovolnˇe v z´avislosti na tom, jak je mravenec unaven´y (tj. kolik mu zb´yv´a energie), viz Obr´azek 2.1.

Stav SPAT V tomto stavu mravenec pouze ˇcek´a v mraveniˇsti, dokud se pro nˇej nenajde nˇejak´e j´ıdlo. Toto ˇcek´an´ı ho stoj´ı 3x m´enˇe energie, neˇz obvykle. Mravenec se nezapisuje do kalend´aˇre ud´alost´ı na pˇr´ıˇst´ı tah. Zap´ıˇse se na tah, kter´y je vzd´alen tˇri jednotky ˇcasu od souˇcasn´eho. Mravenci se odeˇc´ıt´a energie na poˇc´atku jeho tahu. Jakmile je na tahu, pod´ıv´a se, jestli by se pro mˇej 4

mravenci vid´ı jen pol´ıˇcka ve sv´e bezprostˇredn´ı bl´ızkosti

15

nenaˇslo j´ıdlo. Pokud ne, opˇet se usp´ı. Kdyˇz se naj´ı, tak pˇrech´az´ı do stavu HLEDAT.

Stav HLEDAT V tomto stavu se mravenec snaˇz´ı naj´ıt zdroj j´ıdla, stavebn´ı materi´al, pˇr´ıpadnˇe prozkoumat co nejv´ıc neobjeven´ych pol´ı (pole na nichˇz se nevyskytuj´ı feromony). Pouze v tomto stavu je mravenec schopen sebrat j´ıdlo a stavebn´ı materi´al. Tato akce m˚ uˇze trvat i delˇs´ı dobu, kter´a z´avis´ı na nastaven´ı simulace. Mravenec m˚ uˇze pˇrej´ıt z tohoto stavu pouze do stavu VRATIT. Pˇrech´az´ı pokud sebere j´ıdlo nebo stavebn´ı materi´al, pˇr´ıpadnˇe pokud jeho energie klesne pod urˇcitou hodnotu (viz 2.7.3). Na z´akladˇe pˇr´ıtomnosti feromon˚ u v bezprostˇredn´ım okol´ı, sv´e genetick´e v´ybavy a sv´eho aktu´aln´ıho smˇeru si mravenec zvol´ı pol´ıˇcko, na kter´e se pokus´ı dostat. Pokus´ı se natoˇcit do smˇeru, ve kter´em je pol´ıˇcko dosaˇziteln´e. Pokud se bˇehem ot´aˇcen´ı pole znepˇr´ıstupn´ı, je mravenec nucen volit pole znovu. D´ıky tomu by se dalo ˇr´ıct, ˇze se v tomto stavu se mravenec nach´az´ı ve dvou podstavech. V prvn´ım se ot´aˇc´ı a ve druh´em jde na jin´e pol´ıˇcko. Ot´aˇcen´ı m˚ uˇze b´yt nav´ıc pˇreruˇseno pˇrechodem do stavu VRATIT. V´ybˇer pol´ıˇcek prob´ıh´a tak, ˇze se vˇsechna pol´ıˇcka z okol´ı mravence ohodnot´ı a seˇrad´ı dle hodnocen´ı. Pravdˇepodobnost, ˇze bude pol´ıˇcko vybr´ano, z´avis´ı na jeho ohodnocen´ı a na poˇrad´ı mezi ohodnocen´ymi pol´ıˇcky. Tento zp˚ usob v´ybˇeru pol´ıˇcka n´am zajist´ı, ˇze ne vˇzdy je vybr´ano pole s nejvˇetˇs´ım hodnocen´ım, ale ˇsanci dostanou i pol´ıˇcka s podobnˇe vysok´ym hodnocen´ım. Pol´ıˇcka se ohodnot´ı dle pole GEN (viz 2.7.3): a) Pokud se na pol´ıˇcku vyskytuje Feromon A v mnoˇzstv´ı mA. h = GEN[1] ∗ sin (GEN[2] ∗ mA/maxA + GEN[3]) maxA je maxim´aln´ı mnoˇzstv´ı feromonu A na pol´ıˇcku

16

(2.5)

b) Pokud se na pol´ıˇcku vyskytuje Feromon B v mnoˇzstv´ı mB. h = GEN[4] ∗ sin (GEN[5] ∗ mB/maxB + GEN[6])

(2.6)

maxB je maxim´aln´ı mnoˇzstv´ı feromonu B na pol´ıˇcku c) Pokud se na pol´ıˇcku vyskytuje Feromon A i Feromon B. h = GEN[7] ∗ sin (GEN[8] ∗ mA/maxA + GEN[9]) + + GEN[10] ∗ sin (GEN[11] ∗ mB/maxB + GEN[12]) (2.7) d) Pokud se na pol´ıˇcku nevyskytuje ˇ z´ adn´ y Feromon. h = GEN[13]

(2.8)

• Pokud se mravenec mus´ı ot´aˇcet, aby se dostal hodnocen´e pol´ıˇcko, zvyˇsujeme hodnocen´ı: h := h − GEN[14]/5 ∗ poˇcet otoˇcen´ı

(2.9)

• K v´ysledku se pˇriˇcte n´ahodn´a hodnota ε reprezentuj´ıc´ı chybu receptor˚ u. Tato chyba n´am pom´ah´a v situac´ıch na poˇc´atku simulace, kdy se na pol´ıˇcku nevyskytuj´ı feromony. Mravenec si d´ıky tomu nevyb´ır´a poˇr´ad ty stejn´a pole. Hodnota chyby je dostateˇcnˇe mal´a, takˇze nebude m´ıt vˇetˇs´ı vliv na volbu pol´ıˇcka v pozdˇejˇs´ıch f´az´ıch simulace. ε ∈ h0, 0.01) h := h + ε D´ıky pouˇzit´ı funkce sinus m´a genetick´a v´ybava vliv na: • urˇcen´ı interval˚ u hodnot, kter´e mravence pˇritahuj´ı/odpuzuj´ı • nastaven´ı velikosti tˇechto interval˚ u

17

(2.10)

Stav VRATIT Tento stav zodpov´ıd´a za pokud moˇzno bezprobl´emov´y n´avrat mravence do mraveniˇstˇe. D´ıky moˇznosti volby, zda si bude mravenec pamatovat cestu zpˇet ˇci nikoliv, bylo nezbytn´e vytvoˇrit dvˇe verze algoritmu pro n´avrat: S pamˇ et´ı: Mravenec se snaˇz´ı j´ıt zpˇet do mraveniˇstˇe dle cesty, kterou vyˇsel z mraveniˇstˇe. Z cesty jsou nav´ıc odstranˇeny smyˇcky, takˇze se nem˚ uˇze st´at, ˇze by mravenec pˇriˇsel na jedno pole dvaktr´at. M˚ uˇze se ovˇsem st´at, ˇze se mravenci postav´ı do cesty pˇrek´aˇzka. Pokud mu cestu blokuje jin´y mravenec, tak se pokus´ı chv´ıli poˇckat. Kdyˇz ˇcek´an´ı nezabere, tak odstran´ı blokovan´a pole z pamˇeti a snaˇz´ı se dostat na prvn´ı voln´e pole na cestˇe. Zapamatuje si pole kam m´a nam´ıˇreno, vzd´alenost od toho pole a pˇrejde do stavu OBCHAZET. V pˇr´ıpadˇe, ˇze se nejedn´a o mravence, tak pˇrech´az´ı do stavu OBCHAZET rovnou bez ˇcek´an´ı a d´ale postupuje stejnˇe. Bez pamˇ eti: Mravenec se snaˇz´ı j´ıt zp´atky do mraveniˇstˇe podle klesaj´ıc´ıh hodnot feromonu A, kter´y mravenec pokl´adal na cestu bˇehem sv´eho v´yletu. Nejprve se snaˇz´ı j´ıt na pol´ıˇcka s niˇzˇs´ım mnoˇzst´ım feromonu A. N´ahodnˇe vyb´ır´a na kter´e. Potom se snaˇz´ı dostat na pol´ıˇcka s vyˇsˇs´ım mnoˇzstv´ım feromonu A. Pole opˇet vyb´ır´a n´ahodnˇe. Pokud se v jeho okol´ı nevyskytuje ˇz´adn´e pole s feromonem A, tak postupuje obdobnˇe jako u stavu HLEDAT. Tento postup m´a smysl pouze, kdyˇz nastav´ıme vysok´e hodnoty feromonu A v parametrech simulace a nav´ıc se v simulaci mus´ı vyskytovat menˇs´ı poˇcet mravenc˚ u.

Stav OBCHAZET ´ Ukolem tohoto stavu je pokusit se obej´ıt pˇrek´aˇzku, kter´a se postavila mravenci do cesty. Mravenec k tomuto u ´ˇcelu vyuˇz´ıv´a algoritmus prav´e/lev´e ruky5 . Jakmile se dostane bl´ıˇz k poli, kam m´a nam´ıˇreno6 , neˇz byl pˇri pˇrechodu do tohoto stavu pole pˇrech´az´ı zpˇet do stavu VRATIT. Pokud se stane, ˇze pˇrek´aˇzka z niˇceho nic zmiz´ı, tak tak´e pˇrech´az´ı do stavu VRATIT. Pokud se stane, ˇze pole, kam m´a nam´ıˇreno, je voln´e, ale ned´a se na nˇej dostat, tak m´a 5 6

Jde co nejtˇesnˇeji pod´el pˇrek´aˇzky bud’ z leva nebo zprava. prvn´ı voln´e pole na jeho cestˇe zpˇet

18

mravenec prostˇe sm˚ ulu a bude se aˇz do sv´e smrti pokouˇset obej´ıt pˇrek´aˇzku. Jestli bude mravenec obch´azet pˇrek´aˇzku z prava ˇci z leva si mravenec vol´ı n´ahodnˇe. Po celou dobu jeho n´avratu vˇsak obch´az´ı pˇrek´aˇzku pouze z jedn´e strany.

2.7.6

Kˇ r´ıˇ zen´ı

Kˇr´ıˇzen´ı implementovan´e v modelu neodpov´ıd´a mnoˇzen´ı mravenc˚ u ve skuteˇcnosti. Neexistuje zde kastovn´ı syst´em. D´ıky tomu mohou genetickou informaci ˇs´ıˇrit vˇsichni jedinci, ne pouze kr´alovny a sameˇcci. N´aˇs model pˇredstavuje urˇcit´e zjednoduˇsen´ı a nav´ıc umoˇzn ˇ uje pozorovat vˇetˇs´ı dynamiku v´yvoje, kter´a by jinak byla vidˇet jen pˇri v´yvoji cel´ych mraveniˇst’. Zrozen´ı nov´eho mravence prob´ıh´a tak, ˇze se vezmou ˇctyˇri mravenci, dva nej´ uspˇeˇsnˇejˇs´ı v noˇsen´ı a dva v objevov´an´ı. Polovina nov´ych potomk˚ u je v´ysledkem zkˇr´ıˇzen´ı dvou nejlepˇs´ıch nosiˇc˚ u, druh´a polovina dvou nejlepˇs´ıch objevitel˚ u (viz 2.7.2). D´ıky tomu by se postupem ˇcasu mˇely vytvoˇrit dvˇe v´yjov´e vˇetve. Jedna specializovan´a na objevov´an´ı, druh´a na noˇsen´ı. Pˇr´ıpadnˇe by se mohla vytvoˇrit jedna vˇetev univerz´aln´ıch mravenc˚ u, kteˇr´ı budou zvl´adat oboj´ı, ale to je vzhledem k odliˇsnosti jejich u ´ kol˚ u nepravdˇepodobn´e. Samotn´e kˇr´ıˇzen´ı prob´ıh´a tak, ˇze se pˇri vytv´aˇren´ı genetick´e v´ybavy nov´eho jedince vezme polovina pole GEN (viz 2.7.3) od prvn´ıho mravence a druh´a polovina od druh´eho. Nav´ıc m˚ uˇze nˇekter´a poloˇzka pole GEN s urˇcitou prav7 dˇepodobnost´ı zmutovat .

2.7.7

Pohyb

Na jednom pol´ıˇcku m˚ uˇze b´yt vˇzdy maxim´alnˇe jeden mravenec. Jedinou v´yjimkou je pol´ıˇcko s mraveniˇstˇem, kde se m˚ uˇze vyskytovat libovoln´y poˇcet mravenc˚ u. 7

Dostane novou n´ ahodnou hodnotu v dan´em rozsahu

19

Mravenec je v kaˇzd´em okamˇziku natoˇcen do jednoho z osmi smˇer˚ u. Budeme je oznaˇcovat podle svˇetov´ych stran. Pˇri v´ychodu z mraveniˇstˇe je mu pˇriˇrazen n´ahodn´y smˇer. NW W SW

N M S

NE E SE

Tabulka 2.1: Smˇery

Mravenec m˚ uˇze j´ıt pˇr´ımo (bez ot´aˇcen´ı) na tˇri pol´ıˇcka - na pole, kter´e leˇz´ı pˇr´ımo v jeho smˇeru a na pole, kter´a leˇz´ı v pˇrilehl´ych smˇerech jeho p˚ uvodn´ıho smˇeru. Bˇehem pˇresunu po pˇrilehl´ych smˇerech nedoch´az´ı, ke zmˇenˇe p˚ uvodn´ıho smˇeru. napˇr. Pokud je orientov´an na SE, m˚ uˇze j´ıt i na pol´ıˇcka nach´azej´ıc´ı se ve smˇeru E a S. Pokud se chce mravenec dostat na jin´a pole, tak se mus´ı otoˇcit. Jedno otoˇcen´ı vˇzdy zab´ır´a jeden tah aˇz tˇri tahy v z´avislosti na pr˚ uchodnosti pol´ıˇcka, na kter´em se nach´az´ı. D´elka pˇresunu pak z´avis´ı na pr˚ uchodnosti pol´ıˇcka, na kter´e se mravenec pˇresouv´a. Otoˇcen´ım m˚ uˇze mravenec zmˇenit sv˚ uj souˇcasn´y smˇer pouze na jeden z pˇrilehl´ych smˇer˚ u.

2.8

Monitorov´ an´ı

Monitorov´an´ı v programu je implementov´ano, tak aby jeho v´ysledky byly co nejl´epe porovnateln´e s v´ysledky v [1].

2.8.1

Poˇ c´ıtadla

Poˇc´ıtadlo je skupina dvojic souˇradnic (tj. mnoˇzina {((X1,Y1),(X2,Y2)), ...}). M´a unik´atn´ı pojmenov´an´ı (pr´avˇe dva znaky) a slouˇz´ı k poˇc´ıt´an´ı mravenc˚ u, kteˇr´ı proˇsli mezi dvojicemi zadan´ych bod˚ u. Mezi kaˇzdou dvojic´ı bod˚ u vede spojnice. Kdyˇz ji mravenec pˇrekon´a, vejde na pol´ıˇcka na spojnici a zase z 20

nich odejde, tak se zv´yˇs´ı hodnota poˇc´ıtadla. Kaˇzd´a spojnice si udrˇzuje seznam mravenc˚ u, kteˇr´ı se na n´ı vyskytovali v minul´em kole, a na z´akladˇe rozd´ılu seznamu mezi minul´ym a souˇcasn´ym kolem si zjist´ı poˇcet mravenc˚ u, kteˇr´ı j´ı proˇsli. Pokud se spojnice jednoho poˇc´ıtadla nˇekde prot´ınaj´ı, tak se m˚ uˇze st´at, ˇze jeden mravenec bude zapoˇc´ıt´an do jednoho poˇc´ıtadla v´ıcekr´at8 .

2.8.2

Cesty a Skupiny cest

Cesta je posloupnost poˇc´ıtadel, kter´ymi mravenec proˇsel pˇri sv´em putov´an´ı. Cesty se d´ale sdruˇzuj´ı do skupin. Kaˇzd´a skupina cest m´a svoje pojmenov´an´ı (maxim´alnˇe ˇctyˇri znaky), kter´e nemus´ı b´yt unik´atn´ı. Pokud mravenec doˇsel aˇz ke zdroji potravy a proˇsel vˇsemi poˇc´ıtadly v takov´em poˇrad´ı, jak´e je u nˇekter´e z cest, tak se hodnota u skupiny cest, do n´ıˇz dan´a cesta patˇr´ı, zv´yˇs´ı o jedna. Pˇred t´ımto porovn´an´ım jsou z tˇechto cest odstranˇeny smyˇcky, abychom mˇeli lepˇs´ı pˇrehled o tom, jakou cestu mravenec vlastnˇe pouˇzil. Poˇcet cest se smyˇckami je pak uloˇzen ve speci´aln´ı promˇenn´e. Pokud mravencova cesta nen´ı ani v jedn´e skupinˇe cest, tak se zvyˇsuje poˇcet u v´ychoz´ı cesty pojmenovan´e osta.

2.8.3

Zaj´ımav´ e promˇ enn´ e

Mimo monitorov´an´ı cest a poˇc´ıtadel, n´as jeˇstˇe zaj´ımaj´ı dalˇs´ı promˇenn´e veliˇciny simulace. Glob´aln´ı ˇcas simulace je nutnost´ı, bez nˇej se ned´a urˇcit, kdy se co odehr´av´a. D´ale jeˇstˇe chceme zn´at poˇcet mravenc˚ u a poˇcet jednotek j´ıdla, abychom mˇeli pˇrehled o populaˇcn´ıch v´ykyvech. M´enˇe d˚ uleˇzitou vlastnost´ı je kapacita mraveniˇstˇe, z kter´e lze vyˇc´ıst pouze to, jak zhruba byla populace mravenc˚ u poˇcetn´a v dobˇe jej´ıho nejvˇetˇs´ıho rozkvˇetu. Pro statistick´e se u ´ˇcely se nav´ıc hod´ı celkov´y poˇcet sebran´eho j´ıdla a jiˇz zmiˇ novan´y poˇcet cest ke zdroji potravy se smyˇckami.

2.8.4

Shrnut´ı

Veˇsker´e v´ysledky pˇredchoz´ıch odstavc˚ u jsou pouˇzity pro tvorbu v´ystup˚ u pro statistiky. Ty se pak vypisuj´ı pˇr´ımo na konzoli, pˇr´ıpadnˇe se daj´ı zobrazit ve 8

Pokud opust´ı spojnice v pr˚ useˇc´ıku.

21

speci´aln´ım oknˇe. Statistiky se nevypisuj´ı v kaˇzd´em kole, ale pouze jednou za 300 kol. Pˇr´ıpadnˇe lze v konzolov´e verzi nastavit ˇcasy, kdy se maj´ı statistiky zobrazit.

2.9

Pr˚ ubˇ eh jednoho kola

1. Navyˇsov´an´ı poˇc´ıtadel (viz 2.8.1) 2. Kontrola kalend´aˇr˚ u j´ıdla a pˇrek´aˇzek (viz 2.2.1, 2.3.1) 3. Zpracov´an´ı v´ystupu statistiky (viz 2.8.4) 4. Generovn´an´ı j´ıdla (viz 2.2) 5. Kontrola mnoˇzen´ı (viz 2.7.6) 6. Tahy mravenc˚ u (viz 2.7.4) 7. Zv´yˇsen´ı ˇcasu simulace 8. Vypaˇrov´an´ı feromon˚ u

2.10

Pozn´ amky k implementaci

K implementaci jsem pouˇzil jazyk Java. Zvolil jsem si jej pˇredevˇs´ım kv˚ uli moˇznostem snadn´e pˇrenositelnosti na r˚ uzn´e platformy. Samotn´a aplikace jde spustit ze dvou verz´ıch: • Konzolov´a verze • GUI verze Bliˇzˇs´ı popis tˇr´ıd, metod a parametr˚ u se d´a vyˇc´ıst z vygenerovan´eho javadocu (viz Pˇr´ıloˇzen´e CD).

22

2.10.1

Verze Javy

Pro pˇreloˇzen´ı zdrojov´ych k´od˚ u je nutn´e m´ıt nainstalovan´e JDK verze 1.5 a vyˇsˇs´ı9 . Na spuˇstˇen´ı by mˇelo staˇcit JRE verze 1.5 a vyˇsˇs´ı10 . Pro vˇetˇs´ı pohodl´ı je moˇzn´e pouˇz´ıt pro pˇreklad program ant11 .

2.10.2

Popis soubor˚ u

mraveniste/gui/Ram.java mraveniste/gui/Pohled.java mraveniste/gui/RamStatistika.java mraveniste/gui/Vypocet.java mraveniste/gui/GUI.java mraveniste/gui/dialog/DJidloVyskyt.java mraveniste/gui/dialog/DPromene.java mraveniste/gui/dialog/DZakladna.java mraveniste/gui/dialog/DJidloKalendar.java mraveniste/gui/dialog/DPrekazky.java mraveniste/gui/dialog/DPocitadla.java mraveniste/Main.java mraveniste/Konstanty.java mraveniste/Data.java

2.10.3

okno s menu vizualizace simulace okno se statistikou hlavn´ı smyˇcka simulace hlavn´ı tˇr´ıda GUI aplikace dialog v´yskytu j´ıdla dialog nastaven´ı vlastnost´ı dialog nastaven´ı polohy z´akladny dialog nastaven´ı kalend´aˇre j´ıdla dialog nastaven´ı kalend´aˇre pˇrek´aˇzek dialog nastaven´ı poˇc´ıtadel a cest hlavn´ı tˇr´ıda konzolov´e aplikace interface s konstantami tˇr´ıda pro simulaci

Rozd´ıly mezi GUI a konzol´ı

V konzolov´e verzi se hlavn´ı smyˇcka nach´az´ı pˇr´ımo v hlavn´ı tˇr´ıdˇe, kter´a tak´e pracuje s aktu´aln´ı instanc´ı tˇr´ıdy Data. Pokud je aplikace spuˇstˇena s parametrem -gui, tak je pouze otevˇreno okno GUI, ˇz´adn´y dalˇs´ı v´ypoˇcet pak neprob´ıh´a. GUI pro vlastn´ı simulaci vyuˇz´ıv´a tˇr´ıdu Vypocet, ve kter´e bˇeˇz´ı smyˇcka. Vypocet pracuje s aktu´aln´ı instanc´ı tˇr´ıdy Data a bˇeˇz´ı ve vlastn´ım vl´aknu12 . Hlavn´ı smyˇcka programu se v GUI a v konzolov´e verzi liˇs´ı pouze ve vykreslov´an´ı a ve v´ystupn´ıch datech. Z´akladn´ı sch´ema ˇcinnosti z 2.9 z˚ ust´av´a za9

http://java.sun.com/javase/downloads/index.jsp http://java.sun.com/javase/downloads/index.jsp 11 http://ant.apache.org/ 12 Bez vlastn´ıho vl´ akna by se pˇrestala vykreslovat okna aplikace. 10

23

chov´ano. C´ılem toho rozdˇelen´ı bylo, aby se v konzolov´e smyˇcce neprov´adˇely zbyteˇcn´e akce.

2.10.4

Uˇ zit´ e datov´ e struktury

• Kalend´aˇre Do kalend´aˇr˚ u j´ıdla a pˇrek´aˇzek se bˇehem simulace nepˇrid´avaj´ı prvky. Jedin´a akce, kter´a se s nimi prov´ad´ı, je maz´an´ı prvn´ıho prvku. Toto maz´an´ı neprob´ıh´a pˇr´ıliˇs ˇcasto. M˚ uˇzeme oˇcek´avat, ˇze probˇehne jen p´arkr´at za simulaci. D´ıky tomu m˚ uˇzeme pro uchov´av´an´ı prvk˚ u pouˇz´ıt t´emˇeˇr libovolnou datovou strukturu, aniˇz by toto rozhodnut´ı mˇelo pozorovateln´y vliv na rychlost simulace. Naproti tomu z kalend´aˇre akc´ı budeme prvky nejen odeb´ırat, ale i pˇrid´avat a to pomˇernˇe ˇcasto, protoˇze se do nˇej zapisuje kaˇzd´y mravenec pohybuj´ıc´ı se na mapˇe. Pˇristupujeme vˇzdy k prvn´ımu prvku, kter´y n´aslednˇe ˇrad´ıme d´ale do fronty. Poˇzadavk˚ um na tuto operaci asi nejl´epe vyhovuje datov´a struktura typu haldy. V jazyce Java je halda reprezentov´an´a tˇr´ıdou PriorityQueue13 . • Mapa Mapa je reprezentov´ana jako pole. Jednotliv´a pol´ıˇcka obsahuj´ı pouze statick´e poloˇzky: informace o mnoˇzstv´ı j´ıdla, o stavebn´ım materi´alu, o mnoˇzstv´ı feromon˚ u, ... . Tyto u ´ daje bychom mohli udrˇzovat v nˇejak´e dynamick´e datov´e strukturu (LinkedList pol´ıˇcek, co obsahuj´ı j´ıdlo, atd.), abychom se vyhnuli zbyteˇcn´e redundanci. Nicm´enˇe by pak bˇehem simulace prob´ıhala spousta alokac´ı, kter´e by zpomalovaly v´ypoˇcet. • Poˇc´ıtadla Poˇc´ıtadlo (viz 2.8.1) proch´az´ı vˇsechna pole, kter´a obsahuje, a hled´a na nich mravence, kter´e n´aslednˇe ukl´ad´a do ArrayListu. D´ale si pamatuje kteˇr´ı mravenci se na nˇem vyskytovali v minul´em kole. Na z´akladˇe porovn´an´ı tˇechto dvou ArrayList˚ u je moˇzn´e urˇcit kolik mravenc˚ u proˇslo poˇc´ıtadlem. ArrayList jsem pouˇzil, protoˇze je v´ıce optimalizov´an na sekvenˇcn´ı proch´azen´ı. 13

viz dokumentace k jazyku Java

24

Jin´a moˇznost by byla, ˇze by kaˇzd´e pol´ıˇcko na mapˇe mˇelo seznam poˇc´ıtadel, kter´a zvyˇsuje. Mravenec by si zapamatoval seznam poˇc´ıtadel pol´ıˇcka, na kter´em se nach´az´ı. D´ıky tomu by pˇri pˇrechodu na nov´e pol´ıˇcko bylo moˇzn´e zjistit, jak se seznamy liˇs´ı, a podle toho nav´yˇsit urˇcit´a poˇc´ıtadla. Tuto moˇznost jsem nezvolil pˇredevˇs´ım proto, ˇze jsem do programu pˇrid´aval podporu pro poˇc´ıtadla aˇz pozdˇeji a nechtˇel jsem pˇr´ıliˇs zasahovat do jiˇz funguj´ıc´ı implementace. • Mravenec – Cesta zpˇet Kaˇzd´y mravenec si pˇresnˇe pamatuje cestu zpˇet do mraveniˇstˇe. Pˇri pˇresunu na nov´e pole si ukl´ad´a souˇradnice tohoto pole do ArrayListu. Nav´ıc je zajiˇstˇeno, aby se v t´eto struktuˇre nevyskytovaly smyˇcky. Pˇri pˇrid´an´ı nov´e souˇradnice se pˇr´ıpadn´a smyˇcka smaˇze. Tato kontrola sice stoj´ı urˇcitou reˇzii, ale redukuje spotˇrebu pamˇeti, kter´a by zvl´aˇstˇe pˇri vˇetˇs´ım poˇctu mravenc˚ u byla ne´ unosn´a. – Navˇst´ıven´a poˇc´ıtadla Mravenec si pamatuje vˇsechna poˇc´ıtadla, kter´ymi proˇsel. D´ıky tomu m˚ uˇzeme zjistit, jakou cestou (posloupnost´ı poˇc´ıtadel) pˇriˇsel ke zdroji potravy. Prvky se zde mohou opakovat. Z t´eto cesty jsou pˇri zpracov´an´ı vyjmuty smyˇcky. Tato operace m˚ uˇze tedy mazat i prvky uprostˇred seznamu a tud´ıˇz je pro n´aˇs u ´ˇcel vhodnˇejˇs´ı LinkedList. Mohli bychom mazat smyˇcky uˇz pˇri pˇrid´av´an´ı jednotliv´ych poˇc´ıtadel, nicm´enˇe bychom tuto ˇcinnost prov´adˇeli i u mravenc˚ u, kteˇr´ı ’ cestu k j´ıdlu nenajdou, coˇz je zbyteˇcn´e. Pamˇet ovˇe je toto ˇreˇsen´ı sice n´aroˇcnˇejˇs´ı, nicm´enˇe na rozd´ıl od cest zpˇet tu nebude poˇc´ıtadel tolik. Nav´ıc se zde nevytv´aˇr´ı nov´a struktura, pouze se kop´ıruje odkaz na poˇc´ıtadlo. D´ale m˚ uˇzeme poˇc´ıtat s t´ım, ˇze poˇcet smyˇcek u navˇst´ıven´ych poˇc´ıtadel nebude tak velk´y jako u cest zpˇet. Nav´ıc chceme zn´at poˇcet cest se smyˇckami, ne celkov´y poˇcet smyˇcek. Kdybychom je odstraˇ novali v kaˇzd´em kole, tak by bylo nezbytn´e si drˇzet u mravence promˇennou, kter´e by ˇr´ıkala, zda proˇsel smyˇckou.

25

Kapitola 3 Uˇ zivatelsk´ a Dokumentace Program se obyˇcejnˇe spouˇst´ı pˇr´ıkazem: java -jar dist/mraveniste.jar [PARAMETRY]

3.1

Ovl´ ad´ an´ı pˇ res konzoli

PARAMETRY : -bp Vyp´ın´a pamˇet’ mravence. Mravenec si ve v´ychoz´ım nastaven´ı pamatuje cestu zpˇet do mraveniˇstˇe. Pokud se k vol´an´ı pˇrid´a tento parametr, tak se mravenec pokus´ı naj´ıt cestu zpˇet pomoc´ı feromonov´ych stop. -nk Zap´ın´a nekoneˇcn´y svˇet. Kdyˇz se mravenec dostane na okraj plochy, tak m˚ uˇze pˇrel´ezt a objevit se na opaˇcn´e stranˇe. -mut N N je mezi 0 a 100. Nastavuje pravdˇepodobnost mutace pˇri kˇr´ıˇzen´ı. Pravdˇepodobnost je rovna N/100 .

26

-pocm N N je mezi 1 a 100. Nastavuje kolik mravenc˚ u je vytvoˇreno na poˇc´atku simulace. Z´aroveˇ n se pro tento poˇcet mravenc˚ u bude automaticky generovat potrava. Pokud jsou mravenci naˇcteni ze souboru, tak se mravenci na poˇc´atku simalace nevytv´aˇr´ı. -je N M N je mezi 1000 a 100000. M je mezi 200 a N. N urˇcuje kolik z´ısk´a mravenec tah˚ u, kdyˇz se naj´ı. Pokud mravenci dojde energie, tak um´ır´a. M urˇcuje tzv. energetickou hranici. Pokud je energie mravence vyˇsˇs´ı neˇz energetick´a hranice, tak se mravenec nenaj´ı. Energetick´a hranice m´a tak´e vliv na to, kdy se zaˇcne mravenec vracet do mraveniˇstˇe. -jo X1 xY1 :X2 xY2 [:D[:OD[:DO]]] X1, X2 jsou mezi 0 a 199. Y1, Y2 jsou mezi 0 a 99. D je mezi 0 a 263 − 1. OD je mezi 0 a 263 − 1. DO je mezi OD a 263 − 1. Pˇrid´av´a na mapu novou oblast, kde se bude objevovat j´ıdlo. Pokud nebude ˇz´adn´a takov´a oblast vytvoˇrena, j´ıdlo se bude objevovat n´ahodnˇe. Pokud je v´ıc oblast´ı a pokud m´a nˇejak´a oblast vysok´e D, tak se tam bude j´ıdlo objevovat ˇcastˇeji neˇz v ostatn´ıch oblastech. OD a DO nastavuj´ı dobu platnosti dan´e oblasti. Tento parametr m´a smysl pouˇz´ıt v´ıckr´at. -p X1 xY1 :X2 xY2 [:CAS [:CENA]] X1, X2 jsou mezi 0 a 199. Y1, Y2 jsou mezi 0 a 99. CAS je mezi 0 a 263 − 1. CENA je mezi 0 a 4. Pˇrid´av´a/Odeb´ır´a z mapy pˇrek´aˇzky. CENA pak urˇcuje dobu, za kterou mravenec pˇrekon´a dan´e pole. Napˇr. Pokud je CENA 3, tak mravenci bude trvat 3 tahy, neˇz pole pˇrejde. Kdyˇz cena je rovna 0, tak je pole nepr˚ uchodn´e. Pokud pˇri um´ıst’ov´an´ı nepr˚ uchodn´e 27

pˇrek´aˇzky najdeme na poli mravence, tak jej pˇresuneme zp´atky na z´akladnu. Pol´ıˇcko se z´akladnou je vˇzdy voln´e a m´a nastavenu cenu za pr˚ uchod na 1. Tento parametr m´a smysl pouˇz´ıt v´ıckr´at. -z X1 xY1 :X2 xY2. X1, X2 jsou mezi 0 a 199. Y1, Y2 jsou mezi 0 a 99. Nastavuje novou polohu z´akladny. Zvolen´e pole je nastaveno jako voln´e a jeho cena za pr˚ uchod se nastav´ı na 1. -jp N M N je mezi 0 a 1000. M je mezi 1 a 1000. M a N urˇcuj´ı kolik tah˚ u vydrˇz´ı zdroj j´ıdla, neˇz se vyˇcerp´a. V´ysledn´y poˇcet tah˚ u je M + n´ahodn´e ˇc´ıslo mezi 0 a N. -jobev N N je mezi 1 a 1000. Nastavuje pravdˇepodobnost (N / 1000 ), ˇze se v pˇr´ıˇst´ım tahu na mapˇe objev´ı nov´y zdroj j´ıdla. -fA N N je mezi 0 a 1000. Nastavuje kolik jednotek Feromonu A vylouˇc´ı mravenec na pol´ıˇcko. -fB N N je mezi 0 a 1000. Nastavuje kolik jednotek Feromonu B vylouˇc´ı mravenec na pol´ıˇcko. -maxfA N N je mezi 1000 a 100000. Nastavuje maxim´aln´ı hodnotu Feromonu A na pol´ıˇcku. -maxfB N N je mezi 1000 a 100000. Nastavuje maxim´aln´ı hodnotu Feromonu B na pol´ıˇcku.

28

-vypfA N N je mezi 1 a 100. Nastavuje kolik jednotek Feromonu A zmiz´ı z pol´ıˇcka bˇehem jednoho tahu. -vypfB N N je mezi 1 a 100. Nastavuje kolik jednotek Feromonu B zmiz´ı z pol´ıˇcka bˇehem jednoho tahu. -sbmin N N je mezi 1 a 1000. Nastavuje min´aln´ı dobu trv´an´ı akce, pˇri n´ıˇz mravenec zdvih´a z pol´ıˇcka j´ıdlo a stavebn´ı materi´al. -sbnah N N je mezi 0 a 1000. Tento parametr omezuje shora n´ahodnou hodnotu, kter´a se pˇriˇc´ıt´a k hodnotˇe parametru -sbmin. Mravenec potˇrebuje pro zdvihnut´ı j´ıdla ˇcas, kter´y se rovn´a souˇctu u parametru -sbmin a n´ahodn´e hodnotˇe z rozsahu h0, N). -pocstavm N N je mezi 0 a 100. Nastavuje poˇcet stavebn´ıho materi´alu na mapˇe. -rozstavm N N je mezi 1 a 200. Nastavuje poˇcet stavebn´ıho materi´alu, potˇrebn´eho pro rozˇs´ıˇren´ı z´akladny. -maxpobyt N N je mezi 1 a 500. Omezuje shora n´ahodou hodnotu reprezentuj´ıc´ı ˇcas, kter´y mravenec str´av´ı v mraveniˇsti. N´ahodn´a hodnota leˇz´ı v rozsahu h1, Ni.

29

-konec N N je mezi 1 a 263 − 1. Ukonˇc´ı v dan´y ˇcas simulaci. Plat´ı pouze pro konzolovou verzi. -vypis N1 :[N2 :[...]] Nx je mezi 1 a 263 − 1 a nav´ıc Nx < Nx+1 Statistiky se budou vypisovat pouze v zadan´e ˇcasy. Plat´ı pouze pro konzolovou verzi. -rozdil Statistiky se budou poˇc´ıtat jako rozd´ıl mezi jednotliv´ ymi v´ypisy. Plat´ı pouze pro konzolovou verzi. -pocnov N N je mezi 1 a 10. Nastavuje kolik mravenc˚ u se vytvoˇr´ı bˇehem jednoho kˇr´ıˇzen´ı. -mnozspot N M N je mezi 1 a 50. M je mezi 1 a N. N urˇcuje kolik mus´ı b´yt na z´akladnˇe nadbyteˇcn´eho j´ıdla, aby se mravenci zkˇr´ıˇzili. M urˇcuje kolik j´ıdla se spotˇrebuje pˇri kˇr´ıˇzen´ı. -nos N N je mezi 1 a 10. N urˇcuje kolik jednotek j´ıdla mravenec unese. -dzivot N N je mezi 100000 a 1000000. Nastavuje maxim´aln´ı dobu ˇzivota mravence. Kdyˇz mravenec pˇrekroˇc´ı tuto dobu um´ır´a. -sims SOUBOR SOUBOR urˇcuje cestu k souboru se simulac´ı kter´y se m´a naˇc´ıst. Naˇcte uloˇzenou simulaci1 ze souboru. 1

pol´ıˇcka, kalend´aˇr j´ıdla, kalend´aˇr pˇrek´aˇzek, poloha z´ akladny, poˇc´ıtadla a cesty

30

-mras SOUBOR SOUBOR urˇcuje cestu k souboru s mravenci kter´y se m´a naˇc´ıst. Naˇcte mravence ze souboru. -gui Spust´ı GUI. Vˇsechny zadan´e parametry se budou br´at jako v´ychoz´ı nastaven´ı simulace. Toto nastaven´ı je moˇzn´e upravit pˇr´ımo v GUI, nicm´enˇe po resetu se obnov´ı v´ychoz´ı nastaven´ı. -mon JMENO:X1 xY1 :X2 xY2 :[X1 xY1 :X2 xY2 :[X1 xY1 :X2 xY2 :[...]]] JMENO je jm´eno nov´eho poˇc´ıtadla, mus´ı b´yt unik´atn´ı. X1, X2 jsou mezi 0 a 199. Y1, Y2 jsou mezi 0 a 99. Pˇrid´a na mapu poˇc´ıtadlo s unik´atn´ım jm´enem. Poˇc´ıtadlo mus´ı m´ıt minim´alnˇe jeden z´aznam. Z´aznamem se ruzum´ı dvojice souˇradnic ((X1,Y1),(X2,Y2)). Kdyˇz mezi nimi projde mravenec, tak poˇc´ıtadlo zv´yˇs´ı svoji hodnotu. Je to vlastnˇe skupina kontroln´ıch bod˚ u monitoruj´ıc´ıch pohyb mravence. V´ystup simulace je doplnˇen o jm´ena vˇsech poˇc´ıtadel a jejich hodnoty. Tento parametr m´a smysl pouˇz´ıt v´ıckr´at. -cst JMENO:[POC [-POC [-...]]:[POC [-POC [-...]][:...]]] JMENO je jm´eno nov´e skupiny cest. POC jm´ena poˇc´ıtadel (vytvoˇren´ych parametrem -mon) Pˇrid´a novou skupinu cest. Cesta je reprezentov´ana tvarem p1p2-p3-p1, kde p1, p2, p3 jsou existuj´ıc´ı poˇc´ıtadla. Cesty jsou od sebe oddˇeleny dvojteˇckou. Cesta m´a u sebe hodnotu, kter´a urˇcuje poˇcet mravenc˚ u, kteˇr´ı ji vyuˇzili pˇri u ´ spˇeˇsn´e cestˇe za potravou. V´ystup simulace bude doplnˇen o jm´ena vˇsech cest a jejich hodnoty. Tento parametr m´a smysl pouˇz´ıt v´ıckr´at.

31

3.2

Ovl´ ad´ an´ı pˇ res GUI

1. menu Simulace (alt + s) • Start - Spouˇst´ı simulaci se zvolenou rychlost´ı. ctrl + s • Pauza - Zmraz´ı aktu´aln´ı stav simulace. ctrl + p • Reset - Zastav´ı simulaci a pˇrenastav´ı vˇsechna data do p˚ uvodn´ıho stavu. ctrl + r • Rychlost - Nastav´ı rychlost simulace a spust´ı simulaci. – Nejpomalejˇ s´ı - Na dalˇs´ı tah se ˇcek´a 300 ms. ctrl + 1 – Pomalejˇ s´ı - Na dalˇs´ı tah se ˇcek´a 200 ms. ctrl + 2 – Norm´ aln´ı - Na dalˇs´ı tah se ˇcek´a 100 ms. ctrl + 3 – Rychlejˇ s´ı - Na dalˇs´ı tah se ˇcek´a 50 ms. ctrl + 4 – Nejrychlejˇ s´ı - Na dalˇs´ı tah se ˇcek´a 10 ms (poˇc´ıtaˇc nemus´ı stihnout pˇrekreslen´ı cel´eho okna). ctrl + 5 – Bez Vykreslov´ an´ı - Okno simulace se nepˇrekresluje, v´yvoj simulace lze sledovat pomoc´ı okna Statistika (ctrl + t). ctrl + 6

32

• Konec - Ukonˇc´ı aplikaci a uvoln´ı program z pamˇeti. ctrl + k 2. menu Data (alt + d ) • Z´ akladna - Zobraz´ı dialog, ve kter´em je moˇzn´e nastavit polohu z´akladny (m´ısta kam mravenci nos´ı j´ıdlo). ctrl + b • J´ıdlo na mapˇ e - Zobraz´ı dialog, kter´y upravuje oblasti, kde se objevuje j´ıdlo. ctrl + j • Parametry - Zobraz´ı dialog s moˇznost´ı nastaven´ı nejr˚ uznˇejˇs´ıch parametr˚ u. ctrl + v J´ıdlo a stavebn´ı materi´ al – Minim´ aln´ı doba zdvih´ an´ı - Urˇcuje minim´aln´ı dobu, kterou mravenec str´av´ı zdvih´an´ım j´ıdla a stavebn´ıho materi´alu. – N´ ahodn´ a doba zdvih´ an´ı - V´ysledn´y ˇcas, kter´y mravenec potˇrebuje pro zdvihnut´ı j´ıdla nebo stavebn´ıho materi´alu, se poˇc´ıt´a jako souˇcet mezi Minim´ aln´ı dobou zdvih´ an´ı a n´ahodn´ym ˇc´ıslem z intervalu h0, N), kde N je N´ ahodn´ a doba zdvih´ an´ı. – Poˇ cet stavebn´ıho materi´ alu - Urˇcuje poˇcet jednotek stavebn´ıho materi´alu na mapˇe. Pokud je hodnota tohoto parametru nastavena na 0, tak mravenc˚ u na mapˇe nepˇrib´yv´a, protoˇze nelze zvˇetˇsit kapacitu mraveniˇstˇe. – Nutn´ y stavebn´ı materi´ al - Nastavuje poˇcet stavebn´ıho materi´alu, kter´y je nutn´y pro rozˇs´ıˇren´ı kapacity mraveniˇstˇe o jedna.

33

– Energie z j´ıdla - Nastavuje kolik mravenec z´ısk´a energie (poˇcet tah˚ u), kdyˇz se naj´ı. – Nov´ e j´ıdlo - Nastavuje minim´aln´ı poˇcet jednotek j´ıdla novˇe vytvoˇren´eho zdroje. – Koeficient nov´ eho j´ıdla - Pˇri vytv´aˇren´ı zdroje nov´eho j´ıdla se k celkov´emu poˇctu jednotek j´ıdla na pol´ıˇcku (Nov´ e j´ıdlo) pˇriˇc´ıt´a nav´ıc n´ahodn´e ˇc´ıslo z intervalu h0, N), kde N je Koeficient nov´ eho j´ıdla. – Pravdˇ epodobnost vytvoˇ ren´ı j´ıdla - Nastavuje pravdˇepodobnost, ˇze se v pˇr´ıˇst´ım tahu na mapˇe objev´ı nov´y zdroj j´ıdla. Mravenci – Pravdˇ epodobnost mutace - Nastavuje pravdˇepodobnost, ˇze pˇri kˇr´ıˇzen´ı dostane nˇejak´a genov´a promˇenn´a novou n´ahodnou hodnotu. – J´ıdlo potˇ rebn´ e pro kˇ r´ıˇ zen´ı - Nastavuje kolik nadbyteˇcn´eho j´ıdla mus´ı b´yt na z´akladnˇe, aby se mravenci zkˇr´ıˇzili. – J´ıdlo spotˇ rebovan´ e pro kˇ r´ıˇ zen´ı - Nastavuje kolik j´ıdla se spotˇrebuje pˇri kˇr´ıˇzen´ı. – Poˇ cet nov´ ych mravenc˚ u - Nastavuje kolik mravenc˚ u se vytvoˇr´ı bˇehem jednoho kˇr´ıˇzen´ı. – Poˇ c´ ateˇ cn´ı poˇ cet mravenc˚ u - Nastavuje kolik mravenc˚ u se vytvoˇr´ı na poˇc´atku simulace. Nav´ıc se bude na z´akladnˇe automaticky generovat j´ıdlo, postaˇcuj´ıc´ı k v´yˇzivˇe tohoto poˇctu jedinc˚ u. – Nosnost Mravence - Nastavuje poˇcet jednotek j´ıdla, kter´e mravenec unese. 34

– Energetick´ a hranice - Pokud je energie mravence vyˇsˇs´ı, neˇz Energetick´a hranice, tak se mravenec nenaj´ı. Mravenec se nav´ıc na z´akladˇe tohoto parametru a genetick´e v´ybavy rozhodne, kdy se zaˇcne vracet do mraveniˇstˇe. – Doba ˇ zivota - Jakmile pˇres´ahne st´aˇr´ı mravence tuto hodnotu, tak mravenec um´ır´a. – Pobyt v mraveniˇ sti - Ovlivˇ nuje dobu, kterou mravenec str´av´ı v mraveniˇsti pˇri doplˇ nov´an´ı energie a vykl´ad´an´ı j´ıdla nebo stavebn´ıho materi´alu. Doba se vyb´ır´a jako n´ahodn´e ˇc´ıslo v rozmez´ı h1, Ni. Feromony – Intenzita Feromonu A - Nastavuje kolik jednotek Feromonu A se objev´ı na pol´ıˇcku po pr˚ uchodu mravence vyluˇcuj´ıc´ıho Feromon A. – Intenzita Feromonu B - Nastavuje kolik jednotek Feromonu B se objev´ı na pol´ıˇcku po pr˚ uchodu mravence vyluˇcuj´ıc´ıho Feromon B. – Maximum Feromonu A - Urˇcuje maxim´aln´ı poˇcet jednotek Feromonu A na pol´ıˇcku. – Maximum Feromonu B - Urˇcuje maxim´aln´ı poˇcet jednotek Feromonu B na pol´ıˇcku. – Rychlost vypaˇ rov´ an´ı Feromonu A - Poˇcet jednotek Feromonu A, kter´e se vypaˇr´ı za jeden tah. – Rychlost vypaˇ rov´ an´ı Feromonu B - Poˇcet jednotek Feromonu B, kter´e se vypaˇr´ı za jeden tah.

35

• Kalend´ aˇ r J´ıdla - Zobraz´ı dialog, kde se d´a nastavit, jak se budou mˇenit zdroje j´ıdla v z´avislosti na ˇcase. ctrl + g • Kalend´ aˇ r Pˇ rek´ aˇ zek - Zobraz´ı dialog, kde se d´a nastavit, jak se budou mˇenit pˇrek´aˇzky v z´avislosti na ˇcase. Lze zde mˇenit pr˚ uchodnost (0-3) jednotliv´ych oblast´ı bˇehem simulace. ctrl + z • Poˇ c´ıtadla a cesty - Zobraz´ı dialog, kde se nastavuj´ı body slouˇz´ıc´ı pro monitorov´an´ı simulace. Poˇc´ıtadla jsou skupiny spojnic mezi dvˇema body, kter´e poˇc´ıtaj´ı kolik mravenc˚ u jimi proˇslo a cesty jsou skupiny posloupnost´ı poˇc´ıtadel, kter´a zjiˇst’uj´ı, kolik mravenc˚ u vyuˇzilo danou cestu skupinu cest ke zdroji j´ıdla. ctrl + y • Pˇ rek´ aˇ zky - Zde se vol´ı, jak´e pˇrek´aˇzky se um´ıst´ı na plochu po stisku lev´eho tlaˇc´ıtka. – Nepr˚ uchodn´ e - Pˇrek´aˇzka je nepr˚ uchodn´a. ctrl + q – Tˇ eˇ zko Pr˚ uchodn´ e - Pr˚ uchod zabere mravenci tˇri tahy. ctrl + w – H˚ uˇ re Pr˚ uchodn´ e - Pr˚ uchod zabere mravenci dva tahy. ctrl + e • Nekoneˇ cn´ y svˇ et - Urˇcuje, co se stane, kdyˇz se mravenec dostane k okraji plochy. Pokud je zatrˇzena, tak se mravenec po pˇrelezen´ı okraje ocitne na opaˇcn´e stranˇe plochy. Kdyˇz nen´ı, tak se mravenec chov´a jakoby by byly okraje nepr˚ uchodn´e. ctrl + i • Pamˇ et’ mravence - Zap´ın´a / Vyp´ın´a pamˇet’ mravence. Mravenec si za norm´aln´ıch okolnost´ı pˇresnˇe pamatuje, cestu kterou pˇriˇsel z mraveniˇstˇe (bez smyˇcek). Pokud vypneme pamˇet mravence, tak 36

se mravenec pokus´ı dostat zp´atky do mraveniˇstˇe pomoc´ı feromonov´e stopy, kterou vyluˇcoval cestou od mraveniˇstˇe. ctrl + m • Naˇ cti Mravence - Naˇcte mravence z bin´arn´ıho souboru. ctrl + n • Uloˇ z Mravence - Uloˇz´ı mravence do bin´arn´ıho souboru. ctrl + u • Naˇ cti Simulaci - Naˇcte uloˇzenou simulaci ze souboru. Simulac´ı se rozum´ı pol´ıˇcka, kalend´aˇr j´ıdla, kalend´aˇr pˇrek´aˇzek, poloha z´akladny, poˇc´ıtadla a cesty. ctrl + c • Uloˇ z Simulaci - Uloˇz´ı simulaci do souboru. ctrl + d • Edituj Mapu - Resetuje simulaci a zapne/vypne m´od pro editaci mapy. ctrl + f 3. menu Zobrazen´ı (alt + z ) • Statistika - Zap´ın´a / Vyp´ın´a zobrazov´an´ı okna Statistika. ctrl + t • Data k zobrazen´ı - Zde se d´a zvolit, kter´a data se budou zobrazovat v oknˇe Statistika. Hodnoty se budou zobrazovat ve stejn´em poˇrad´ı, jak´e je v menu. ˇ - Zobraz´ı ˇcas. – Cas ctrl + 7 – Poˇ cet mravenc˚ u - Zobraz´ı poˇcet mravenc˚ u. ctrl + 8

37

– Mnoˇ zstv´ı j´ıdla - Zobraz´ı mnoˇzstv´ı j´ıdla v mraveniˇsti. ctrl + 9 – Kapacitu mraveniˇ stˇ e - Zobraz´ı maxim´aln´ı poˇcet mravenc˚ u, jenˇz je schopn´e mraveniˇstˇe pojmout. ctrl + 0 – Poˇ c´ıtadla - Zobraz´ı jm´ena poˇc´ıtadel a kolik mravenc˚ u uˇz jimi proˇslo. ctrl + – Cesty - Zobraz´ı jm´ena cest a kolik mravenc˚ u je jiˇz pouˇzilo. ctrl + . – Smyˇ cky - Zobraz´ı poˇcet cest se smyˇckami. ctrl + = – Celkem cest - Zobraz´ı celkov´y poˇcet cest. ctrl + , • Zobrazit mˇ r´ıˇ zku - Zap´ın´a / Vyp´ın´a zobrazov´an´ı mˇr´ıˇzky. ctrl + x • Zobrazit feromony - Zap´ın´a / Vyp´ın´a zobrazov´an´ı feromon˚ u. ctrl + l • Zobrazit Poˇ c´ıtadla - Zap´ın´a / Vyp´ın´a zobrazov´an´ı poˇc´ıtadel. ctrl + / 4. menu N´ apovˇ eda (alt + n) • O programu - Zobraz´ı informace o programu. ctrl + h

38

5. Tlaˇ c´ıtka myˇ si • Lev´ e - Pˇrid´av´a / Odeb´ır´a pˇrek´aˇzky. • Prostˇ redn´ı - Pˇrid´av´a oblasti, ve kter´ych se objevuje j´ıdlo. V editaˇcn´ım m´odu pak pˇrid´av´a/odeb´ır´a oblasti pˇrek´aˇzek. • Prav´ e - Pˇrid´av´a j´ıdlo.

39

Kapitola 4 Porovn´ an´ı se skuteˇ cn´ ymi mravenci V t´eto ˇc´asti se nach´az´ı porovn´an´ı navrˇzen´eho modelu s chov´an´ım skuteˇcn´ych mravenc˚ u popsan´em v [1].

4.1 4.1.1

Experiment se skuteˇ cn´ ymi mravenci Popis prostˇ red´ı

Experiment se odehr´al v prostˇred´ı umˇele vytvoˇren´eho bludiˇstˇe. Bludiˇstˇe se skl´adalo ze ˇctyˇr identick´ych kosoˇctverc˚ u sloˇzen´ych dohromady a z pˇeti kruhov´ych dutin, viz Obr´azek 4.1. Pro pokus byli pouˇziti Argentinˇst´ı mravenci Linepithema humile. Bylo vytvoˇreno 10 pokusn´ych koloni´ı, kaˇzd´a obsahuj´ıc´ı cca 2000 jedinc˚ u. Vˇsichni mravenci byli posb´ır´an´ı mimo mraveniˇstˇe a m˚ uˇzeme je tud´ıˇz povaˇzovat za sbˇeraˇce. Kaˇzd´a kolonie byla um´ıstˇena v plastov´em kontejneru a ponech´ana 4 dny bez j´ıdla.

4.1.2

Popis experiment˚ u

Na poˇc´atku experimentu se kolonie spojila s bludiˇstˇem plastov´ym mostem. Mravenci museli proj´ıt pˇres tento most, pak skrz bludiˇstˇe aˇz ke zdroji potravy a zp´atky. J´ıdlo bylo um´ıstˇeno v polovinˇe experiment˚ u do dutiny A, 40

Obr´azek 4.1: Prostˇred´ı experimentu s re´aln´ymi mravenci - Obr´azek z [1]

Cesty ke zdroji A Cesty ke zdroji B 1-2a-2b-3a 4-5a-5b-6a 1-10-8-11-3a 1-10-8-9-6a 4-7-8-11-3a 4-7-8-9-6a 4-5a-5b-9-11-3a 1-2a-2b-11-9-6a 4-7-10-2a-2b-3a 1-10-7-5a-5b-6a 4-5a-5b-6a-6b-3b 1-2a-2b-3a-3b-6b 4-7-8-9-6a-6b-3b 1-10-8-11-3a-3b-6b 1-10-8-9-6a-6b-3b 4-7-8-11-3a-3b-6b 1-2a-2b-11-9-6a-6b-3b 4-5a-5b-9-11-3a-3b-6b 1-10-7-5a-5b-6a-6b-3a 4-7-10-2a-2b-3a-3b-6b 1-10-7-5a-5b-9-11-3a 4-7-10-2a-2b-11-9-6a 4-7-10-2a-2b-11-9-6a-6b-3b 1-10-7-5a-5b-9-11-3a-3b-6b Tabulka 4.1: Moˇzn´e cesty k potravˇe

41

D´elky cest s - 21,5 cm kr´atk´e m - 30,5 cm stˇredn´ı

l - 39,5 cm dlouh´e vl - 48,5 cm velmi dlouh´e

v druh´e polovinˇe do dutiny B. Po kaˇzd´em experimentu bylo bludiˇstˇe ˇr´adnˇe oˇciˇstˇeno. Kaˇzd´y experiment trval 60 minut. V s´ıti existuje dvan´act moˇzn´ych cest (bez smyˇcek) jak se dostat skrz bludiˇstˇe ke zdroji potravy, viz Tabulka 4.1. Vˇsech deset kolonii bylo testov´ano tˇremi r˚ uzn´ymi zp˚ usoby: 1. Prostˇred´ı simulace se nemˇenilo. 2. Prvn´ıch tˇricet minut, mˇeli mravenci pˇr´ıstup do vˇsech ˇc´ast´ı bludiˇstˇe. Pot´e se zablokovala chodba tˇesnˇe u zdroje potravy. V pˇr´ıpadˇe, kdyˇz je zdroj j´ıdla v dutinˇe A, zataras´ı se 3a. Pokud je v dutinˇe B, tak 6a. 3. Prvn´ıch tˇricet minut mohli mravenci vyuˇz´ıvat pouze jednu cestu ke zdroji potravy. Pokud bylo j´ıdlo uloˇzeno v dutinˇe dutinˇe A, to byla cesta 1-10-7-5-9-11-3a. V pˇr´ıpadˇe dutiny B 4-7-10-2-11-9-6a. Pot´e mˇeli mravenci pˇr´ıstup do cel´eho bludiˇstˇe.

4.1.3

V´ ysledky pokus˚ u

Re´ aln´ı mravenci Ve vˇetˇsinˇe experiment˚ u ˇsli mravenci ke zdroji j´ıdla nejkratˇs´ı cestou. Ve vˇsech experimentech zvolili nejkratˇs´ı cestu od zdroje j´ıdla do mraveniˇstˇe. Nicm´enˇe v druh´e ˇc´asti experiment˚ u po zablokov´an´ı cest nebyly nˇekter´e kolonie schopn´e naj´ıt cestu ke zdroji j´ıdla. Mravenci se v takov´em pˇr´ıpadˇe dostali do smyˇcky, ze kter´e se uˇz nedostali. Nˇekter´ym koloni´ım se tak´e po odblokov´an´ı cest nedaˇrilo nal´ezt nejkratˇs´ı cestu k j´ıdlu. Bˇehem simulace vyuˇz´ıvaly jen cestu, kter´a byla voln´a v prvn´ı ˇc´asti experimentu. Jedna kolonie dokonce zaˇcala vyuˇz´ıvat v´ıce cest nar´az vˇcetnˇe p˚ uvodn´ı, viz Obr´azek 4.2. U mravenc˚ u byly tak´e namˇeˇreny dalˇs´ı zajimav´e charekteristiky: • Pr˚ umˇern´a rychlost mravence - 1.10 cm/s • Frekvence ot´aˇcen´ı o 180◦ stupˇ n˚ u pˇri cestˇe ke zdroji j´ıdla - 0.15 • Frekvence ot´aˇcen´ı o 180◦ stupˇ n˚ u pˇri cestˇe do mraveniˇstˇe - 0.10 • Pr˚ umˇern´a doba pobytu u zdroje j´ıdla. - 185.30 s 42

• Pr˚ umˇern´y Maxim´aln´ı poˇcet mravenc˚ u v bludiˇsti - 100 jedinc˚ u

Obr´azek 4.2: V´ysledky experimentu s re´aln´ymi mravenci - Obr´azek z [1] (a) Neomezen´y pˇr´ıstup do vˇsech m´ıst cel´ych 60 minut. (b)-(c) Zablokov´an´ı cesty: frekvence pˇred (b) a po (c) zablokov´an´ı cesty ve 30. minutˇe. (d) Po uvolnˇen´ı vˇsech cest, pouze druh´a polovina experimentu.

43

4.2 4.2.1

Simulace Popis prostˇ red´ı

Mapu jsem vytv´aˇrel v editaˇcn´ım m´odu programu (viz 3.2). Jeden centimetr by mˇel odpov´ıdat zhruba ˇsesti pol´ıˇck˚ um. Kv˚ uli ˇcast´emu ucp´av´an´ı cest pobl´ıˇz vstupu do mraveniˇstˇe jsem se rozhodl ˇs´ıˇrku cest zdvojn´asobit, viz Obr´azek 4.3. Mravenci mˇeli k dispozici 3764 pˇr´ıstupn´ych pol´ıˇcek.

Obr´azek 4.3: Prostˇred´ı vytvoˇren´e v editaˇcn´ıho m´odu

4.2.2

Popis simulace

Program nejprve vytvoˇr´ı urˇcit´y poˇcet mravenc˚ u s n´ahodnou genetickou v´ybavou. Tito mravenci jsou ale nevhodn´ı pro porovn´an´ı, protoˇze se u nich jeˇstˇe nevyvinula dobr´a strategie pro hled´an´ı a transport potravy. Kv˚ uli tomu je nutn´e si nejprve pˇripravit vyzr´alejˇs´ı populaci. Tato populace byla vytvoˇrena v grafick´em m´odu programu postupn´ym pˇresouv´an´ım zdroje j´ıdla a pˇrid´av´an´ım pˇrek´aˇzek.

44

Vzhledem k pr˚ umˇern´e rychlosti re´aln´ych mravenc˚ u pohybuj´ıc´ıch se na mapˇe (viz 4.1.3) bude simulace trvat 25000 tah˚ u. Poˇcet jedinc˚ u bude 100. Na mapˇe se nebude vyskytovat stavebn´ı materi´al. T´ım doc´ıl´ıme toho, ˇze mravenc˚ u nebude na mapˇe pˇrib´yvat. Mravenci str´av´ı u zdroje j´ıdla 900 aˇz 1300 tah˚ u. V mraveniˇsti pak nebudou d´ele neˇz 400 tah˚ u. Kaˇzd´a simulace prob´ıhala 100-kr´at a byla spouˇstˇena s parametry: - pocm 100 - konec 25000 - vypis 12500:25000 - rozdil - sbmin 900 - sbnah 400 - maxpobyt 400 - pocstavm 0

Vlastn´ı pokus mˇel stejnou strukturu, jako pokus s opravdov´ymi mravenci. V´ysledky se dˇel´ı: 1. Dle typu simulace: Obyˇ cejn´ a - prostˇred´ı se nemˇenilo. Zablokov´ an´ı - v p˚ ulce simulace se zablokovaly nejkratˇs´ı cesty do mraveniˇstˇe a mravenci byli nuceni pouˇz´ıt delˇs´ı cestu. Zpr˚ uchodnˇ en´ı - na poˇc´atku bylo moˇzn´e pouˇz´ıt pouze jednu dlouhou cestu a v p˚ ulce simulace se vˇsechny cesty zpr˚ uchodnily. 2. Dle um´ıstˇen´ı zdroje potravy (viz Obr´azek 4.1): A - j´ıdlo bylo v dutinˇe A B - j´ıdlo bylo v dutinˇe B 45

3. Dle ˇcasu: 12500 - prvn´ı ˇc´ast simulace. 25000 - druh´a ˇc´ast simulace. D´ale byl tak´e sledov´an celkov´y poˇcet nalezen´ych cest ke zdroji j´ıdla a celkov´y poˇcet cest ke zdroji j´ıdla se smyˇckami.

A Obyˇcejn´a 1. ˇc´ast A Obyˇcejn´a 2. ˇc´ast A Zablokov´an´ı 1. ˇc´ast A Zablokov´an´ı 2. ˇc´ast A Zpr˚ uchodnˇen´ı 1. ˇc´ast A Zpr˚ uchodnˇen´ı 2. ˇc´ast B Obyˇcejn´a 1. ˇc´ast B Obyˇcejn´a 2. ˇc´ast B Zablokov´an´ı 1. ˇc´ast B Zablokov´an´ı 2. ˇc´ast B Zpr˚ uchodnˇen´ı 1. ˇc´ast B Zpr˚ uchodnˇen´ı 2. ˇc´ast

Pr˚ umˇernˇe naˇsli cest 238,85 300,25 238,21 47,97 125,38 221,03 238,99 298,41 238,26 54,07 125,96 233,75

Z toho se smyˇckami 96,15 83,23 96,14 34,14 100,49 83,49 96,47 85,91 97,72 37,87 99,19 86,96

Tabulka 4.2: Pr˚ umˇern´e poˇcty cest a smyˇcek

46

Obr´azek 4.4: V´ysledky pokusu s j´ıdlem v dutinˇe A 47

Obr´azek 4.5: V´ysledky pokusu s j´ıdlem v dutinˇe B 48

4.2.3

V´ ysledky

Je snadno pozorovateln´e, ˇze pokud jsou simulace stejn´eho typu liˇs´ıc´ı se pouze v um´ıstˇen´ı zdroje j´ıdla, tak jsou jejich grafy takˇrka totoˇzn´e, viz Obr´azky 4.4 a 4.5. Pˇri pokusech se zablokov´an´ım cesty se i ve druh´e ˇc´asti experiment˚ u objevuje menˇs´ı mnoˇzstv´ı cest d´elky s, kter´e by mˇely b´yt zablokovan´e. Je to d´ano t´ım, ˇze se nˇekteˇr´ı mravenci vyskytovali jiˇz za novˇe pˇridanou pˇrek´aˇzkou, ale jeˇstˇe nestihli nal´ezt j´ıdlo. Ve statistik´ach se ˇc´ıtaˇc u cest zvyˇsuje aˇz v momentˇe, kdy mravenec najde j´ıdlo. T´ım p´adem se do statistik zapoˇc´ıtala kr´atk´a cesta, aˇckoliv v tu dobu uˇz nebyla pr˚ uchodn´a. Ve v´ysledc´ıch je pomˇernˇe ˇcasto zastoupena skupina cest ostat, reprezentuj´ıc´ı ostatn´ı cesty1 . Z cest jsou sice pˇri pˇrid´av´an´ı do statistik odstraˇ nov´any cykly. Nicm´enˇe pokud mravenec vstoup´ı do poˇc´ıtadla a vystoup´ı z nˇej na stejn´e stranˇe, kudy veˇsel, pak se pˇriden´e poˇc´ıtadlo nepovaˇzuje za smyˇcku a tud´ıˇz nen´ı pˇri pˇrid´av´an´ı do statistik odstranˇeno. Cesta s takov´ymto ”hrotem” je ˇrazena mezi ostatn´ı. Nejvˇetˇs´ı v´yskyt tˇechto cest je v situaci po zablokov´an´ı kr´atk´ych cest ke zdroji j´ıdla.

4.3

Srovn´ an´ı

Skuteˇcn´ı mravenci pouˇz´ıvaj´ı pˇri cestˇe ke zdroji potravy a zpˇet r˚ uzn´e cesty. Naproti tomu simulovan´ı mravenci chod´ı zp´atky do mraveniˇstˇe po t´emeˇr totoˇzn´e cestˇe, ze kter´e se jen odstran´ı smyˇcky. Veˇsker´a srovn´av´an´ı se proto budou t´ykat pouze cesty k j´ıdlu.

4.3.1

Obyˇ cejn´ a

V´ysledky se zde nejsou zas aˇz tak rozd´ıln´e. Vypad´a to, ˇze mravenci ze simulace jsou trochu lepˇs´ı, vezmeme-li ale v potaz relativnˇe vysok´e mnoˇzstv´ı smyˇcek, kter´e se zapoˇc´ıt´avaly jako regulern´ı cesta, tak se jejich v´ykonnost nezd´a aˇz tak oslniv´a. Nicm´enˇe v obou pˇr´ıpadech se jasnˇe ukazuje, ˇze mra1

D´ale v textu jsou tak´e uznaˇcov´any jako nezaˇraditeln´e.

49

venci preferovali nejkratˇs´ı moˇznou variantu.

4.3.2

Zablokov´ an´ı

V t´eto ˇc´asti experiment˚ u mˇeli mravenci v obou pˇr´ıpadech pomˇernˇe dost probl´emu naj´ıt optim´aln´ı cestu. Opravdov´ı mravenci chodili celkem ˇcasto po dlouh´ych cest´ach a nav´ıc nˇekter´e kolonie v˚ ubec nebyly schopn´e naj´ıt cestu ke zdroji a cesty konˇcily ve smyˇcce. Mravenci ze simulace tak´e nijak moc neoslnili. Dlouh´e cesty vyb´ırali sice je zˇr´ıkda, ale bˇehem pokusu vyuˇzili nezanedbateln´e mnoˇzstv´ı nezaˇraditeln´ych cest (viz 4.2.3). Nav´ıc se zde cesty bez smyˇcek vyskytovaly opravdu po skromnu.

4.3.3

Zpr˚ uchodnˇ en´ı

Skuteˇcn´ı mravenci si v t´eto ˇc´asti pokusu vedli relativnˇe sluˇsnˇe. Nicm´enˇe nˇekter´e kolonie nebyly schopn´e naj´ıt nejkratˇs´ı cestu do mraveniˇstˇe a drˇzely se zn´am´e vyˇslapan´e cestiˇcky. Mravenci ze simulace tak´e pod´avali velice dobr´e v´ykony. Sice mˇeli v prvn´ı ˇc´asti simulace vysok´y pod´ıl smyˇcek, ale ve druh´e ˇc´asti pro nˇe nebyl probl´em naj´ıt a vyuˇz´ıvat nejkratˇs´ı cestu. Jejich graf z druh´e ˇc´asti je hodnˇe podobn´y graf˚ um simulace s nemˇenn´ym prostˇred´ım.

50

Kapitola 5 Z´ avˇ er 5.1

Diskuze

Po porovn´an´ı v´ysledk˚ u by se dalo ˇr´ıct, ˇze se mravenci ze simulace um´ı l´epe pˇrizp˚ usobit zmˇen´am prostˇred´ı. Je to d´ano t´ım, ˇze celkem ˇcasto hledaj´ı nov´e cesty a snaˇz´ı se v´ıce objevovat. Toto chov´an´ı by se jistˇe dalo ovlivnit tak, ˇze by se zmˇenil pomˇer objevitel˚ u a nosiˇc˚ u. Ot´azkou ovˇsem z˚ ust´av´a, jak tento pomˇer vypad´a a jak´y m´a vliv na efektivitu sbˇeru j´ıdla. Re´aln´ı mravenci se naopak snaˇz´ı drˇzet jedn´e cesty, coˇz m˚ uˇze m´ıt neblah´y vliv na efektivitu. Na to doplatily pˇredevˇs´ım kolonie, kter´e zaˇcaly chodit v ˇ kruhu v druh´e ˇc´asti experimentu se zablokov´an´ım cest. Rekl bych, ˇze by vˇetˇs´ı mnoˇzstv´ı ”objevitel˚ u” mohlo tˇemto koloni´ım pomoci k lepˇs´ım v´ysledk˚ um. Nicm´enˇe pokud vezmeme v u ´ vahu n´astrahy re´aln´eho svˇeta, mus´ıme pˇripustit ˇze mravenec, kter´y se ocitne na ciz´ım j´ıdeln´ıˇcku, uˇz moc toho j´ıdla neodnos´ı a osamˇel´y objevitel je pro pred´atora velmi snadn´a koˇrist. Pˇri pokusu s umˇel´ymi mravenci se ˇcasto st´avalo, ˇze mravenec pˇri cestˇe do mraveniˇstˇe vyuˇzil cestu, kter´a obsahovala smyˇcku. Nav´ıc se zde vyskytovalo tak´e pomˇernˇe velk´e mnoˇzstv´ı nezaˇraditeln´ych cest. Tyto jevy jsou dle m´eho n´azoru zp˚ usobeny obˇcasn´ym ”ucp´an´ı” cest, kdy mravenci nezbyde nic jin´eho, neˇz se vr´atit a t´ım vytvoˇr´ı smyˇcku. Nezaˇraditeln´e cesty by ˇsly ze statistik odstranit lepˇs´ı implementac´ı poˇc´ıtadel, kter´a by l´epe rozliˇsovala pr˚ uchody mravenc˚ u pˇres pol´ıˇcka poˇc´ıtadla. Tento oprava je pl´anov´ana do budouc´ıch verz´ı programu.

51

5.2

Z´ avˇ er

C´ılem pr´ace bylo navrˇzen´ı a vytovoˇren´ı modelu napodobuj´ıc´ıho chov´an´ı mravenc˚ u pˇri sbˇeru potravy. Oproti p˚ uvodn´ımu pl´anu implementovan´y model obsahuje nav´ıc rozdˇelen´ı hodnocen´ı mravenc˚ u na nosiˇce a objevitele (v p˚ uvodn´ım pl´anu byli pouze nosiˇci) a nekoneˇcn´y svˇet (viz 3.1). Nav´ıc se kv˚ uli moˇznosti srovn´an´ı s re´aln´ymi mravenci musel do aplikace zakomponovat cel´y syst´em monitorov´an´ı cest a poˇc´ıtadel. Pˇribyla tak´e ˇrada drobnˇejˇs´ıch doplˇ nuj´ıc´ıch nastaven´ı napˇr´ıklad nastaviteln´a doba, kterou mravenec str´av´ı v mraveniˇsti, ˇci nastaviteln´a doba, kterou str´av´ı nakl´ad´an´ım j´ıdla. Tyto vlastnosti hodnˇe pˇrispˇely k vytvoˇren´ı sloˇzitˇejˇs´ıho prostˇred´ı. Porovn´an´ı s v´ysledky expteriment˚ u z [1] uk´azalo, ˇze se n´aˇs model sv´ym chov´an´ım pˇribl´ıˇzil k chov´an´ı skuteˇcn´ych mravenc˚ u, nicm´enˇe k dokonalosti mu jeˇstˇe nˇeco chyb´ı. Model postr´ad´a napˇr´ıklad: • Lepˇs´ı implementaci poˇc´ıtadel (viz 2.10.4) • Odstranˇen´ı nezaˇraditeln´ych cest (viz 4.2.3) • Pˇrid´an´ı nastaven´ı pomˇeru mezi nosiˇci a objeviteli • Moˇznost pˇrid´an´ı v´ıce vchod˚ u do mraveniˇstˇe • Nov´a strategie mravenc˚ u pˇri n´avratu do mraveniˇstˇe, tak aby v´ıce odpov´ıdala skuteˇcnosti. • atd.

Pr´ace na projektu byla ˇcasovˇe n´aroˇcnˇejˇs´ı, neˇz jsem p˚ uvodnˇe oˇcek´aval. Nicm´enˇe jsem se bˇehem pr´ace dovˇedˇel spoustu zaj´ımav´ych vˇec´ı o etologii mravenc˚ ua douf´am, ˇze jsem aspoˇ n trochu pˇrispˇel k objasnˇen´ı jejich komplexn´ı etologie.

52

Kapitola 6 Pˇ r´ılohy 6.1

CD

CD obsahuje: • Zdrojov´e k´ody programu psan´e v jazyce Java • Pˇreloˇzen´y program • Ebuild pro Gentoo • Vygenerovan´y javadoc

53

Literatura [1] Karla Vittori, Jacques Gautrais, Aluizio F.R. Araj´ uo, Vincent Fourcassi´e and Guy Theraulaz: Modeling Ant Behaviour Under a Variable Environment, ANTS Workshop, 2004. ˇ ep´an: Pravdˇepodobnost a matematick´a statistika, [2] Karel Zv´ara, Josef Stˇ MATFYZPRESS, 2006.

54