UNIVERZITA KOMENSKÉHO V BRATISLAVE
FAKULTA MATEMATIKY, FYZIKY A INFORMATIKY
Algoritmický prístup k
modelovaniu umelých mravcov
2011
Martin Bobák
UNIVERZITA KOMENSKÉHO V BRATISLAVE
FAKULTA MATEMATIKY, FYZIKY A INFORMATIKY
201401b0-7134-47f3-8494-4aa100a6ab29
Algoritmický prístup k
modelovaniu umelých mravcov
Bakalárska práca
Študijný program: Aplikovaná informatika
Študijný odbor: 9.2.9 Aplikovaná informatika
Školiace pracovisko: Katedra aplikovanej informatiky
Školiteľ: RNDr. Andrej Lúčny, PhD.
Bratislava, 2011
Martin Bobák
Čestné prehlásenie.
Prehlasujem, že bakalársku prácu som vypracoval
samostatne, s použitím citovaných prameňov.
.................................
i
Poďakovanie
Týmto by som sa chcel poďakovať RNDr. Andrejovi Lúčnemu, PhD.,
vedúcemu bakalárskej práce, za odborné vedenie, za poskytovanie
materiálových podkladov a za cenné rady, usmernenia a pripomienky.
ii
Abstrakt
Práca sa zaoberá algoritmom, ktorým prehľadávajú mravce terén. Týmto
spôsobom dokážu mravce nájsť najkratšiu cestu k zdroju potravy. Súčasťou
práce je aj simulácia umelých mravcov.
Kľúčové slová: umelá inteligencia, multiagentové systémy, ant colony
optimisation algoritmus, agent, NetLogo
iii
Abstract
In this thesis we study Ant-based routing algorithm, that provides optimal
path to food source. Part of this thesis is a simulation of artificial ants.
Keywords: Artificial intelligence (AI), Multi-agent system, Ant colony
optimisation algorithm, Agent, NetLogo
iv
Obsah
Úvod
1
1 Biologická motivácia - mravce
3
1.1 Život a smrť kolónie ….............................................................................................
7
1.2 Komunikácia …........................................................................................................
8
1.3 Superorganizmus …..................................................................................................
10
1.4 Centralizácia verzus decentralizácia ........................................................................
11
2 Biologicky motivované oblasti informatiky
12
2.1 Multiagentové systémy .............................................................................................
13
2.2 Ant computing ..........................................................................................................
14
2.2.1 ACO a problém obchodného cestujúceho ........................................................ 15
3 Zvolené technológie
17
3.1 NetLogo ...................….............................................................................................
17
3.1.1 Logo .................................................................................................................
18
4 Model správania mravcov
20
5 Návrh a implementácia riešenia
22
5.1 Návrh riešenia ..........................................................................................................
22
5.2 Implementácia riešenia ...........................................................................................
26
5.2.1 Implementácia agentov – robotníc ..................................................................
26
5.2.2 Implementácia agentov – políčok ...................................................................
28
6 Experimenty
29
6.1 Experiment 1. - viaceré zdroje potravy v rôznej vzdialenosti od hniezda ..............
29
6.2 Experiment 2. - viaceré zdroje potravy v rovnakej vzdialenosti od hniezda ..........
31
6.3 Experiment 3. - modifikácia ACO algoritmu ..........................................................
32
7 Záver
35
Príloha A
39
A.1 CD so zdrojovými kódmi .......................................................................................
39
Úvod
Podľa tradovanej povesti kráľ Svätopluk, na počiatku našich národných dejín, odkázal
svojim potomkom: „V jednote je sila!“ Vtedy možno ešte ani netušil koľko živočíšnych
druhov aktívne využíva túto tézu, narozdiel od jeho troch rozvadených synov. Tímovú
prácu (obrázok 1 znázorňuje tímovú spoluprácu mravcov) prirodzene preferujú živočíšne
druhy zoskupujúce sa do kŕdľov (vtáci), svoriek (vlci), skupín (ryby), ale na druhej strane
aj neuróny, tvoriace nervovú sústavu, leukocyty starajúce sa o našu imunitu a podobne. Je
priam fascinujúce ako jedinec, riadiaci sa jednoduchými pravidlami, dokáže v skupine
úspešne riešiť úlohy, ktoré ďaleko prevyšujú jeho osobné schopnosti. Sú to náročné úlohy s
riešením ktorých majú problémy aj súčasné superpočítače a to je už čo povedať.
Obrázok 1: Mravčie spoločenstvo (Zdroj: www.alexanderwild.com)
V ríši hmyzu sa už na prvý pohľad javí pohyb mravca ako mimoriadne efektívny –
perfektne naplánovaný a zároveň synchronizovaný s ostatnými členmi skupiny. Ako to
dokážu? Navonok to vyzerá tak, akoby mravce mali svojho „vodcu“. Niekoho, kto to celé
naplánuje a „oznámi“ im, čo má kto a kedy urobiť. Takisto sa môže zdať, akoby ich
usmerňovala mravčia kráľovná a signalizovala im kde najbližšie pri mravenisku sa
nachádza potrava. Odpoveď na túto zložitú otázku je však taká jednoduchá, že sa zdá byť
až neskutočná. Mravce, podobne ako aj sťahovaví vtáci, majú totiž spoločné, že sa riadia
1
niekoľkými jednoduchými pravidlami a ostatné je „len“ výsledkom ich spoločného
správania.
Každý živočíšny druh ponúka riešenie určitého problému. Biológovia preto venujú
veľa času intenzívnemu pozorovaniu správania sa živočíchov [6]. Informatiku, konkrétne
umelú inteligenciu, zaujal mravec. Kľúčovú úlohu pri hľadaní potravy mravcami zohráva
feromón. Je to biologická látka prostredníctvom ktorej komunikujú medzi sebou živočíchy
jedného druhu. Keď mravce hľadajú potravu, tak sa najprv rozptýlia po celom okolí
mraveniska. V prvej fáze hľadajú potravu decentralizovane. Hneď ako niektorý z mravcov
nájde zdroj potravy, zoberie ju a vracia sa s ňou do mraveniska. Cestou zanecháva za sebou
feromónovú stopu. Týmto signalizuje svojim druhom, kde sa nachádza potrava. Hľadanie
potravy sa dostáva do druhej – organizovanej fázy. Len čo mravec, pri svojom chaotickom
pobehovaní za potravou, narazí na feromónovú stopu, okamžite sa vydá po vyznačenej
ceste a súčasne zosilní feromónovú stopu. Týmto sa vytvorí feromónový koridor, cez ktorý
mravce postupne odnesú celú potravu do mraveniska. Zaujímavé na tomto algoritme je, že
ak sa v blízkosti mraveniska nachádza viac zdrojov potravy, tak mravce postupujú od
najbližšieho k najvzdialenejšiemu zdroju.
V informatike tieto javy reprezentujeme a skúmame pomocou „multiagentových
systémov“. Sú to systémy skladajúce sa zo stoviek či tisícov agentov. Agent reprezentuje v
tomto prípade jedného jedinca. Agent teda dokáže vnímať svoje okolie a reagovať naň,
respektíve sledovať určitý cieľ.
Cieľ práce: Naším cieľom je modelovať správanie sa mravcov so zameraním na
modelovanie algoritmov, ktoré mravenisko používa pri riešení parciálnych úloh, ako je
hľadanie najkratšej cesty k potrave. Najprv vytvoríme model, v ktorom budeme simulovať
správanie sa mravcov. Úlohou mravcov (agentov) bude hľadať najkratšiu cestu vedúcu
z mraveniska k zdroju. Keď budeme mať vytvorený model zameriame sa na to, ako vplýva
prostredie na tento algoritmus. To znamená, že si vytvoríme prostredie s rôznymi
prekážkami, či zdrojmi potravy. V týchto rôznorodých podmienkach budeme sledovať,
ako sa nami vytvorené umelé mravce budú správať.
2
Kapitola 1
Biologická motivácia - mravce
Pri skúmaní uvedených javov rieši väčšina biologických odborov dve základné otázky: ako
to funguje a prečo to tak funguje. Inými slovami povedané, ako je ten-ktorý proces
determinovaný anatomicky, ako prebieha na molekulárnej úrovni a prečo sa v procese
vývoja prejavila práve táto vlastnosť a nie iná. Biológovia sa domnievajú, že v princípe
vedia ako fungujú mravčie pospolitosti, a že poznajú približne aj dobu ich vzniku, t. j. pred
100 až 120 miliónmi rokov [6]. Nastal však čas položiť si základnú otázku prečo v procese
evolúcie došlo k sformovaniu pospolitosti? Aká bola výhoda sociálneho života dávnych ôs,
predchodkýň mravcov, prečo tento faktor zásadne ovplyvnil ich ďalší život?
Jedným z najdôležitejších rysov mravčej kolónie je existencia kasty robotníc,
tvorenej samičkami, ktoré slúžia svojej matke a sú ochotné potlačiť aj vlastnú reprodukciu,
len aby sa mohli starať o svoje sestry a bratov. Ich prirodzený inštinkt spôsobuje nie len to,
že sa vzdávajú svojho vlastného potomstva, ale aj to že kvôli mravčej kolónií riskujú aj
vlastný život. Len fyzické opustenie hniezda, za účelom zháňania potravy, znamená zvoliť
si
nebezpečenstvo
bezpečnosťou
v
pred
mravenisku.
relatívnou
Napríklad
mravce zrnojedé (žijúce v západnej časti USA)
vykazujú pri zháňaní potravy, len v dôsledku
stretu so susednými kolóniami mravcov, až 6
% úmrtnosť za hodinu. Ďalšie robotnice hynú
ako korisť predátorov, iné zablúdia a zahynú.
V každú chvíľu sa asi 15 % robotníc
zúčastňuje na dlhých a nebezpečných cestách
za potravou mimo hniezda. Životnosť jednej
robotnice je priemerne jeden týždeň. Za túto
dobu však dokáže do mraveniska zhromaždiť
potravu, ktorá váži 15 – 20 krát viac ako váži
ona sama (na obrázku 2 vidíme, že robotnica
odnesie náklad vážiaci stokrát viac ako ona).
Obrázok 2: Mravec nesúci závažia, ktoré vážia stokrát viacej ako on sám (Zdroj: idmilano.com)
3
Robotnice typickej mravčej kolónie sú dcérami jednej kráľovnej. Samčeky,
potomkovia kráľovnej, sa rodia až potom, keď je populácia robotníc stabilná a je pred
rojením. Samčeky žijú iba niekoľko týždňov, prípadne mesiacov. Nijako sa nezapájajú do
práce. Počas svojho pobytu v hniezde sú úplne závislí na svojich sestrách „amazonkách“.
Tieto ich tolerujú, pretože zabezpečujú prenos génov kolónie.
Britský entomológ a genetik William D. Hamilton vyslovil prevratný názor, že
pohlavie mravcov je určené, podobne ako pri iných blanokrídlovcoch (osy, včely), tým
najjednoduchším spôsobom. Keď je vajíčko oplodnené – je diploidné – vznikne z neho
samička. Ak vajíčko nie je oplodnené – je haploidné – a vznikne z neho samček. Kráľovná
týmto spôsobom reguluje pohlavie svojho potomstva.
Prečo sa vlastne mravce chovajú tak altruisticky? Aká je vývojová výhoda života v
skupine? Správna odpoveď sa priam ponúka. Ak živočích, ako integrálny člen skupiny,
ľahšie prežíva a má aj viac potomstva, potom je racionálnejšie spolupracovať, než žiť
individuálne. Sú dôkazy, že v prírode to takto funguje. Napríklad vtáci v kŕdľoch, alebo
slony v skupinách, žijú oveľa dlhšie a majú oveľa viac potomstva, než ak by žili
samostatne. Vďaka skupine rýchlejšie nachádzajú potravu a ich obrana proti nepriateľom
je oveľa efektívnejšia.
Inú odpoveď na túto otázku nám ponúka Hamiltonova teória, ktorú Dawkins nazval
„teória sebeckého génu“. Podľa tejto teórie všetky blanokrídlovce, teda aj mravce, sú
haploidné. Samičky majú sadu génov zdedených od otca a matky, z ktorých prispieva
každý rovnakým počtom génov. Matky s dcérami zdieľajú polovicu zhodných génov, čo
nie je nič nezvyčajné v živočíšnej ríši. Sestry však zdieľajú až tri štvrtiny svojich génov. To
je spôsobené tým, že otec pochádza z neoplodneného vajíčka [4].
Samček, na rozdiel od samičky, nemá zmiešané gény. Má iba jednu sadu génov,
ktorú získal od matky. Dôsledkom toho je, že všetky spermie, ktoré samčeky mravcov (či
iných blanokrídlovcov) odovzdávajú svojim dcéram, sú totožné. Sestry sú si preto
geneticky bližšie, majú spoločné tri štvrtiny génov, namiesto zvyčajnej polovice.
Samička je polovicou svojich génov spriaznená so svojou matkou a tak isto aj so
svojimi dcérami. Takže stačí, keď sa o ne bude obyčajne starať. Ale so svojimi sestrami sú
spojené tromi štvrtinami svojich génov. A tak vzniklo nové, bizarnejšie biologické
usporiadanie: aby do budúcej generácie vložila samička rovnaké gény aké má ona sama, je
pre ňu „výhodnejšie“ starať sa o sestry, než o dcéry.
4
Vzťah medzi bratmi je tiež nerovnomerný. V podstate nemajú žiadneho otca, preto
iba s jednou štvrtinou svojich génov sú príbuzní so samičkami. Pre sestry je výhodnejšie
vychovať iba nevyhnutný počet bratov a to len v dobe nutnej na oplodnenie mladých
kráľovien. Pre bratov je výhodnejšia pasivita v mravenisku, keďže majú šancu sa stať
otcami novej kolónie. Pre nich nemá zmysel tráviť čas vychovávaním sestier. Lepšie je žiť
na úkor spoločenstva.
Obrázok 3: Mravenisko (Zdroj: blog.crowdspring.com )
Mravce sa na Zemi objavili v období dinosaurov. Rozšírili sa po celom svete a
vytvorili obrovské množstvo rôznych druhov. Odhaduje sa, že dnes žije na našej planéte
okolo 10 000 druhov mravcov [6]. Prečo sú mravce také úspešné? Príčinou je pohotovo
využívaná sila, prameniaca zo spolupráce jednotlivých členov kolónie (obrázok 3).
Spoluprácu v kolónii im umožňuje dokonalá chemická komunikácia. Uvoľnenie zmesi
látok z rôznych častí tela vyvoláva medzi ostatnými členmi kolónie rôzne reakcie – brániť
sa i napadať nepriateľa, ošetrovať potomstvo, zháňať potravu a podobne.
5
Množstvo mravcov je úchvatné. Kdekoľvek sa oprieme o strom, mravec bude
pravdepodobne prvý, koho zbadáme. Na Zemi je zhruba 1018 jedincov hmyzu [6]. Z nich
približne až jedno percento tvoria mravce, čo je desať tisíc biliónov. Všetky mravce na
Zemi vážia spolu asi toľko ako všetci ľudia.
Mravce sú úplne nezávislé na faune a flóre. Ich celková adaptačná schopnosť voči
prostrediu nepozná hranice. Napríklad existujú druhy mravcov, adaptované na život
v podzemí, ktoré nikdy nevyjdú na zemský povrch. Vysoko nad nimi obývajú iné druhy
mravcov koruny stromov na najvyšších poschodiach lesa. Mravce sú predátori, hrobári i
obracači pôdy (obrátia jej viac ako dážďovky). Obývajú dažďové pralesy, trópy, púšte, ale
aj nehostinné oblasti za polárnym kruhom,.
Poznáme iba 13 500 druhov vysoko organizovaného sociálneho hmyzu. Z nich je
až 9 500 druhov mravcov, z celkového počtu 750 000 druhov hmyzu, ktoré sú momentálne
známe [6]. Ako je možné, že mravce a ďalší sociálny hmyz získali prevahu v
suchozemskom prostredí? Pravdepodobne to vyplýva z ich sociálnej povahy. V množstve
je sila – ak sú naprogramovaní tak, aby vzájomne spolupracovali. Toto konštatovanie sa
netýka len hmyzu. Sociálna organizácia je totiž jednou z najúspešnejších genetických
stratégií v celej histórií evolučného vývoja. Mravce sú najdokonalejšie vyvinutým
sociálnym hmyzom, ktorý vytvára najväčšiu a najzložitejšiu pospolitosť.
V procese vývoja získali túto vlastnosť kombináciou troch faktorov:
1) dospelí jedinci sa viac starajú o sestry, ako o vlastné potomstvo.
2) v jednom hniezde spolu žijú dve či viac generácií.
3) členovia každej kolónie sa delia na reprodukujúcu sa „kráľovskú“ kastu a na
nereprodukujúcu sa „robotnícku“ kastu.
Výhoda sociálneho hmyzu tkvie aj v tom, že keď plnia komplikovanejšiu úlohu
(starostlivosť o potomstvo) a napríklad jedna robotnica zahynie, alebo zabudne niečo
urobiť, tak jej sestra ju okamžite nahradí. Ak by na splnenie úlohy boli naprogramovaní len
jednotlivci, tak ich celkové úsilie by bolo neefektívne. Takisto keď mravce napadne
nepriateľ, tak v okamžiku sa z nich môžu stať chodiace kamikadze. Z hľadiska zachovania
kolónie strata jednotlivca, alebo skupiny, ešte neznamená jej zánik. Stratu totiž okamžite
nahradí nové potomstvo. V prípade bezprostredného ohrozenia kolónie (hniezda) si mravce
6
takisto delia svoje úlohy. Jedni bránia kolóniu pred útočníkom, iní evakuujú potomstvo do
bezpečia.
1.1
Život a smrť kolónie
Kráľovné sa v divočine dožívajú päť a viac rokov (najmenej sa dožívajú kráľovné malých
tropických mravcov – fazónov, len 3 mesiace) [6]. V laboratórnych podmienkach žijú
mravce priemerne dvadsať rokov. Svetový rekord medzi mravcami a tým aj v rámci
hmyzu vôbec, drží kráľovná druhu Lasius niger, európsky druh žijúci pozdĺž ciest a v
lesoch. V laboratórnom hniezde prežila až 29 rokov [6].
Kolónia je úplne oddaná svojej kráľovnej. Čo sa deje v mravenisku, keď kráľovná
zahynie? Bolo by prirodzené, že robotnice vychovajú ďalšiu kráľovnú. Tá by nahradila tú
mŕtvu. A naozaj smrť kráľovnej nemusí nevyhnutne znamenať zánik celej kolónie. I keď
niektoré druhy mravcov, spolu s prvou kráľovnou, zaniknú. Ich robotnice totiž nemajú
vaječníky, v dôsledku čoho reprodukčná sila kolónie po smrti kráľovnej – matky
exponenciálne klesá. Iné druhy mravcov však nakoniec nahradia mŕtvu kráľovnú. Pretože
niektoré z tých samičích vajíčok a lariev, ktoré sú doteraz živé sa môžu potenciálne
vyvinúť na kráľovné. Postačí im k tomu len správna výživa. Nová kráľovná však môže byť
aj obyčajná robotnica, alebo robotnice zachytia vlastnú mladú kráľovnú. Z hľadiska
kolónie je to správne rozhodnutie. Je výhodnejšie mať sestru, ktorá bude pokračovať ako
kráľovná. Bude sa starať o bratrancov a sesternice. Kolónia, počas hľadania svojej
kráľovnej, je vo väčšine prípadov neúspešná. Neustále sa zmenšuje až kým nezahynie
posledná, osirelá robotnica.
Robotnice mnohých druhov majú vaječníky a v období vymierania nakladú
neoplodnené vajíčka. Z týchto vajíčok sa vyliahnu samčeky. Keď je kolónia na pokraji
vyhynutia, signalizuje tento fakt práve prítomnosť veľkého počtu dospelých samčekov
a neprítomnosť dospelých, okrídlených kráľovien, či mladých robotníc.
Plodnosť kráľovien závisí od druhu. Môže to byť niekoľko stoviek dcér – robotníc
a tucet kráľovien a samčekov, alebo až tristo miliónov dcér, čo je viac než populácia žijúca
napríklad v USA [6]. Založenie novej kolónie nie je však jednoduché. Väčšina mladých
kráľovien sa totiž stáva veľmi ľahkou obeťou predátorov. Padá do vody, alebo zablúdi a
zahynie. Keď je kráľovná oplodnená odlamuje svoje suché blanité krídla a hľadá bezpečné
7
miesto, kde by si postavila hniezdo. Vonkajšie prostredie však neustále pracuje proti nej.
Pravdepodobnosť, že rýchlo postaví hniezdo a jeho hĺbenie dokončí skôr než ju odhalí
predátor, je veľmi malá. Len jednej z päťsto mladých kráľovien sa podarí založiť novú
kolóniu [6].
Na prvý pohľad sa javí nahradzovanie starej kráľovnej mladou ako dobrá voľba.
Prečo sa však všetky druhy mravcov nestali „nesmrteľnými“? Asi preto, že cena ktorú by
museli zaplatiť za nesmrteľnosť je privysoká. Touto cenou je totiž výmena génov medzi
príbuznými. To by neúmerne zvýšilo nebezpečenstvo smrti, sterilitu, ako aj zníženú
schopnosť adaptovania sa na zmeny okolia. A tak staré kolónie väčšiny mravčích druhov
vymierajú, aby mohli vzniknúť nové kolónie.
1.2
Komunikácia
Tak ako niektoré druhy zvierat značkujú svoje teritórium močom, tak aj africké mravce
(Oecphyla smaragdina) používajú svoje výlučky na označenie svojho územia. Používajú
päť rôznych „oznamov“ [6], ktorými značkujú svoju cestu k určitému cieľu (mimo
hniezda). Súčasne s nimi popisujú aj o aký cieľ ide. Každý oznam sa totiž skladá z
niekoľkých signálov. Základom je chemické látka, ktorá sa vždy, keď sa prieskumníčka
stretne v hniezde s družinou, kombinuje s pohybmi tela (tancom, dotykom tykadiel).
Chemickými látkami sú sekréty z jednej, respektíve z dvoch žliaz umiestnených v blízkosti
análneho otvoru, na poslednom článku tela.
Keď robotnica objaví potravu takisto značkuje cestu k hniezdu z rektálnych žliaz.
Keď sa stretne s ďalšími robotnicami kýva hlavou a dotkne sa ich svojimi tykadlami. Ak
ide o tekutú potravu, otvorí čeľuste a dá im ochutnať vzorku. Družky sa po rýchlej
ochutnávke rozbehnú po stope k novému zdroju potravy.
Ďalší druh mobilizujúcej správy odovzdáva úplne iné posolstvo. Keď robotnica
objaví na prieskume miesto, na ktorom by sa dalo postaviť nové hniezdo, takisto značkuje
cestu pomocou rektálnej žľazy. V tomto prípade však značkovanie kombinuje aj s
dotykovými signálmi, ktoré inej robotnici ukazujú, že je pripravená dotlačiť ju, alebo
preniesť k miestu pre nové hniezdo.
8
Tretí druh správy použije robotnica ak v blízkosti hniezda narazí na nepriateľa.
Okamžite vysiela poplašný signál – sekrétom z druhej rektálnej žľazy označí niekoľkými
kruhmi miesto okolo votrelca. V tomto prípade nedochádza k žiadnemu dotyku.
Zostávajúce dva mobilizujúce signály, ktoré používajú robotnice, sú rôzne
kombinované. Vedú ich družky k novému, doteraz neobsadenému územiu, alebo k
nepriateľovi na ktorého narazili ďalej od hniezda.
Africké mravce majú ešte iný poplašný systém, založený na viacerých feromónoch
s rôznym informačným obsahom. Keď sa robotnica stretne pri hniezde alebo na území
svojej kolónie s nepriateľom, uvoľní zo žliaz, ktoré sčasti vyplňujú hlavu a ústia na
vonkajšej strane kúsadiel, zmes štyroch chemických látok. Tieto látky sa šíria vzduchom
rozličnou rýchlosťou a ostatné robotnice ich jedna po druhej zachytávajú v rôznej
koncentrácií. Najprv k mravcom prenikne hexanol, aldehyd ich uvedie do stavu bdelosti.
Robotnice začnú intenzívne pohybovať tykadlami, aby zachytili ďalšie pachy. Potom
detegované množstvo hexanolu (ekvivalentného alkoholu) spôsobí medzi mravcami
poplach, takže behajú a hľadajú zdroj problému. Nasleduje undekanon, ktorý robotnice
privádza bližšie k zdroju a stimuluje ich k tomu, aby sa vrhli na cudzí objekt. A nakoniec,
najbližšie pri objekte, začne pôsobiť butyloktenol, ktorý zosilňuje nutkanie k ich
agresívnemu útoku na nepriateľa. Ako vidíme, mravce dokážu dokonale modulovať
intenzitu primárnych signálov, zložených z dotykov a zvuku.
Mravce vo všeobecnosti komunikujú pomocou feromónov, ale niektoré signály sú
vysielané aj iným spôsobom. Väčšina druhov jednoduché príkazy odovzdáva dotykom,
alebo postrkovaním. Pohyby sú jednoduché a priame. Robotnica môže vyvolať zvracanie
potravy napríklad tým, že natiahne predné nohy a dotkne sa jej hlavy v oblasti spodného
pysku. Väčšina mravcov komunikuje aj zvukom. Vydávajú vysoké, vŕzgajúce tóny.
Niektoré mravce takto volajú o pomoc, napríklad keď je nejaká robotnica zasypaná v
labyrinte podzemných ciest (často sa to stáva v období silných dažďov). Záchranári však
nereagujú na zvuk nesúci sa vzduchom. Vďaka veľmi citlivým detektorom na nohách
zachytávajú vibrácie šíriace sa zemou. Ak mravce nájdu niečo chutného, alebo potrebujú,
aby im s tým niekto pomohol, zaspievajú. V tomto prípade zvuk slúži ako podporný signál.
V žiadnom prípade však nie ako primárny signál. Zvukový signál sám o sebe nepriťahuje
ostatné robotnice, ale spôsobí, že rýchlejšie reagujú na bežné chemické, mobilizujúce
signály, ako aj na dotyk tela.
9
Mravce ovládajú 10 – 20 feromónových slov [6]. Ďalšie feromóny, ktoré produkuje
kráľovná, zabraňujú jej dcéram klásť vajíčka, alebo zabraňujú vývoju lariev svojej
kráľovskej sokyne. Iné feromóny, ktoré zrejme produkuje kasta vojakov, majú tiež
inhibičnú funkciu – znižujú percento lariev, z ktorých sa stanú vojaci. Nie je to však prejav
akéhosi sebeckého aktu, ale skôr ide o snahu zabezpečiť rovnováhu, stabilnú veľkosť
obranných síl.
Ako mravce vlastne hľadajú najkratšiu cestu od hniezda k potrave? Mravce pri
hľadaní jedla využívajú čuch, ktorým vnímajú feromóny. Keď hľadajú potravu, pohybujú
sa náhodne po okolí, preferujúc miesta s vyššou koncentráciou feromónu. Keď mravec
príde k zdroju potravy, vezme si z nej kúsok a po pachu sa presúva k hniezdu. Pri ceste
späť, do hniezda, zanecháva za sebou feromónovú stopu. Najprv je cesta úzka, nestabilná a
nemusí byť nevyhnutne najkratšia. Spočiatku nemusí byť vybudovaná len jedna cesta,
môže byť ich viacej. Mravcom trvá dlhšiu dobu kým prejdú dlhšie cesty vedúce od potravy
k hniezdu a preto feromónová stopa týchto ciest postupne slabne. Naopak, po kratších
cestách prejde v oveľa kratšom čase čoraz viac mravcov. Feromónová stopa týchto ciest
neustále silnie. Nakoniec vzniká jedna, jediná cesta po ktorej chodí väčšina mravcov – je to
tá najkratšia cesta.
1.3
Superogranizmus
Keď hovoríme, že kolónia mravcov, či iného sociálneho hmyzu, je niečo viac ako obyčajné
spojenie jednotlivcov. Týmto naznačujeme, že ide o superorganizmus a toto spoločenstvo v
bežnom zmysle slova detailne porovnávame s organizmom. Kolónia živočíchov je
skutočným organizmom a nie len jeho analógiou. Správa sa ako organizovaná jednotka.
Má určité vlastnosti – veľkosť, správanie sa, organizáciu – ktoré sú odovzdávané jednou
kolóniou či generáciou tej nasledujúcej. Rozmnožovacím orgánom je kráľovná, robotnice
tvoria mozog, srdce, črevá a ďalšie tkanivá. Vzájomné odovzdávanie tekutej potravy medzi
členmi kolónie zodpovedá obehu krvi a lymfy.
Veľkou výhodou mravcov je, že aj keď majú malý mozog, sú schopné vytvárať
pevné väzby a zložité sociálne usporiadania. Dosiahli to tým spôsobom, že reagujú na
obmedzený rozsah veľmi špecifických podnetov.
10
Organizačná štruktúra, ktorú vybudovali kolónie mravcov, vyvoláva opodstatnený
obdiv, ale základ ich sily – reťaz jednoduchých podnetov – je tiež zdrojom ich veľkej
slabosti. Mravce sa dajú totiž veľmi ľahko oklamať. Iné organizmy môžu ľahko rozlúštiť
ich kód a kopírovaním jedného či niekoľkých kľúčových signálov využívať vo svoj
prospech ich sociálnu väzbu. Sociálne paraziti, ktoré toto robia sa podobajú zlodejom, ktorí
sa potichu vkradnú do domu, potom, ako použili štyri či päť správnych čísiel, čím vypli
poplašný systém. Mravec totiž dokáže identifikovať člena svojej rodiny, alebo druha z
hniezda, len podľa pachu.
1.4
Centralizácia verzus decentralizácia
Pozorujeme veľa systémov a sami sa pritom stávame ich súčasťou. Ale nestačí len
pozorovať a zúčastniť sa. Ľudia pozorovali kŕdle vtákov tisíce rokov a nikto si pritom
nevšimol, že kŕdeľ v skutočnosti nemá vodcu. Tiež tí, ktorí uviaznu v dopravných
zápchach, bez pochopenia decentralizácie, nemôžu pochopiť skutočnú príčinu zápchy.
Takmer všade, kam sa pozrieme, nachádzame decentralizáciu.
Rovnako ako stúpa vplyv decentralizovaných myšlienok, vzrastá aj zakorenený
odpor k nim. Sú situácie, keď ľudia preferujú centralizovaný spôsob myslenia. Keď
pozorujeme svet (napríklad kŕdeľ vtákov), mylne predpokladáme, že kŕdeľ predstavuje typ
centralizovanej kontroly (vodca kŕdľa). Podľa toho, ako rozmýšľame, vytvárame vlastné
modely a teórie. Tie však existujú iba ak niekto (alebo niečo) ich vytvára a popíše. Jedným
z príkladov centralizovaného myslenia je aj to, že veľa ľudí stále trvá na tom, že niekto,
alebo niečo muselo stvoriť vesmír a s ním aj život.
Centralizované myslenie nie je vždy a priori zlé. Niektoré javy sú veľmi dobre
popísané centralizovanými teóriami. Niektoré spoločnosti, či systémy, majú svojich
vodcov. Keď sa pokúšame vytvoriť nové technológie a organizácie, centralizovanosť je
dobrá stratégia. Problém je však v tom, že ľudia sa až príliš často spoliehajú len na
centralizované stratégie. Decentralizovaný prístup je v podstate ignorovaný, podceňovaný
a prehliadaný.
11
Kapitola 2
Biologicky motivované oblasti informatiky
Algoritmus, ktorým mravce prehľadávajú terén je zo skupiny stochastických (skupina
prehľadávajúcich algoritmov), evolučných algoritmov. Zároveň však ide o heuristický
algoritmus.
Evolučné algoritmy, sú prehľadávacie algoritmy, ktoré sa snažia riešiť problém tak,
aby o ňom vedeli čo najmenej. Motiváciu si berú z genetiky a evolúcie. Ich veľká výhoda
tkvie v tom, že sú jednoduché. Vďaka čomu sa ľahko implementujú a používajú v praxi.
Sú jedným z najlepších nástrojov na hľadanie riešenia zložitých problémov (napr. z triedy
zložitosti NP).
Tento algoritmus je na báze multiagentového systému. Populáciu v tomto systéme
tvorí kolektív – kolónia (množina jednoduchých agentov). Systém je decentralizovaný
a samoorganizujúci. Populácia sa správa kolektívne, čo je dôsledok nepriamej formy
komunikácie (pomocou feromónu). Kolónia rieši úlohu, ktorá je ďaleko za hranicami
schopností jej členov.
12
2.1 Multiagentové systémy
Multiagentové systémy sú systémy v ktorých daná množina inteligentných agentov sa
snaží dosiahnuť určitý cieľ. Inteligencia v tomto kontexte znamená použitie algoritmov na
hľadanie, nájdenie a vyriešenie problému.
Obrázok 4: Multiagentový systém. (Zdroj: lucalongo.allrightsolutions.com)
Agenti v multiagentových systémoch sú autonómni. Žiadny z agentov sa nepozerá
na virtuálny svet globálne. Vnímajú ho len lokálne, pomocou svojich prostriedkov, ktoré
im boli pridelené. Agenti na jednej strane disponujú určitými prostriedkami, na druhej
strane sú „vsadení“ medzi určité hranice, v rámci ktorých musia daný problém vyriešiť. Ich
činnosť je decentralizovaná. Nemajú špeciálneho agenta, ktorý by ich navigoval. Ich
správanie je často samoorganizujúce (obrázok 4). Vďaka čomu sa snažia nájsť najlepšie
riešenie problému, ktorý riešia bez zásahu niečoho iného [2]. Agenti pracujú buď spoločne
na vyriešení problému, alebo pracujú samostatne na riešení navzájom súvisiacich
podproblémoch.
Multiagentové systémy sa používajú pri online obchodovaní, simulovaní
prírodných katastrof, data mining, modelovaní sociálnych štruktúr, v hrách, filmoch...
13
2.2 Ant computing
Ant computing je skupina algoritmov, ktorých predmetom sú modely odvodené na základe
pozorovaní mravcov v prírode. Rôzne aspekty sa stali inšpiráciami rozličných „mravčích
algoritmov“. Často sú používané ako
zdroj inšpirácie nových algoritmov.
Takýmito
príkladmi
potravy,
deľba
potomstva
sú:
hľadanie
práce,
triedenie
(brood
sorting),
či kooperácia pri prenášaní. V každom
z týchto
prípadov
mravce
spolupracujú pomocou stigmergií[5],
čo je forma nepriamej komunikácie,
využívajúca zmeny prostredia.
Obrázok 5: Mravčie algoritmy. (Zdroj: flickr.com)
Napríklad mravec označkuje cestu z mraveniska k potrave feromónom, čo spôsobí, že
ostatné mravce budú sledovať túto cestu. V ríši hmyzu nájdeme veľa príkladov správania
na úrovni kolónií, ktoré je možné popísať jednoduchými modelmi, založenými práve na
stigmergickej komunikácií. Inými slovami, stigmergia je vysvetlením ako dosahujú tieto
modely samoorganizáciu. Jedným z takýchto algoritmov je teda Ant Colony Optimization
algorithm (ACO) [5]. Jednou zo zaujímavostí tohto algoritmu je, že nijako v ňom
nevyužívame zrak (niektoré druhy mravcov, ktoré ho používajú sú úplne slepé). Z toho
dôvodu komunikácia prebieha trochu zvláštnym spôsobom. Na rozdiel od ľudí
(komunikujeme prevažne pomocou zraku a sluchu), mravce komunikujú medzi sebou a aj
s okolím prostredníctvom čuchu, a to pomocou chemikálií. Tieto chemikálie sa nazývajú
feromóny, ktoré vytvárajú feromónové cesty. Takýmto spôsobom spájajú mravenisko
s potravou, vďaka čomu aj ostatné mravce sa rýchlo dostanú k potrave objavenej ich
sestrami (obrázok 6). Toto správanie mravcov sa stalo vzorom pre ACO algoritmus.
14
Celý
algoritmus
postavený
je
totiž
na
princípe
samoorganizácie.
Feromón
používa ako nepriamu formu
komunikácie.
Mravce
vystupujúce
v tomto
algoritme, sa snažia nájsť
najkratšiu cestu z mraveniska
k potrave.
Potravu
hľadajú
tak, že sa rozlezú po okolí,
náhodne
hľadajúc
nejaký
zdroj potravy. V momente,
Obrázok 6: Na obrázku sú zachytené tri fázy hľadania najkratšej cesty
k potrave. V prvej fáze mravce preskúmavajú prostredie. V druhej fáze
zisťujú ktorá cesta je najkratšia. V tretej fáze prenášajú jedlo po
najkratšej ceste.(Zdroj:en.wikipedia.org)
keď nejaký mravec (presnejšie robotnica) nájde potravu, kúsok z nej odtrhne a prinesie ho
do hniezda. Počas návratu do hniezda označkuje cestu feromónom (v našej simulácií sú
tieto miesta zelené. Čím je koncentrácia feromónu väčšia, tým je farba svetlejšia).
Vzhľadom aj na to, ako iné mravce sledujú tieto feromónové stopy a vyberajú si tú
s najväčšou koncentráciou feromónu. Tento koridor na spiatočnej ceste čím ďalej tým viac
zosilňujú.
Feromónová
stopa
je
príkladom
usporiadanej
štruktúry
s veľkou
premenlivosťou. Je vytvorená na základe lokálnych interakcií medzi mravcami. Cesta trvá
dovtedy, pokiaľ sa zdroj jedla neminie. Keď je celá kopa jedla prenesená do mraveniska,
zelená cesta sa vyparí. Následne začnú mravce hľadať nový zdroj potravy.
2.2.1 ACO a problém obchodného cestujúceho
Problém obchodného cestujúceho pochádza z roku 1800, keď ho definovali W.R. Hamilton
a T. Kirkman. Bol podrobený mnohým štúdiám. Tento problém má dôležité postavenie
popri skúmaní ACO algoritmu. Samotný ACO algoritmus bol testovaný na probléme
obchodného cestujúceho. Jednak preto, že problém obchodného cestujúceho je NP-úplný
problém, ktorého optimalizácia by mala široké uplatnenie. Ale aj pretože sa chovanie ACO
15
algoritmu prenesie najľahšie na tento problém, nepotrebujeme žiadne zložité techniky na
jeho transformáciu.
Definícia problému obchodného cestujúceho: Obchodný cestujúci má postupne
navštíviť n miest, ale každé len raz. Na konci cesty sa má vrátiť do mesta, v ktorom bol na
začiatku. Nech je p daná hranica. Existuje okružná cesta, ktorej celková vzdialenosť by
bola menšia, alebo rovnajúca sa p? Presnejšie: Je daných n miest s1, s2, ..., sn a tabuľka
vzdialeností, ktorá obsahuje všetky vzdialenosti dij = „vzdialenosť z mesta si do mesta sj“
s1 je mesto v ktorom obchodný cestujúci svoju cestu začína. Existuje také usporiadanie si1,
si2, ..., sin miest s1, s2, ..., sn, i1=1, pri ktorom je súčet vzdialeností menší alebo sa rovná
danej hranici p t.j.:
Problém obchodného cestujúceho môžeme formulovať nielen ako problém
rozhodnuteľnosti (možná odpoveď je áno/nie), ale aj ako optimalizačný problém (vraciame
hodnotu – najkratšiu cestu). [3] Môžeme ho vysloviť nad grafmi: vtedy chceme navštíviť
každý vrchol (mesto) práve raz a vrátiť sa do počiatočného vrcholu s cieľom precestovať
pritom čo najkratšiu trasu (v zmysle ohodnotených hrán). Takto vyslovený problém je
ekvivalentný nájdeniu hamiltonovskej kružnice s minimálnym súčtom váh v kompletnom
ohodnotenom neorientovanom grafe. [8]
16
Kapitola 3
Zvolené technológie
Ako sme už v úvode spomínali, najprv budeme vytvárať model, simulujúci správanie
mravcov pri hľadaní najkratšej cesty od mraveniska k potrave. Potom ho otestujeme
v rôznych prostrediach. Od prostredia chceme, aby poznalo multiagentovú a paralelnú
paradigmu. K tejto požiadavke asi nie je čo dodať vzhľadom na, že vytvárame model na
multiagentovej báze. Vyžadujeme od prostredia, aby simulácia príliš nezaťažovala procesor
a pamäť, čiže simulácia má byť rýchla a plynulá. Veľkou výhodou prostredia by bola
multiplatformovosť.
Po
zosumarizovaní
našich
požiadaviek
sme
sa
rozhodli
naprogramovať aplikáciu ako applet v jazyku NetLogo.
3.1
NetLogo
Veľkou výhodou NetLoga je, že je to multiplatformové, multiagentové prostredie. Samotné
NetLogo je napísané v jazyku Java, model sa píše v jazyku Logo.
NetLogo vytvára svet, v ktorom medzi sebou interagujú agenti (obrazok 7).
Používa štyri typy agentov: turtles (korytnačky), patches (políčka), links (spojenia)
a observer (pozorovateľ). Korytnačky sa pohybujú v dvojrozmernom svete po políčkach.
Môžu byť spojené pomocou spojení. Pozorovateľ nie je umiestnený v tomto svete.
Pomocou neho môžeme so svetom „komunikovať“, alebo „pretvárať“. V každom modeli je
práve jeden pozorovateľ. Poloha korytnačiek a políčok je určená ich súradnicami. Poloha
spojenia je určená korytnačkami, medzi ktorými je dané spojenie. Agenti vedia zistiť stav
iných agentov (reagovanie na feromónovú stopu a jej nasledovanie...), požiadať ich
o vykonanie nejakej procedúry, alebo priamo s nimi pracovať (zvyšovanie/znižovanie
feromónu, difúzia...). Čas je chápaný krokovo (jedna procedúra vykonáva udalosti jedného
kroku). Je možné nastaviť rýchlosť plynutia času. Od najpomalšej, keď svet takmer stojí,
až po tú najrýchlejšiu, keď sa svet z dôvodu urýchlenia už takmer neprekresľuje.
Menšou nevýhodou je, že NetLogo neposkytuje žiadnu podporu pre debugging.
Treba si vystačiť s ladiacimi výpismi. Väčšou nevýhodou je nemožnosť oddeliť modelovú
17
a vizualizačnú vrstvu, keďže vzhľad sveta je súčasťou modelu. Spomínané nevýhody nám
nerobili problémy, preto sme sa rozhodli pre NetLogo. Veľkým plusom NetLoga je jeho
rýchlosť.
Obrázok 7: Ukážka rozhranie modelu vytoreného v NetLogu
3.1.1
Logo
Korytnačka v Logu môže v podstate reprezentovať ľubovoľný objekt z reálneho sveta
(mravca, auto v dopravnej zápche, protilátku v imunitnom systéme, či molekulu plynu).
K dispozícii máme tisíce korytnačiek.
Logo je paralelný programovací jazyk. To znamená, že všetky korytnačky
vykonávajú svoje úlohy súčasne. Čo je nevyhnutné, keď chceme sledovať správanie
kolónie. Logo je tiež procedurálny programovací jazyk. Každá procedúra musí mať určené,
ktorý typ agentov ju vykonáva (hovoríme to príkazom ask). Keď nestanovíme, kto ju má
vykonať, vykoná ju pozorovateľ. V prípade rozsiahlejších simulácií môžeme zaviesť breed
(rasy), vďaka čomu budú procedúry vykonávať jednotlivé rasy. Nedá sa však povedať, že
18
Logo je čisto procedurálny jazyk. Procedúry síce nie sú zapuzdrené v objektoch
(agentoch), ale dajú sa použiť pre akýkoľvek objekt (keď sú dostatočne všeobecné). Skôr
mám ponúka akúsi kombináciu procedurálneho a objektového programovania.
19
Kapitola 4
Model správania mravcov
Snažili sme sa vytvoriť model, ktorý hodnoverne popisuje dynamiku mravčej kolónie.
V modeli predpokladáme, že množstvo feromónu závisí len od množstva mravcov. Model
sa stará iba o difúziu a vyparovanie feromónu.
Obrázok 8: Ukážka nášho modelu. Čierny štvorec je plocha po ktorej sa pohybujú mravce. Mravce sú
znázornené ako červené trojuholníčky. Červená kružnica je mravenisko, modré kružnice sú zdroje potravy.
Oranžový obdĺžnik je prekážka. Môžeme pozorovať kruhový emergentný jav.
Prostredie, po ktorom sa pohybujú mravce, je štvorcová plocha. V prostredí sa
nachádzajú prekážky. Prekážky, tak ako aj okraje prostredia, sú nepriechodné. Prekážky sú
20
farebne odlíšené od prostredia. Na začiatku simulácie sa mravce vytvoria v strede tejto
plochy, s náhodnými vektormi otočenia. V tomto okamihu vzniká zaujímavý, emergentný
jav: v každom experimente vytvorili mravce, na krátku dobu, kružnicu (obrázok 8). Je to
spôsobené tým, že ich otočenia sú náhodné. Prostredie je ohraničené, horizontálne aj
vertikálne. Mravec je v ňom reprezentovaný agentom – v našom prípade korytnačkou.
Pohyb agentov je obmedzovaný iba prekážkami a krajnými hranami prostredia. Inak sa
môže agent pohybovať bez obmedzenia.
Mravce (agenti) sú v modeli graficky reprezentovaní ako trojuholníky. Samotné
prostredie má čiernu farbu. Nachádza sa v ňom okrem mravcov mravenisko, zdroje
potravy a prekážka. Mravenisko je zafarbené na červeno. Územie, na ktorom sa
nachádzajú zdroje potravy je červené. Plocha, ktorá reprezentuje prekážku je oranžová.
Mravce na prekážku nedokážu vyliezť (obrázok 8). Keď sa po prostredí pohybuje mravec
bez potravy, potom je zafarbený načerveno – prieskumníci sú červený. Ak nesie do hniezda
potravu, tak sa sfarbí namodro – mravce s potravou sú modré (obrázok 14).
Agent nemá žiadne globálne senzory o okolí. Svoje zmysly (čuch a hmat), ktorými
je vybavený, vie zistiť informácie o políčku, ktoré s ním bezprostredne susedí (políčko,
ktorého vzdialenosť od neho je jedna). Vzhľadom na to, že prostredie je dvojrozmerné,
agenti nevedie preskočiť prekážku, alebo na ňu vyliezť. Jediná možnosť, ako prekonať
prekážku, je vyhnúť sa jej. Agenti sa môžu otáčať o akýkoľvek uhol. V jednom kroku sú
schopný prejsť jedno políčko. Smer vektora rýchlosti je akýkoľvek, jeho veľkosť je však
konštantná – jedno políčko za jednotku času (tik). Agent pomocou čuchu dokáže sledovať
feromónové stopy. Feromón je látka, ktorú vylučuje agent. Každý agent má žľazy, ktorými
ho podľa potreby vylučuje. Feromón je tak, ako prekážky, farebne odlíšený od prostredia.
Agenti sa vedia pohybovať po políčkach označených feromónom.
21
Kapitola 5
Návrh a implementácie riešenia
Teraz sa budeme zaoberať realizáciou simulácie ACO algoritmu v modeli mravcov.
Ukážeme ako prebiehala analýza algoritmu cez návrh, až po jeho implementáciu.
5.1
Návrh riešenia
Je viacero spôsobov ako pristupovať k analýze problému. My sme sa rozhodli pre Agent
UML [1]. Agent UML je rozšírenie jazyka UML (Unified Modelling Language)
o možnosti modelovania v rámci agentovej paradigmy.
Obrázok 9: Agentové UML pre mravcov. Spodné diagramy venujúce sa hľadaniu potravy a návratu do
hniezda sú pre modifikovanú verziu ACO algoritmu.
22
Obrázok 10: Agentové UML pre patche.
Najprv sme vytvorili upravený triedny diagram (obrázok 9 a obrázok 10), ktorý
zachytáva stavy vyskytujúce sa v našom modeli. Týmto sme si ujasnili čo je potrebné
urobiť v jednotlivých stavoch a v ktorej metóde budeme zachytávať daný stav a správanie
v tomto stave.
Následne sme vytvorili sekvenčný diagram (obrázok 11) zachytávajúci vzájomné
pôsobenie jednotlivých objektov.
23
Obrázok 11: Sekvenčný diagram
Obrázok 12: Transformačný automat mravcov
24
Obrázok 13: Transformačný automat patchov
Pre prehľadnosť sme ešte vytvorili transformačné automaty agentov (obrázok 12 a obrázok
13). Robotnice zabezpečujú potravu, preto sa usilujú nájsť zdroj potravy. Vypomáhajú si
feromónovými cestičkami. Pritom sa vzájomne sa usmerňujú, vďaka čomu nájdu
najkratšiu cestu. Okolie (konkrétne jednotlivé patche) im ponúkajú aktuálnu „pachovú
situáciu“ a robotnice naopak ich aktualizujú. Vo svete je zabudovaná simulácia difúzie
feromónu a jeho následné odparovanie – vzájomná interakcia medzi patchmi.
25
5.2
Implementácia riešenia
Ďalej si popíšeme ako prebiehala samotná implementácia modelu. Riešenie začína mať
„hmatateľnú“ podobu a môžeme pozorovať prvé výsledky. Využívame dva typy agentov –
korytnačky (reprezentujúce mravčie robotnice) a políčka (reprezentujúce okolitý svet).
Tak, ako to vyplýva z návrhu riešenia.
Model má dve globálne stavové premenné: diffusion-rate a evaporation-rate. Obe
sú celočíselné, stavové premenné. Vzhľadom k nim prebieha difúzia feromónu, respektíve
jeho vyparovanie.
Veľmi dôležitým prvkom implementácie je správna inicializácia riešenia. Model
inicializujeme metódou setup. Najprv vyčistí prostredie. Inicializuje globálne, stavové
premenné diffusion-rate a evaporation-rate. Vytvorí korytnačky a zavolá metódy, ktoré
inicializujú políčka a korytnačky. Inicializácia políčok prebieha prostredníctvom metódy
setup-patches. Setup-patches inicializuje jej podliehajúce stavové premenné - feromon,
potrava, hniezdo, pachHniezda a stena. Zavolá nasledujúce „nastavujúce“ metódy: sethniezdo – určuje polohu hniezda, set-potrava – určuje počet zdrojov potráv a ich polohu
a set-stena – určuje polohu, tvar a počet prekážok v prostredí modelu. Nakoniec metóda
setup-patches zavolá metódu kresli, ktorá vykreslí stav prostredia po inicializácií. Turtlesetup zase inicializuje, tak ako jej meno napovedá, korytnačky/robotnice. Táto metóda
zabezpečuje iba počiatočnú inicializáciu stavových premenných agentov, nevolá žiadne iné
metódy. Konkrétne teda inicializuje nasledovné stavové premenné - nesie-jedlo, drop-size,
xcor a ycor (počiatočné súradnice), color (počiatočná farba agenta) a size (ich veľkosť).
5.2.1
Implementácia agentov - robotníc
Máme dve verzie algoritmu, čomu sme prispôsobili aj implementáciu. Najprv popíšeme
implementáciu pôvodného algoritmu mravčej kolónie a na konci uvedieme rozšírenia.
Robotniciam sme pridali dve stavové premenné: nesie-jedlo a drop-size. Nesiejedlo je boolovská stavová premenná, v ktorej si uchovávame informáciu o tom, či daný
agent/robotnica nesie jedlo. Druhou stavovou premennou drop-size korigujeme veľkosť
zložky, ktorou jedna robotnica prispieva k feromónovej ceste.
26
Hlavnou metódou, ktorá sa stará o celý beh modelu je metóda go. Podľa toho, či
robotnica nesie jedlo ju zafarbí (modré robotnice nesú jedlo, naopak červené nenesú jedlo).
Zavolá príslušnú metódu, ktorá zodpovedá momentálnemu stavu robotnice. Stará sa o beh
času a samozrejme má na starosti aj prostredie. To však vysvetlíme neskôr. Ako sme už
naznačili jej úlohou je rozlíšiť robotnice, ktoré nesú jedlo od tých ktoré ho nenesú. Modrá
robotnica, nesúca jedlo, sa má vrátiť do hniezda. Vtedy sa k slovu dostáva metóda navrat.
Má za úlohu vysvetliť robotnici, ako sa má vrátiť do hniezda. Nasmeruje ju na tú
najpriamejšiu cestu do hniezda – nasmeruje ju za pachom hniezda. Hovorí jej, že práve
teraz je ten správny čas zanechávať feromón. Týmto informuje ostatných mravcov, kde sa
nachádza potrava. Feromón ukladá s klesajúcim gradientom (ostatným mravcom stačí
vydať sa za políčkami s najväčšou intenzitou feromónu). Putovanie robotnice sa skončí
príchodom do hniezda (položí kúsok potravy, ktorý doniesla) a opäť sa vydáva na novú
cestu za potravou.
Tu by sme sa chceli na chvíľu pozastaviť, lebo toto je jedno z kľúčových miest
algoritmu. Teraz sa robotnica rozhodne pre smer, odkiaľ najviac zaváňa feromónom.
Robotnice sa začnú zameriavať na cesty ktorými prešlo viacero družiek. To znamená, že
kratšie cesty sa zvýhodnia a naopak tie dlhšie sa znevýhodnia. Takto nakoniec nájdu tú
najkratšiu – ideálnu cestu. Veď načo si život zbytočne komplikovať, v jednoduchosti je
krása. To, sofistikované správanie je zakomponované do metódy hladaj. Metóda hladaj sa
stará ešte o situáciu, keď mravec našiel zdroj potravy. To znamená, že robotnica zoberie
kúsok potravy (odčítame veľkosť kúsku zo zdroja potravy a stavová premenná nesie-jedlo
sa nastaví na true) a otočí sa o 180°. Robotnica sa otáča kvôli tomu, že týmto smerom leží
mravenisko.
Obe metódy hladaj aj navrat sa samozrejme starajú o pohyb robotnice, ako taký.
Keď sa robotnica nasmeruje, potom urobí krok. Predtým, ako urobí v danom smere krok,
je však potrebné skontrolovať, či pred robotnicou nie je stena. O toto sa stará metóda smer.
Metóda smer navyše znáhodňuje pohyb v prostredí.
Neskôr sme trochu upravili pôvodnú verziu algoritmu. Robotnice sa nevracajú
naspäť po pachu hniezda, ale po ceste ktorou už prešli. Pridali sme im novú stavovú
premennú cesta. Je to zoznam bodov, ktoré navštívila daná robotnica. Následne sme tomu
prispôsobili metódu hladaj. V nej si budeme pridávať navštívené body. Metóda navrat
simuluje absolvovanú cestu. Nevedie robotnicu za pachom feromónu. Inicializačná metóda
turtle-setup inicializuje stavovú premennú cesta ako prázdny zoznam.
27
5.2.2
Implementácia agentov – políčok
Políčka majú nasledujúce stavové premenné: feromon, potrava, hniezdo, pachHniezda
a stena. Feromon je celočíselná stavová premenná, ktorá nám hovorí, aká je intenzita
feromónu na danom políčku. Potrava je tiež celočíselná stavová premenná, v ktorej si
uchovávame počet kusov potravy na danom políčku. Hniezdo je boolovská stavová
premenná, v ktorej si uchovávame informáciu o tom, či dané políčko je súčasťou
mraveniska. PachHniezda je celočíselná stavová premenná, v ktorej si uchovávame
intenzitu pachu hniezda na danom políčku. Stena je boolovská stavová premenná, ktorá
hovorí o tom, či na danom políčku je prekážka/stena, alebo nie je.
Ako sme už spomenuli, metóda, ktorá obsluhuje celý model, je metóda go. Jednak
sa stará o robotnice, ale aj o políčka. Má na starosti difúziu feromónu na základe globálnej
stavovej premennej diffusion-rate. A vyparovanie feromónu, to sa deje na základe
globálnej premennej evaporation-rate.
Políčka sa v každom kroku prekresľujú. O prekresľovanie sa stará metóda kresli.
V nej postupným pýtaním (séria volaní if) vydedukujeme o aký typ políčka sa ide. Keď je
to políčko hniezda – zafarbíme ho na červeno. Keď sa jedná o políčko s potravovou –
zafarbíme ho na modro. Keď ide o políčko s prekážkou – zafarbíme ho na oranžovo. Keď
sa na danom políčku nachádza feromón, tak, v závislosti na jeho intenzite, zvolíme si
intenzitu zelenej farby.
28
Kapitola 6
Experimenty
6.1 Experiment 1. - viaceré zdroje potravy v rôznej vzdialenosti
od hniezda
Do prostredia (v ktorom neboli žiadne prekážky) sme dali dva zdroje potravy, každé v inej
vzdialenosti od hniezda. Výsledné správanie, na úrovni kolónie, bolo zaujímavé. Kolónia
začne prenášať zdroj jedla, ktorý je najbližšie k hniezdu (obrázok 14). Keď je tento zdroj
jedla prenesený celý, potom začnú prenášať druhý, vzdialenejší zdroj potravy. A takto
prenesú všetko jedlo nachádzajúce sa v okolí kolónie. Celý tento proces sa navonok javí,
akoby niekto z hniezda poznal okolie a navigoval ostatných kam majú ísť. Samozrejme
nikto takýto v hniezde nie je. Toto je len dôsledok distribuovaného poznávania okolia
mravcami.
Čo spôsobuje tento plánovaný útok na jedlo? Na vytvorenie stabilnej feromónovej
cesty potrebujeme určitý počet mravcov (testami sme zistili, že toto číslo závisí od
vzdialenosti najbližšieho zdroja jedla od hniezda; od rýchlosti vyparovania a difúzovania
feromónu; od typu prostredia a od toho, či sme použili modifikovaný alebo pôvodný ACO
algoritmus). Ak je mravcov málo, cesta sa vyparí a rozplynie sa po okolí rýchlejšie než ju
mravce stihnú obnovovať (v tomto prípade udržať).
Čím je jedlo vzdialenejšie od hniezda, tým viac mravcov potrebujeme na
vytvorenie stabilnej feromónovej stopy. Prečo je tomu tak? Absolvovanie cesty k
vzdialenejším zdrojom jedla zaberie mravcom oveľa viac času. To spôsobuje, že po tejto
feromónovej ceste prejde ten istý mravec menej krát, než po ceste, keď zdroj potravy je
bližšie. Dlhšia feromónová stopa bude menej krát obnovená, či zvýraznená. Takže na
vyváženie účinku difúzie a vyparovania potrebujeme oveľa viac mravcov. Zdroj potravy,
ktorý je najbližšie k mravenisku, bude ako prvý prenášaný z týchto dôvodov:
1. Je to najpravdepodobnejší prvý kandidát, na ktorého natrafia mravce pri
náhodnom potulovaní sa v prostredí.
2. Potrebuje minimálnu populáciu na vytvorenie stabilnej cesty. Preto tento blízky
zdroj bude s najväčšou pravdepodobnosťou uprednostnený.
29
Keď mravec začne prenášať potravu po stabilnej feromónovej ceste, je málo
pravdepodobné, žeby prestal po nej chodiť, kým všetko jedlo neprenesie. To znamená, že
cesta je dôsledkom cirkulácie (samozrejme počet mravcov musí byť stabilný, tak ako tomu
bolo v našej simulácií). Keď už je vytvorená stabilná cesta, prostredie ďalej prehľadáva už
len pár mravcov, ktorí sa často snažia konštruovať cesty k ďalším zdrojom potravy. Ako
sme však už naznačili, je veľmi malá pravdepodobnosť, žeby tieto málopočetné mravce
vytvorili stabilnú cestu, respektíve, aby sa vytvorilo viac stabilných ciest k rôznym
zdrojom potravy. Kolónia vždy vytvorila len jednu stabilnú cestu – najbližšiu cestu
k najbližšiemu zdroju potravy od hniezda. Robotnice postupne prenášajú do mraveniska
jeden zdroj jedla za druhým, v zdanlivo naplánovanom poradí, od najbližšieho k
najvzdialenejšiemu zdroju jedla.
Obrázok 14: Nakoniec experiment dopadol tak, že všetky mravce chodili po najkratšej ceste
30
6.2 Experiment 2. - viaceré zdroje potravy v rovnakej vzdialenosti
od hniezda
Čo sa však bude diať, keď dáme dva zdroje potravy, ktoré sú rovnako vzdialené od hniezda
(v ktorom nie sú žiadne prekážky)? Kolónia vytvorí slabé feromónové stopy k obom
zdrojom? Alebo si nevytvorí feromónovú cestu k žiadnemu z nich? Kolónia si
pravdepodobne medzi nimi vyberie a predbežne sa sústredí na jeden zo zdrojov potravy.
Náš program veľmi dobre simuloval aj toto správanie mravčej kolónie (obrázok
15). Spočiatku sa vytvorili slabé cestičky, približne rovnakej koncentrácie, ktoré viedli ku
každému zdroju potravy. Všetky rozdiely v koncentrácie feromónu na oboch cestách, ktoré
boli zapríčinené viac-menej náhodnými faktormi, sa časom zvýrazňovali. Od istého
Obrázok 15: Mravce si vytvorili feromónovú cestičku k obom zdrojom potravy. Ako vidíme jedna z nich
bola silnejšia.
31
okamihu však jedna cestička trochu zosilnela. A práve toto prilákalo ďalších mravcov
a bolo už veľmi nepravdepodobné, aby opustili túto cestu. Skôr bolo pravdepodobné, že
mravce putujúce po slabšej cestičke sa nakoniec rozhodli putovať po tejto silnejšej. Tento
jav sa neustále vyskytuje, keď nie je od počiatku jasné, ktorá cestička je tá ideálna –
najkratšia. Týmto správaním sa silnejšie cesty stávajú ešte silnejšími, cesty s menšou
koncentráciou feromónu postupne slabnú. Malé rozdiely sa zväčšujú a nakoniec vedú
k tomu, že jedna z ciest sa stane dominantnou (pre lepšiu viditeľnosť tohto správania, sme
zmenšili premennú diffusion-rate z pôvodnej hodnoty 10 na hodnotu 1).
Pri hľadaní potravy mravce vôbec nepotrebovali kráľovnú a súčasne dokázali nájsť
aj najkratšiu cestu. Ľudia veľmi často chápu „kráľovnú“ ako vojvodkyňu. Pre spoločenstvo
mravcov je však skôr matkou než vojvodkyňou. Čo dokazuje náš druhý experiment.
6.3 Experiment 3. - modifikácia ACO algoritmu
V tomto experimente nás zaujímalo, ako sa efektivita algoritmu zmení, keď sa mravce
pokúsia vydedukovať spiatočnú cestu na základe svojich predchádzajúcich skúseností.
Každý mravec si v tejto modifikácií pamätá cestu, ktorú prešiel. Ako neskôr uvidíme, táto
zmena dosť výrazne ovplyvní algoritmus. Predtým bolo prostredie nosičom dvoch typov
chemických správ. Jeden typ zabezpečoval nepriamu komunikáciu medzi mravcami –
jeden mravec označkuje kúsok prostredia a ďalší túto značku identifikuje. Druhý typ
pochádzal z hniezda. Celé prostredia bolo plné tohto signálu. Vďaka nemu boli mravce
schopné nájsť cestu k mravenisku. Ľudia si však často myslia, že mravce majú
sofistikovanejšiu pamäť, alebo že s hniezdom komunikujú inak, keď sa snažia prísť do
mraveniska. A tak sme sa rozhodli overiť toto tvrdenie.
Mravce počas experimentu nedokážu rozpoznať pach hniezda, ale majú
výbornú pamäť. V prostredí nie je žiadna prekážka. Intuitívne cítime, že toto by nemalo
zhoršiť situáciu. Opak je však pravdou. Potravu nájdu bez problémov, tak ako
v prechádzajúcich experimentoch. Nedokážu však rýchlo a efektívne určiť najkratšiu cestu
k najbližšiemu zdroju potravy (obrázok 16). Keď zistia, ktorý zdroj potravy je najbližšie,
cesta je široká. S týmto v podstate neurobili nič. Šírka cesty spôsobila, že informácia, kde
a akým spôsobom sa dá dostať k jedlu, bola nepresná. Mravce doslova blúdili po
robustných feromónových útvaroch.
32
Keď sme do však prostredia pridali prekážku, efektívnosť algoritmu rapídne klesla.
Kolónia v podstate nebola schopná rozoznať, ktorý je najbližší zdroj jedla. Triviálne
vylúčila najvzdialenejší zdroj. Čo však vôbec nebol uspokojivý výsledok.
Obrázok 16: Mravce určili správne, ktorý zdroj potravy je najbližší, ale nenašli minimálnu cestu. V tomto
experimente bola použitá modifikovaná verzia ACO algoritmu.
Prečo sa to celé pokazilo? Problémy robili zatúlané mravce. To boli mravce, ktoré
sa momentálne nezapojili do úlohy, respektíve hľadali ďalšie zdroje potravy. Často krát sa
stávalo, že prešli omnoho väčšiu cestu než bola tá minimálna. Nakoniec sa však predsa len
dostali k tomu najbližšiemu zdroju potravy. V tejto chvíli sa intenzívne usilovali odovzdať
informácie ostatným mravcom, ako sa k potrave dostali. Ich cesta bola však dlhšia. No
ostatné mravce to nevedeli a nasledovali ich. Tak sa vytvorilo veľa skupiniek, chodiacich
po rôznych cestách. Postupom času feromón difuzoval, šíril sa okolím. A tak nakoniec tieto
33
čiastočné cestičky postupne splynuli do jednej širokej cesty. Pokúsili sme sa zvýšiť
intenzitu vyparovania feromónu. Týmto sme zabránili vzniku jednej obrovskej cesty. No
v prostredí s týmito parametrami sa nevytvorila v podstate žiadna stabilná cesta.
Keď to zhrnieme a porovnáme s predchádzajúcim pokusom – zatúlané mravce tu
tvorili väčšinu, kým v prechádzajúcich experimentoch tvorili menšinu. Predtým vytvorili
maximálne slabú cestičku k vzdialenejšiemu zdroju potravy a ďalej skúmali okolie. Kým
väčšina mravcov sa sústredila na najbližší zdroj potravy, ktorú prenášala do mraveniska.
Nájdenie najkratšej cesty z mraveniska k potrave bola príliš ťažká úloha pre takto
modifikovaný algoritmus. Ale keď efektívne použijeme okolie, mravce nájdu hniezdo
pomocou jednoduchého pravidla a interakcie s prostredím.
34
Kapitola 7
Záver
Cieľom tejto bakalárskej práce bolo pochopenie algoritmu, ktorý mravenisko používa pri
hľadaní najkratšej cesty k potrave. Následne sme vytvorili model simulujúci toto
sofistikované správanie.
Pri tvorbe práce som sa stretol s niekoľkými ťažkosťami. Nefunkčnosť
novovytvoreného kódu bola z nich najzávažnejšia. Niekedy som chybne pochopil
dokumentáciu a tak došlo k nesprávnej implementácií. Rozmýšľať decentralizovane bolo
dosť náročné a pre mňa z istého pohľadu neprirodzené. Veľmi ťažko som rozlišoval
implementačné chyby od návrhových chýb. Čo dosť spomaľovalo implementáciu. Avšak
bolo fascinujúce sledovať ako sa model dokázal zorganizovať bez organizátora, čo bola aj
jedna z motivácii vedúca k dokončeniu bakalárskej práce.
Problematické bolo tiež testovanie modelu. Dôvodom bola absencia debuggera
v NetLogu. Preto som si musel vypomáhať rôznymi pomocnými výpismi a inými
metódami zachytenia chyby. Túto stránku NetLoga som na začiatku veľmi podcenil, čo sa
prejavilo behom implementácie. Realizácia samotnej simulácie sa ukázala počas
implementácie komplikovanejšia, ako som na začiatku predpokladal. Keď to zhrniem,
návrh bol približne rovnako náročný ako implementácia.
Vzájomné pôsobenie objektov, v modeli, na jednej úrovni umožnilo vzniknúť
novému správaniu. Správanie na nižšej úrovni bolo rozdielne od správania na vyššej
úrovni. Správanie celku sa javilo sofistikovanejšie a malo úplne iný charakter než
správanie jednotlivcov, ktorí tvorili celok. Správanie sa jednotlivcov – mravcov, bolo
triviálne, riadili sa jednoduchými pravidlami. Ale kolónia, ako celok, bola schopná
inteligentnejšieho správania. V žiadnom prípade však nebola jedným veľkým mravcom. Je
dôležité, aby sme si tieto pojmy neplietli. Často sa stáva, že individuálne správanie je
zamieňané za správanie skupiny a naopak.
V konečnom štádiu nám náhodnosť pomáhala k usporiadanosti. Čo je zaujímavé
konštatovanie, vzhľadom aj na to, že väčšina ľudí vníma náhodnosť ako deštruktívny jav.
35
Ako sme videli v tomto systéme náhodnosť, často protiklad usporiadanosti, viedla
nakoniec k usporiadanosti systému. Umožnila nám skúmať viac zdrojov jedla súčasne.
Súčasťou bakalárskej práce sú tri experimenty. V prvom experimente sme
pozorovali, ako sa náš model správa. V druhom experimente sme pozorovali jeho reakcie
na situáciu, keď zdroje potravy boli rovnako vzdialené od mraveniska. V treťom
experimente sme modifikovali ACO algoritmus a porovnávali sme ho s výsledkami
z predchádzajúcich dvoch experimentov. Všetky experimenty sa odohrávali rozdielnych
typoch prostredia. Prvé prostredie bolo prázdne, nachádzalo sa v ňom mravenisko a zdroje
potravy. Do druhého prostredia sme pridali prekážku.
Experiment
Výsledky
V oboch prostrediach sa model správal
1. Experiment
podľa očakávania. Pri prenose potravy do
mraveniska si mravce správne zvolili
najkratšiu cestu.
V oboch prostrediach model hodnoverne
2. Experiment
simuloval správanie svojich biologických
predlôh.
Modifikácia ACO algoritmu sa už v prvom
prostredí
3. Experiment
nesprávala
podľa
očakávania
(pozri obrázok 16). V druhom prostredí sa
správanie
modifikovaného
algoritmu
výrazne zhoršilo.
Naše experimenty ukázali, že mravce sú akosi heuristikou pri hľadaní najkratšej
cesty. Na základe jednoduchých pravidiel získajú mravce lokálne informácie. Vďaka týmto
informáciám, sú schopné nájsť najkratšiu cestu medzi dvoma rozdielnymi bodmi.
Aplikáciou tohto algoritmu vieme vytvoriť umelých mravcov, ktorí sa budú pohybovať po
grafoch. Tieto umelé mravce sú takisto schopné nájsť najkratšiu cestu medzi dvomi
vrcholmi, ktoré budú predstavovať mravenisko a zdroj potravy.
Experimentmi sme súčasne dokázali, že mravce, putujúce po najkratšej ceste, ju len
s malou pravdepodobnosťou opustia. Čo je dobrá vlastnosť za predpokladu, že prostredie
36
v ktorom sa pohybujú je statické. Ak by sa algoritmus ocitol v dynamickom prostredí,
v ktorom sa môže časom objaviť kratšia cesta, algoritmus by v tejto situácii nereagoval
správne. Mravce by neustále chodili po tej istej, avšak nie najkratšej ceste. Táto vlastnosť
nie je spôsobená chybným návrhom, ale je to emergentný jav ACO algoritmu ako takého.
Napriek všetkým problémom model, ktorý sme vytvorili, v princípe zachytáva
správanie sa mravčej kolónie, čím sme splnili vytýčený cieľ našej bakalárskej práce.
Nasledujúci vývoj tohto modelu môžeme zamerať napríklad na rozličné obohatenia ACO
algoritmu a ich porovnania s pôvodným ACO algoritmom. Tak, ako sme to demonštrovali
v experimente 3. Respektíve danú modifikáciu ACO algoritmu budeme testovať na
probléme obchodného cestujúceho.
37
Literatúra
[1] Bauer, B.: UML Class Diagrams: Revisited in the Context of AgentBased Systems. In: Agent-Oriented Software Engineering, 2001.
[2] Cao, L.: Data Mining and Multi-agent Integration, Springer, 2009. 328.
ISBN 978-1-4419-0521-5
[3] Claus, V., Schwill, A.: Lexikón informatiky, SPN Bratislava, 1991. 544.
ISBN 80-08-00755-9
[4] Dawkins, R.: The Selfish Gene, Oxford University Press, 1999. 368.
ISBN 978-0192860927.
[5] Dorigo, M. – Stützle,T.: Ant Colony Optimization, The MIT Press, 2004.
305. ISBN 0-262-04219-3.
[6] Hölldobler, B. - Wilson, E.O.: Cesta k mravencům. Academia Praha,
1997.198. ISBN 80-200-0612-5.
[7] Kubík, A.: Inteligentní agenty. Computer press Brno, 2004. 280. ISBN
80-251-0323-4.
[8] Kvasnička, V., Pospíchal, J.: Algebra a diskrétna matematika, STU
Press, Bratislava 2008. 493. ISBN 978-80-227-2934-5
[9] Návrat P., Bieliková M., Beňušková Ľ., Kapustík I., Unger M.: Umelá
inteligencia. Vydavateľstvo STU, 2002. 396. ISBN 80-227-1645-6.
[10] Resnick, M.: Turtles, termites, and traffic jams: explorations in
massively
parallel microworlds. Cambridge: Bradford Book, 1994. 163.
ISBN 0-262-68093-9.
[11] Wilensky, U. 1999. NetLogo. http://ccl.northwestern.edu/netlogo/.
Center
for
Connected
Learning
and
Computer-Based
Modelling,
Northwestern University. Evanston, IL.
38
Príloha A
A.1 CD so zdrojovými kódmi
Na CD sa nachádzajú zdrojové súbory vytvoreného modelu, videoukážky
z experimentov, inštalačné súbory NetLoga pre Windowsové a Unixové
systémy a pdf súbor bakalárskej práce.
39
Download

Algoritmický prístup k modelovaniu umelých mravcov