Lista metaheurystyk opartych na metaforach - List of metaphor-based metaheuristics

Jest to uporządkowana chronologicznie lista metaheurystyk opartych na metaforach i algorytmów inteligencji roju .

Algorytmy

Symulowane wyżarzanie (Kirkpatrick i in., 1983)

Symulowane wyżarzanie (SA) to technika probabilistyczna inspirowana metodą obróbki cieplnej w metalurgii . Jest często używany, gdy przestrzeń wyszukiwania jest dyskretna (np. wszystkie wycieczki, które odwiedzają dany zbiór miast). W przypadku problemów, w których znalezienie dokładnego globalnego optimum jest mniej ważne niż znalezienie akceptowalnego lokalnego optimum w ustalonym czasie, symulowane wyżarzanie może być lepsze niż alternatywy, takie jak opadanie gradientowe .

Symulowane wyżarzanie interpretuje powolne chłodzenie jako powolny spadek prawdopodobieństwa zaakceptowania gorszych rozwiązań podczas eksploracji przestrzeni rozwiązania. Akceptowanie gorszych rozwiązań jest podstawową właściwością metaheurystyk, ponieważ pozwala na szersze poszukiwanie rozwiązania optymalnego.

Optymalizacja kolonii mrówek (Dorigo, 1992)

Algorytm optymalizacji kolonii mrówek (ACO) to probabilistyczna technika rozwiązywania problemów obliczeniowych, którą można sprowadzić do znalezienia dobrych ścieżek przez grafy . Po raz pierwszy zaproponowany przez Marco Dorigo w 1992 r. 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 algorytmami szacowania dystrybucji .

Optymalizacja roju cząstek (Kennedy i Eberhart, 1995)

Optymalizacja roju cząstek (PSO) to metoda obliczeniowa, która optymalizuje problem poprzez iteracyjne próby poprawy potencjalnego rozwiązania w odniesieniu do danej miary jakości. Rozwiązuje problem, mając populację potencjalnych rozwiązań, tutaj nazwanych cząstkami , i przesuwając te cząstki w przestrzeni poszukiwań zgodnie z prostymi wzorami matematycznymi nad położeniem i prędkością cząstki . Na ruch każdej cząstki wpływa jej najlepiej znana lokalna pozycja, ale jest ona również kierowana w kierunku najbardziej znanych pozycji w przestrzeni poszukiwań, które są aktualizowane w miarę znajdowania lepszych pozycji przez inne cząstki. Oczekuje się, że przesunie to rój w kierunku najlepszych rozwiązań.

PSO jest pierwotnie przypisywana Kennedy'emu , Eberhartowi i Shi i była początkowo przeznaczona do symulowania zachowań społecznych , jako stylizowana reprezentacja ruchu organizmów w ptasim stadzie lub ławicy ryb . Algorytm został uproszczony i zaobserwowano, że przeprowadza optymalizację. Książka Kennedy'ego i Eberharta opisuje wiele filozoficznych aspektów PSO i inteligencji roju . Poli przeprowadza obszerny przegląd aplikacji PSO . Niedawno Bonyadi i Michalewicz opublikowali obszerny przegląd prac teoretycznych i eksperymentalnych dotyczących PSO.

Poszukiwanie harmonii (Geem, Kim i Loganathan, 2001)

Wyszukiwanie harmonii to metaheurystyka naśladująca zjawisko, wprowadzona w 2001 roku przez Zong Woo Geema, Joong Hoon Kima i GV Loganathana. Poszukiwanie harmonii inspirowane jest procesem improwizacji muzyków jazzowych. W artykule stwierdzono, że wyszukiwanie harmonii jest szczególnym przypadkiem algorytmu strategii ewolucji . Jednak ostatni artykuł twierdzi, że struktura Strategii Ewolucji różni się od struktury poszukiwania harmonii.

Przeszukiwanie harmonii (HS) jest stosunkowo prostym, ale wydajnym algorytmem ewolucyjnym. W algorytmie HS zestaw możliwych rozwiązań jest generowany losowo (tzw. pamięć Harmony). Nowe rozwiązanie jest generowane przez użycie wszystkich rozwiązań w pamięci Harmony (a nie tylko dwóch, jak w GA) i jeśli to nowe rozwiązanie jest lepsze niż najgorsze rozwiązanie w pamięci Harmony, to najgorsze rozwiązanie zostaje zastąpione tym nowym rozwiązaniem. Skuteczność i zalety HS zostały zademonstrowane w różnych zastosowaniach, takich jak projektowanie miejskich sieci wodociągowych, projektowanie konstrukcji, problem przenoszenia obciążenia w elektrotechnice, optymalizacja wielozadaniowa, problemy z harmonogramem, grupowanie oraz klasyfikacja i dobór cech. Szczegółowy przegląd zastosowań HS można znaleźć w oraz zastosowania HS w eksploracji danych można znaleźć w.

Algorytm sztucznej kolonii pszczół (Karaboga, 2005)

Algorytm sztucznej kolonii pszczół jest algorytmem metaheurystycznym wprowadzonym przez Karabogę w 2005 roku i symuluje zachowanie żerowania pszczół miodnych. Algorytm ABC ma trzy fazy: pszczoła użytkowana, pszczoła gapiowska i pszczoła harcerska. W fazie zatrudnionej pszczoły i w fazie obserwacyjnej pszczoły eksploatują źródła poprzez lokalne poszukiwania w sąsiedztwie rozwiązań wybranych na podstawie selekcji deterministycznej w fazie zatrudnionej pszczoły i selekcji probabilistycznej w fazie obserwacyjnej. W fazie harcerskiej pszczoły, która jest analogią porzucania wyczerpanych źródeł pożywienia w procesie żerowania, porzuca się rozwiązania, które nie są już korzystne dla postępu poszukiwań, a zamiast nich wstawiane są nowe rozwiązania, aby eksplorować nowe regiony w przestrzeni poszukiwań. Algorytm ma dobrze wyważoną zdolność eksploracji i eksploatacji.

Algorytm pszczół (Pham, 2005)

Algorytm pszczół w swoim podstawowym sformułowaniu został stworzony przez Phama i jego współpracowników w 2005 roku i dopracowywany w kolejnych latach. Wzorowany na zachowaniach żerujących pszczół miodnych algorytm łączy globalne wyszukiwanie eksploracyjne z lokalnym wyszukiwaniem eksploatacyjnym. Niewielka liczba sztucznych pszczół (harcerzy) eksploruje losowo przestrzeń rozwiązań (środowisko) dla rozwiązań o wysokiej sprawności (wysoce opłacalne źródła pożywienia), podczas gdy większość populacji poszukuje (zbiera) sąsiedztwo najlepiej przystosowanych rozwiązań w poszukiwaniu optymalnej sprawności . Deterministyczna procedura rekrutacyjna, która symuluje taniec biologicznych pszczół, służy do przekazywania wyników zwiadowców zbieraczom i rozmieszczania zbieraczy w zależności od kondycji dzielnic wybranych do lokalnych poszukiwań. Gdy poszukiwania w sąsiedztwie rozwiązania ulegną stagnacji, uważa się, że lokalne optimum sprawności zostało znalezione, a teren zostaje opuszczony. Podsumowując, algorytm pszczół przeszukuje jednocześnie najbardziej obiecujące regiony przestrzeni rozwiązań, jednocześnie próbkując je w poszukiwaniu nowych korzystnych regionów.

Optymalizacja roju świetlików (Krishnanand i Ghose, 2005)

Optymalizacja roju świetlików to algorytm optymalizacji inteligencji roju opracowany na podstawie zachowania świetlików (znanych również jako świetliki lub błyskawice). Algorytm GSO został opracowany i wprowadzony przez KN Krishnananda i Debasish Ghose w 2005 roku w Laboratorium Systemów Przewodnictwa, Sterowania i Decyzji w Departamencie Inżynierii Kosmicznej w Indyjskim Instytucie Nauki w Bangalore w Indiach .

Wzorzec zachowania świetlików, który jest wykorzystywany w tym algorytmie, to pozorna zdolność świetlików do zmiany intensywności emisji lucyferyny, a tym samym wydaje się, że świecą z różną intensywnością.

1. Algorytm GSO sprawia, że ​​agenci świecą z intensywnością w przybliżeniu proporcjonalną do optymalizowanej wartości funkcji. Zakłada się, że świetliki o jaśniejszym natężeniu przyciągają świetliki o mniejszej intensywności.
2. Druga istotna część algorytmu obejmuje dynamiczny zakres decyzyjny, w którym efekt odległych świetlików jest dyskontowany, gdy świetlik ma wystarczającą liczbę sąsiadów lub zakres wykracza poza zakres percepcji świetlików.

Część 2 algorytmu odróżnia go od innych ewolucyjnych algorytmów optymalizacji multimodalnej . Jest to ten etap, który umożliwia Glowworm rojów aby automatycznie dzielą się na podgrupy, które mogą następnie zbiegają się wielokrotną miejscową optymalnych jednocześnie Ta właściwość algorytmu pozwala na zastosowanie do identyfikacji wielu pików multimodalnego funkcji i sprawia, że część składową rodzina ewolucyjnych algorytmów optymalizacji multimodalnej.

Algorytm przetasowania żaby (Eusuff, Lansey & Pasha, 2006)

Algorytm tasowanych żab skaczących jest algorytmem optymalizacyjnym stosowanym w sztucznej inteligencji . Jest porównywalny z algorytmem genetycznym .

Optymalizacja roju kotów (Chu, Tsai i Pan, 2006)

Algorytm optymalizacji roju kotów, który rozwiązuje problemy optymalizacji i jest inspirowany zachowaniem kotów. Jest podobny do innych algorytmów optymalizacji roju, takich jak Ant Colony Optimization lub Particle Swarm Optimization. Poszukiwanie i śledzenie, dwa typowe zachowania kotów, składają się na dwa podmodele algorytmu. Tryb szukania jest inspirowany zachowaniem kota w stanie spoczynku, który szuka kolejnego miejsca. W trybie szukania wybiera kilka kandydujących punktów, a następnie wybiera losowo jeden, do którego przejdzie, zwiększając prawdopodobieństwo wybrania punktów o wyższej wartości sprawności. Tryb śledzenia jest inspirowany kotem tropiącym jakiś cel. W tym trybie kot będzie próbował przesunąć się w kierunku pozycji o najlepszej kondycji. Koty będą się poruszać w trybie poszukiwania i śledzenia, dopóki nie zostanie spełniony warunek zakończenia.

Imperialistyczny algorytm rywalizacji (Atashpaz-Gargari i Lucas, 2007)

Imperialistyczny algorytm rywalizacji jest metodą obliczeniową, która służy do rozwiązywania różnego rodzaju problemów optymalizacyjnych . Jak większość metod z obszaru obliczeń ewolucyjnych , ICA nie potrzebuje gradientu funkcji w procesie optymalizacji. Z konkretnego punktu widzenia, ICA może być postrzegana jako społeczny odpowiednik algorytmów genetycznych (GA). ICA to model matematyczny i komputerowa symulacja ewolucji społecznej człowieka , podczas gdy GA opierają się na biologicznej ewolucji gatunków.

Algorytm ten rozpoczyna się od wygenerowania zbioru losowych rozwiązań kandydujących w przestrzeni przeszukiwania problemu optymalizacji. Wygenerowane losowe punkty nazywane są początkowymi Krajami . Kraje w tym algorytmie są odpowiednikami chromosomów w GA i cząstek w optymalizacji roju cząstek (PSO) i jest to tablica wartości potencjalnego rozwiązania problemu optymalizacyjnego. Funkcja kosztu problemu optymalizacji określa siłę każdego kraju. W oparciu o swoją siłę, niektóre z najlepszych początkowych krajów (kraje o najniższych wartościach funkcji kosztu), stają się imperialistami i zaczynają przejmować kontrolę nad innymi krajami (zwanymi koloniami ) i tworzą początkowe imperia .

