Įženk į mišką
Skruzdžių takai
Pasižiūrėta iš gamtos

Skruzdžių takai

Vabzdžiai be žemėlapio, kurie moko kompiuterius ieškoti kelio

✦ Patvirtinta

Nė viena skruzdė nežino žemėlapio. Vis dėlto visa kolonija suranda trumpiausią kelią iki maisto. Jaunas italas šį triuką pavertė kompiuterine programa.

Kas: Jean-Louis Deneubourg, Marco Dorigo · Kada: 1989–1992 · Kur: Briuselis, Belgija ir Milanas, Italija

Žiūrėti iliustruotą istorijąnuotraukos, animacijos ir bandymai, kuriuos gali atlikti pats

Gamta ir išradimas

Skruzdėlės žymi kelią kvapu, feromonu. Trumpesniu taku skruzdėlės grįžta greičiau, todėl kvapas tirštėja ir pritraukia vis daugiau kitų. Ilgesnis kelias pamažu išsivadina.

Skruzdėlių algoritmai, t. y. programos, kuriose virtualios skruzdėlės ieško gerų maršrutų sunkvežimiams, gamybos planams ir srautams kompiuterių tinkluose.

Pasakojimas

Devintojo dešimtmečio pabaigoje Jean-Louis Deneubourg belgų komanda skruzdėlėms argentininėms uždavė užduotį: nuo lizdo iki maisto vedė du tiltukai, trumpas ir ilgas. Iš pradžių skruzdėlės abiem keliais ėjo po lygiai.

Po kelių minučių beveik visa kolonija pasirinko trumpesnį tiltuką. Niekas jų nevadovavo. Pakako to, kad skruzdėlės trumpesniu keliu grįždavo greičiau ir dažniau jį pažymėdavo.

Marco Dorigo, Milano politechnikos doktorantas, nusprendė, kad tai paruoštas receptas sudėtingiems matematikos uždaviniams. 1992 m. savo daktaro disertacijoje jis aprašė pirmąjį skruzdėlių algoritmą: virtualios skruzdėlės vaikšto miestų žemėlapiu, palieka skaitmeninį kvapą, o kvapas garuoja.

Šiandien skruzdėlių algoritmai yra viena iš optimizavimo metodų šeimų. Jie naudojami pristatymo maršrutams planuoti, užduotims paskirstyti ir maršrutizavimo kompiuterių tinkluose tyrimams.

Kaip tai veikia

  1. Kvapas: Kiekviena skruzdėlė, grįžtanti su maistu, pažymi kelią. Kitos skruzdėlės renkasi takus, kurie kvepia stipriau.
  2. Sustiprinimas: Trumpas kelias įveikiamas greičiau, todėl per tą patį laiką gauna daugiau kvapo. Geras maršrutas pats save sustiprina.
  3. Garavimas: Programoje kvapas pamažu išnyksta. Dėl to virtualios skruzdėlės neužstringa pirmajame, atsitiktiniame maršrute ir toliau ieško geresnio.

Patikrink pats

  1. Du keliai prie cukraus: Vasarą padėk lašą medaus dviejuose skirtinguose atstumuose nuo skruzdžių takelio, su dviem pagaliukais kaip tiltukais: trumpu ir ilgu. Po ketvirčio valandos suskaičiuok skruzdėles ant kiekvieno tiltuko.
  2. Ištrink pėdsaką: Perbraukite pirštu skersai skruzdžių takelio ant šaligatvio plytelės. Žiūrėk, kaip skruzdėlės šioje vietoje pasimeta ir ieško kvapo.
  3. Skruzdėlės ant popieriaus: Nupiešk lape penkis miestus ir ieškok trumpiausio maršruto per visus. Suskaičiuok, kiek yra galimų maršrutų. Esant dvidešimčiai miestų jų yra daugiau nei smiltelių paplūdimyje.

Kas tikrai žinoma

Eksperimentus su tiltukais aprašė Goss, Aron, Deneubourg ir Pasteels 1989 metais. Skruzdžių algoritmą 1992 metais pasiūlė Marco Dorigo, ir nuo to laiko tai plačiai naudojamas metodas apytiksliai spręsti maršrutų uždavinius. Ne visada jis duoda geriausią rezultatą, bet dažniausiai gerą ir greitai.

Šaltiniai