Cześć, w tym świątecznym okresie mam dla Ciebie kolejny artykuł, a w nim algorytm mrówkowy, który będzie teoretycznym wprowadzeniem do mojego wrześniowego kursu Python 3 by MR, gdzie poruszę temat algorytmu mrówkowego w sposób praktyczny.

Na wstępie chcę Ci złożyć najserdeczniejsze życzenia z okazji Świąt Wielkiej Nocy! Temat świąteczny nie jest wcale czymś wyjątkowym. Oczywiście jak każdy algorytm, algorytm mrówkowy ma swoje uroki. Trafiłem na niego, gdy szukałem dodatkowych informacji na temat problemu komiwojażera.

Zapisałem go na swoją magiczną listę i właśnie dziś przyszedł czas, by przedstawić go szerzej publiczności. W tym artykule skupię się na następujących zagadnieniach:

  • Czym jest algorytm mrówkowy?
  • Jaka jest geneza nazwy?
  • Do czego można go wykorzystać?

Czas rozprawić się z powyższymi pytaniami. Zaczynamy!

Wprowadzenie

Nie będę ukrywał, że gdy usłyszałem o tym algorytmie i zagłębiłem się w jego działanie, byłem po prostu zaszokowany pomysłem. Nauka wielokrotnie brała pomysły z obserwacji przyrody i tym razem również tak było. 

Wyobraź sobie kolonię mrówek, które na początku losowo poruszają się po pewnym obszarze w poszukiwaniu jedzenia. Gdy takowe znajdą, wracają poinformować o tym swoją kolonię, przy okazji zostawiając za sobą zapach (feromony). Zjawisko to nazywa się stygmergia. Gdy inne mrówki z tej samej kolonii trafią na zapach poprzedniej mrówki, która już znalazła jedzenie, przestają poruszać się losowo i zaczynają podróżować w stronę jedzenia po linii wyznaczonej przez pierwotną mrówkę. Feromony z czasem ulatują i zaciera się ślad, dlatego pozostałe mrówki go wzmacniają, aż do momentu, gdy inna mrówka nie znajdzie krótszej ścieżki do jedzenia. Parowanie ma jedną super zaletę — pozwala dobrać optymalną ścieżkę. Gdyby nie było parowania, mrówki stwierdziłyby, że najkrótszą ścieżka jest tylko ta pierwotna. 

A tak następuje parowanie, zacierają się mniej uczęszczane ścieżki, przez co mrówki z pierwszych ścieżek przechodzą na kolejne, a pierwotne trasy zostaje z czasem zapomniane. Można to nazwać tak zwaną inteligencją zespołową. 

Piękne, prawda?

Stygmergia to pośredni sposób porozumiewania się poprzez zmiany środowiska

Przykładowa ilustracja

Zobaczmy przykładowe zachowanie dwóch mrówek. Po lewej stronie obrazka w ciemnym szarym prostokącie znajduje się kolonia, czerwona kropka to mrówka numer jeden, zielona kropka to mrówka numer dwa. Mają dwie alternatywne trasy, jedna jest dwa razy krótsza od drugiej. Punktem docelowym jest pożywienie, czyli szary prostokąt po prawej stronie.

W pierwszej iteracji czerwona mrówka idzie dłuższą drogą i dochodzi do pożywienia. Zielona natomiast dochodzi do pożywienia i wraca do kolonii. Już po pierwszej iteracji proporcje intensywności zapachów wynoszą 66 % do 33% na korzyść zielonej mrówki.

Druga iteracja to powtórka, czyli znów sytuacja, gdzie przewaga się nie uwidoczniła, mrówka czerwona wróciła do kolonii pierwszy raz. Mrówka zielona ma za sobą dwa cykle.

Iteracja numer trzy jest odmienna, następuje osłabienie zapachów na ścieżkach, zarówno czerwonej mrówki, jak jak i zielonej. Następuje tu zarysowanie przewagi mrówki zielonej i proporcje wyglądają teraz 75% do 25% na korzyść optymalnej ścieżki.

Czwarta iteracja to już przechylenie szali na korzyść krótszej trasy. Od tej pory dwie mrówki podążają tą samą, krótszą trasą, a dłuższa w kolejnej iteracji zostaje zapomniana. 