Dwa główne operatory tego algorytmu to Asymilacja i Rewolucja . Asymilacja sprawia, że ​​kolonie każdego imperium zbliżają się do państwa imperialistycznego w przestrzeni cech społeczno-politycznych (przestrzeń poszukiwań optymalizacyjnych). Rewolucja powoduje nagłe, losowe zmiany pozycji niektórych krajów w przestrzeni poszukiwań. Podczas asymilacji i rewolucji kolonia może osiągnąć lepszą pozycję i ma szansę przejąć kontrolę nad całym imperium i zastąpić obecne imperialistyczne państwo imperium.

Konkurencja imperialistyczna to kolejna część tego algorytmu. Wszystkie imperia próbują wygrać tę grę i przejąć w posiadanie kolonie innych imperiów. Na każdym kroku algorytmu, w oparciu o swoją siłę, wszystkie imperia mają szansę przejąć kontrolę nad jedną lub kilkoma koloniami najsłabszego imperium.

Algorytm kontynuuje wykonywanie wspomnianych kroków (Asymilacja, Rewolucja, Konkurencja) aż do spełnienia warunku zatrzymania.

Powyższe kroki można podsumować jako poniższy pseudokod .

0) Define objective function: ${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$
1) Initialization of the algorithm. Generate some random solution in the search space and create initial empires.
    2) Assimilation: Colonies move towards imperialist states in different in directions.
    3) Revolution: Random changes occur in the characteristics of some countries.
    4) Position exchange between a colony and Imperialist. A colony with a better position than the imperialist,
       has the chance to take the control of empire by replacing the existing imperialist.
    5) Imperialistic competition: All imperialists compete to take possession of colonies of each other.
    6) Eliminate the powerless empires. Weak empires lose their power gradually and they will finally be eliminated.
    7) If the stop condition is satisfied, stop, if not go to 2.
8) End

Dynamika powstawania rzek (Rabanal, Rodríguez & Rubio, 2007)

Dynamika powstawania rzek opiera się na naśladowaniu sposobu, w jaki woda tworzy rzeki poprzez erozję gruntu i odkładanie osadów (krople działają jak rój). Po tym, jak krople przekształcają krajobraz, zwiększając/zmniejszając wysokość miejsc, rozwiązania podaje się w postaci ścieżek o malejących wysokościach. Tworzone są malejące gradienty, po których następują kolejne spadki, aby skomponować nowe gradienty i wzmocnić najlepsze. Ta heurystyczna metoda optymalizacji została po raz pierwszy zaprezentowana w 2007 r. przez Rabanala i in. Zbadano możliwość zastosowania RFD do innych problemów NP-zupełnych, a algorytm zastosowano w takich dziedzinach, jak wyznaczanie tras i nawigacja robotami. Główne zastosowania RFD można znaleźć w szczegółowej ankiecie.

Inteligentny algorytm kropli wody (Shah-Hosseini, 2007)

Inteligentny algorytm kropel wody zawiera kilka istotnych elementów naturalnych kropel wody oraz akcji i reakcji zachodzących między korytem rzeki a kropelkami wody płynącymi w jego obrębie. IWD został po raz pierwszy wprowadzony do problemu komiwojażera w 2007 roku.

Prawie każdy algorytm IWD składa się z dwóch części: grafu pełniącego rolę pamięci rozproszonej, na której zachowane są gleby o różnych krawędziach, oraz części ruchomej algorytmu IWD, czyli kilku inteligentnych kropel wody. Te inteligentne krople wody (IWD) współzawodniczą i współpracują ze sobą, aby znaleźć lepsze rozwiązania, a zmieniając gleby na wykresie, ścieżki do lepszych rozwiązań stają się bardziej osiągalne. Wspomniano, że algorytmy oparte na IWD wymagają do działania co najmniej dwóch IWD.

Algorytm IWD ma dwa rodzaje parametrów: parametry statyczne i dynamiczne. Parametry statyczne są stałe podczas procesu algorytmu IWD. Parametry dynamiczne są ponownie inicjowane po każdej iteracji algorytmu IWD. Pseudokod algorytmu opartego na IWD można określić w ośmiu krokach:

1) Inicjalizacja parametrów statycznych

a) Reprezentacja problemu w postaci grafu

b) Wartości nastaw dla parametrów statycznych

2) Dynamiczna inicjalizacja parametrów: gleba i prędkość IWD

3) Rozkład IWD na wykresie problemu

4) Konstrukcja rozwiązania za pomocą IWD wraz z aktualizacją gleby i prędkości

a) Lokalna aktualizacja gleby na wykresie

b) Aktualizacja gleby i prędkości na IWD

5) Lokalne wyszukiwanie w każdym rozwiązaniu IWD (opcjonalnie)

6) Globalna aktualizacja gleby

7) Całkowita najlepsza aktualizacja rozwiązania

8) Przejdź do kroku 2, chyba że warunek zakończenia jest spełniony

Grawitacyjny algorytm przeszukiwania (Rashedi, Nezamabadi-pour i Saryazdi, 2009)

Grawitacyjny algorytm wyszukiwania opiera się na prawie grawitacji i pojęciu oddziaływań masowych. Algorytm GSA wykorzystuje teorii fizyki Newtona i jego Searcher środki stanowią zbiór mas. W GSA istnieje izolowany system mas. Wykorzystując siłę grawitacji, każda masa w układzie może widzieć sytuację innych mas. Siła grawitacyjna jest zatem sposobem przekazywania informacji między różnymi masami (Rashedi, Nezamabadi-pour i Saryazdi 2009). W GSA agenci są uważani za obiekty, a ich wydajność mierzy się ich masami. Wszystkie te obiekty przyciągają się siłą grawitacji , a siła ta powoduje ruch wszystkich obiektów w kierunku obiektów o większej masie. Cięższe masy odpowiadają lepszym rozwiązaniom problemu. Położenie środka odpowiada rozwiązanie problemu, a jego masa jest określane za pomocą funkcji fitness. Z upływem czasu masy są przyciągane przez najcięższą masę, która idealnie przedstawiałaby optymalne rozwiązanie w przestrzeni poszukiwań. GSA można by uznać za izolowany system mas. Jest jak mały sztuczny świat mas przestrzegających newtonowskich praw grawitacji i ruchu. Wielocelowy wariant GSA, zwany MOGSA, został po raz pierwszy zaproponowany przez Hassanzadeha i in. w 2010.

Poszukiwanie kukułki (Yang i Deb, 2009)

W badaniach operacyjnych , szukaj kukułka jest optymalizacja algorytm opracowany przez Xin-she Yang i Suash Deb w roku 2009. Został on zainspirowany zobowiązać potomstwa pasożytnictwa niektórych kukułką gatunków, układając swoje jaja w gniazdach innych ptaków goszczących (innych gatunków) . Jeśli ptak-żywiciel odkryje, że jaja nie są jego własnymi jajami, wyrzuci je z gniazda lub porzuci gniazdo i zbuduje nowe. Zasadą poszukiwania kukułki jest umieszczanie „jajek” (nowo znalezionych rozwiązań) w „gniazdach” i trzymanie najlepszych jako kandydatów na następne pokolenie. Nowe rozwiązania mogą być losowo odrzucane („jajka” są wyrzucane z „gniazda”).

Algorytm nietoperza (Yang, 2010)

Bat algorytm jest algorytmem rój inteligencji opartej zainspirowany echolokacji zachowania microbats . BA automatycznie równoważy eksplorację (skoki na duże odległości po globalnej przestrzeni wyszukiwania, aby uniknąć utknięcia w pobliżu jednego lokalnego maksimum) z eksploatacją (bardziej szczegółowe wyszukiwanie znanych dobrych rozwiązań w celu znalezienia lokalnych maksimów) poprzez kontrolowanie głośności i częstotliwości emisji impulsów symulowanych nietoperzy w wielowymiarowa przestrzeń poszukiwań.

Algorytm optymalizacji spiralnej (SPO) (Tamura & Yasuda 2011, 2016-2017)

Spirala algorytm optymalizacji (SPO) jest nieskomplikowany wyszukiwania pojęcie zainspirowany zjawisk spiralnych w przyrodzie. Motywacja do skupienia się na zjawiskach spiralnych była spowodowana spostrzeżeniem, że dynamika, która generuje spirale logarytmiczne, łączy zachowania zróżnicowania i intensyfikacji. Zachowanie dywersyfikacji może działać dla globalnego poszukiwania (eksploracji), a zachowanie intensyfikacji umożliwia intensywne poszukiwanie wokół aktualnie znalezionego dobrego rozwiązania (eksploatacja). Algorytm SPO to wielopunktowy algorytm wyszukiwania, który nie ma gradientu funkcji celu, który wykorzystuje wiele modeli spiralnych, które można opisać jako deterministyczne układy dynamiczne. Ponieważ punkty wyszukiwania podążają spiralnymi trajektoriami logarytmicznymi w kierunku wspólnego środka, zdefiniowanego jako bieżący najlepszy punkt, można znaleźć lepsze rozwiązania i zaktualizować wspólny środek.

Algorytm zapylania kwiatów (Yang, 2012)

Algorytm zapylania kwiatów to meta- heurystyczny algorytm, który został opracowany przez Xin-She Yang , w oparciu o proces zapylania roślin kwitnących .

Ten algorytm ma 4 zasady lub założenia:

1. Zapylanie biotyczne i krzyżowe jest uważane za globalny proces zapylania, w którym pyłki przenoszące zapylacze wykonują loty Levy'ego .
2. Zapylanie abiotyczne i samozapylenie uważane są za lokalne.
3. Stałość kwiatów można uznać za prawdopodobieństwo rozmnażania proporcjonalne do podobieństwa dwóch zaangażowanych kwiatów.
4. Zapylanie lokalne i globalne jest kontrolowane przez prawdopodobieństwo zmiany . Ze względu na bliskość fizyczną i inne czynniki, takie jak wiatr, lokalne zapylanie może mieć znaczący udział q w ogólnej aktywności zapylania.${\displaystyle p\w [0,1]}$

Reguły te można przełożyć na następujące równania aktualizacyjne:

${\ Displaystyle x_ {i} ^ {t + 1} = x_ {i} ^ {t} + L (x_ {i} ^ {t} -g_ {*})}$

${\ Displaystyle x_ {i} ^ {t + 1} = x_ {i} ^ {t} + \ epsilon (x_ {i} ^ {t} -x_ {k} ^ {t})}$

gdzie jest wektorem rozwiązania i jest obecnie najlepszym znalezionym do tej pory podczas iteracji. Prawdopodobieństwo zamiany dwóch równań podczas iteracji wynosi . Dodatkowo jest losowa liczba losowana z rozkładu równomiernego. to wielkość kroku zaczerpnięta z rozkładu Lévy'ego. ${\ Displaystyle x_ {i} ^ {t}}$${\displaystyle g_{*}}$${\displaystyle p}$${\displaystyle \epsilon}$${\ Displaystyle L}$

Loty Lévy'ego z wykorzystaniem kroków Lévy'ego to potężny spacer losowy, ponieważ zarówno globalne, jak i lokalne możliwości wyszukiwania mogą być przeprowadzane w tym samym czasie. W przeciwieństwie do standardowych marszów losowych, loty Lévy'ego mają sporadyczne długie skoki, które umożliwiają algorytmowi wyskoczenie z dowolnych lokalnych dolin. Kroki Lévy'ego są zgodne z następującym przybliżeniem:

${\ Displaystyle L \ SIM {\ Frac {1} {s ^ {1 + \ beta}}}}$

gdzie jest wykładnik Lévy'ego. Prawidłowe narysowanie kroków Lévy'ego może być trudne, a prostym sposobem wygenerowania lotów Lévy'ego jest użycie dwóch rozkładów normalnych i przekształcenia ${\ Displaystyle \ beta}$${\displaystyle s}$${\ Displaystyle u}$${\displaystyle v}$

${\ Displaystyle s = {\ Frac {u} {| V | ^ {1 + \ beta}}}}$

z

${\ Displaystyle u \ SIM N (0, \ Sigma ^ {2}), \ Quad v \ SIM N (0, 1),}$

gdzie jest funkcją . ${\displaystyle \sigma}$${\ Displaystyle \ beta}$

Algorytm heterogenicznych pszczół rozproszonych (Tkach i in., 2013)

Heterogeniczny algorytm rozproszonych pszczół (HDBA) znany również jako zmodyfikowany algorytm rozproszonych pszczół (MDBA) to wieloagentowy algorytm metaheurystyczny wprowadzony przez Tkacha i jego współpracowników w 2013 r., opracowany w ramach jego rozprawy doktorskiej. HDBA wykorzystuje technikę probabilistyczną, czerpiąc inspirację z zachowania żerowania pszczół. Umożliwia rozwiązywanie problemów optymalizacji kombinatorycznej z wieloma heterogenicznymi agentami o różnych możliwościach i wydajnościach. Ostateczny mechanizm podejmowania decyzji wykorzystuje regułę wyboru kołowego, w której każdy agent ma prawdopodobieństwo, z jakim wybiera rozwiązanie. Po raz pierwszy zastosowano go w przypadku czujników heterogenicznych w problemie rozpoznawania celu, aby poprawić wydajność systemu poprzez skorelowanie funkcji użytkowej czujników z wartością ich wydajności. Następnie z powodzeniem zastosowano go do innych problemów, w tym problemu przydzielania agentów policyjnych do incydentów przestępczych i tworzenia niemal optymalnych rozwiązań problemu komiwojażera.

Algorytm sztucznego ekosystemu (Baczyński, 2013)

Algorytm sztucznego ekosystemu (AEA) to probabilistyczna metoda optymalizacji inspirowana niektórymi zjawiskami zachodzącymi w naturalnych ekosystemach. Relacje między jednostkami są modelowane zarówno przez ich wzajemne relacje w ramach jednej grupy, jak i relacje między jednostkami należącymi do różnych grup, współistniejących w ramach systemu ekologicznego. Istnieją trzy główne typy organizmów: rośliny, zwierzęta roślinożerne i drapieżniki. Wszystkie typy organizmów rozmnażają się (krzyżują i mutują) w obrębie własnego gatunku. Jako metoda zawiera niektóre algorytmy ewolucyjne i elementy PSO z dodatkowymi rozszerzeniami. Jest to dość skomplikowana metoda, ale okazała się zdolna do rozwiązywania zarówno problemów optymalizacji ciągłej, jak i kombinatorycznej.

Optymalizacja grupy spółdzielczej (2014)

System optymalizacji grup kooperacyjnych (CGO) to metaheurystyczna platforma do implementacji instancji algorytmów, łącząca zalety grupy kooperacyjnej i niskopoziomowego projektu portfela algorytmów. Podążając za inspirowanym naturą paradygmatem grupy kooperatywnej, agenci nie tylko eksplorują równolegle swoją pamięć indywidualną, ale także współpracują ze swoimi rówieśnikami poprzez pamięć grupową. Każdy agent posiada portfolio (heterogenicznych) wbudowanych heurystyk wyszukiwania (ESH), w których każdy ESH może skierować grupę do samodzielnego przypadku CGO, a hybrydowe przypadki CGO w przestrzeni algorytmicznej można zdefiniować za pomocą kooperacyjnego wyszukiwania niskiego poziomu między portfolio algorytmów (ESH) dzięki dostosowanemu współużytkowaniu pamięci. Proces optymalizacji może również ułatwić pasywny lider grupy poprzez zakodowanie wiedzy w krajobrazie poszukiwań. Został on zastosowany zarówno w zagadnieniach optymalizacji numerycznej, jak i kombinatorycznej.

Sztuczna inteligencja roju (Rosenberg, 2014)

Sztuczna inteligencja roju odnosi się do działającego w czasie rzeczywistym systemu zamkniętej pętli użytkowników ludzkich połączonych przez Internet i ustrukturyzowanego w ramach wzorowanych na naturalnych rojach, tak że przywołuje zbiorową mądrość grupy jako zunifikowaną wschodzącą inteligencję. W ten sposób roje ludzi mogą odpowiadać na pytania, przewidywać, podejmować decyzje i rozwiązywać problemy, wspólnie badając różnorodny zestaw opcji i synchronicznie zbliżając się do preferowanych rozwiązań. Wynaleziona przez dr Louisa Rosenberga w 2014 r. metodologia ASI stała się znana ze swojej zdolności do tworzenia dokładnych prognoz zbiorowych, które przewyższają wyniki poszczególnych członków roju. W 2016 r. reporter wyzwał sztuczną inteligencję roju od Unanimous AI do przewidzenia zwycięzców Kentucky Derby i pomyślnie wybrał pierwsze cztery konie w kolejności, pokonując szanse 540 do 1.

Optymalizacja ciał kolidujących (Kaveh i Mahdavi, 2014)

Algorytm optymalizacji ciał zderzeniowych (CBO) został stworzony przez Kaveha i Mahdavi w 2014 roku w oparciu o prawa pędu i energii. Algorytm ten nie jest zależny od żadnego parametru wewnętrznego, a ponadto jest niezwykle prosty w implementacji i użyciu oraz w różnego rodzaju problemach inżynierskich.

Algorytm pojedynków (Biyanto, 2016)

Algorytm Duelist odnosi się do algorytmu optymalizacji opartego na genach, podobnego do algorytmów genetycznych . Duelist Algorithm rozpoczyna się od początkowego zestawu pojedynków. Pojedynek ma wyłonić zwycięzcę i przegranego. Przegrany uczy się od zwycięzcy, a zwycięzca wypróbowuje nową umiejętność lub technikę, która może poprawić jego zdolności bojowe. Kilku pojedynkowiczów o najwyższych zdolnościach bojowych jest nazywanych mistrzami. Mistrz trenuje nowego pojedynku, takiego jak ich umiejętności. Nowy pojedynkowicz dołączy do turnieju jako reprezentant każdego mistrza. Wszyscy pojedynkujący się są ponownie oceniani, a pojedynkujący się z najgorszymi zdolnościami bojowymi są eliminowani, aby utrzymać liczbę pojedynkujących się.

Optymalizacja jastrzębi Harrisa (Heidari i in., 2019)

