Prírodou inšpirované algoritmy

Stigmergia

Základná myšlienka stigmergie (Grass, 1959) je, že pre koordinovanie práce skupiny nie sú potrebné žiadne priame interakcie, ale že interakcií medzi hniezdom a robotníkmi je dostatok práve vďaka značkám vytvorených robotníkmi. Robotníci, napr. termity, modifikujú svoje prostredie tým, že mu dodávajú dostatočné stimuly, napr. vo feromónovej podobe. Nové stimuly vytvárajú zase nové odpovede vo forme správania sa, ktoré v ich bezprostrednom okolí opäť modifikuje prostredie. S týmto poradím akcií a reakcií, je spoločnosť schopná produkovať rôzne štruktúry (výstavba hniezda termitov a pod.). Je to práca, ktorá predpokladá koordináciu aktivít robotníkov.

Termity v nasledujúcich úvahách budú používať určité stigmergické mechanizmy. Termity sa pohybujú v hniezde náhodne a v každom časovom kroku je každý termit charakterizovaný pravdepodobnosťou kopania a vyberania čiastočiek zeminy. Model predpokladá, že keď termity vyťahujú pôdne čiastočky, označia najbližšie okolie feromónom a tiež cestu k nemu, a tak pravdepodobnosť kopania v jednom mieste rastie. Tieto chemické značky podnecujú členov hniezda kopať (pravdepodobnosť kopania rastie) na rovnakom mieste alebo v jeho najbližšom okolí.

Tak je pravdepodobnosť kopania podmienená jedine miestnymi podmienkami. Na nasledujúcom obrázku je znázornené ako aktivita kopania na jedného termita rastie spolu s rastom celkového počtu termitov.

Regulácia veľkosti hniezda

V prírodných systémoch, ako populácia hniezda rastie, tak sa aktivita kopania zvyšuje a tým sa veľkosť hniezda prispôsobuje veľkosti populácie. Algoritmus obsahujúci stigmergické princípy umožňuje práve takúto efektívnu reguláciu a pritom neobsahuje žiadne presné inštrukcie, kedy má hmyz kopať (alebo nekopať). Tieto stigmergické princípy môžu vytvárať rôzne dynamiky rastu hniezda.

Popíšeme tu len dva extrémne prípady. Prvý a značne intuitívny je spojitý priebeh aktivity kopania, ktorý produkuje spojitý nárast vo veľkosti hniezda. Druhý extrém súvisí s pulzujúcim rastom veľkosti hniezda: krátke periódy vysokej kopáčskej aktivity sú striedané s dlhými periódami nedbalého kopania. Toto správanie je napokon ľahké na pochopenie. Pri nízkej hustote je intenzita kopania slabá. Ako populácia narastá, rastie s ňou aj hustota termitov (a teda aj vylučovanie feromónov), čo napokon vyprodukuje vyššiu úroveň aktivity kopania. Táto aktivita náhle rozšíri veľkosť hniezda, ale počas tejto periódy sa veľkosť populácie nezmení. Následok toho je, že hustota termitov klesne a kopačská aktivita bude slabá dovtedy, kým hustota termitov nebude opäť vyššia. Tak bez presného naprogramovanie vzťahu medzi veľkosťou hniezda a populácie kolónie, dostaneme reguláciu, ktorá je výsledkom použitia jednoduchých pravidiel.

Výber jedného staveniska

Hniezdo môže byť obkolesené rôznorodým materiálom: napr. niektoré časti sa vykopávajú ľahšie, iné zase ťažšie. Tento model jednoducho predpokladá, že termity vylúčia feromón len vtedy, ak sa im podarí vykopať čiastočku. A keďže je vyššia pravdepodobnosť, že termitom sa podarí skôr odštiepiť mäkšiu čiastočku než tvrdú, feromónových značiek súvisiacich s mäkkým materiálom bude viac. Výsledné rozhodnutie, ktoré je funkciou veľkosti kolónie (napr. skupina v porovnaní so samotársky žijúcim jedincom) bude, že skupina sa dokáže skoncentrovať svoju aktivitu na mäkšie časti a nevšímať si tvrdé. Túto možnosť samotársky žijúci jedinec nemá.

Tieto príklady ukazujú silu jednoduchých pravidiel a ich prejavy ako sú: regulácia, výber vhodného miesta, a namáhavosť práce pre samotársky a spoločensky žijúceho živočícha.