Algorytmy optymalizacji kolonii mrówek - Ant colony optimization algorithms

Zachowanie mrówek było inspiracją dla techniki optymalizacji metaheurystycznej

Kiedy kolonia mrówek staje przed wyborem dotarcia do pożywienia dwiema różnymi drogami, z których jedna jest znacznie krótsza od drugiej, ich wybór jest całkowicie losowy. Jednak ci, którzy korzystają z krótszej trasy, szybciej docierają do pożywienia i dlatego częściej poruszają się tam iz powrotem między mrowiskiem a pożywieniem.

W informatyce i Badań Operacyjnych The Ant optymalizacja kolonii algorytm ( ACO ) jest probabilistyczny technika rozwiązywania problemów obliczeniowych, które można sprowadzić do znalezienia dobrych ścieżek poprzez wykresach . Sztuczne mrówki to wieloczynnikowe metody inspirowane zachowaniem prawdziwych mrówek. Najczęściej stosowanym paradygmatem jest komunikacja mrówek biologicznych oparta na feromonach . Kombinacje sztucznych mrówek i lokalnych algorytmów wyszukiwania stały się metodą z wyboru w wielu zadaniach optymalizacyjnych obejmujących pewnego rodzaju grafy , np. wyznaczanie tras pojazdów i tras internetowych .

Na przykład optymalizacja kolonii mrówek to klasa algorytmów optymalizacji wzorowanych na działaniach kolonii mrówek . Sztuczne „mrówki” (np. agenty symulacyjne) lokalizują optymalne rozwiązania, poruszając się w przestrzeni parametrów reprezentującej wszystkie możliwe rozwiązania. Prawdziwe mrówki podczas eksploracji otoczenia składają feromony kierując się nawzajem do zasobów. Symulowane "mrówki" w podobny sposób rejestrują swoje pozycje i jakość swoich rozwiązań, dzięki czemu w późniejszych iteracjach symulacji więcej mrówek znajduje lepsze rozwiązania. Jedną z odmian tego podejścia jest algorytm pszczół , który jest bardziej analogiczny do wzorców żerowania pszczoły miodnej , innego owada społecznego.

Algorytm ten należy do rodziny algorytmów kolonii mrówek w metodach inteligencji roju i stanowi pewne optymalizacje metaheurystyczne . Po raz pierwszy zaproponowany przez Marco Dorigo w 1992 roku w jego rozprawie doktorskiej, pierwszy algorytm miał na celu poszukiwanie optymalnej ścieżki na wykresie, na podstawie zachowania mrówek poszukujących drogi między swoją kolonią a źródłem pożywienia. Pierwotna idea została od tego czasu zróżnicowana, aby rozwiązać szerszą klasę problemów numerycznych, w wyniku czego pojawiło się kilka problemów, czerpiących z różnych aspektów zachowania mrówek. Patrząc z szerszej perspektywy, ACO przeprowadza wyszukiwanie oparte na modelu i wykazuje pewne podobieństwa z estymacją algorytmów dystrybucji .

Przegląd

W świecie przyrody mrówki niektórych gatunków (początkowo) wędrują losowo , a po znalezieniu pożywienia wracają do swojej kolonii, kładąc ślady feromonów . Jeśli inne mrówki znajdą taką ścieżkę, prawdopodobnie nie będą podróżować dalej losowo, ale zamiast tego podążają szlakiem, powracając i wzmacniając go, jeśli w końcu znajdą pożywienie (patrz Komunikacja z mrówkami ).

Z czasem jednak ślad feromonów zaczyna wyparowywać, zmniejszając w ten sposób jego atrakcyjność. Im więcej czasu zajmuje mrówce przejście ścieżką iz powrotem, tym więcej czasu muszą wyparować feromony. Krótka ścieżka jest dla porównania maszerowana częściej, a tym samym gęstość feromonów staje się wyższa na krótszych ścieżkach niż na dłuższych. Parowanie feromonów ma również tę zaletę, że pozwala uniknąć konwergencji do lokalnie optymalnego rozwiązania. Gdyby w ogóle nie było parowania, ścieżki wybrane przez pierwsze mrówki byłyby zbyt atrakcyjne dla następnych. W takim przypadku eksploracja przestrzeni rozwiązań byłaby ograniczona. Wpływ parowania feromonów w rzeczywistych układach mrówek jest niejasny, ale jest bardzo ważny w układach sztucznych.

Ogólny wynik jest taki, że gdy jedna mrówka znajdzie dobrą (tj. krótką) drogę z kolonii do źródła pożywienia, inne mrówki z większym prawdopodobieństwem podążą tą ścieżką, a pozytywne sprzężenie zwrotne ostatecznie prowadzi do tego, że wiele mrówek podąża jedną ścieżką. Ideą algorytmu kolonii mrówek jest naśladowanie tego zachowania z „symulowanymi mrówkami” chodzącymi po wykresie przedstawiającym problem do rozwiązania.

Otoczenie sieci inteligentnych obiektów

