Prírodou inšpirované algoritmy

Správanie sa reálnych mravcov

Reálne mravce sú schopné nájsť najkratšiu cestu od zdroja potravy do hniezda (Beckers, Deneubourg and Goss, 1992; Goss, Aron, Deneubourg and Pasteels, 1989) bez použitia zraku (Hölldobler and Wilson, 1990). Taktiež sú schopné adaptovať sa zmenám v prostredí, napr. nájdenie novej najkratšej cesty v prípade, keď stará nie je viac použiteľná kvôli zataraseniu prekážkou (Beckers, Deneubourg and Goss, 1992; Goss, Aron, Deneubourg and Pasteels, 1989). Uvážme nasledujúcu situáciu, v ktorej mravce sa pohybujú po priamej línii spájajúcej zdroj potravy a hniezdo:

Je dobre známe, že hlavné prostriedky použité mravcami na formovanie a udržiavanie spojenia je feromónova stopa. Mravce pri svojom putovaní zanechávajú za sebou určité množstvo feromónov, a každý mravec uprednostňuje smer, ktorý je feromónovo voňavejší. Toto elementárne správanie reálnych mravcov môže vysvetliť, akým spôsobom môžu reálne mravce nájsť najkratšiu cestu, ktorá spojí líniu nečakane prerušenú prekážkou, ako to ukazuje nasledujúci obrázok:

Fakticky, akonáhle sa objaví prekážka, tie mravce, ktoré sú vo fronte pred prekážkou a nemôžu pokračovať v sledovaní feromónovej stopy, sa musia rozhodnúť pre otočenie vpravo alebo vľavo. V tejto situácii my môžeme očakávať, že polovica mravcov sa rozhodne pre otočenie vľavo a druhá polovica vpravo. Táto situácia môže nastať na obidvoch stranách prekážky.

Je dobré poznamenať, že tie mravce, ktoré si zvolili kratšiu cestu okolo prekážky, rýchlejšie zrekonštruujú novú cestu ako tie, ktoré si vybrali dlhšiu cestu. Teda, kratšia cesta získa vyššie množstvo feromónov za jednotku času a stane sa pre ostatné mravce voňavejšou. Vďaka tomuto pozitívne spätno-väzobnému (autokatalytickému) procesu sa prichádzajúce mravce ľahšie rozhodnú a to pre kratšiu cestu.

Najzaujímavejším aspektom tejto autokatalytického procesu je, že nájdenie najkratšej cesty okolo prekážky sa vyznačuje emergentnou vlastnosťou interakcie medzi tvarom prekážky a správaním mravcov. Všetky mravce sa pohybujú rovnakou rýchlosťou a feromón vylučujú v približne rovnakom pomere. To má za následok, že feromón sa bude rýchlejšie akumulovať na kratšej strane a táto cesta sa stane novou pri putovaní mravcov za potravou.