
Mravčie chodníčky
Hmyz bez mapy, ktorý učí počítače hľadať cestu
✦ Potvrdené
Žiadny mravec nepozná mapu. Napriek tomu celá kolónia nájde najkratšiu cestu k jedlu. Mladý Talian premenil tento trik na počítačový program.
Kto: Jean-Louis Deneubourg, Marco Dorigo · Kedy: 1989–1992 · Kde: Brusel, Belgicko a Miláno, Taliansko
Príroda a vynález
Mravce značia cestu vôňou, feromónom. Po kratšej ceste sa mravce vracajú rýchlejšie, takže vôňa zhustne a pritiahne ďalšie. Dlhšia cesta sa pomaly vyvetrá.
Mravčie algoritmy, teda programy, v ktorých virtuálne mravce hľadajú dobré trasy pre nákladiaky, plány výroby a prevádzku v počítačových sieťach.
Príbeh
Koncom 80. rokov postavil belgický tím Jeana-Louisa Deneubourga pred argentínske mravce úlohu: z hniezda k potrave viedli dva mostíky, krátky a dlhý. Spočiatku išli mravce oboma cestami rovnomerne.
Po niekoľkých minútach si takmer celá kolónia vybrala kratší mostík. Nikto to nerozkazoval. Stačilo, že mravce na kratšej ceste sa vracali rýchlejšie a častejšie ju značili.
Marco Dorigo, doktorand z Miláneskej polytechniky, usúdil, že to je hotový recept na ťažké matematické úlohy. V roku 1992 opísal vo svojej dizertácii prvý mravčí algoritmus: virtuálne mravce chodia po mape miest, zanechávajú digitálnu vôňu a tá sa vyparuje.
Dnes sú mravčie algoritmy jednou z rodín optimalizačných metód. Používajú sa na plánovanie trás dodávok, rozdeľovanie úloh a výskum smerovania v počítačových sieťach.
Ako to funguje
- Vôňa: Každá mravca vracajúca sa s potravou značí cestu. Ďalšie mravce uprednostňujú chodníky, ktoré voňajú silnejšie.
- Posilnenie: Krátka cesta sa prejde rýchlejšie, takže v rovnakom čase dostane viac vône. Dobrá trasa sa sama posilňuje.
- Vyparovanie: V programe vôňa pomaly mizne. Vďaka tomu virtuálne mravce neuviaznu na prvej, náhodnej trase a hľadajú ďalej lepšiu.
Over si sám
- Dve cesty k cukru: V lete polož kvapku medu v dvoch vzdialenostiach od mravčieho chodníka, s dvoma paličkami ako mostíkmi: krátkym a dlhým. Po štvrťhodine spočítaj mravce na každom mostíku.
- Zmaž stopu: Prejdi prstom naprieč mravčím chodníčkom na chodníkovej dlaždici. Pozoruj, ako sa mravce na tom mieste strácajú a hľadajú pach.
- Mravce na papieri: Nakresli päť miest na kus papiera a hľadaj najkratšiu trasu cez všetky. Spočítaj, koľko je možných trás. Pri dvadsiatich mestách ich je viac než zrniek piesku na pláži.
Čo je isté
Pokusy s mostíkmi opísali Goss, Aron, Deneubourg a Pasteels v roku 1989. Mravčí algoritmus navrhol Marco Dorigo v roku 1992 a odvtedy je to široko používaná metóda približného riešenia úloh o trasách. Nie vždy dá najlepší výsledok, ale zvyčajne dobrý a rýchlo.