Potrzebne są nowe koncepcje, ponieważ „inteligencja” nie jest już scentralizowana, ale można ją znaleźć we wszystkich maleńkich przedmiotach. Wiadomo, że koncepcje antropocentryczne prowadzą do produkcji systemów informatycznych, w których przetwarzanie danych, jednostki sterujące i siły obliczeniowe są scentralizowane. Te scentralizowane jednostki stale zwiększają swoją wydajność i można je porównać do ludzkiego mózgu. Model mózgu stał się ostateczną wizją komputerów. Otoczenie sieci inteligentnych obiektów i, prędzej czy później, nowa generacja systemów informatycznych, jeszcze bardziej rozproszonych i opartych na nanotechnologii, dogłębnie zmienią tę koncepcję. Małe urządzenia, które można porównać do owadów, same w sobie nie dysponują wysoką inteligencją. Rzeczywiście, ich inteligencję można uznać za dość ograniczoną. Na przykład niemożliwe jest zintegrowanie wysokowydajnego kalkulatora z możliwością rozwiązania jakiegokolwiek problemu matematycznego z biochipem wszczepianym do ludzkiego ciała lub zintegrowanym z inteligentnym znacznikiem przeznaczonym do śledzenia artykułów komercyjnych. Jednakże, gdy te obiekty zostaną połączone, dysponują formą inteligencji, którą można porównać do kolonii mrówek lub pszczół. W przypadku pewnych problemów ten rodzaj inteligencji może przewyższać rozumowanie scentralizowanego systemu podobnego do mózgu.

Natura podaje kilka przykładów na to, jak maleńkie organizmy, jeśli wszystkie przestrzegają tej samej podstawowej zasady, mogą tworzyć formę zbiorowej inteligencji na poziomie makroskopowym. Kolonie owadów społecznych doskonale ilustrują ten model, który bardzo różni się od ludzkich społeczeństw. Model ten opiera się na współpracy niezależnych jednostek o prostym i nieprzewidywalnym zachowaniu. Poruszają się po okolicy, aby wykonać określone zadania, a do tego posiadają bardzo ograniczoną ilość informacji. Na przykład kolonia mrówek reprezentuje liczne cechy, które można zastosować również do sieci otaczających obiektów. Kolonie mrówek mają bardzo dużą zdolność przystosowania się do zmian w środowisku, a także ogromną siłę w radzeniu sobie z sytuacjami, w których jeden osobnik nie jest w stanie wykonać danego zadania. Taka elastyczność byłaby również bardzo przydatna w przypadku sieci komórkowych obiektów, które stale się rozwijają. Paczki informacji, które przenoszą się z komputera do obiektu cyfrowego, zachowują się w taki sam sposób, jak zachowują się mrówki. Poruszają się po sieci i przechodzą od jednego węzła do drugiego, aby jak najszybciej dotrzeć do miejsca docelowego.

System sztucznych feromonów

Komunikacja feromonowa to jeden z najskuteczniejszych sposobów komunikacji, który jest powszechnie obserwowany w przyrodzie. Feromon jest używany przez owady społeczne, takie jak pszczoły, mrówki i termity; zarówno do komunikacji między agentami, jak i do komunikacji z rojem agentów. Ze względu na swoją wykonalność sztuczne feromony zostały zaadoptowane w systemach robotów wielorobotowych i roju. Komunikacja oparta na feromonach była realizowana różnymi środkami, takimi jak chemiczne lub fizyczne (znaczniki RFID, światło, dźwięk). Jednak te implementacje nie były w stanie odtworzyć wszystkich aspektów feromonów w naturze.

Korzystanie z rzutowanego światła zostało przedstawione w 2007 roku w artykule opublikowanym w IEEE przez Garniera, Simona i in. jako eksperymentalny zestaw do badania komunikacji opartej na feromonach z mikroautomatami autonomicznymi. W innym badaniu zaprezentowano system, w którym feromony wprowadzono za pomocą poziomego ekranu LCD, na którym poruszały się roboty, przy czym roboty mają czujniki światła skierowane w dół do rejestrowania wzorów pod nimi.

Algorytm i formuły

W algorytmach optymalizacji kolonii mrówek sztuczna mrówka jest prostym agentem obliczeniowym, który wyszukuje dobre rozwiązania danego problemu optymalizacyjnego. Aby zastosować algorytm kolonii mrówek, problem optymalizacji należy przekształcić w problem znalezienia najkrótszej ścieżki na grafie ważonym. W pierwszym kroku każdej iteracji każda mrówka stochastycznie konstruuje rozwiązanie, tj. kolejność, w jakiej powinny być przestrzegane krawędzie grafu. W drugim kroku porównywane są ścieżki znalezione przez różne mrówki. Ostatni krok polega na aktualizacji poziomów feromonów na każdej krawędzi.

procedure ACO_MetaHeuristic is
    while not terminated do
        generateSolutions()
        daemonActions()
        pheromoneUpdate()
    repeat
end procedure

Wybór krawędzi

Każda mrówka musi skonstruować rozwiązanie, aby poruszać się po wykresie. Aby wybrać następną krawędź w swojej trasie, mrówka weźmie pod uwagę długość każdej krawędzi dostępnej z jej aktualnej pozycji, a także odpowiedni poziom feromonów. Na każdym kroku algorytmu każda mrówka przechodzi ze stanu do stanu , co odpowiada bardziej kompletnemu rozwiązaniu pośredniemu. W ten sposób każda mrówka w każdej iteracji oblicza zbiór możliwych rozszerzeń do swojego aktualnego stanu i z prawdopodobieństwem przechodzi do jednego z nich. W przypadku mrówki prawdopodobieństwo przejścia ze stanu do stanu zależy od kombinacji dwóch wartości, atrakcyjności ruchu, obliczonej za pomocą pewnej heurystyki wskazującej a priori celowość tego ruchu oraz poziomu śladu ruchu, wskazującego, jak bardzo jest on sprawny. był w przeszłości, aby wykonać ten konkretny ruch. Poziom śladu reprezentuje a posteriori wskazanie celowości tego ruchu. ${\displaystyle x}$${\displaystyle y}$${\displaystyle k}$${\ Displaystyle A_ {k} (x)}$${\displaystyle k}$${\ Displaystyle p_ {xy} ^ {k}}$${\displaystyle x}$${\displaystyle y}$ ${\ Displaystyle \eta _ {xy}}$ ${\ Displaystyle \ tau _ {xy}}$

