Ewolucyjna optymalizacja multimodalny - Evolutionary multimodal optimization
W matematyce stosowanej , multimodalne optymalizacji dotyczy optymalizacji zadań, które wymagają znalezienia wszystkich lub większości wielokrotności (przynajmniej lokalnie) optymalne rozwiązania problemu, w przeciwieństwie do jednego najlepszego rozwiązania. Ewolucyjna optymalizacja multimodalny jest gałęzią obliczeń ewolucyjnych , które jest ściśle związane z uczenia maszynowego . Wong zapewnia krótką ankietę, w której rozdział Shir i księga Preuss pokrycie temat w sposób bardziej szczegółowy.
Zawartość
Motywacja
Znajomość wielu rozwiązań do zadania optymalizacji jest szczególnie przydatne w inżynierii, gdy ze względu na fizyczne (i / lub kosztów) ograniczeń, najlepsze wyniki nie zawsze są wykonalne. W takim scenariuszu, w przypadku wielu rozwiązań (lokalnie i / lub globalnie optymalne) są znane, realizacja może być szybko przełączany do innego rozwiązania i nadal uzyskać najlepszą możliwą wydajność systemu. Wiele rozwiązań może być również analizowane, aby odkryć ukryte właściwości (lub relacji) bazowych problemu optymalizacji, co czyni je ważnym dla uzyskania wiedzy domeny . Ponadto, algorytmy optymalizacji multimodalnego zwykle nie tylko zlokalizować wiele Optima w jednym biegu, ale także zachowania ich różnorodności populacji, powodując ich globalnej zdolności optymalizacja funkcji multimodalnych. Ponadto techniki multimodalnego optymalizacji zwykle pożyczył jak techniki konserwacji różnorodność innych problemów.
tło
Klasyczne techniki optymalizacji musiałby wiele punktów restart i wielokrotne przejazdy w nadziei, że inne rozwiązanie może być odkryta każdy bieg, jednak bez gwarancji. Ewolucyjne algorytmy (EAS), ze względu na ich podejścia opartego populacji zapewniają naturalną przewagę nad klasycznych metod optymalizacji. Twierdzą oni populację możliwych rozwiązań, które są przetwarzane w każdym pokoleniu, a jeśli wiele rozwiązań może być zachowana w stosunku do wszystkich tych pokoleń, a następnie na zakończenie algorytmu będziemy mieć wiele dobrych rozwiązań, a nie tylko najlepsze rozwiązanie. Należy zauważyć, że jest to na naturalnej tendencji klasycznych technik optymalizacji, które zawsze są zbieżne najlepsze rozwiązanie, lub rozwiązaniu suboptymalnym (w trudnych „źle zachowuje” funkcja). Ustalenie i utrzymanie wielu rozwiązań jest to, w którym znajduje się wyzwanie przy użyciu EA na multimodalnym optymalizacji. Niching to ogólne określenie dalej techniką poszukiwania i zachowanie wielu stabilnych wnęki lub korzystne części przestrzeni roztwór ewentualnie około różne rozwiązania, aby uniknąć zbliżenia do pojedynczego roztworu.
Pole algorytmów ewolucyjnych obejmuje algorytmy genetyczne (gaz), strategii ewolucji (ES), ewolucja różnica (DE), optymalizacji cząstek rój (PSO) i inne metody. Podejmowano próby rozwiązania multimodalnego optymalizację we wszystkich tych sferach i większość, jeśli nie wszystkie różne metody wdrażają niching w innej formie lub innych.
Multimodalny optymalizacji za pomocą algorytmów genetycznych / strategii ewolucji
Metoda stłoczenie De Jong, podejście funkcja dzielenia Goldberga, metoda rozliczeń Petrowski, w ograniczony krycia, zachowując wiele subpopulacje to tylko niektóre z popularnych metod, które zostały zaproponowane przez społeczność. Pierwsze dwie metody są szczególnie dobrze zbadany, jednak nie wykonują one wyraźne oddzielenie do rozwiązań należących do różnych basenów przyciągania.
Stosowanie multimodalnego optymalizacji w ES nie było jawne dla wielu lat i został zbadany dopiero niedawno. Ramy niching wykorzystaniem derandomized ES wprowadził Shir, proponuje CMA-ES jako optymalizator niching po raz pierwszy . Podstawa dla tej ramy był dobór indywidualnych szczytowego na subpopulacji w każdym pokoleniu, a następnie przez jej pobierania próbek w celu wytworzenia kolejnych dyspersji wyszukiwania punktów. Analogia biologiczny tej maszyny jest alfa-mężczyzna wygrywając wszystkie nałożone konkursy i dominuje następnie swoją niszę ekologiczną , który następnie uzyskuje wszystkie zasoby seksualnych w nim, aby wygenerować jego potomstwo.
Ostatnio ewolucyjny optymalizacja wielokryterialna podejście (EMO) zaproponowano, w którym nadaje się drugi cel dodaje się początkowo jeden cel multimodalnego problemu optymalizacji, tak że tworzą liczne rozwiązania słabej PARETO optymalnego przodu. Stąd wielomodalna Problem optymalizacji można rozwiązać w jego różnych rozwiązań przy użyciu algorytmu EMO. Poprawa na swojej pracy, ci sami autorzy dokonały ich algorytm samodostosowuj, eliminując potrzebę wstępnego określania parametrów.
Podejście to nie wykorzystuje promień do rozdzielenia populacji na subpopulacji (lub gatunków), lecz stosuje topologii przestrzeń zamiast proponuje się.
Multimodalny optymalizacji korzystania DE
Metody stosowane w niching gaz zostały również zbadane z powodzeniem w środowisku DE. DE na podstawie lokalnych i globalnych wybór metody selekcji zostały również próbę rozwiązywania problemów multimodalne. DE na połączeniu z lokalnych algorytmów wyszukiwania (memetyczny DE) zostały zbadane jako podejście do rozwiązywania problemów multimodalne.
Dla kompleksowego leczenia multimodalnych metod optymalizacji w DE, przekazanie pracy doktorskiej Ronkkonen, J. (2009). Ciągłe multimodalny optymalizacji globalnej z rozmazem Evolution metody oparte .
Multimodalny optymalizacji algorytmem GSO inteligencja roju opartej
Optymalizacja Glowworm rój (GSO) jest algorytm oparty rój inteligencja, wprowadzony przez KN Krishnanand i D. Ghose w 2005 roku, do jednoczesnego obliczania stwardnienia optima funkcji multimodalnych. Algorytm dzieli kilka funkcji z niektórych bardziej znanych algorytmów, takich jak mrówki optymalizacji kolonii i optymalizacja rojem cząstek , ale z kilku istotnych różnic. Agenci w GSO są traktowane jako robaczki świętojańskie, które przenoszą ilość luminescencji nazwie lucyferyna razem z nimi. Glowworms zakodować kondycję swoich obecnych miejsc, oceniano za pomocą funkcji celu, do wartości lucyferyna że transmitowany do swoich sąsiadów. Glowworm identyfikuje jej sąsiadów i oblicza jego ruchy wykorzystując adaptacyjny sąsiedztwa, która jest ograniczona przez jego zasięgu powyżej czujnika. Każdy wybiera Glowworm, wykorzystujące mechanizm probabilistyczny, sąsiad, który ma wartość wyższą niż lucyferyna własnej i rusza w jego kierunku. Ruchy te oparte tylko na miejscowej informacji i selektywnej interakcji sąsiednich włączyć rój robaczki świętojańskie rozdziałowi w rozłączne podgrupy, które zbiegają się na wielu optymalnych danej funkcji multimodalnego. W przeciwieństwie do większości innych multimodalnych ewolucyjnych algorytmów optymalizacji, własność podziału na podgrupy pozwala algorytm jednocześnie zbiegają się do lokalnego optimum różnych wartości, dzięki czemu nadaje się do rozwiązywania wielu problemów, szukając źródła sygnału za pomocą robotów.
Zobacz też
Referencje
Bibliografia
- Goldberg i D. J. Richardson. (1987) „Genetic algorytmy Sharing multimodalnego optymalizację funkcji”. W postępowaniu Drugiej Międzynarodowej Konferencji na temat algorytmów genetycznych na algorytmach genetycznych oraz ich stolika aplikacji treści, strony 41-49. L. Erlbaum Associates Inc. Hillsdale, NJ, USA, 1987.
- A. Petrowski. (1996) „procedury rozliczeniowej jako metoda niching algorytmów genetycznych”. W Proceedings of 1996 IEEE Międzynarodowej Konferencji na temat obliczeń ewolucyjnych, strony 798-803. CiteSeer, 1996.
- Deb, K., (2001) "optymalizacja wielokryterialna przy użyciu algorytmów ewolucyjnych", Wiley ( Google Książki)
- F. Streichert G. Stein H Ulmer i A. Zell. (2004) „To grupowanie oparte niching EA dla multimodalnych przestrzeni poszukiwań”. Lecture Notes in Computer Science, strony 293-304, 2004.
- Singh, G., Deb, K., (2006) "Porównanie algorytmów optymalizacji multimodalnych oparty na algorytmach ewolucyjnych". W Proceedings of the 8th dorocznej konferencji na temat genetycznych i obliczeń ewolucyjnych, strony 8-12. ACM, 2006.
- Ronkkonen J., (2009). Ciągłe multimodalny optymalizacji globalnej z rozmazem Evolution metody oparte
- Wong, KC, (2009). Ewolucyjny algorytm specyficzne gatunkowo eksplozji dla multimodalnego optymalizacji. GECCO 2009: 923-930
- J. Barrera CAC Coello. "A Review of optymalizacja rojem cząstek metod stosowanych dla Multimodal Optimization", strony 9-37. Springer, Berlin, listopad 2009 r.
- Wong, KC, (2010). Wpływ przestrzennego Miejscowość na ewolucyjny algorytm Multimodal Optimization. EvoApplications (1) 2010: 481-490
- Deb, K., Saha, A. (2010) Znalezienie różne rozwiązania dotyczące multimodalnych Optimization Problemy używając Wielu obiektywne podejście ewolucyjnego. GECCO 2010: 447-454
- Wong, KC, (2010). Przewidywanie struktury białka na modelu siatkowej poprzez multimodalnych techniki optymalizacji. GECCO 2010: 155-162
- Saha, A., Deb, K. (2010), Bi-kryterium podejście do optymalizacji Multimodal: samodostosowującego Podejścia. SEAL 2010: 95-104
- Zbierający OM Emmerich, M., i z powrotem, T. (2010), adaptacyjny niszy próbkowe Kształty niszy Podejścia Niching z CMA-ES. Obliczenia ewolucyjne Vol. 18, nr 1, str. 97-126.
- C Stoean M. Preuss R. Stoean D. Dumitrescu (2010) Optymalizacja wielofunkcyjną środki topologiczne ochrony gatunkowej algorytmu . W IEEE Transactions on obliczeń ewolucyjnych, Vol. 14, Issue 6, strony 842-864, 2010.
- S. Das, S. Maity, Qu, PN Suganthan, "Real-parametr ewolucyjny multimodalny optymalizacja - Badanie state-of-the-art", Vol. 1, nr 2, s. 71-88, Swarm i obliczeń ewolucyjnych, czerwiec 2011.