Algorytmy optymalizacji kolonii mrówek

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 przypadkowy. Jednak ci, którzy wybierają krótszą drogę, szybciej docierają do pożywienia i dlatego częściej przemieszczają się tam iz powrotem między mrowiskiem a pokarmem.

W informatyce i badaniach operacyjnych algorytm optymalizacji kolonii mrówek ( ACO ) jest probabilistyczną techniką rozwiązywania problemów obliczeniowych, które można sprowadzić do znajdowania dobrych ścieżek w grafach . Sztuczne mrówki to wieloagentowe metody inspirowane zachowaniem prawdziwych mrówek . Komunikacja mrówek biologicznych oparta na feromonach jest często dominującym stosowanym paradygmatem. Kombinacje sztucznych mrówek i lokalnych algorytmów wyszukiwania stały się metodą wybieraną w wielu zadaniach optymalizacyjnych obejmujących pewien rodzaj grafu , np. trasy pojazdów i trasy internetowe .

Na przykład optymalizacja kolonii mrówek to klasa algorytmów optymalizacyjnych wzorowanych na działaniach kolonii mrówek . Sztuczne „mrówki” (np. agenty symulacyjne) lokalizują optymalne rozwiązania, poruszając się po przestrzeni parametrów reprezentującej wszystkie możliwe rozwiązania. Prawdziwe mrówki rozkładają feromony , kierując się wzajemnie do zasobów podczas eksploracji otoczenia. Symulowane „mrówki” podobnie 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 pewną metaheurystyczną optymalizację. Pierwotnie zaproponowany przez Marco Dorigo w 1992 roku w jego rozprawie doktorskiej, pierwszy algorytm miał na celu poszukiwanie optymalnej ścieżki na wykresie, w oparciu o zachowanie mrówek poszukujących ścieżki między ich kolonią a źródłem pożywienia. Od tego czasu pierwotny pomysł został zdywersyfikowany, aby rozwiązać szerszą klasę problemów numerycznych, w wyniku czego pojawiło się kilka problemów, opierając się na różnych aspektach zachowania mrówek. Z szerszej perspektywy ACO przeprowadza wyszukiwanie oparte na modelach i ma pewne podobieństwa z algorytmami szacowania 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, wyznaczając szlaki feromonowe . Jeśli inne mrówki znajdą taką ścieżkę, prawdopodobnie nie będą dalej podróżować w sposób losowy, ale zamiast tego podążą śladem, wracając i wzmacniając go, jeśli w końcu znajdą pożywienie (patrz Komunikacja mrówek ) .

Z czasem jednak ślad feromonowy zaczyna odparowywać, zmniejszając w ten sposób jego siłę atrakcyjną. Im więcej czasu zajmuje mrówce przejście ścieżki iz powrotem, tym więcej czasu mają feromony na odparowanie. Dla porównania, krótka ścieżka jest częściej przemaszerowana, a zatem 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 wybierane przez pierwsze mrówki byłyby nadmiernie atrakcyjne dla kolejnych. W takim przypadku eksploracja przestrzeni rozwiązań byłaby ograniczona. Wpływ parowania feromonów w rzeczywistych systemach mrówek jest niejasny, ale jest bardzo ważny w systemach sztucznych.

Ogólny wynik jest taki, że gdy jedna mrówka znajdzie dobrą (tj. krótką) ścieżkę z kolonii do źródła pożywienia, inne mrówki z większym prawdopodobieństwem pójdą tą drogą, 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 za pomocą „symulowanych mrówek” chodzących po wykresie przedstawiającym problem do rozwiązania.

Sieci otoczenia obiektów inteligentnych

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 tworzenia 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. Otaczające sieci inteligentnych obiektów i prędzej czy później nowa generacja systemów informatycznych, które są jeszcze bardziej rozproszone i oparte na nanotechnologii, gruntownie 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 sklasyfikować jako dość ograniczoną. Niemożliwe jest na przykład zintegrowanie wysokowydajnego kalkulatora zdolnego do rozwiązywania dowolnego problemu matematycznego w biochipie, który jest wszczepiany w ludzkie ciało lub zintegrowany z inteligentnym znacznikiem przeznaczonym do śledzenia artykułów handlowych. Jednak po połączeniu tych obiektów dysponują one pewną 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 oferuje kilka przykładów tego, jak maleńkie organizmy, jeśli wszystkie kierują się tą samą podstawową zasadą, mogą stworzyć formę zbiorowej inteligencji na poziomie makroskopowym. Kolonie owadów społecznych doskonale ilustrują ten model, który znacznie różni się od społeczeństw ludzkich. Model ten opiera się na współpracy niezależnych jednostek o prostym i nieprzewidywalnym zachowaniu. Poruszają się po okolicy, aby wykonać określone zadania i posiadają bardzo ograniczoną ilość informacji, aby to zrobić. Na przykład kolonia mrówek reprezentuje liczne cechy, które można również zastosować do sieci otaczających obiektów. Kolonie mrówek mają bardzo dużą zdolność przystosowania się do zmian w środowisku, a także ogromną siłę radzenia sobie w sytuacjach, gdy jeden osobnik nie wywiązuje się z danego zadania. Tego rodzaju elastyczność byłaby również bardzo przydatna dla sieci mobilnych obiektów, które nieustannie się rozwijają. Pakiety informacji, które przechodzą z komputera do obiektu cyfrowego, zachowują się tak samo, jak mrówki. Poruszają się po sieci i przechodzą od jednego węzła do drugiego w celu jak najszybszego dotarcia do miejsca docelowego.

System sztucznych feromonów

Komunikacja za pomocą feromonów jest jednym 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 dla komunikacji między agentami, jak i komunikacji między agentami. Ze względu na wykonalność sztuczne feromony zostały przyjęte w systemach robotów wielorobotowych i rojowych. Komunikacja oparta na feromonach została wdrożona różnymi środkami, takimi jak środki chemiczne lub fizyczne (tagi RFID, światło, dźwięk). Jednak te implementacje nie były w stanie odtworzyć wszystkich aspektów feromonów widocznych w naturze.

Wykorzystanie rzutowanego światła zostało przedstawione w artykule IEEE z 2007 r. autorstwa Garniera, Simona i in. jako eksperymentalna konfiguracja do badania komunikacji opartej na feromonach z mikro autonomicznymi robotami. W innym badaniu przedstawiono system, w którym feromony zostały wprowadzone za pośrednictwem poziomego ekranu LCD, po którym poruszały się roboty, przy czym roboty miały czujniki światła skierowane w dół, aby rejestrować wzory pod nimi.

Algorytm i formuła

W algorytmach optymalizacji kolonii mrówek sztuczna mrówka jest prostym agentem obliczeniowym, który szuka dobrych rozwiązań zadanego problemu optymalizacyjnego. Aby zastosować algorytm kolonii mrówek, problem optymalizacji należy przekształcić w problem znalezienia najkrótszej ścieżki na wykresie ważonym. W pierwszym kroku każdej iteracji każda mrówka stochastycznie konstruuje rozwiązanie, tj. kolejność, w jakiej należy podążać za krawędziami wykresu. W drugim etapie porównuje się ścieżki znalezione przez różne mrówki. Ostatni krok polega na aktualizacji poziomów feromonów na każdej krawędzi.

    
 procedura  ACO_MetaHeuristic  nie  została jeszcze   zakończona  do  generateSolutions() daemonActions() pheromoneUpdate()  powtórz  koniec procedury 

Wybór krawędzi

Każda mrówka musi skonstruować rozwiązanie, aby przejść przez wykres. 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 etapie algorytmu każda mrówka przechodzi ze stanu $.$ stanu pełniejszemu rozwiązaniu pośredniemu $W$ ten sposób każda mrówka $do$ zestaw swojego obecnego stanu w każdej iteracji i przechodzi do jednego z Dla mrówki ${$ przejścia ze stanu do stanu zależy od kombinacji $}$$^ {k$$xy}$ η ${\ Displaystyle \ eta _ {xy}}$ ruchu, obliczona za pomocą heurystyki wskazującej a priori celowość tego ruchu i poziom szlaku $}}$${\ Displaystyle \ tau _ {xy$ ruchu, wskazując, jak biegły był w przeszłości, aby wykonać ten konkretny ruch. Poziom śladu reprezentuje a posteriori wskazanie celowości tego ruchu.

Ogólnie rzecz biorąc, $k {\$ przechodzi ze stanu $displaystyle$ stanu $k}$ prawdopodobieństwem

$\ Displaystyle p_ {xy} ^ {k }={\frac {(\tau _{xy}^{\alpha})(\eta _{xy}^{\beta})}{\sum _{z\in \mathrm {dozwolone} _{x} }(\tau _{xz}^{\alfa})(\eta _{xz}^{\beta})}}}$

gdzie ${\ Displaystyle \ tau _ {xy}}$ to ilość feromonu zdeponowanego w celu przejścia ze stanu do $,$${\ Displaystyle y}$ 0 ≤ ${\ Displaystyle \ alpha}$ jest parametrem τ x y { \ Displaystyle \ tau _ τ ${\ Displaystyle \ tau _ {xy}}$ , ${\ Displaystyle \ eta _ {xy}}$ pożądana zmiana stanu ${\ Displaystyle xy}$ ( wiedza a priori , zazwyczaj ${\ Displaystyle 1/d_ {xy}}$ , gdzie ${\ Displaystyle d}$ to odległość) i ${\ Displaystyle \ beta}$ ≥ 1 to parametr kontrolujący wpływ ${ \displaystyle \eta _{xy}}$ . ${\ displaystyle \ tau _ {xz}}$$poziom$ szlaku i atrakcyjność dla innych możliwych przejść między stanami

Aktualizacja feromonów

Ślady są zwykle aktualizowane, gdy wszystkie mrówki zakończą 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} \ lewa strzałka (1- \ rho) \ tau _ {xy} + \ suma _ {k }^{m}\Delta \tau _{xy}^{k}}$

gdzie ${\ Displaystyle \ tau _ {xy}}$ to ilość feromonu zdeponowanego w celu przejścia stanu ${\ Displaystyle xy}$ , ${\ Displaystyle \ rho}$ to współczynnik parowania feromonów , ${\ Displaystyle m }$ to liczba mrówek i to ilość feromonu zdeponowanego przez $k$ , zwykle podawana w przypadku problemu z TSP $}}$ (z ruchami odpowiadającymi łukom wykresu) wg

${\ Displaystyle \ Delta \ tau _ {xy} ^ {k} = {\ rozpocząć {przypadki} Q / L_ {k} &{\mbox{if ant }}k{\mbox{ używa krzywej }}xy{\mbox{ w swojej trasie}}\\0&{\mbox{inaczej}}\end{przypadki}}}$

gdzie $jest$ kosztem $jest$$,$ a stałą.

Wspólne rozszerzenia

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

System mrówkowy (AS)

System mrówkowy jest pierwszym algorytmem ACO. Algorytm ten odpowiada algorytmowi przedstawionemu powyżej. Został opracowany przez Dorigo.

System kolonii mrówek (ACS)

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

1. Wybór krawędzi jest ukierunkowany 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 wybieranych przez siebie krawędzi, 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 na świecie rozwiązanie osadza feromon na swoim śladzie po każdej iteracji (nawet jeśli ten ślad nie był ponownie odwiedzany) wraz ze wszystkimi innymi mrówkami. Strategia elitarna ma na celu skierowanie poszukiwań wszystkich mrówek w celu skonstruowania rozwiązania zawierającego powiązania aktualnej najlepszej trasy.

System mrówek max-min (MMAS)

Algorytm ten kontroluje maksymalne i minimalne ilości feromonów na każdym szlaku. Tylko najlepsza trasa na świecie lub najlepsza trasa iteracji może dodawać feromony do swojego śladu. 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 na τ _max , aby wymusić wyższą 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 uszeregowane są według 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 ścieżkach odkładają więcej feromonu niż roztwory o dłuższych ścieżkach.

Równoległa optymalizacja kolonii mrówek (PACO)

Opracowano system kolonii mrówek (ACS) ze strategiami komunikacyjnymi. Sztuczne mrówki są podzielone na kilka grup. Zaproponowano siedem metod komunikacji do aktualizacji poziomu feromonów między grupami w ACS, które pracują nad problemem komiwojażera.

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

Mechanizm odkładania się feromonów COAC ma umożliwić mrówkom wspólne i skuteczne poszukiwanie rozwiązań. Korzystając z ortogonalnej metody 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ę dopasowania promienia adaptacyjnego można również rozszerzyć na inne algorytmy optymalizacji, aby zapewnić szersze 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 subdomen i rozwiązuje cel na tych subdomenach. Wyniki ze wszystkich subdomen są porównywane i kilka najlepszych z nich awansuje na wyższy poziom. Poddomeny odpowiadające wybranym wynikom są dalej dzielone, a proces jest powtarzany, aż do uzyskania danych wyjściowych o pożądanej precyzji. Ta metoda została przetestowana na źle postawionych problemach inwersji geofizycznej i działa dobrze.

Konwergencja

Dla niektórych wersji algorytmu można wykazać, że jest on zbieżny (tj. jest w stanie znaleźć optimum globalne w skończonym czasie). Pierwszy dowód zbieżności algorytmu kolonii mrówek uzyskano w 2000 r., Algorytm systemu mrówek oparty na grafach, a później algorytmy ACS i MMAS. Podobnie jak większość metaheurystyk , oszacowanie teoretycznej szybkości zbieżności jest bardzo trudne. Analiza wydajności algorytmu ciągłej kolonii mrówek w odniesieniu do jego różnych parametrów (strategia wyboru krawędzi, metryka miary 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 opadania gradientu , na krzyżową entropię i algorytm estymacji rozkładu . Zaproponowali te metaheurystyki jako „model oparty na badaniach”.

Aplikacje

Problem plecakowy : mrówki wolą mniejszą kroplę miodu niż obfitszy, ale mniej pożywny cukier

Algorytmy optymalizacji kolonii mrówek zostały zastosowane do wielu kombinatorycznych problemów optymalizacyjnych, począwszy od przypisania kwadratowego do pojazdów zwijania lub trasowania białek , a wiele metod pochodnych zostało dostosowanych do dynamicznych problemów ze zmiennymi rzeczywistymi, problemów stochastycznych, wielu celów i implementacji równoległych . Został również wykorzystany do stworzenia prawie optymalnych rozwiązań problemu komiwojażera . Mają przewagę nad symulowanego wyżarzania i algorytmów genetycznych do podobnych problemów, gdy wykres może zmieniać się dynamicznie; 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 przypadku tras sieciowych i systemów transportu miejskiego.

Pierwszy algorytm ACO nosił nazwę systemu mrówkowego i miał na celu rozwiązanie problemu komiwojażera, w którym celem jest znalezienie najkrótszej podróży w obie strony, aby połączyć szereg miast. Ogólny algorytm jest stosunkowo prosty i oparty na zestawie mrówek, z których każda wykonuje jedną z możliwych podróży w obie strony wzdłuż miast. Na każdym etapie mrówka wybiera przejście z jednego miasta do drugiego zgodnie z pewnymi zasadami:

Wizualizacja algorytmu kolonii mrówek zastosowanego do problemu komiwojażera. Zielone linie to ścieżki wybrane przez każdą mrówkę. Niebieskie linie to ścieżki, którymi może podążać w każdym punkcie. Kiedy mrówka kończy, poziomy feromonów są reprezentowane na czerwono.

1. Musi odwiedzić każde miasto dokładnie raz;
2. Odległe miasto ma mniejsze szanse na wybór (widoczność);
3. Im intensywniejszy ślad feromonowy wytyczony na krawędzi 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, które pokonała, jeśli podróż jest krótka;
5. Po każdej iteracji ślady feromonów odparowują.

Problem z harmonogramem

• Problem z kolejnością sekwencyjną (SOP)
• z planowaniem pracy w sklepie (JSP)
• z harmonogramem otwartego sklepu (OSP)
• Problem sklepu z przepływem permutacji (PFSP)
• Problem całkowitego spóźnienia pojedynczej maszyny (SMTTP)
• Całkowity ważony problem spóźnienia pojedynczej maszyny (SMTWTP)
• Problem z planowaniem projektów z ograniczonymi zasobami (RCPSP)
• Problem z planowaniem sklepu grupowego (GSP)
• Całkowity problem spóźnienia pojedynczej maszyny z czasami ustawiania zależnymi od sekwencji (SMTTPDST)
• Wieloetapowy problem planowania flowshop (MFSP) z czasem konfiguracji/przełączenia zależnym od sekwencji
• Problemy planowania sekwencji montażu (ASP).

Problem z wyznaczaniem tras pojazdów

• Problem z wyznaczaniem trasy pojazdu z pojemnością (CVRP)
• Problem z trasowaniem pojazdów w wielu zajezdniach (MDVRP)
• Problem z trasowaniem pojazdu z epoki (PVRP)
• Problem z wyznaczaniem tras dla pojazdów dostawczych (SDVRP)
• Stochastyczny problem wyznaczania tras pojazdów (SVRP)
• Problem z wyznaczaniem trasy pojazdu z odbiorem i dostawą (VRPPD)
• Problem z wyznaczaniem tras pojazdów z oknami czasowymi (VRPTW)
• Zależny od czasu problem wyznaczania tras pojazdów z oknami czasowymi (TDVRPTW)
• Problem z wyznaczaniem tras pojazdów z oknami czasowymi i wieloma pracownikami serwisu (VRPTWMS)

Problem z przydziałem

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

Ustaw problem

• Problem z okładką zestawu (SCP)
• Problem z partycją (SPP)
• Problem partycji drzewa grafów z ograniczeniami wagowymi (WCGTPP)
• Problem drzewa l-liczności ważony łukiem (AWlCTP)
• Problem z wieloma plecakami (MKP)
• Maksymalny problem zbioru niezależnego (MIS)

Problem wymiarowania urządzeń w fizycznym projektowaniu nanoelektroniki

• Optymalizacja kolonii mrówek (ACO) oparta na optymalizacji obwodu wzmacniacza sensownego opartego na 45 nm CMOS może doprowadzić do optymalnych rozwiązań w bardzo krótkim czasie.
• Synteza obwodów odwracalnych oparta na optymalizacji 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. Przykładem mogą być 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 2-D, a mrówki przechodzą od jednego piksela osadzając feromon. Ruch mrówek z jednego piksela do drugiego jest kierowany przez lokalną zmianę wartości intensywności obrazu. Ten ruch powoduje, że największa gęstość feromonu osadza się na krawędziach.

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

Krok 1: Inicjalizacja. Losowo $umieść$$=$ obrazie $)$ ∗ . Matryce $_$ _ Głównym wyzwaniem w procesie inicjalizacji jest określenie macierzy heurystycznej.

Istnieją różne metody określania macierzy heurystycznej. W poniższym przykładzie macierz heurystyczna została obliczona na podstawie lokalnych statystyk: lokalnych statystyk w pozycji piksela ${\ Displaystyle (i, j)}$ .

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

gdzie ${\ displaystyle I}$ to obraz o rozmiarze ${\ Displaystyle M_ {1} * M_ {2}}$ ,

${\ Displaystyle Z = \ suma _ {i = 1: M_ {1}} \ suma _ {j = 1: M_{2}}Vc(I_{i,j})}$

jest czynnikiem normalizującym, i

${\ Displaystyle {\ begin{aligned}Vc(I_{i,j})=&f\left(\left\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)\ koniec {wyrównany}}}$

${\ Displaystyle f (\ cdot)}$ można obliczyć za pomocą następujących funkcji:

${\ 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) = {\ rozpocząć {przypadki} \ sin ({\ Frac {\ pi x} {2 \ lambda}}) i {\ tekst {dla 0 ≤ x ≤}} \lambda {\tekst{; (3)}}\\0,&{\text{else}}\end{przypadków}}}$

${\ Displaystyle f (x) = {\ rozpocząć {przypadki} \ pi x \ sin ({\ Frac {\ pi x} {2 \ lambda}}) i {\ tekst {dla 0 ≤ x ≤}}\lambda {\tekst{; (4)}}\\0,&{\text{else}}\end{przypadki}}}$