Ogólnie rzecz biorąc, mrówka przechodzi ze stanu do stanu z prawdopodobieństwem ${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$

${\ Displaystyle p_ {xy} ^ {k} = {\ Frac {(\ tau _ {xy} ^ {\ alfa}) (\ _ eta {xy} ^ {\ beta})} {\ suma _ {z \ w \mathrm {dozwolone} _{x}}(\tau _{xz}^{\alpha })(\eta _{xz}^{\beta })}}}$

gdzie

${\ Displaystyle \ tau _ {xy}}$Jest to ilość feromonów wyłożone do przejścia ze stanu do , 0 ≤ jest parametrem kontrolować wpływ , jest pożądana zmiany stanu ( a priori wiedzę, na ogół , w którym to dystansu) i ≥ 1 jest parametrem kontrolować wpływ . i reprezentują poziom szlaku i atrakcyjność dla innych możliwych zmian stanu. ${\displaystyle x}$${\displaystyle y}$${\ Displaystyle \ alfa}$${\ Displaystyle \ tau _ {xy}}$${\ Displaystyle \eta _ {xy}}$${\displaystyle xy}$${\displaystyle 1/d_{xy}}$${\displaystyle d}$${\ Displaystyle \ beta}$${\ Displaystyle \eta _ {xy}}$${\ Displaystyle \ tau _ {xz}}$${\ Displaystyle \eta _ {xz}}$

Aktualizacja feromonów

Ślady są zwykle aktualizowane, gdy wszystkie mrówki zakończyły swoje rozwiązanie, zwiększając lub zmniejszając poziom śladów odpowiadających ruchom, które były odpowiednio częścią „dobrych” lub „złych” rozwiązań. Przykładem globalnej reguły aktualizacji feromonów jest:

${\ Displaystyle \ tau _ {xy} \ leftarrow (1- \ rho) \ tau _ {xy} + \ suma _ {k} ^ {m} \ Delta \ tau _ {xy} ^ {k}}$

gdzie to ilość feromonu osadzonego dla zmiany stanu , to współczynnik parowania feromonów , to liczba mrówek i to ilość feromonu nałożonego przez mrówkę , typowo podawana dla problemu TSP (z ruchami odpowiadającymi łukom wykresu) za pomocą ${\ Displaystyle \ tau _ {xy}}$${\displaystyle xy}$${\ Displaystyle \ rho}$${\ Displaystyle m}$${\ Displaystyle \ Delta \ tau _ {xy} ^ {k}}$${\displaystyle k}$

${\ Displaystyle \ Delta \ tau _ {xy} ^ {k} = {\ zacząć {przypadki} Q / L_ {k} i {\ mbox {jeśli mrówka}} k {\ mbox {używa krzywej}} xy {\ mbox { w swojej wycieczce}}\\0&{\mbox{otherwise}}\end{cases}}}$

gdzie jest koszt wycieczki mrówki (zazwyczaj długość) i jest stałą. ${\ Displaystyle L_ {k}}$${\displaystyle k}$${\displaystyle Q}$

Wspólne rozszerzenia

Oto niektóre z najpopularniejszych odmian algorytmów ACO.

System mrówek (AS)

System mrówkowy to pierwszy algorytm ACO. Algorytm ten odpowiada przedstawionemu powyżej. Został opracowany przez Dorigo.

System kolonii mrówek (ACS)

W algorytmie systemu kolonii mrówek pierwotny system mrówek został zmodyfikowany w trzech aspektach:

1. Wybór krawędzi jest nastawiony na eksploatację (tj. faworyzowanie prawdopodobieństwa wyboru najkrótszych krawędzi z dużą ilością feromonów);
2. Budując rozwiązanie, mrówki zmieniają poziom feromonów na krawędziach, które wybierają, stosując lokalną regułę aktualizacji feromonów;
3. Pod koniec każdej iteracji tylko najlepsza mrówka może aktualizować ślady, stosując zmodyfikowaną globalną regułę aktualizacji feromonów.

Elitarny system mrówek

W tym algorytmie najlepsze rozwiązanie globalne umieszcza feromon na swoim śladzie po każdej iteracji (nawet jeśli ten ślad nie został ponownie odwiedzony), wraz ze wszystkimi innymi mrówkami. Strategia elitarna ma na celu skierowanie poszukiwań wszystkich mrówek w celu skonstruowania rozwiązania zawierającego linki aktualnie najlepszej trasy.

System mrówek Max-Min (MMAS)

Algorytm ten kontroluje maksymalną i minimalną ilość feromonów na każdym śladzie. Tylko najlepsza trasa globalna lub najlepsza trasa iteracyjna może dodać feromon do swojego szlaku. Aby uniknąć stagnacji algorytmu wyszukiwania, zakres możliwych ilości feromonów na każdym śladzie jest ograniczony do przedziału [τ _max ,τ _min ]. Wszystkie krawędzie są inicjowane do τ _max, aby wymusić głębszą eksplorację rozwiązań. Ślady są ponownie inicjowane do τ _max, gdy zbliżają się do stagnacji.

System mrówek oparty na rangach (ASrank)

Wszystkie rozwiązania są uszeregowane według ich długości. Tylko ustalona liczba najlepszych mrówek w tej iteracji może aktualizować swoje próby. Ilość osadzonego feromonu jest ważona dla każdego roztworu tak, że roztwory o krótszych drogach deponują więcej feromonu niż roztwory o dłuższych drogach.

Ciągła kolonia mrówek ortogonalnych (COAC)

Mechanizm osadzania feromonów COAC ma umożliwić mrówkom wspólne i efektywne poszukiwanie rozwiązań. Stosując ortogonalną metodę projektowania, mrówki w wykonalnej domenie mogą szybko i wydajnie eksplorować wybrane regiony, z ulepszonymi możliwościami i dokładnością wyszukiwania globalnego. Metodę projektowania ortogonalnego i metodę adaptacyjnego dostosowania promienia można również rozszerzyć na inne algorytmy optymalizacji w celu zapewnienia szerszych korzyści w rozwiązywaniu praktycznych problemów.

Rekurencyjna optymalizacja kolonii mrówek

Jest to rekurencyjna forma systemu mrówek, który dzieli całą domenę wyszukiwania na kilka poddomen i rozwiązuje cel na tych poddomenach. Wyniki ze wszystkich subdomen są porównywane i kilka najlepszych z nich jest promowanych na wyższy poziom. Poddomeny odpowiadające wybranym wynikom są dalej dzielone i proces jest powtarzany aż do uzyskania wyniku o pożądanej precyzji. Ta metoda została przetestowana na źle postawionych problemach geofizycznej inwersji i działa dobrze.

Konwergencja

Dla niektórych wersji algorytmu można wykazać, że jest zbieżny (tzn. jest w stanie znaleźć globalne optimum w skończonym czasie). Pierwszy dowód na zbieżność algorytmu kolonii mrówek powstał w 2000 roku, algorytmu systemu mrówek opartego na grafie, a później algorytmów ACS i MMAS. Jak większość metaheurystyk , bardzo trudno jest oszacować teoretyczną prędkość zbieżności. Analiza wydajności algorytmu ciągłej kolonii mrówek w odniesieniu do jego różnych parametrów (strategia wyboru krawędzi, metryka odległości i szybkość parowania feromonów) wykazała, że ​​jego wydajność i szybkość konwergencji są wrażliwe na wybrane wartości parametrów, a zwłaszcza na wartość szybkości parowania feromonów. W 2004 roku Zlochin i jego współpracownicy wykazali, że algorytmy typu COAC mogą być asymilowanymi metodami stochastycznego spadku gradientu , entropii krzyżowej i estymacji algorytmu rozkładu . Zaproponowali te metaheurystyki jako „ model oparty na badaniach ”.

Aplikacje

Problem plecakowy : mrówki wolą mniejszą kroplę miodu od bardziej obfitego, ale mniej odżywczego cukru

Algorytmy optymalizacji kolonii mrówek zostały zastosowane w wielu kombinatorycznych problemach optymalizacji , począwszy od przyporządkowania kwadratowego do pojazdów składających lub trasujących białka, a wiele metod pochodnych zostało dostosowanych do problemów dynamicznych w rzeczywistych zmiennych, problemów stochastycznych, wielu celów i implementacji równoległych . Został również wykorzystany do stworzenia niemal optymalnych rozwiązań problemu komiwojażera . Mają przewagę nad podejściami z symulowanym wyżarzaniem i algorytmem genetycznym podobnych problemów, gdy wykres może się dynamicznie zmieniać; algorytm kolonii mrówek może działać w sposób ciągły i dostosowywać się do zmian w czasie rzeczywistym. Jest to interesujące w wyznaczaniu tras sieciowych i systemach transportu miejskiego.

Pierwszy algorytm ACO został nazwany systemem mrówkowym i miał na celu rozwiązanie problemu komiwojażera, w którym celem jest znalezienie najkrótszej podróży w obie strony łączącej szereg miast. Ogólny algorytm jest stosunkowo prosty i opiera się na zestawie mrówek, z których każda wykonuje jedną z możliwych podróży w obie strony po miastach. Na każdym etapie mrówka postanawia przenieść się z jednego miasta do drugiego zgodnie z pewnymi zasadami:

1. Musi odwiedzić każde miasto dokładnie raz;
2. Odległe miasto ma mniejsze szanse na wybór (widoczność);
3. Im intensywniejszy jest ślad feromonów ułożony na granicy między dwoma miastami, tym większe prawdopodobieństwo, że ta krawędź zostanie wybrana;
4. Po zakończeniu podróży mrówka osadza więcej feromonów na wszystkich krawędziach, przez które przebyła, jeśli podróż jest krótka;
5. Po każdej iteracji ślady feromonów ulatniają się.

Problem z planowaniem

• Problem z porządkowaniem sekwencyjnym (SOP)
• Problem z planowaniem warsztatów (JSP)
• Problem planowania otwartego sklepu (OSP)
• Problem z przepływem permutacji (PFSP)
• Problem całkowitego spóźnienia pojedynczej maszyny (SMTTP)
• Problem całkowitego ważonego spóźnienia pojedynczej maszyny (SMTWTP)
• Problem planowania projektów o ograniczonych zasobach (RCPSP)
• Problem z planowaniem pracy grupowej (GSP)
• Problem całkowitego opóźnienia pojedynczej maszyny z czasami konfiguracji zależnej od sekwencji (SMTTPDST)
• Wielostopniowy problem z harmonogramowaniem flowshop (MFSP) z zależnymi od sekwencji czasami konfiguracji/przełączania

Problem z wyznaczaniem trasy pojazdu

• Problem z wyznaczaniem tras pojazdów z pojemnością (CVRP)
• Problem z wyznaczaniem tras pojazdów w wielu zajezdniach (MDVRP)
• Problem wyznaczania tras pojazdów okresowych (PVRP)
• Problem z podziałem trasy pojazdów dostawczych (SDVRP)
• Stochastyczny problem wyznaczania tras pojazdów (SVRP)
• Problem z wyznaczaniem trasy pojazdu z odbiorem i dostawą (VRPPD)
• Problem wyznaczania tras pojazdów z oknami czasowymi (VRPTW)
• Problem wyznaczania tras pojazdów w zależności od czasu z oknami czasowymi (TDVRPTW)
• Problem wyznaczania tras pojazdów z oknami czasowymi i wieloma pracownikami serwisu (VRPTWMS)

Problem z przypisaniem

• Problem przypisania kwadratowego (QAP)
• Uogólniony problem przypisania (GAP)
• Problem przydziału częstotliwości (FAP)
• Problem alokacji nadmiarowości (RAP)

Ustaw problem

• Ustaw problem z okładką (SCP)
• Problem z partycją (SPP)
• Problem podziału drzewa grafów z ograniczeniami wagowymi (WCGTPP)
• Problem drzewa l-kardynalności ważonego łukiem (AWlCTP)
• Problem z wieloma plecakami (MKP)
• Maksymalny problem z niezależnymi zestawami (MIS)

Problem wymiarowania urządzeń w projektowaniu fizycznym nanoelektroniki

• Optymalizacja w oparciu o optymalizację kolonii mrówek (ACO) 45 nm obwodu wzmacniacza czujnika opartego na CMOS może doprowadzić do uzyskania optymalnych rozwiązań w bardzo krótkim czasie.
• Synteza odwracalnych obwodów w oparciu o optymalizację kolonii mrówek (ACO) może znacznie poprawić wydajność.

Optymalizacja i synteza anten

Wibratory loopback 10×10, syntetyzowane za pomocą algorytmu ACO

Wibratory unloopback 10×10, syntetyzowane za pomocą algorytmu ACO

Aby zoptymalizować kształt anten, można zastosować algorytmy kolonii mrówek. Jako przykład można podać anteny tagi RFID oparte na algorytmach kolonii mrówek (ACO), wibratory loopback i unloopback 10×10

Przetwarzanie obrazu

Algorytm ACO jest używany w przetwarzaniu obrazu do wykrywania krawędzi obrazu i łączenia krawędzi.

• Wykrywanie krawędzi:

Wykres tutaj jest obrazem 2D, a mrówki przechodzą od jednego piksela deponującego feromon. Ruch mrówek z jednego piksela do drugiego jest kierowany przez lokalne zmiany wartości intensywności obrazu. Ten ruch powoduje osadzanie się największej gęstości feromonów na krawędziach.

Poniżej przedstawiono kroki związane z wykrywaniem krawędzi za pomocą ACO:

Krok 1: Inicjalizacja:
Losowo umieść mrówki na obrazie, gdzie . Macierze feromonowe są inicjowane z wartością losową. Głównym wyzwaniem w procesie inicjalizacji jest określenie macierzy heurystycznej. ${\ Displaystyle K}$${\displaystyle I_{M_{1}M_{2}}}$${\ Displaystyle K = (M_ {1} * M_ {2}) ^ {\ tfrac {1} {2}}}$${\ Displaystyle \ tau _ {(i, j)}}$

Istnieją różne metody wyznaczania macierzy heurystycznej. Dla poniższego przykładu macierz heurystyczna została obliczona na podstawie statystyk lokalnych: statystyk lokalnych na pozycji piksela (i,j).

${\ Displaystyle \eta _ {(i, j)} = {\ tfrac {1} {Z}} * Vc * I_ {(i, j)}}$

Gdzie jest obraz rozmiaru , który jest współczynnikiem normalizacji? ${\ Displaystyle I}$${\displaystyle M_{1}*M_{2}}$
${\ Displaystyle Z = \ suma _ {i = 1: M_ {1}} \ suma _ {j = 1: M_ {2}} Vc (I_ {i, j})}$

${\ Displaystyle {\ zacząć {wyrównany} Vc (I_ {i, j}) = i f \ lewo (\ lewo \ vert I_ {(i-2, j-1)}-I_ {(i + 2, j + 1 )}\right\vert +\left\vert I_{(i-2,j+1)}-I_{(i+2,j-1)}\right\vert \right.\\&+\left\ vert I_{(i-1,j-2)}-I_{(i+1,j+2)}\right\vert +\left\vert I_{(i-1,j-1)}-I_{ (i+1,j+1)}\right\vert \\&+\left\vert I_{(i-1,j)}-I_{(i+1,j)}\right\vert +\left \vert I_{(i-1,j+1)}-I_{(i-1,j-1)}\right\vert \\&+\left.\left\vert I_{(i-1,j +2)}-I_{(i-1,j-2)}\right\vert +\left\vert I_{(i,j-1)}-I_{(i,j+1)}\right\ vert \right)\end{aligned}}}$

${\displaystyle f(\cdot)}$można obliczyć za pomocą następujących funkcji: Parametr w każdej z powyższych funkcji dostosowuje odpowiednie kształty funkcji. Krok 2 Proces budowy: Ruch mrówki opiera się na 4 połączonych pikselach lub 8 połączonych pikselach . Prawdopodobieństwo, z jakim porusza się mrówka, określa równanie prawdopodobieństwa Krok 3 i Krok 5 Proces aktualizacji: Macierz feromonów jest aktualizowana dwukrotnie. w kroku 3 ślad mrówki (podany przez ) jest aktualizowany, przy czym, jak w kroku 5, aktualizowana jest szybkość parowania śladu, którą określa poniższe równanie. , gdzie jest współczynnikiem rozpadu feromonów
${\ Displaystyle f (x) = \ lambda x, \ quad {\ tekst {dla x ≥ 0; (1)}}}$
${\ Displaystyle f (x) = \ lambda x ^ {2}, \ quad {\ tekst {dla x ≥ 0; (2)}}}$
${\ Displaystyle f (x) = {\ zacząć {przypadki} \ grzech ({\ Frac {\ pi x} {2 \ lambda}}}), i {\ tekst {dla 0 ≤ x ≤}} \ lambda {\ tekst {; (3)}}\\0,&{\text{else}}\end{przypadki}}}$
${\ Displaystyle f (x) = {\ zacząć {przypadki} \ pi x \ grzech ({\ Frac {\ pi x} {2 \ lambda}}), i {\ tekst {dla 0 ≤ x ≤}} \ lambda {\tekst{; (4)}}\\0,&{\text{else}}\end{przypadki}}}$
${\ Displaystyle \ lambda}$

