Algorytm mrówkowy

By | 1 lutego 2014

Algorytm mrówkowy zaproponowany przez Marco Dorigo, jest probabilistyczną techniką rozwiązywania problemów poprzez szukanie optymalnych dróg w grafach. Jest on zainspirowany zachowaniem mrówek szukających pożywienia dla swojej kolonii.

Jak działa algorytm mrówkowy
Mrówki poruszają się w sposób losowy, ale gdy znajdą pożywienie, wracają do swojej kolonii pozostawiając ślad składający się z feromonów. Gdy inna mrówka natknie się na ten ślad, przestaje poruszać się w sposób losowy i podąża za śladem w kierunku pożywienia.

Jednak po pewnym czasie feromony wyparowują, a więc siła ich działania maleje. Im dłuższa jest trasa od pożywienia do kolonii, tym większa jest szansa że zapach w postaci feromonu wyparuje. Krótsze trasy zapewniają, iż siła działania feromonów będzie większa. Parowanie feromonów jest efektem pozytywnym, bowiem pozwala to na odnajdywanie optymalnej trasy do pożywienia. Gdyby feromony nie wyparowywały, każda kolejna trasa miałaby taką samą siłę jak poprzednia, przez co nie dochodziłoby do odnalezienia optymalnego rozwiązania problemu.

Porównanie dla mrówek wyczuwających feromon i nie wyczuwających

Porównanie dla mrówek wyczuwających feromon i nie wyczuwających

Zatem, gdy jedna mrówka odnajdzie dobrą (krótką) drogę, inne mrówki będą podążać tą właśnie drogą również zostawiając feromony, a więc zwiększając ich natężenie. Ostatecznie wszystkie mrówki będą poruszać się tą samą, najlepszą drogą, a pozostałe drogi zostaną zapomniane (wyparują).

Algorytm mrówkowy a technika
Algorytm mrówkowy to stosunkowo nowe podejście w dziedzinie obliczeń inteligentnych. Służy głównie optymalizacji, jednak jego zastosowanie nie daje gwarancji znalezienia optimum globalnego. Algorytm mrówkowy można stosować do szerokiego

spektrum problemów, w których rozwiązanie można przedstawić jako szereg kroków, które może zrobić wirtualna mrówka. Istnieje wiele wariacji tej techniki, często dużo bardziej skomplikowane niż zaprezentowany w tej pracy schemat działań. Algorytmy mrówkowe znalazły zastosowanie w różnych dziedzinach, np. problemach poszukiwania dróg w grafie, szukania pokryć i partycji zbiorów, problemy alokacji zasobów, harmonogramowania.

Przeczytaj więcej:
http://prac.us.edu.pl/~uboryczk/strony/prace/efekt/efekt.htm

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *