Algorytm memetyczny - Memetic algorithm

Część serii na
Algorytm ewolucyjny
Sztuczny rozwój Sztuczne życie Komórkowy algorytm ewolucyjny Algorytm kulturowy Ewolucja różnicowa Skuteczna kondycja Obliczenia ewolucyjne Strategia ewolucji Adaptacja Gaussa Ewolucyjna optymalizacja multimodalna Ewolucja gramatyczna Optymalizacja roju cząstek Algorytm memetyczny Strategia naturalnej ewolucji Neuroewolucja Algorytm genetyczny oparty na promotorze Algorytm optymalizacji spirali Kod samomodyfikujący się Kod polimorficzny
Algorytm genetyczny
Chromosom Algorytm selekcji klonów Krzyżowanie Mutacja Pamięć genetyczna Genetyczne systemy rozmyte Wybór Algorytm lotu
Programowanie genetyczne
Kartezjańskie programowanie genetyczne Liniowe programowanie genetyczne Programowanie z wieloma wyrażeniami Schemat Eurisko Wzorzec parytetu
v t mi

W informatyce i badań operacyjnych , o memetyczna algorytm (MA) jest rozszerzeniem tradycyjnego algorytmu genetycznego . Wykorzystuje lokalną technikę wyszukiwania , aby zmniejszyć prawdopodobieństwo przedwczesnej zbieżności.

Algorytmy memetyczne stanowią jeden z najnowszych rozwijających się obszarów badań w dziedzinie obliczeń ewolucyjnych . Termin MA jest obecnie szeroko stosowany jako synergia podejścia ewolucyjnego lub dowolnego podejścia opartego na populacji z oddzielnymi indywidualnymi procedurami uczenia się lub lokalnego doskonalenia w celu wyszukiwania problemów. Dość często MA są również określane w literaturze jako algorytmy ewolucyjne Baldwina (EA), Lamarckowskie EA, algorytmy kulturowe lub genetyczne wyszukiwanie lokalne.

Wprowadzenie

Zainspirowany zarówno darwinowskimi zasadami naturalnej ewolucji, jak i pojęciem memu Dawkinsa , termin algorytm memetyczny (MA) został wprowadzony przez Pablo Moscato w jego raporcie technicznym w 1989 roku, w którym uważał MA za zbliżony do formy populacyjnej hybrydy genetycznej. algorytm (GA) w połączeniu z indywidualną procedurą uczenia się, zdolną do wykonywania lokalnych udoskonaleń. Metaforyczne podobieństwa z jednej strony do ewolucji darwinowskiej, az drugiej strony między memami a heurystyką specyficzną dla domeny (przeszukiwanie lokalne) są ujęte w algorytmach memetycznych, tworząc w ten sposób metodologię, która dobrze balansuje między ogólnością a szczegółowością problemu. Ta dwustopniowa natura czyni je szczególnym przypadkiem ewolucji dwufazowej .

W bardziej zróżnicowanym kontekście, algorytmy memetyczne są obecnie używane pod różnymi nazwami, w tym hybrydowymi algorytmami ewolucyjnymi, algorytmami ewolucyjnymi Baldwina, algorytmami ewolucyjnymi Lamarckiego, algorytmami kulturowymi lub genetycznym wyszukiwaniem lokalnym. W kontekście złożonej optymalizacji, zgłoszono wiele różnych instancji algorytmów memetycznych w szerokim zakresie dziedzin zastosowań , generalnie konwergując do rozwiązań wysokiej jakości bardziej wydajnie niż ich konwencjonalne odpowiedniki ewolucyjne.

Ogólnie rzecz biorąc, używanie idei memetyki w ramach obliczeniowych nazywa się obliczeniami memetycznymi lub obliczeniami memetycznymi (MC). Dzięki MC cechy uniwersalnego darwinizmu są lepiej uchwycone. Z tej perspektywy MA jest bardziej ograniczonym pojęciem MC. Dokładniej rzecz biorąc, MA obejmuje jeden obszar MC, w szczególności zajmując się obszarami algorytmów ewolucyjnych, które łączą inne deterministyczne techniki udoskonalania w celu rozwiązywania problemów optymalizacyjnych. MC rozszerza pojęcie memów na konceptualne byty procedur lub reprezentacji wspomaganych wiedzą.

Rozwój MA

1 generacja

Pierwsza generacja MA odnosi się do algorytmów hybrydowych , połączenia globalnego wyszukiwania populacyjnego (często w formie algorytmu ewolucyjnego) z kulturowym etapem ewolucji. Ta pierwsza generacja MA, chociaż obejmuje cechy ewolucji kulturowej (w postaci lokalnego udoskonalenia) w cyklu poszukiwań, może nie kwalifikować się jako prawdziwy ewoluujący system zgodnie z uniwersalnym darwinizmem , ponieważ wszystkie podstawowe zasady dziedziczenia / transmisji memetycznej, zmienności i brakuje wyboru. Sugeruje to, dlaczego termin MA wywołał krytykę i kontrowersje wśród badaczy po raz pierwszy.