${\displaystyle P_{x,y}}$

${\ Displaystyle \ tau _ {(x, y)}}$
${\ Displaystyle \ tau _ {nowy} \ leftarrow (1- \ psi) \ tau _ {stary} + \ psi \ tau _ {0}}$${\ Displaystyle \ psi}$${\displaystyle 0<\tau <1}$

Krok 7 Proces decyzyjny:
Po przesunięciu się K mrów o ustaloną odległość L dla iteracji, decyzja, czy jest to krawędź, czy nie, opiera się na progu T na matrycy feromonówτ. Próg dla poniższego przykładu jest obliczany na podstawie metody Otsu .

Krawędź obrazu wykryta za pomocą ACO:
Poniższe obrazy są generowane przy użyciu różnych funkcji podanych przez równania (1) do (4).

• Łączenie krawędzi: ACO okazał się również skuteczny w algorytmach łączenia krawędzi.

Inne aplikacje

• Przewidywanie upadłości
• Klasyfikacja
• Routing sieciowy zorientowany na połączenie
• Bezpołączeniowy routing sieci
• Eksploracja danych
• Zdyskontowane przepływy pieniężne w harmonogramowaniu projektów
• Rozproszone wyszukiwanie informacji
• Projektowanie sieci energetycznych i elektrycznych
• Problem z planowaniem przepływu pracy w sieci
• Projekt peptydu hamującego dla oddziaływań białkowych
• Inteligentny system testowania
• Projektowanie obwodów elektronicznych mocy
• Fałdowanie białek
• Identyfikacja systemu

