Vstúp do lesa
Mravčie chodníčky
Odpozorované v prírode

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

Pozri si ilustrovaný príbehfotografie, animácie a pokusy, ktoré si môžeš urobiť sám

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

  1. Vôňa: Každá mravca vracajúca sa s potravou značí cestu. Ďalšie mravce uprednostňujú chodníky, ktoré voňajú silnejšie.
  2. Posilnenie: Krátka cesta sa prejde rýchlejšie, takže v rovnakom čase dostane viac vône. Dobrá trasa sa sama posilňuje.
  3. 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

  1. 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.
  2. 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.
  3. 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.

Zdroje