Vstup do lesa
Mravenčí stezky
Odkoukáno přírodě

Mravenčí stezky

Hmyz bez mapy, který učí počítače hledat cestu

✦ Potvrzeno

Žádný mravenec nezná mapu. Přesto celá kolonie najde nejkratší cestu k jídlu. Mladý Ital z tohoto triku udělal počítačový program.

Kdo: Jean-Louis Deneubourg, Marco Dorigo · Kdy: 1989–1992 · Kde: Brusel, Belgie a Milán, Itálie

Zobrazit ilustrovaný příběhfotografie, animace a pokusy, které si můžeš vyzkoušet sám

Příroda a vynález

Mravenci značí cestu vůní, feromonem. Po kratší stezce se mravenci vracejí rychleji, takže vůně houstne a přitahuje další. Delší cesta pomalu vyvětrává.

Mravenčí algoritmy, tedy programy, ve kterých virtuální mravenci hledají dobré trasy pro nákladní auta, plány výroby a provoz v počítačových sítích.

Příběh

Koncem 80. let dal belgický tým Jean-Louise Deneubourga argentinským mravencům úkol: z hnízda k potravě vedly dva mostky, krátký a dlouhý. Na začátku šli mravenci oběma cestami stejně.

Po několika minutách si téměř celá kolonie vybrala kratší mostek. Nikdo tomu nevelel. Stačilo, že se mravenci na kratší cestě vraceli rychleji a značili ji častěji.

Marco Dorigo, doktorand z Milánské polytechniky, usoudil, že to je hotový recept na obtížné matematické úlohy. V roce 1992 ve své disertaci popsal první mravenčí algoritmus: virtuální mravenci chodí po mapě měst, zanechávají digitální vůni a ta se vypařuje.

Dnes jsou mravenčí algoritmy jednou z rodin optimalizačních metod. Používají se k plánování doručovacích tras, přidělování úkolů a při výzkumu směrování v počítačových sítích.

Jak to funguje

  1. Vůně: Každý mravenec vracející se s potravou značí cestu. Další mravenci dávají přednost stezkám, které voní silněji.
  2. Posílení: Krátká cesta se překoná rychleji, takže za stejný čas dostane víc vůně. Dobrá trasa se sama posiluje.
  3. Vypařování: V programu vůně pomalu mizí. Díky tomu virtuální mravenci neuvíznou na první, náhodné trase a hledají dál lepší.

Ověř si sám

  1. Dvě cesty k cukru: V létě polož kapku medu do dvou různých vzdáleností od mravenčí stezky a přidej dvě tyčinky jako mostky: krátkou a dlouhou. Po čtvrt hodině spočítej mravence na každém mostku.
  2. Smaž stopu: Přetři prstem mravenčí stezku napříč na dlažební desce. Pozoruj, jak se mravenci na tom místě ztrácejí a hledají pach.
  3. Mravenci na papíře: Nakresli na papír pět měst a hledej nejkratší trasu přes všechna. Spočítej, kolik je možných tras. Při dvaceti městech jich je víc než zrnek písku na pláži.

Co se ví jistě

Pokusy s mostky popsali Goss, Aron, Deneubourg a Pasteels v roce 1989. Mravenčí algoritmus navrhl Marco Dorigo v roce 1992 a od té doby se hojně používá k přibližnému řešení úloh o trasách. Nedává vždy nejlepší výsledek, ale obvykle dobrý a rychle.

Zdroje