Trudność definicji

W przypadku algorytmu ACO najkrótsza ścieżka na wykresie, pomiędzy dwoma punktami A i B, jest zbudowana z kombinacji kilku ścieżek. Nie jest łatwo podać dokładną definicję tego, czym algorytm jest, a czym nie jest kolonią mrówek, ponieważ definicja może się różnić w zależności od autorów i zastosowań. Mówiąc ogólnie, algorytmy kolonii mrówek są uważane za zaludnione metaheurystyki, w których każde rozwiązanie jest reprezentowane przez mrówkę poruszającą się w przestrzeni poszukiwań. Mrówki wyznaczają najlepsze rozwiązania i uwzględniają wcześniejsze oznaczenia, aby zoptymalizować swoje poszukiwania. Można je postrzegać jako probabilistyczne algorytmy wieloagentowe wykorzystujące rozkład prawdopodobieństwa do przejścia między każdą iteracją . W swoich wersjach dla problemów kombinatorycznych stosują iteracyjną konstrukcję rozwiązań. Według niektórych autorów tym, co odróżnia algorytmy ACO od innych pokrewnych (takich jak algorytmy szacowania rozkładu czy optymalizacja roju cząstek), jest właśnie ich aspekt konstrukcyjny. W problemach kombinatorycznych możliwe jest, że w końcu uda się znaleźć najlepsze rozwiązanie, nawet jeśli żadna mrówka nie okaże się skuteczna. Tak więc na przykładzie problemu komiwojażera wcale nie jest konieczne, aby mrówka faktycznie przebyła najkrótszą trasę: najkrótszą trasę można zbudować z najsilniejszych segmentów najlepszych rozwiązań. Definicja ta może być jednak problematyczna w przypadku problemów ze zmiennymi rzeczywistymi, gdzie nie istnieje struktura „sąsiadów”. Zbiorowe zachowania owadów społecznych pozostają źródłem inspiracji dla badaczy. Szeroka gama algorytmów (do optymalizacji lub nie) dążących do samoorganizacji w systemach biologicznych doprowadziła do koncepcji „ inteligencji roju ”, która jest bardzo ogólną ramą, w której pasują algorytmy kolonii mrówek.