Optymalizator jastrzębi Harrisa (HHO) inspiruje strategie łowieckie jastrzębia Harrisa i wzorce ucieczki królików w przyrodzie .

Algorytm zabójcy wielorybów (Biyanto, 2016)

Killer Whale Algorithm to algorytm zainspirowany życiem Killer Whale. Filozofią algorytmu są wzorce ruchu orka w polowaniu na zdobycz i struktura społeczna orka. Nowością tego algorytmu jest włączenie do algorytmu „ zdolności zapamiętywania ” Killer Whale.

Algorytm wody deszczowej (Biyanto, 2017)

„ Fizyczne ruchy kropli deszczu z wykorzystaniem ruchu prawa Newtona ” zainspirowały autorów do stworzenia tego algorytmu. Każda kropla deszczu reprezentuje losowe wartości zoptymalizowanych zmiennych, które różnią się masą i wysokością. Spadnie na ziemię podążając za „ ruchem swobodnego spadania ” z prędkością wyrażoną jako pierwiastek kwadratowy z czasu przyspieszenia grawitacyjnego. Następnym ruchem jest „ jednostajnie przyspieszony ruch ” wzdłuż drogi kropli deszczu do najniższego miejsca na ziemi. Najniższe miejsce w ziemi jest funkcją obiektywną tego algorytmu.

Algorytm bilansów masy i energii (Biyanto, 2018)

Bilanse masy i energii to fundamentalne „ prawa fizyki ” stwierdzające, że masy nie można ani wytworzyć, ani zniszczyć. Jest tylko konserwowany. Równie fundamentalne jest prawo zachowania energii. Chociaż energia może zmieniać formę, nie można jej również tworzyć ani niszczyć. Piękno tego algorytmu polega na możliwości osiągnięcia globalnego optymalnego rozwiązania poprzez jednoczesną pracę „ metodą minimalizacji i maksymalizacji wyszukiwania ”.

Algorytm cyklu hydrologicznego (Wedyan i in., 2017)

Zaproponowano nowy algorytm optymalizacji inspirowany naturą, zwany algorytmem cyklu hydrologicznego (HCA), oparty na ciągłym ruchu wody w przyrodzie. W HCA zbiór kropel wody przechodzi przez różne etapy hydrologicznego obiegu wody, takie jak przepływ, parowanie, kondensacja i opady. Każdy etap odgrywa ważną rolę w generowaniu rozwiązań i unikaniu przedwczesnej konwergencji. HCA udostępnia informacje poprzez bezpośrednią i pośrednią komunikację między kroplami wody, co poprawia jakość roztworu. HCA zapewnia alternatywne podejście do rozwiązywania różnego rodzaju problemów optymalizacyjnych, a także ogólne ramy dla algorytmów opartych na wodzie.

Kolonia pingwinów cesarskich (Harifi i in., 2019)

Algorytm ten jest nowym algorytmem metaheurystycznym, zainspirowanym zachowaniem pingwinów cesarskich żyjących na Antarktydzie. EPC jest kontrolowane przez promieniowanie cieplne ciała pingwinów i ich spiralny ruch w ich kolonii. Pingwiny cesarskie w kolonii dążą do wytworzenia odpowiedniego ciepła i regulacji temperatury ciała, a to ciepło jest całkowicie koordynowane i kontrolowane przez ruchy pingwinów.

Algorytm równowagi pędu (MBA) (Biyanto i in., 2019)

Równowaga pędu jest jednym z trzech podstawowych „praw fizyki”, które stwierdzają, że masa, energia i pęd są zachowane. W wielu zastosowaniach zaproponowano wykorzystanie równowagi pędu.

W tych badaniach przyjęto równowagę pędów, aby uzyskać idealnie sprężyste zderzenie. W idealnym, idealnie sprężystym zderzeniu nie ma strat energii kinetycznej na inne formy, takie jak energia potencjalna, ciepło i hałas. Piękno tego algorytmu jest tak proste, jak deterministyczne algorytmy optymalizacji, jednak algorytm równowagi pędu ma możliwość osiągnięcia globalnego rozwiązania optymalnego.

Algorytm optymalizacji Shuffled Shepherd (SSOA) (Kaveh i Zaerreza, 2020)

Ta metoda jest nowym algorytmem optymalizacji metaheurystycznej dla wielu społeczności. W tym algorytmie Agenci są najpierw dzieleni na wiele społeczności, a następnie przeprowadzany jest proces optymalizacji naśladujący zachowanie pasterza z natury działającego na każdej społeczności.

Algorytm optymalizacji jętek (MA) (Zervoudakis & Tsafarakis, 2020)

Algorytm optymalizacji jętek został opracowany w celu rozwiązania zarówno problemów z optymalizacją ciągłą, jak i dyskretną i jest inspirowany zachowaniem się jętek w locie i procesem kojarzenia jętek. Procesy tańca weselnego i losowego lotu wzmacniają równowagę między właściwościami eksploracyjnymi i eksploatacyjnymi algorytmu i pomagają w ucieczce od lokalnego optima. Wydajność algorytmu mayfly jest lepsza od innych popularnych metaheurystyk, takich jak PSO, DE, GA i FA, pod względem szybkości zbieżności i szybkości zbieżności.

Optymalizator polityczny (PO) (Qamar Askari, Irfan Younas i Mehreen Saeed, 2020)

Political Optimizer (PO) to algorytm oparty na ludzkich zachowaniach społecznych inspirowany wielopartyjnym systemem politycznym. Źródłem inspiracji jest zestaw 5 faz: tworzenie partii i przydział okręgów wyborczych, zmiana partii, kampania wyborcza, wybory międzypartyjne i sprawy parlamentarne. PO ma dwie unikalne cechy: logiczny podział populacji w celu przypisania podwójnej roli każdemu kandydatowi na rozwiązanie oraz strategię aktualizacji pozycji w oparciu o ostatnią przeszłość (RPPUS). PO wykazuje doskonałą wydajność w porównaniu z 15 dobrze znanymi metaheurystykami dla 50 jednomodalnych i multimodalnych funkcji wzorcowych oraz 4 problemów inżynieryjnych.

