Czego komputery mogą się nauczyć od mrówek?

http://thumbs.dreamstime.com/z/pustynnej-wyspy-kresk%C3%B3wki-ilustracja-40694126.jpg
Kolejny mój wpis odnoszący się do sztucznej inteligencji dotyczyć będzie wąskiej, ale owocnej dziedziny tak zwanych algorytmów mrówkowych. Żartobliwy rysunek sygnalizujący temat dzisiejszego wpisu nawiązuje do stale powtarzanego tu stwierdzenia, że poszczególne metody sztucznej inteligencji są jak wyspy archipelagu - każda z nich cechuje się odrębnymi właściwościami, ale nie łączą się one ze sobą i nie jest łatwe przejście od jednej grupy metod do innej.

Algorytmy mrówkowe należą do obszerniejszej dziedziny sztucznej inteligencji, tak zwanej "inteligencji roju" (swarm intelligence), w której tworzy się algorytmy komputerowe, naśladujące inteligentne zachowania rojów (rodzin) osobników, z których żaden nie posiada indywidualnej (własnej) inteligencji, ale których zbiorowość obserwowana jako całość - jest zdolna do inteligentnego działania. To inteligentne działanie zbiorowości uzyskiwane jest zwykle dzięki współdziałaniu osobników według bardzo prostych reguł. Odkrycie i mądre zastosowanie tych reguł w programach komputerowych pozwala na tworzenie narzędzi informatycznych zdolnych do inteligentnego działania przy zaangażowaniu niezbyt złożonych algorytmów i przy dość szybkim osiąganiu wymaganych celów. Omawiane tu algorytmy mrówkowe należą do najpopularniejszych narzędzi tego typu, chociaż nie są one jedyne - buduje się modele rodziny pszczelej, kopca termitów, ławicy ryb, klucza ptaków itp. Ale mrówki są tu szczególnie ciekawe.



Ludzie od dawna zauważyli, że pracę mrówek cechuje wysoka celowość działania całej zbiorowości. Ważnym przykładem tego są optymalnie wybierane szlaki komunikacyjne, którymi poruszają się mrówki .
Szlaki te zapewniają najwygodniejszy transport pożywienia od miejsca jego występowania do gniazda (mrowiska) i są bardzo zręcznie dostosowane do przeszkód terenowych. Czy to nie zadziwiające, jak mrówki potrafią wytyczyć taki optymalny szlak przy równoczesnym niezwykle niskim poziomie inteligencji pojedynczego owada?

Rozwiązaniem tej zagadki okazał się bardzo prosty mechanizm komunikacji między owadami. Każda mrówka poruszając się w terenie pozostawia na podłożu ślad zapachowy w postaci tak zwanego feromonu. Ślad ten bardzo szybko się ulatnia, więc jest wyczuwalny tylko wtedy, gdy daną drogą przeszło dużo mrówek - i to niedawno.

Na tej obserwacji oparte jest główne założenie algorytmu mrówkowego: Mrówka z większym prawdopodobieństwem wybierze tę drogę, po której niedawno przeszło wiele innych mrówek.
Ta prosta reguła wystarczy, żeby mrówki uformowały optymalną drogę nawet w skomplikowanym labiryncie. Popatrzmy na rysunek.
Gdy pojedyncza mrówka wracająca od znalezionego pożywienie F do mrowiska N napotka przeszkodę - to jest równie prawdopodobne, że ominie ją z prawej lub z lewej strony. Sytuacja taka przedstawiona jest na rysunku (a). Jeśli jednak od źródła pożywienia wracać będą dalsze mrówki, to te, które wybiorą krótszą drogę (na rysunku oznaczoną C) przejdą ją szybciej i ich ślad feromonowy będzie silniejszy (mniej zwietrzały) niż ślad tych mrówek, które wybrały drogę dłuższą (na rysunku oznaczoną H). W efekcie następne mrówki, które dotrą do rozwidlenia dróg, będą zdecydowanie częściej wybierały tę krótszą drogę. Sytuacja taka przedstawiona jest na rysunku (c). Co ciekawe i zabawne - tę teoretycznie rozważaną w podręcznikach sztucznej inteligencji sytuację udało się odtworzyć w eksperymencie z udziałem prawdziwych mrówek.
Algorytmy mrówkowe działające zgodnie z opisaną zasadą mogą służyć do poszukiwania najkrótszej drogi w skomplikowanym grafie. Na rysunku poniżej pokazano zrzut z ekranu podczas pracy jednego z wielu programów, które poprzez symulacje zachowania mrówek rozwiązują tego rodzaju problemy.
Poprzez znajdowanie takiej drogi w grafie można próbować rozwiązywać (pośrednio) wiele ważnych problemów związanych z wyborem optymalnej drogi postępowania, by wspomnieć tylko o słynnym "problemie komiwojażera".

I kto by pomyślał, że komputery będą się uczyć od mrówek?
Trwa ładowanie komentarzy...