Algorytmy stygmeryzacji

W praktyce istnieje duża liczba algorytmów, które twierdzą, że są „koloniami mrówek”, nie zawsze dzieląc ogólne ramy optymalizacji dla kanonicznych kolonii mrówek. W praktyce wykorzystanie wymiany informacji między mrówkami za pośrednictwem środowiska (zasada zwana „ stigergią ”) uważa się za wystarczające, aby algorytm należał do klasy algorytmów kolonii mrówek. Ta zasada skłoniła niektórych autorów do stworzenia terminu „wartość” do organizowania metod i zachowań opartych na poszukiwaniu pożywienia, sortowaniu larw, podziale pracy i wspólnym transporcie.

Powiązane metody

Algorytmy genetyczne (GA)

Utrzymują one pulę rozwiązań, a nie tylko jedno. Proces znajdowania lepszych rozwiązań naśladuje ewolucję, przy czym rozwiązania są łączone lub mutowane w celu zmiany puli rozwiązań, przy czym rozwiązania gorszej jakości są odrzucane.

Algorytm szacowania dystrybucji (EDA)

Ewolucyjny algorytm , który zastępuje tradycyjne operatorów słownikowych przez operatorów modelowych przewodnikiem. Takie modele są uczone od populacji poprzez zastosowanie technik uczenia maszynowego i reprezentowane jako probabilistyczne modele graficzne, z których można próbować nowe rozwiązania lub generować je z krzyżowania kierowanego.