Parametr w każdej z $powyższych funkcji dostosowuje odpowiednie$ 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 ${\ Displaystyle P_ {x, y}}$

Krok 3 i Krok 5: Proces aktualizacji. Matryca feromonów jest dwukrotnie aktualizowana. w kroku 3 ślad mrówki (podany przez $podana$ kroku 5 aktualizowana jest szybkość parowania śladu, przez:

${\ Displaystyle \ tau _ {nowy} \ strzałka w lewo (1- \ psi) \ tau _ {stary} + \ psi \ tau _ {0}}$ ,

gdzie ${\ Displaystyle \ psi}$ jest współczynnikiem rozpadu feromonów ${\ Displaystyle 0 <\ tau <1}$

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

Krawędzie obrazu wykryte za pomocą ACO: Poniższe obrazy są generowane przy użyciu różnych funkcji podanych w równaniach (1) do (4).

• Łączenie brzegowe: ACO okazało się również skuteczne w algorytmach łączenia brzegowego.

Inne aplikacje

• Przewidywanie upadłości
• Klasyfikacja
• Routing sieciowy zorientowany na połączenie
• Bezpołączeniowy routing sieciowy
• Eksploracja danych
• Zdyskontowane przepływy pieniężne w harmonogramowaniu projektów
• Rozproszone wyszukiwanie informacji
• Projektowanie sieci energetycznych i elektroenergetycznych
• Problem z harmonogramem przepływu pracy w siatce
• Projekt peptydu hamującego dla interakcji białek z białkami
• Inteligentny system testowania
• Projektowanie układów energoelektronicznych
• Fałdowanie białek
• Identyfikacja systemu

Definicja trudności

W przypadku algorytmu ACO najkrótsza ścieżka na wykresie, między dwoma punktami A i B, jest tworzona z kombinacji kilku ścieżek. Nie jest łatwo podać dokładną definicję algorytmu, który jest lub 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 zaznaczają najlepsze rozwiązania i biorą pod uwagę 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 algorytmów (takich jak algorytmy szacowania rozkładu czy optymalizacji roju cząstek) jest właśnie ich aspekt konstrukcyjny. W problemach kombinatorycznych możliwe jest ostatecznie znalezienie najlepszego rozwiązania, nawet jeśli żadna mrówka nie okazałaby się skuteczna. Tak więc w przykładzie problemu komiwojażera nie jest konieczne, aby mrówka faktycznie podróżowała najkrótszą trasą: najkrótszą trasę można zbudować z najsilniejszych segmentów najlepszych rozwiązań. Jednak ta definicja może być problematyczna w przypadku problemów ze zmiennymi rzeczywistymi, gdzie nie istnieje struktura „sąsiadów”. Zbiorowe zachowanie owadów społecznych pozostaje źródłem inspiracji dla badaczy. Szeroka gama algorytmów (do optymalizacji lub nie) poszukujących samoorganizacji w systemach biologicznych doprowadziła do koncepcji „ inteligencji roju ”, która jest bardzo ogólną ramą, w której mieszczą się algorytmy kolonii mrówek.

Algorytmy stygmagiczne

W praktyce istnieje duża liczba algorytmów, które twierdzą, że są „koloniami mrówek”, bez zawsze wspólnych ogólnych ram optymalizacji według kanonicznych kolonii mrówek. W praktyce wykorzystanie wymiany informacji między mrówkami za pośrednictwem środowiska (zasada zwana „ stygmerią ”) uznaje się za wystarczające, aby algorytm zaliczyć do klasy algorytmów kolonii mrówek. Ta zasada skłoniła niektórych autorów do stworzenia terminu „wartość” w celu uporządkowania metod i zachowań opartych na poszukiwaniu pożywienia, sortowaniu larw, podziale pracy i transporcie spółdzielczym.

Powiązane metody

Algorytmy genetyczne (GA)

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

Algorytm estymacji rozkładu (EDA)

Algorytm ewolucyjny , który zastępuje tradycyjne operatory reprodukcji operatorami sterowanymi modelami. Takich modeli uczy się od populacji za pomocą technik uczenia maszynowego i przedstawia w postaci probabilistycznych modeli graficznych, z których można pobierać próbki nowych rozwiązań lub generować je na podstawie krzyżowania z przewodnikiem.

Symulowane wyżarzanie (SA)

Powiązana technika optymalizacji globalnej, która przemierza przestrzeń poszukiwań, generując sąsiednie rozwiązania bieżącego rozwiązania. Lepszy sąsiad jest zawsze akceptowany. Podrzędny sąsiad jest akceptowany probabilistycznie na podstawie różnicy w jakości i parametrze temperatury. Parametr temperatury jest modyfikowany w miarę postępu algorytmu w celu zmiany charakteru wyszukiwania.

Reaktywna optymalizacja wyszukiwania

Koncentruje się na połączeniu uczenia maszynowego z optymalizacją, dodając wewnętrzną pętlę sprzężenia zwrotnego w celu samoczynnego dostrojenia wolnych parametrów algorytmu do charakterystyki problemu, instancji i lokalnej sytuacji wokół bieżącego rozwiązania.

Wyszukiwanie z Tabu (TS)

Podobne do symulowanego wyżarzania, ponieważ oba przechodzą przez przestrzeń rozwiązań, testując mutacje indywidualnego 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ższym dopasowaniu spośród wygenerowanych. Aby zapobiec cyklom i zachęcić do większego ruchu w przestrzeni rozwiązań, prowadzona jest lista tabu częściowych lub kompletnych rozwiązań. Zabrania się przechodzenia do rozwiązania, które zawiera elementy z 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)