Ten prosty schemat obrazuję potęgę algorytmu. Ścieżek może być dużo więcej, tak samo jak mrówek. Wtedy to wygląda jeszcze bardziej atrakcyjnie, jednak na potrzeby tego artykułu jeden rysunek poglądowy wystarczy do zrozumienia idei.

Przykładowe zachowanie mrówek.
Rysunek 1. Przykładowe zachowanie mrówek.

Opis ogólny

Algorytm mrówkowy (inaczej nazywany ACO — Ant Colony Optimization) został zaproponowany na początku lat 90 przez włoskiego badacza Marco Dorigo. Podczas swojej pracy doktorskiej miał na celu poszukiwanie optymalnej ścieżki na wykresie, opartej na zachowaniu mrówek szukających drogi między kolonią a źródłem pożywienia

Sam algorytm, który wzoruje się na opisie przyrody zobrazowanym we wstępie, można przedstawić w następujący sposób.

Po pierwsze, optymalizacja następuje w sposób iteracyjny dzięki posiadaniu pewnej grupy „agentów”, którzy są odzwierciedleniem rzeczywistych mrówek. Każdy z agentów rozwiązuje zadanie w sposób unikalny, za pomocą losowych kroków, przy okazji zostawiając po sobie pewnego rodzaju ślad. Rozwiązane zadania są tutaj analogią drogi pomiędzy kolonią a jedzeniem. Następnie rozwiązanie to jest oceniane, a dalej nadawana jest mu waga, która jest odpowiednikiem intensywności zapachu (feromonów). Ocena bazuje na ocenie jakości, którą można przedstawić jako długość drogi — im krótsza droga, tym lepsza jakość rozwiązania zadania.

Warto powiedzieć jeszcze kilka słów na temat agentów. Przyjmuje się, że posiadają oni kilka cech:

  • Mają możliwość tworzenia nowych zadań w sposób losowy
  • Są prymitywni i indywidualnie zdolni do pojedynczych rzeczy
  • Posiadają idealny sposób oceny jakości

Jest to opis ogólny algorytmu, ale pokazuje już pewne zależności. Trzeba mieć na uwadze, że algorytm mrówkowy jest dość młodym algorytmem i są znane jego różne wersje, dodatkowo czasami są one przedstawiane w różnych kombinacjach z innymi algorytmami. Jeżeli ktoś orientuje się w algorytmice, to może skojarzyć losowość algorytmu mrówkowego z tą samą cechą w algorytmie zachłannym. Nie będę jednak rozpisywał tej kwestii w tym artykule, ponieważ planuję zrobić na temat algorytmu zachłannego osobny wpis. Ważne jest, by czytelnik zdawał sobie sprawę z powiązań tych dwóch algorytmów.

Opis szczegółowy

Czas przejść do bardziej szczegółowego opisu wraz z przykładem. Wyobraź sobie, że masz za zadanie zaplanować trasę dla samochodów dostawczych, tak by była ona optymalna. Problem ten szerzej znany jest jako problem komiwojażera.

Niech każde miasto będzie wierzchołkiem grafu takim jak poniżej. Nie jest to co prawda graf pełny, ale na potrzeby niniejszego przykładu będzie idealny do demonstracji. Przed rozpoczęciem działania algorytmu ustalmy pewne kwestie. Po pierwsze, każdy z wierzchołków grafu będzie miał na start przypisany identyczny poziom feromonów, zwany wagą. Jest to niezależne od długości krawędzi, czyli odcinka od jednego wierzchołka do drugiego. Po drugie, jedna iteracja będzie trwać do momentu, aż agent wróci do miejsca startu — w grafie poniżej zaczynamy grupą agentów od najbardziej na lewo wysuniętego wierzchołka i robimy pełną trasę na kilka sposobów, które reprezentują lekko pogrubione linie na drugim grafie. Na trzecim grafie widzimy koniec iteracji i optymalną trasę.

Inne grupy agentów zaczynają od innych wierzchołków i lecą swoją unikalną trasą. Następnie wyliczane są nowe wagi poszczególnych tras dla poszczególnych agentów za pomocą wzoru

w = 1/(1 + d1 + … + dn)