Symulowane wyżarzanie (SA)

Powiązana globalna technika optymalizacji, która przemierza przestrzeń wyszukiwania, generując sąsiednie rozwiązania bieżącego rozwiązania. Lepszy sąsiad jest zawsze akceptowany. Gorszy sąsiad jest akceptowany probabilistycznie na podstawie różnicy w jakości i parametrze temperatury. Parametr temperatury jest modyfikowany w miarę postępu algorytmu, aby zmienić charakter wyszukiwania.

Reaktywna optymalizacja wyszukiwania

Koncentruje się na połączeniu uczenia maszynowego z optymalizacją poprzez dodanie wewnętrznej pętli sprzężenia zwrotnego w celu samodzielnego dostrojenia dowolnych parametrów algorytmu do charakterystyki problemu, instancji i lokalnej sytuacji wokół bieżącego rozwiązania.

Wyszukiwanie tabu (TS)

Podobny do symulowanego wyżarzania, w którym oba przechodzą przez przestrzeń rozwiązania, testując mutacje pojedynczego rozwiązania. Podczas gdy symulowane wyżarzanie generuje tylko jedno zmutowane rozwiązanie, wyszukiwanie tabu generuje wiele zmutowanych rozwiązań i przechodzi do rozwiązania o najniższej przydatności spośród wygenerowanych. Aby zapobiec cyklom i zachęcić do większego ruchu w przestrzeni rozwiązań, utrzymywana jest lista tabu z rozwiązaniami częściowymi lub całkowitymi. Zabronione jest przechodzenie do rozwiązania, które zawiera elementy listy tabu, która jest aktualizowana w miarę przechodzenia rozwiązania przez przestrzeń rozwiązań.

Sztuczny układ odpornościowy (AIS)

Wzorowany na układach odpornościowych kręgowców.

Optymalizacja roju cząstek (PSO)

Rój inteligencja metoda.

Inteligentne krople wody (IWD)

Algorytm optymalizacji oparty na roju na podstawie naturalnych kropel wody płynących w rzekach

Grawitacyjny algorytm wyszukiwania (GSA)

Rój inteligencja metoda.

Metoda tworzenia skupisk kolonii mrówek (ACCM)

Metoda wykorzystująca podejście klastrowe, rozszerzająca ACO.

Wyszukiwanie dyfuzji stochastycznej (SDS)

Oparta na agentach probabilistyczna technika globalnego wyszukiwania i optymalizacji, która najlepiej nadaje się do rozwiązywania problemów, w których funkcję celu można rozłożyć na wiele niezależnych funkcji częściowych.

Historia

Wynalazcami są Frans Moyson i Bernard Manderick . Pionierzy tej dziedziny to Marco Dorigo , Luca Maria Gambardella .

Chronologia algorytmów COA

Chronologia algorytmów optymalizacji kolonii mrówek.

• 1959, Pierre-Paul Grassé wynalazł teorię stygmazji, aby wyjaśnić zachowanie termitów podczas budowania gniazd ;
• 1983, Deneubourg i jego współpracownicy badali zbiorowego zachowania się mrówek ;
• 1988, a Moyson Manderick ma artykuł o samoorganizacji wśród mrówek;
• 1989, praca Gossa, Arona, Deneubourga i Pasteelsa na temat zbiorowego zachowania mrówek argentyńskich , która da ideę algorytmów optymalizacji kolonii mrówek;
• 1989, wdrożenie przez Eblinga i jego współpracowników modelu zachowań związanych z jedzeniem;
• 1991, M. Dorigo zaproponował system mrówek w swojej pracy doktorskiej (opublikowanej w 1992 roku). Raport techniczny zaczerpnięty z tezy, którego współautorami byli V. Maniezzo i A. Colorni, został opublikowany pięć lat później;
• 1994, Appleby i Steward of British Telecommunications Plc opublikowali pierwszą aplikację do sieci telekomunikacyjnych
• 1995, Gambardella i Dorigo zaproponowali ant-q , wstępną wersję systemu kolonii mrówek jako pierwsze rozszerzenie systemu mrówek;.
• 1996, Gambardella i Dorigo zaproponowali system kolonii mrówek
• 1996, publikacja artykułu o systemie mrówkowym;
• 2000, Hoos i Stützle opracowują system max-min ant ;
• 1997 Dorigo i Gambardella zaproponowali hybrydyzację systemu kolonii mrówek z wyszukiwaniem lokalnym;
• 1997 Schoonderwoerd i jego koledzy opublikowali ulepszoną aplikację do sieci telekomunikacyjnych ;
• 1998 Dorigo rozpoczyna pierwszą konferencję poświęconą algorytmom ACO;
• 1998, Stützle proponuje wstępne równoległe wdrożenia ;
• 1999, Gambardella, Taillard i Agazzi zaproponowali macs-vrptw , pierwszy system kolonii wielu mrówek stosowany do problemów z trasami pojazdów z oknami czasowymi,
• 1999, Bonabeau, Dorigo i Theraulaz publikują książkę poświęconą głównie sztucznym mrówkom
• 2000, wydanie specjalne czasopisma Future Generation Computer Systems poświęcone algorytmom mrówkowym
• 2000, pierwsze zastosowania do szeregowania , kolejność szeregowania i spełnienie ograniczeń ;
• 2000, Gutjahr dostarcza pierwszych dowodów na zbieżność algorytmu kolonii mrówek
• 2001, pierwsze zastosowanie algorytmów COA przez firmy ( Eurobios i AntOptima );
• 2001, Iredi i jego koledzy opublikowali pierwszy algorytm wielokryterialny
• 2002, pierwsze zastosowania w projektowaniu harmonogramów, sieci bayesowskie;
• 2002 Bianchi i jej współpracownicy zaproponowali pierwszy algorytm problemu stochastycznego ;
• 2004, Dorigo i Stützle publikują książkę o optymalizacji kolonii mrówek w MIT Press
• 2004, Złochin i Dorigo pokazują, że niektóre algorytmy są równoważne stochastycznemu zejściu gradientowemu , metodzie entropii krzyżowej i algorytmom szacowania rozkładu
• 2005, pierwsze zastosowania do problemów z fałdowaniem białek .
• 2012 Prabhakar i współpracownicy publikują badania dotyczące działania pojedynczych mrówek komunikujących się w tandemie bez feromonów, odzwierciedlając zasady organizacji sieci komputerowej. Model komunikacji porównano z protokołem Transmission Control Protocol .
• 2016, pierwsza aplikacja do projektowania sekwencji peptydów.
• 2017, udana integracja wielokryterialnej metody podejmowania decyzji PROMETHEE z algorytmem ACO ( algorytm HUMANT ).