Optymalizator oparty na stercie (HBO) (Qamar Askari, Mehreen Saeed, Irfan Younas, 2020)

HBO to metaheurystyka oparta na ludzkich zachowaniach społecznych, inspirowana hierarchią rang korporacyjnych i interakcją między pracownikami ułożonymi w hierarchii. Wyjątkowość HBO polega na wykorzystaniu struktury danych sterty do modelowania hierarchicznego rozmieszczenia pracowników oraz wprowadzeniu parametru (γ) w celu alternatywnego włączenia eksploracji i eksploatacji. Co więcej, trzy równania wyprowadzone dla trzech faz HBO są probabilistycznie łączone, aby zrównoważyć poszukiwania i eksploatację. HBO wykazuje niesamowitą wydajność w 97 testach porównawczych i 3 problemach inżynierii mechanicznej.

Algorytm śledczy oparty na kryminalistyce (FBI) (JS Chou i NM Nguyen, 2020)

Główną motywacją do opracowania nowego algorytmu jest jego zdolność do skutecznego i wydajnego rozwiązywania różnych problemów optymalizacyjnych. Opracowano nowatorską metodę optymalizacji, algorytm dochodzeniowy oparty na kryminalistyce (FBI), w celu określenia globalnych rozwiązań dla ciągłych funkcji nieliniowych przy niskim wysiłku obliczeniowym i wysokiej dokładności. FBI inspiruje się procesem dochodzenia, lokalizacji i ścigania podejrzanych funkcjonariuszy policji. Główne cechy FBI: (1) FBI to algorytm optymalizacji bez parametrów; (2) FBI znacznie przewyższyło znane i nowo opracowane algorytmy; (3) FBI ma krótki czas obliczeniowy i szybko osiąga optymalne rozwiązania w rozwiązywaniu problemów; (4) FBI jest skuteczne w rozwiązywaniu problemów wielowymiarowych (D=1000); oraz (5) Struktura FBI ma dwa zespoły, które dobrze równoważą eksplorację i eksploatację.

Szczegóły można znaleźć pod adresem: Chou JS, Nguyen NM, metaoptymalizacja inspirowana przez FBI, Applied Soft Computing, 2020:106339, ISSN 1568-4946, https://doi.org/10.1016/j.asoc.2020.106339

Poszukiwanie meduz (JS) (JS Chou i DN Truong, 2021)

Jellyfish Search (JS) Optimizer jest inspirowany zachowaniem meduz w oceanie. Symulacja zachowań poszukiwawczych meduz obejmuje ich podążanie za prądem oceanicznym, ich ruchy wewnątrz roju meduz (ruchy aktywne i ruchy pasywne), mechanizm kontroli czasu do przełączania się między tymi ruchami oraz ich zbieżność w rozkwit meduz. Nowy algorytm jest z powodzeniem testowany na funkcjach porównawczych i problemach optymalizacji. Warto zauważyć, że JS ma tylko dwa parametry kontrolne, którymi są wielkość populacji i liczba iteracji. Dlatego JS jest bardzo prosty w użyciu i potencjalnie doskonałym algorytmem metaheurystycznym do rozwiązywania problemów optymalizacyjnych.

Optymalizator Golden Eagle (GEO) (Mohammadi-Balani i in., 2020)

Golden Eagle Optimizer (GEO) to inspirowany naturą algorytm metaheurystyczny oparty na populacji opartej na inteligencji roju, który opiera się na zachowaniach łowieckich orłów przednich . Algorytm modeluje to zachowanie, dzieląc wektor prędkości orłów przednich na dwie składowe: a) wektor ataku ib) wektor przelotu. Wektor ataku dla każdego orła przedniego (agenta wyszukiwania) zaczyna się od aktualnej pozycji orła przedniego i kończy się w miejscu zdobyczy w pamięci każdego orła przedniego. Ofiarą każdego orła przedniego jest najlepsza lokalizacja, jaką do tej pory odwiedził. Orły przednie krążą wokół ofiary w hipotetycznych hipersferach. Wektor rejsu jest wektorem stycznym do hipotetycznej hipersfery dla każdego orła przedniego. Oryginalna praca zawiera zarówno jedno-, jak i wielokryterialne wersje algorytmu. Kod źródłowy, zestaw narzędzi i graficzny interfejs użytkownika dla Golden Eagle Optimizer (GEO) i Multi-Objective Golden Eagle Optimizer (MOGEO) są również opracowywane dla MATLAB.

Krytyka metodologii metafory

Podczas gdy indywidualne metaheurystyki inspirowane metaforami przyniosły niezwykle skuteczne rozwiązania konkretnych problemów, metaheurystyki inspirowane metaforami ogólnie spotkały się z krytyką społeczności badawczej za ukrywanie ich braku skuteczności lub nowości za skomplikowaną metaforą. Kenneth Sörensen zauważył, że:

W ostatnich latach dziedzina optymalizacji kombinatorycznej doświadczyła prawdziwego tsunami „nowatorskich” metod metaheurystycznych, z których większość opiera się na metaforze jakiegoś naturalnego lub stworzonego przez człowieka procesu. Zachowanie się praktycznie każdego gatunku owadów, przepływ wody, grający razem muzycy – wydaje się, że żaden pomysł nie jest zbyt daleko idący, by posłużyć za inspirację do uruchomienia kolejnej metaheurystyki. [Ja] będę argumentować, że ten kierunek badań grozi odprowadzeniem obszaru metaheurystyki od naukowego rygoru.

Sörensen i Glover stwierdzili, że:

