Jestem studentem pracującym nad symulatorem kolonii mrówek dla projektu kursu. Algorytm do tego jest (oczywiście) algorytmem kolonii mrówek. Wiem, że istnieją różne formy algorytmu, ale wszystkie były dla nas zbyt matematyczne, więc przyjęliśmy podejście, w którym:
- Mrówka rodzi się w kolonii i musi zbierać żywność ze źródła, aby utrzymać kolonię.
- Wszystkie mrówki są podobne.
- Obszar, w którym porusza się mrówka, to siatka o wymiarach 1000 x 1000, więc każdy punkt siatki służy jako prawidłowy punkt do zajęcia przez mrówkę. Teraz wszystkie algorytmy, które napotkałem, dotyczą oddzielnego traktowania wierzchołków i krawędzi, ale ponieważ ograniczamy ruch mrówek tylko do czterech kierunków (w górę, w dół, w lewo, w prawo), myślę, że nie ma znaczenia, gdzie umieszczamy feromon.
- Punkty siatki wspomniane powyżej przechowują feromon.
- Mrówka upuszcza feromon tylko wtedy, gdy przenosi jedzenie.
- W przypadku mrówki w pozycji (i, j) decyduje, gdzie się poruszać w następnym kroku, biorąc pod uwagę ilości feromonów na czterech sąsiednich węzłach w prostej formule probabilistycznej, tj. Prawdopodobieństwo podróży do węzła jest określone przez (ilość feromonu w danym sąsiednim węźle) / (suma ilości feromonu w 4 sąsiadujących węzłach).
- Mrówka nie może wrócić do pozycji, z której właśnie przyszła. Może to zrobić tylko wtedy, gdy znajduje się w miejscu z żywnością lub w swojej kolonii.
Teraz obawiam się (i co tak naprawdę dzieje się w naszym programie), że kiedy Mrówka PIERWSZA osiągnie pozycję z jedzeniem i ją odbierze, to po drodze naszego algorytmu może się poruszać gdziekolwiek! Wynika to z tego, że pozostawia ślad feromonów, gdy tylko dostanie jedzenie, a nie wcześniej, a ponieważ jest to pierwsza mrówka, nie ma już śladu.
Jeśli mrówka może się gdziekolwiek poruszać, mrówki, które docierają do źródła pokarmu po nim, również zwykle podążają za nim. NAWET JEŚLI nie porusza się z powrotem w kierunku kolonii. To przeczy celowi całego algorytmu.
Więc moje pytania są
- Czy powyższy problem jest ważny? Jeśli nie, to dlaczego? Jeśli tak, to jak sobie z tym poradzić?
- Czy musimy wprowadzić pewne zmiany w naszym podstawowym zrozumieniu algorytmu, aby faktycznie działał?
- Jakie inne subtelne, ale ważne rzeczy mogą pominąć w tym przypadku nowicjusze tacy jak ja?
źródło
Odpowiedzi:
Nie tak działa ACO. ACO upuszcza feromony tylko po tym, jak mrówki przemierzą wszystkie punkty na planszy. Następnie oceniasz coś (być może całkowity czas podróży), a następnie upuszczasz feromony dla dobrych mrówek i powtarzasz.
Zasadniczo nie przechodzą one do tego samego wierzchołka, choć można to dostosować do specyfiki implementacji.
Feromony nie są upuszczane przy każdym ruchu, upuszczają się po każdym ruchu i coś jest oceniane, aby określić, które mrówki są lepsze. Mrówki, które są lepsze, niż upuszczają fenomony (być może najlepsze 25% mrówek).
źródło
Wdrożenia, które widziałem od innych, i te, które napisałem dla siebie, zawsze kazały mrówkom wypuszczać feromony na drodze, którą podróżowały, aby dostać się do jedzenia, gdy już do niego dotrą. To znaczy, mrówki maszerują ze swojej kolonii do jedzenia po losowym spacerze; ścieżki, którymi podążają mrówki z kolonii do pokarmu, są następnie oznaczane za pomocą feromonów dopiero po tym, jak mrówkom udało się dotrzeć do pokarmu. Podróż powrotna nie jest wyraźnie symulowana. Ogólnie rzecz biorąc, wiele mrówek biegnie, zanim jakiekolwiek feromony zostaną zdeponowane w bieżącej iteracji. Feromony są następnie rozmieszczane dla udanych ścieżek i rozpoczyna się nowa runda.
Zwykle szanse mrówki na wejście do danego węzła są ważone ilością feromonów razy pewną miarą „dobroci”. Na przykład miarą dobroci może być coś w rodzaju odwrotności odległości między mrówką a pokarmem - dzięki temu mrówki będą próbowały zbliżyć się do pokarmu, niezależnie od wcześniejszych depozytów feromonów. Dobroć może być dodatkowo ważona, aby uwzględnić inne czynniki, np. Niektóre węzły mogą być łatwiejsze do pokonania niż inne. I jak wskazuje Enderland, zazwyczaj istnieje pewna forma „wyboru ścieżki”, gdy wszystkie mrówki pomyślnie uruchomią swoje kursy, w których tylko część „najlepszych” ścieżek jest wybierana do depozytu feromonów. Jednak nadal powinieneś uzyskać rozsądne ścieżki, nawet bez wyboru,
źródło