Metoda inteligencji roju .

Inteligentne krople wody (IWD)

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

Algorytm wyszukiwania grawitacyjnego (GSA) Metoda

inteligencji roju .

Metoda grupowania kolonii mrówek (ACCM)

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

Stochastyczne przeszukiwanie dyfuzyjne (SDS)

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

Historia

Chronologia algorytmów COA

Chronologia algorytmów optymalizacji kolonii mrówek.

• 1959 Pierre-Paul Grassé wynalazł teorię stygmatyzacji , aby wyjaśnić zachowanie termitów podczas budowania gniazd ;
• 1983 , Deneubourg i jego współpracownicy badali zbiorowe zachowanie mrówek ;
• 1988 i Moyson Manderick mają artykuł o samoorganizacji wśród mrówek;
• 1989, praca Gossa, Arona, Deneubourga i Pasteelsa dotycząca zbiorowego zachowania mrówek argentyńskich , która da pomysł na algorytmy optymalizacji kolonii mrówek;
• 1989, wdrożenie modelu zachowania wobec żywności przez Eblinga i jego współpracowników;
• 1991, M. Dorigo zaproponował system mrówkowy w swojej pracy doktorskiej (która została opublikowana w 1992). Raport techniczny wyodrębniony z pracy, którego współautorami są V. Maniezzo i A. Colorni, został opublikowany pięć lat później;
• 1994, Appleby i Steward z British Telecommunications Plc opublikowali pierwszą aplikację do sieci telekomunikacyjnych
• 1995, Gambardella i Dorigo zaproponowali ant-q , wstępną wersję systemu kolonii mrówek jako pierwszą wersję systemu mrówek;
• 1996, Gambardella i Dorigo zaproponowali system kolonii mrówek
• 1996, publikacja artykułu o systemie mrówkowym;
• 1997, Dorigo i Gambardella zaproponowali hybrydyzację systemu kolonii mrówek z wyszukiwaniem lokalnym;
• 1997, Schoonderwoerd i jego współpracownicy opublikowali ulepszoną aplikację do sieci telekomunikacyjnych ;
• 1998, Dorigo organizuje pierwszą konferencję poświęconą algorytmom ACO;
• 1998, Stützle proponuje wstępne równoległe implementacje ;
• 1999, Gambardella, Taillard i Agazzi zaproponowali macs-vrptw , pierwszy system wielu kolonii mrówek zastosowany do problemów z wyznaczaniem tras pojazdów z oknami czasowymi,
• 1999, Bonabeau, Dorigo i Theraulaz publikują książkę zajmującą się głównie sztucznymi mrówkami
• 2000, wydanie specjalne czasopisma Future Generation Computer Systems poświęcone algorytmom mrówek
• 2000, Hoos i Stützle wymyślają system mrówek max-min ;
• 2000 r., pierwsze zastosowania do harmonogramowania , sekwencja harmonogramowania i spełnianie 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 );
• W 2001 roku Iredi i jego współpracownicy opublikowali pierwszy algorytm wielocelowy
• 2002, pierwsze zastosowania w projektowaniu harmonogramów, sieci bayesowskie;
• 2002, Bianchi i jej współpracownicy zaproponowali pierwszy algorytm dla problemu stochastycznego ;
• 2004, Dorigo i Stützle publikują książkę Ant Colony Optimization we współpracy z MIT Press
• 2004, Zlochin i Dorigo pokazują, że niektóre algorytmy są równoważne stochastycznemu opadaniu gradientu , metodzie entropii krzyżowej i algorytmom szacowania rozkładu
• 2005, pierwsze zastosowania do problemów fałdowania białek .
• 2012, Prabhakar i współpracownicy publikują badania dotyczące działania poszczególnych mrówek komunikujących się w tandemie bez feromonów, odzwierciedlając zasady organizacji sieci komputerowej. Model komunikacji porównano z protokołem kontroli transmisji .
• 2016, pierwsze zastosowanie do projektowania sekwencji peptydów.
• 2017, udana integracja wielokryterialnej metody podejmowania decyzji PROMETHEE z algorytmem ACO ( algorytm HUMANT ).