gdzie w, to nowa waga dla całej trasy, a zmienna d to długości poszczególnych tras od jednego miasta do drugiego. Ostatnim krokiem przed końcem iteracji jest obniżenie o pewien % wag wszystkich tras, symulując tym samym ulotność feromonów. Pozostaje raz jeszcze rozlosować grupy agentów i przypisać im nowe wierzchołki startowe i rozpocząć kolejną iterację algorytmu z nowymi parametrami wag.

 

Przykładowy graf z miastami w postaci punktów i najbardziej optymalną trasą.
Rysunek 2. Przykładowy graf z miastami w postaci punktów i optymalną trasą.

Podsumowanie

Jak widać, temat jest bardzo interesujący i wielu badaczy współczesnego świata skupia się na połączeniu świata przyrody ze światem technologii.

Jeżeli znasz podobne powiązania, to możesz zasugerować w komentarzu. Bardzo chętnie zapoznam się i przeanalizuję temat.

Chcę też wspomnieć, że celowo nie przedstawiam tu implementacji, ponieważ jest ona bardzo obszerna i same wyjaśnienia działania kodu to kilka długich akapitów. Zależało mi na przedstawieniu teorii, praktyka pojawi się we wrześniowym kursie Python 3 by MR, więc już teraz serdecznie zapraszam do śledzenia bloga i informacji!

Uciekam programować i już za tydzień wracam z kolejnym wpisem z serii Kurs Python 3 by MR.

Na koniec podrzucę Ci jeszcze książki na temat algorytmów, które są warte przeczytania!

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!


Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci e-booka z 10 omówionymi algorytmami pojawiającymi się w pytaniach podczas REKRUTACJI..

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 920 osób!.

Źródła

http://wsinf.edu.pl/assets/img/pdf/Zeszyty%20naukowe/vol.11%20nr%201/548.pdf
https://www.sciencedirect.com/topics/engineering/ant-colony-optimization
http://www.zio.iiar.pwr.wroc.pl/pea/w6_aco.pdf
http://edu.pjwstk.edu.pl/wyklady/nai/scb/wyklad9/w9.htm
https://app.assembla.com/wiki/show/easytsp/Algorytm_Mr%C3%B3wkowy
https://www.ii.uni.wroc.pl/~prz/2011lato/ah/opracowania/alg_mrow.pdf
https://www.ii.uni.wroc.pl/~prz/2011lato/ah/opracowania/alg_mrow.opr.pdf
https://repozytorium.biblos.pk.edu.pl/redo/resources/34273/file/suwFiles/SchiffK_ZastosowanieAlgorytmu.pdf
http://www.mini.pw.edu.pl/~mandziuk/2010-12-15.pdf
https://www.slideshare.net/yarpo/rwnolegy-algorytm-mrwkowy-3005224
https://repozytorium.ukw.edu.pl/bitstream/handle/item/3491/Miroslaw%20Modrzejewski%20Systemy%20mrowkowe%20w%20zastosowaniu%20do%20rozwiazania%20problemu%20komiwojazera.pdf?sequence=1&isAllowed=y
https://www.ii.pwr.edu.pl/~kwasnicka/tekstystudenckie/algorytmymrowkowe.pdf
https://achilles.tu.kielce.pl/portal/Members/332bd2d158a24964b2b98a7fc2879842/obliczenia-naturalne/wyklady/wyklad-9/wyklad_09.pdf
https://achilles.tu.kielce.pl/portal/Members/332bd2d158a24964b2b98a7fc2879842/obliczenia-naturalne/wyklady/wyklad-11/wyklad_11.pdf
http://www.cs.put.poznan.pl/mmachowiak/ok/CI_wyklad_ewoluc_4.pdf
https://www.researchgate.net/publication/279536734_Porownanie_algorytmu_mrowkowego_oraz_programowania_dynamicznego_do_wyznaczania_bezpiecznej_trajektorii_statku
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

9 komentarzy

  1. Fajny wpis. Dużo mnie nauczył, łatwy w zrozumieniu. Podejrzewam że implementacja będzie trudniejsza do zrozumienia. Ciekawi mnie to jakie jeszcze problemy rozwiązuje algorytm mrówkowy oprócz problemu komiwojażera?

    Przyznam że nie znam się za bardzo na data science oraz machine learning.

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.