Bibliografia

Publikacje (wybrane)

• M. Dorigo , 1992. Optymalizacja, uczenie się i algorytmy naturalne , praca doktorska, Politecnico di Milano, Włochy.
• M. Dorigo, V. Maniezzo & A. Colorni, 1996. „ Ant System: Optymalizacja przez kolonię współpracujących agentów ”, IEEE Transactions on Systems, Man and Cybernetics-Part B, 26 (1): 29-41.
• M. Dorigo i LM Gambardella , 1997. „ System kolonii mrówek: wspólne podejście do uczenia się problemu komiwojażera ”. Transakcje IEEE dotyczące obliczeń ewolucyjnych, 1 (1): 53-66.
• M. Dorigo, G. Di Caro i LM Gambardella, 1999. „ Algorytmy mrówek dla optymalizacji dyskretnej ”. Sztuczne życie, 5 (2): 137-172.
• E. Bonabeau, M. Dorigo i G. Theraulaz, 1999. Inteligencja roju: od systemów naturalnych do sztucznych , Oxford University Press. ISBN  0-19-513159-2
• M. Dorigo i T. Stützle, 2004. Optymalizacja kolonii mrówek , MIT Press. ISBN  0-262-04219-3
• M. Dorigo, 2007. „Optymalizacja kolonii mrówek” . Scholarpedia.
• C. Blum, 2005 „ Optymalizacja kolonii mrówek: Wprowadzenie i najnowsze trendy ”. Recenzje Fizyki Życia, 2: 353-373
• M. Dorigo, M. Birattari i T. Stützle, 2006 Optymalizacja kolonii mrówek: sztuczne mrówki jako technika inteligencji obliczeniowej . TR/IRIDIA/2006-023
• Mohd Murtadha Mohamad, „Przegubowe planowanie ruchu robotów za pomocą strategii żerowania mrówek”, Journal of Information Technology - Special Issues in Artificial Intelligence, tom 20, nr 4 s. 163-181, grudzień 2008, ISSN  0128-3790 .
• N. Monmarché, F. Guinand i P. Siarry (red.), "Sztuczne mrówki", sierpień 2010 Hardback 576 s.  ISBN  978-1-84821-194-0 .
• A. Kazharov, V. Kureichik, 2010. „ Algorytmy optymalizacji kolonii mrówek do rozwiązywania problemów transportowych ”, Journal of Computer and Systems Sciences International, tom. 49. Nr 1. s. 30–43.
• CM. Pintea, 2014, Advances in Bio-inspired Computing for Combinatorial Optimization Problem , Springer ISBN  978-3-642-40178-7
• K. Saleem, N. Fisal, MA Baharudin, AA Ahmed, S. Hafizah i S. Kamilah, „Zainspirowany przez kolonię mrówek samooptymalizowany protokół routingu oparty na architekturze międzywarstwowej dla bezprzewodowych sieci czujników”, WSEAS Trans. Komunia, t. 9, nie. 10, s. 669-678, 2010. ISBN  978-960-474-200-4
• K. Saleem i N. Fisal, „Enhanced Ant Colony algorytm for self-optimized data assured routing in wireless sensor networks”, Sieci (ICON) 2012 18th IEEE International Conference on, s. 422-427. ISBN  978-1-4673-4523-1
• Abolmaali S, Roodposhti FR. Optymalizacja portfela przy użyciu metody kolonii mrówek studium przypadku na giełdzie w Teheranie. Dziennik Rachunkowości. 2018 marzec;8(1).

Zewnętrzne linki

• Strona Optymalizacja kolonii mrówek w Scholarpedii
• Strona główna optymalizacji kolonii mrówek
• "Optymalizacja kolonii mrówek" - rosyjskie środowisko naukowo-badawcze
• AntSim - symulacja algorytmów kolonii mrówek
• MIDACO-Solver Oprogramowanie optymalizacyjne ogólnego przeznaczenia oparte na optymalizacji kolonii mrówek (Matlab, Excel, VBA, C/C++, R, C#, Java, Fortran i Python)
• University of Kaiserslautern, Niemcy, AG Wehn: Ant Colony Optimization Applet Wizualizacja Travelling Salesman rozwiązywana przez system mrówkowy z licznymi opcjami i parametrami (Java Applet)
• Symulator farmy mrówek
• Symulacja algorytmu mrówek (aplet Java)
• Struktura systemu Java Ant Colony