Pseudo kod

   Procedure Memetic Algorithm
   Initialize: Generate an initial population;
   while Stopping conditions are not satisfied do
       Evaluate all individuals in the population.
       Evolve a new population using stochastic search operators.
       Select the subset of individuals, ${\displaystyle \Omega _{il}}$, that should undergo the individual improvement procedure.
       for each individual in ${\displaystyle \Omega _{il}}$ do
           Perform individual learning using meme(s) with frequency or probability of ${\displaystyle f_{il}}$, for a period of ${\displaystyle t_{il}}$.
           Proceed with Lamarckian or Baldwinian learning.
       end for
   end while

2. generacji

Mgr multi-memowy, hiperheurystyczny i meta-lamarcki jest określany jako magister drugiej generacji, wykazujący w swoim projekcie zasady memetycznej transmisji i selekcji. W Multi-meme MA materiał memetyczny jest kodowany jako część genotypu . Następnie zdekodowany mem każdego odpowiedniego osobnika / chromosomu jest następnie używany do przeprowadzenia lokalnego udoskonalenia. Materiał memetyczny jest następnie przekazywany przez prosty mechanizm dziedziczenia od rodzica do potomstwa (potomków). Z drugiej strony, w hiperheurystycznym i meta-lamarckowskim MA, pula rozpatrywanych memów kandydatów będzie konkurować na podstawie ich przeszłych zalet w generowaniu lokalnych ulepszeń za pomocą mechanizmu nagrody, decydując o tym, który mem zostanie wybrany, aby przejść do przyszłych lokalnych udoskonalenia. Memy z wyższą nagrodą mają większą szansę na powielenie lub skopiowanie. Do przeglądu MA drugiej generacji; tj. MA biorąc pod uwagę wiele indywidualnych metod uczenia się w systemie ewolucyjnym, odsyła się do czytelnika.

3. generacja

Koewolucję i samo-generujące się IZ można uznać za IZ trzeciej generacji, w przypadku gdy uwzględniono wszystkie trzy zasady spełniające definicje podstawowego ewoluującego systemu. W przeciwieństwie do MA drugiej generacji, która zakłada, że ​​memy, które mają być użyte, są znane a priori, MA trzeciej generacji wykorzystuje oparte na regułach wyszukiwanie lokalne w celu uzupełnienia rozwiązań kandydatów w systemie ewolucyjnym, wychwytując w ten sposób regularnie powtarzające się cechy lub wzorce w przestrzeni problemu.

Kilka uwag projektowych

Częstotliwość i intensywność indywidualnego uczenia się bezpośrednio definiuje stopień ewolucji (eksploracji) w porównaniu z indywidualnym uczeniem się (eksploatacją) w poszukiwaniu tytułu magistra, dla danego ustalonego, ograniczonego budżetu obliczeniowego. Oczywiście bardziej intensywne indywidualne uczenie się zapewnia większą szansę na zbieżność z lokalnymi optymami, ale ogranicza ilość ewolucji, która może być wydatkowana bez ponoszenia nadmiernych zasobów obliczeniowych. Dlatego należy zachować ostrożność podczas ustawiania tych dwóch parametrów, aby zrównoważyć budżet obliczeniowy dostępny w celu osiągnięcia maksymalnej wydajności wyszukiwania. Gdy tylko część populacji osób przechodzi proces uczenia się, należy rozważyć kwestię, który podzbiór osób należy poprawić, aby zmaksymalizować użyteczność wyszukiwania MA. Wreszcie, zastosowana indywidualna procedura / mem uczenia się faworyzuje również inną strukturę sąsiedztwa, stąd potrzeba podjęcia decyzji, którego mema lub memów użyć do danego problemu optymalizacyjnego.

Jak często należy stosować naukę indywidualną?

Jedną z pierwszych kwestii związanych z projektowaniem algorytmów memetycznych jest rozważenie, jak często należy stosować uczenie indywidualne; tj. indywidualna częstotliwość uczenia się. W jednym przypadku uwzględniono wpływ indywidualnej częstotliwości uczenia się na wyniki wyszukiwania MA, gdzie badano różne konfiguracje częstotliwości indywidualnego uczenia się na różnych etapach poszukiwania MA. I odwrotnie, gdzie indziej wykazano, że warto zastosować indywidualne uczenie się dla każdej osoby, jeśli złożoność obliczeniowa indywidualnego uczenia się jest stosunkowo niska.

Na jakich rozwiązaniach należy zastosować naukę indywidualną?

W kwestii doboru odpowiednich osobników spośród populacji EA, które powinny przejść indywidualną naukę, zbadano strategie oparte na sprawności i dystrybucji w celu dostosowania prawdopodobieństwa zastosowania uczenia się indywidualnego na populacji chromosomów w ciągłych problemach wyszukiwania parametrycznego z wydłużaniem pracy przez Landa. do kombinatorycznych problemów optymalizacji . Bambha i in. wprowadzono technikę symulowanego ogrzewania do systematycznego integrowania sparametryzowanego indywidualnego uczenia się z algorytmami ewolucyjnymi w celu osiągnięcia maksymalnej jakości rozwiązania.

