Mrówki, śnieg i wiatr
Istnieje taka klasa algorytmów heurystycznych, którą określa się jako algorytmy mrówkowe. Generalnie wykorzystuje się je do wyszukiwania najkrótszych ścieżek w grafach. Idea ich działania opiera się na symulacji kolektywnego zachowania kolonii mrówek, które poszukują pożywienia.
Na początku mrówki błąkają się losowo, a gdy któraś pokarm znajdzie, wyrusza na poszukiwanie mrowiska, znacząc swoją trasę feromonem. Gdy już dotrze do domu, jej ślad zapachowy zaczyna przyciągać inne mrówki, które zaczynają również wykorzystywać tę drogę, a wracając nią już ze zdobyczą dodają własny ślad feromonowy – wzmacniając go w ten sposób. Jednak feromon nie ma absolutnej siły przyciągania i wiele mrówek nadal błąka się i znajdując pokarm wraca trasami innymi niż ta pierwsza albo zbacza z niej, nawet gdy nią początkowo pójdzie. Gdy oznakowanych jest więcej ścieżek, te dłuższe powoli popadają w zapomnienie. Dzieje się tak dlatego, że feromon jest substancją lotną i powoli wyparowuje, tracąc z upływem czasu atrakcyjność dla mrówek. Im dłuższa trasa, tym większe są średnio odstępy pomiędzy wędrującymi mrówkami i tym słabiej odświeżany jest jej ślad zapachowy, podczas gdy krótsze są mocno odświeżane i systematycznie zyskują na atrakcyjności w porównaniu z nimi. Żeby dostrzec ten efekt, wystarczy wyobrazić sobie trasę tak długą, że w momencie powrotu do gniazda pierwszej mrówki, jej ślad zapachowy w okolicy pokarmu już prawie całkowicie wyparował. Następna użytkowniczka drogi w okolicy pokarmu może pobłądzić, a wracając wybierze zapewne zupełnie inną trasę i nie wzmocni śladu na tej starej. Ten efekt jest tym silniejszy, im dłuższa jest droga do przebycia, ale występuje także dla krótkich ścieżek. Jego efektem jest to, że wędrowczynie generalnie preferują ścieżki krótsze.
Takie zachowanie mrówek można świetnie symulować za pomocą komputera, każąc wirtualnym mrówkom biegać po ścieżkach grafu i używać mechanizmu skopiowanego z przyrody do wyszukiwania w nim najkrótszych ścieżek, a po stosownych modyfikacjach rozwiązywać także inne, trudniejsze problemy obliczeniowe.
Pierwszy takie algorytmy opisał w swoim doktoracie Marco Dorigo z Włoch. Przypomniały mi się w sobotę, gdy wędrowałem z psem na nartach biegowych po łęgach na praskim brzegu Wisły. Bo ludzie w taką pogodę zachowują się jak mrówki. Brną w śniegu, przecierając drogę, ale w miarę upływu czasu wiatr ich ślady zawiewa. Jak ścieżka jest już solidnie zasypana, coraz mniej sensu ma trzymanie się jej i wędrowcy z niej zbaczają. Gdyby Dorigo był Polakiem (albo Eskimosem), pewnie te algorytmy nazywałyby się dziś algorytmami wędrowców w zadymce.
Jerzy Tyszkiewicz
Fot. Mesq, Flickr (CC SA)
Komentarze
Ja bym go nazwał „algorytmem wkurzonego na PGKiM”. Przez trzy dni opadów w ogóle nie odśnieżał chodników, a w taką pogodę mrówki, przepraszam, ludzie prawie wcale nie chodzili. Cały czas czułem się jak pionier.
Oby więcej takich artykułów, dziękuję i pozdrawiam.
Fantastyczny wpis. Czy istnieją inne przykłady inspiracji procesami biologicznymi przy konstrukcji algorytmów? Słyszałem coś o rozwiązywaniu problemu komiwojażera algorytmem naśladującym genetyczne sterowanie mnożeniem i specjalizacją komórek, ale nie znam szczegółów. Może Pan podac jakieś użyteczne linki?
Dziękuję i pozdrawiam,
Bardzo mi miło, że wpis się spodobał. W takim razie przygotuję dalsze teksty na podobne tematy i w nie powsadzam linki.
@Art63
Jest całkiem pokaźna ilość algorytmów wzorowanych na działaniu biologicznych form.
Do rozwoju komórek są to algorytmy genetyczne(ewolucyjne) , gdzie odwzorowane są mechanizmy ewolucji do szukania optimów.
Algorytm mrówczy też można częściowo zaliczyć, gdyż też opiera się na działaniu populacji.
Sieci neuronowe zaś są powstały na podstawie analizy działania ludzkiego mózgu.
Każda z wymienionych gałęzi jest bardzo rozwinięta i wziąż się zmienia, czasem jak w przypadku sieci neuronowych algorytmy wyszły już poza odzworowania biologiczne ,tak jak samoloty już nie naśladują skrzydeł ptaków.
@lenrock,
Dziękuję, pogoogluję w tym kierunku:)