Duża (i rosnąca) liczba publikacji koncentruje się na opracowaniu (podobno) nowych ram metaheurystycznych opartych na metaforach. Lista naturalnych lub wytworzonych przez człowieka procesów, która została wykorzystana jako podstawa ram metaheurystycznych, obejmuje teraz tak różnorodne procesy, jak żerowanie bakteryjne, tworzenie się rzek , biogeografia, wspólne granie muzyków, elektromagnetyzm, grawitacja , kolonizacja przez imperium , wybuchy kopalni, mistrzostwa ligowe, chmury i tak dalej. Ważną podkategorię można znaleźć w metaheurystyce opartej na zachowaniu zwierząt. Mrówki , pszczoły, nietoperze , wilki, koty, robaczki świętojańskie , orły, delfiny, żaby , łososie, sępy, termity, muchy i wiele innych inspirowały „nową” metaheurystykę. [...] Co do zasady publikowanie artykułów dotyczących metaheurystyk opartych na metaforach ogranicza się do czasopism i konferencji drugorzędnych, ale ostatnio można znaleźć pewne wyjątki od tej reguły. Sörensen (2013) stwierdza, że ​​badania w tym kierunku są z gruntu wadliwe. Co najważniejsze, autor twierdzi, że nowość podstawowej metafory nie powoduje automatycznie, że powstałe ramy są „nowe”. Wręcz przeciwnie, istnieje coraz więcej dowodów na to, że bardzo niewiele metod opartych na metaforach jest nowych w jakimkolwiek interesującym sensie.

W odpowiedzi Springer 's Journal of Heuristics zaktualizował swoją politykę redakcyjną, aby stwierdzić, że:

Proponowanie nowych paradygmatów jest dopuszczalne tylko wtedy, gdy zawierają one innowacyjne podstawowe idee, takie jak te, które są osadzone w klasycznych ramach, takich jak algorytmy genetyczne , przeszukiwanie tabu i symulowane wyżarzanie . Journal of Heuristics unika publikowania artykułów, które przepakowują i osadzają stare idee w metodach, które rzekomo opierają się na metaforach naturalnych lub stworzonych przez człowieka systemów i procesów. Te tak zwane „nowatorskie” metody wykorzystują analogie, które obejmują inteligentne krople wody , muzyków grających jazz, społeczeństwa imperialistyczne , żaby skaczące , kangury, wszelkiego rodzaju roje i owady, a nawet procesy wybuchów minowych (Sörensen, 2013). Jeśli badacz posługuje się metaforą, aby pobudzić własne wyobrażenia o nowej metodzie, to metoda ta musi być mimo wszystko przetłumaczona na język pozbawiony metafor, tak aby zastosowane strategie można było jasno zrozumieć, a ich nowość była wyraźnie widoczna. (Patrz punkty 2 i 3 poniżej.) Metafory są tanie i łatwe do zdobycia. Ich użycie do "ubierania okien" metodą jest niedopuszczalne."

[...] Wdrożenia należy wyjaśnić za pomocą standardowej terminologii optymalizacyjnej, gdzie rozwiązanie nazywa się „rozwiązaniem”, a nie czymś innym związanym z jakąś niejasną metaforą (np. harmonia, muchy , nietoperze , kraje itp.).

[…] Journal of Heuristics w pełni popiera pogląd Sörensena, że ​​oparte na metaforach „nowe” metody nie powinny być publikowane, jeśli nie mogą wykazać wkładu w swoją dziedzinę. Zmiana nazw istniejących koncepcji nie liczy się jako wkład. Chociaż metody te są często nazywane „nowatorskimi”, wiele z nich nie przedstawia żadnych nowych pomysłów, z wyjątkiem okazjonalnych marginalnych wariantów już istniejącej metodologii. Metody te nie powinny zajmować w dzienniku przestrzeni prawdziwie innowacyjnych pomysłów i badań. Ponieważ nie używają standardowego słownictwa optymalizacyjnego, są one niepotrzebnie trudne do zrozumienia.

Polityka Springer „s dziennika 4lub - kwartalnik Journal of Operations badań stwierdza się, że:

Nacisk na rygor naukowy i innowacyjność oznacza w szczególności, że czasopismo nie publikuje artykułów, które po prostu proponują ukryte warianty znanych metod bez odpowiedniej walidacji (np. metaheurystyki, które są uważane za „skuteczne” wyłącznie na podstawie porównań metaforycznych z naturalnymi lub sztucznymi systemami i procesami). Nowe metody należy przedstawić w języku wolnym od metafor, ustalając ich związek z klasycznymi paradygmatami. Ich właściwości należy ustalić na podstawie przekonujących naukowo argumentów: dowodów matematycznych, kontrolowanych eksperymentów, obiektywnych porównań itp.

Zobacz też

• Metafora pojęciowa
• Metafora społeczności naukowej

Uwagi

Bibliografia

• Sörensena, Kennetha; Sevaux, Marc; Glover, Fred (16.01.2017). „Historia metaheurystyki” (PDF) . W Martí Rafael; Panosy, Pardalos; Resende, Mauricio (wyd.). Podręcznik heurystyki . Skoczek. Numer ISBN 978-3-319-07123-7.
• Sörensena, Kennetha (2015). „Metaheurystyka-metafora narażone”. Transakcje międzynarodowe w badaniach operacyjnych . 22 : 3–18. CiteSeerX  10.1.1.470.3422 . doi : 10.1111/itor.12001 .
• Samotni, Michael A. (2014). „Metaheurystyka w algorytmach inspirowanych naturą”. Materiały towarzyszące konferencji 2014 dotyczącej Genetycznych i ewolucyjnych obliczeń towarzyszących - GECCO Comp '14 . s. 1419-22. CiteSeerX  10.1.1.1.699.1825 . doi : 10.1145/2598394.2609841 . Numer ISBN 9781450328814. S2CID  14997975 .
• Pięść, Iztok; Yang, Xin-She; Pięść, Iztok; Brześć, Janez; Pięść, Dušan (2013). „Krótki przegląd inspirowanych naturą algorytmów optymalizacji”. Elektrotehniški Vestnik . arXiv : 1307.4186 .

Zewnętrzne linki

• Bestiariusz obliczeń ewolucyjnych  – żartobliwy opis wszystkich dziwacznych, nawet dziwacznych metaheurystyk opartych na metaforach, dostępnych w szerokim świecie publikacji akademickich
• The Science Matrix's List of Metaheuristic  – pełna lista algorytmów metaheurystycznych. Listę można łatwo filtrować według nazwiska, autora lub roku i zawiera link do głównej publikacji każdego algorytmu.