Prírodou inšpirované algoritmy

Kolektívne správanie

Ak chceme popisovať kolektívne správanie, tak si vytvoríme viac mravcov toho istého druhu, t.j. budú mať rovnaký pravidlový reťazec. Mravce sa vyvíjajú nezávisle na sebe, a keď sa dva mravce náhodou zrazia, tak sa budú ignorovať. Akokoľvek, mravce vzájomne vplývajú na svoje správanie prostredníctvom stôp, ktoré po sebe zanechali, pretože tým sa mení stav jednotlivých buniek mriežky, ktoré dynamicky menia prostredie mravcov. Takýto dynamický vývoj mravčieho jedinca implicitne závisí na histórii všetkých ostatých mravcov a udáva vzostup vo všeobecnosti nepredvídateľnej kolektívnej dynamiky.

Dva Langtonove mravce

C.Langton v krátkosti popísal správanie sa systému s dvoma mravcami. Ak by sme otestovali niekoľko konfigurácií, tak by sme mohli pozorovať dve typické správania: periodické interakcie a chaotický vývoj. Keď systém obsahuje periodický atraktor, obrazce sa začnú opakovať s nejakou konštantnou periódou. Na druhej strane, chaotické vývoj dáva vzostup spletitým štruktúram, ktoré vypĺňajú celý dostupný priestor, za podmienky, že im je daný dostatočný časový interval a v ktorých vznikajú nepravidelné priestorovo-časové obrazce. Treba poznamenať, že v týchto simuláciach sa uvažuje mriežkový priestor s cyklickými hraničnými podmienkami, t.j. mriežkou na toroidnej ploche.

Ak vykonáme nasledujúci pokus, zistíme, že konfigurácia sa rozvinie na zaujímavé správanie dvoch mravcov. Teda, na toroidnú mriežku 500x500 umiestnime na pozícii X=200, Y=250 prvého mravca, nasmerujúc ho pritom na juh. Druhého mravca umiestnime rovnakom riadku na X=300, Y=250, so smerovaním na východ. Mravce sú typu 10. Potom je možné pozorovať nasledujúce štádiá v správaní sa tohto systému:

1. Individuálny vývoj: v tejto fáze obidva mravce zanechávajú cestičky nezávislé na sebe a po 10 000 krokoch začnú stavať oddelené diaľnice.

2. Stretnutie: jeden z mravcov stretne diaľnicu druhého a "ide" pozdĺž nej kým nestretne druhého mravca, ktorý je práve zaneprázdnený výstavbou svojej diaľnice. V tomto okamihu sa správanie systému stáva opäť zložité.

3. Ústup: po niekoľkonásobnom stretnutí, mravce od seba odpútajú svoje diaľnice a vrátia sa späť do svojich štartovacích pozícií. Počas tejto fázy, mravec ktorý ide po diaľnici a stretne svojho spoločníka, zmaže jeho cestu takým spôsobom, že druhý mravec nájde svoju vlastnú diaľnicu v rovnakom stave ako bola, keď ju postavil.

Obrázok ukazuje fázu konštrukcie.

Keď sa jeden z dvoch mravcov znovu ocitne v štartovacom bode, tak pokračuje v lození vytváraním diaľnice, ale obrazec je zrotovaný o 180 stupňov vzhľadom k počiatku, pretože mravce sa vracajú k štartovacím bodom so zmenenými smerovaniami. Normálne sa ich stopy nestretnú, pretože začnú divergovať. Avšak, práve vďaka toroidnej mriežke sa opäť ocitnú v rovnakých fázach 1-3. Na konci tohto druhého cyklu sa mravce znovu nájdu v rovnakej pozícii a s rovnakou orientáciou ako v kroku 0. Od tohto okamžiku sa systém vyvíja periodicky prechádzajúc cez rovnaké stavy. Obrazcová perióda je takto jeden kompletný cyklus, kde skutočná perióda sú dva obrazcové cykly. Preto sa toto správanie javí protikladné ku Kong-Cohenovmu teorému, pretože trajektória ostane ohraničená v prípade periodického multi-mravcového systému.

Ak urobíme množstvo pokusov s dvoma mravcami inicializovanými na rovnakom riadku, tak môžeme ako všeobecné pravidlo pozorovať, že ak smerovanie mravcov je na počiatku posunuté o 90 stupňov a rozdiel ich X-ových súradníc je párny, potom iterácia bude periodická, inak, ak rozdiel je nepárny, tak správanie je chaotické. Ak mravce sú umiestnené blízko seba, tak sa môžu stretnúť skôr ako začnú stavať diaľnicu. Avšak, ak táto separácia je párna , systém bude vykazovať periodické správanie, ale bez výstavby diaľnic. Keď sa mravčí pár začne správať chaoticky, tak nevznikajú diaľnice v správaní na časti jedného z mravcov. Namiesto toho, mravec ide po diaľnici nerušene, zanechávajúc za sebou komplikované značky na ceste.

Štyri Langtove mravce

Možno tiež robiť pokusy so štyrmi Langtonovými mravcami. Teraz sa tu popíše len jeden z nich, ktorého počiatočné podmienky dávajú priestor zaujímavému vývoju periodického obrazca. Našich mravcov zinicializujeme v miestach s následujúcimi súradnicami a nasmerovaním: mravec1, X=200, Y=200, juh; mravec2, X=300, Y=200, východ; mravec3, X=200, Y=300, západ; mravec4, X=300, Y=300, sever.

Obrázok nad ukazuje fázu periódy, ktorá sa zjaví po 28000 prejdených krokoch. Krása celej simulácie viac vynikne, keď ju budeme sledovať v behu, ako keď si pozrieme iba nehybný obrázok.

Na vytváranie periodických obrazcov je nutné splniť nasledujúce podmienky. Po prvé, pozície mravcov sú obnovované sekvenčne, jeden po druhom, tak ako je to popísané vyššie. Po druhé, v takom istom poradí sú obsadzované a preznačkované i bunky mriežky. Pokusmi sa zistilo, že ak budeme obnovovať mravce v poradí mravec1-mravec2-mravec3-mravec4, tak nevzniknú periodické obrazce. Ich správanie je prechodne kvázi-periodické a nakoniec sa začnú vytvárať neštruktúrované obrazce.

Fakticky, všetky možné kombinácie poradia mravcov dávajú neperiodické obrazce, okrem dvoch prípadov, pri ktorých sa postupuje križovaním, ako to znázorňuje nasledujúci obrázok.

Tí, ktorých toto vskutku zaujímavé správanie vantov zaujalo a chcú si urobiť pokus samostatne nájdu nejaké simulátori tu.