Jak długo powinna trwać nauka indywidualna?

Indywidualna intensywność uczenia się jest kwotą budżetu obliczeniowego przeznaczonego na iterację indywidualnego uczenia się; tj. maksymalny budżet obliczeniowy, jaki można wydać na indywidualne uczenie się na ulepszanie pojedynczego rozwiązania. ${\ displaystyle t_ {il}}$

Jakiej indywidualnej metody uczenia się lub memu należy użyć w przypadku konkretnego problemu lub osoby?

W kontekście ciągłej optymalizacji indywidualne uczenie się istnieje w postaci lokalnych heurystyk lub konwencjonalnych dokładnych metod wyliczeniowych. Przykłady indywidualnych strategii uczenia się obejmują wspinaczkę górską, metodę Simplex, metodę Newtona/Quasi-Newtona, metody punktów wewnętrznych, metodę gradientów sprzężonych, wyszukiwanie linii i inne lokalne heurystyki. Zauważ, że większość powszechnych indywidualnych metod uczenia się jest deterministyczna.

Z drugiej strony, w optymalizacji kombinatorycznej, indywidualne metody uczenia się powszechnie istnieją w postaci heurystyk (które mogą być deterministyczne lub stochastyczne), które są dostosowane do konkretnego problemu będącego przedmiotem zainteresowania. Typowe procedury i schematy heurystyczne obejmują wymianę genu k, wymianę krawędzi, pierwszą poprawę i wiele innych.

Aplikacje

Algorytmy memetyczne zostały z powodzeniem zastosowane w wielu rzeczywistych problemach. Chociaż wiele osób stosuje techniki ściśle związane z algorytmami memetycznymi, stosuje się również alternatywne nazwy, takie jak hybrydowe algorytmy genetyczne . Co więcej, wiele osób określa swoje techniki memetyczne jako algorytmy genetyczne .

Badacze wykorzystali algorytmy memetyczne do rozwiązania wielu klasycznych problemów NP . Przytoczyć niektóre z nich: partycjonowanie wykres , wielowymiarowy plecak , problem komiwojażera , kwadratowego problemu przydziału , zestaw problemu okładkę , minimalny kolorowanie grafu , max niezależnego problemu zestaw , bin problemu upakowania oraz uogólnionego problemu przydziału .

Nowsze aplikacje obejmują (ale nie są ograniczone do) analitykę biznesową i naukę o danych , szkolenie w zakresie sztucznych sieci neuronowych , rozpoznawanie wzorców , planowanie ruchu robotów , orientację wiązki , projektowanie obwodów , przywracanie usług elektrycznych, medyczne systemy eksperckie , planowanie pojedynczych maszyn , automatyczne planowanie harmonogramów (zwłaszcza harmonogram NHL ), planowania siły roboczej , pielęgniarka dyżurów optymalizacji , przydział procesora , harmonogram konserwacji (na przykład z sieci elektroenergetycznych) wielowymiarowej problemu plecakowego, VLSI konstrukcji, Clustering z profili ekspresji genów , funkcja wyboru / gen , określanie parametrów iniekcji błędów sprzętowych oraz wieloklasowy, wielocelowy wybór funkcji .

Ostatnie działania w algorytmach memetycznych

• Warsztaty IEEE na temat algorytmów memetycznych (WOMA 2009). Kierownicy programów: Jim Smith, University of the West of England, Wielka Brytania; Yew-Soon Ong, Nanyang Technological University, Singapur; Gustafson Steven, University of Nottingham; Wielka Brytania; Meng Hiot Lim, Nanyang Technological University, Singapur; Natalio Krasnogor, University of Nottingham, Wielka Brytania
• Memetic Computing Journal , pierwsze wydanie ukazało się w styczniu 2009 roku.
• 2008 IEEE World Congress on Computational Intelligence (WCCI 2008) , Hong Kong, Special Session on Memetic Algorithms .
• Wydanie specjalne „Nowe trendy w miękkim informatyce — algorytm memetyczny” , Soft Computing Journal, ukończone i w druku, 2008.
• Grupa zadaniowa ds. Nowych technologii IEEE Computational Intelligence Society ds. Obliczeń memetycznych
• Kongres IEEE na temat obliczeń ewolucyjnych (CEC 2007) , Singapur, specjalna sesja na temat algorytmów memetycznych .
• „Memetic Computing” autorstwa Thomson Scientific's Essential Science Indicators jako wschodzący front badawczy.
• Wydanie specjalne dotyczące algorytmów memetycznych , transakcji IEEE dotyczących systemów, człowieka i cybernetyki - część B: Cybernetyka, tom. 37, nr 1, luty 2007.
• Ostatnie postępy w algorytmach memetycznych , Seria: Badania w zakresie nieostrości i miękkich obliczeń, tom. 166, ISBN   978-3-540-22904-9 , 2005.
• Wydanie specjalne na temat algorytmów memetycznych , Obliczenia ewolucyjne jesień 2004, t. 12, nr 3: v-vi.

Bibliografia