Publikacje (wybrane)

• M. Dorigo , 1992. Optymalizacja, uczenie się i naturalne algorytmy , praca doktorska, Politecnico di Milano, Włochy.
• M. Dorigo, V. Maniezzo i A. Colorni, 1996. „ System mrówek: optymalizacja przez kolonię agentów współpracujących ”, 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 do 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, „Planowanie ruchu robotów przegubowych z wykorzystaniem strategii zbierania 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 r. Oprawa twarda 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, Postępy w obliczeniach inspirowanych biologią dla problemu optymalizacji kombinatorycznej , Springer ISBN 978-3-642-40178-7
•   K. Saleem, N. Fisal, MA Baharudin, AA Ahmed, S. Hafizah i S. Kamilah, „Samodzielnie zoptymalizowany protokół routingu inspirowany kolonią mrówek oparty na architekturze międzywarstwowej dla bezprzewodowych sieci czujników”, WSEAS Trans. Komuna, tom. 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 safe routing in wireless sensor networks”, Networks (ICON) 2012 18th International Conference IEEE 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).

Linki zewnętrzne

• Scholarpedia Strona optymalizacji kolonii mrówek
• 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 do optymalizacji 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 komiwojażera rozwiązana przez system mrówek z licznymi opcjami i parametrami (aplet Java)
• Symulator farmy mrówek
• Symulacja algorytmu Ant (aplet Java)
• Struktura systemu Java Ant Colony
• Implementacja algorytmu optymalizacji kolonii mrówek (notatnik Pythona)