Strategia ewolucji

Część serii o
algorytmie ewolucyjnym
Algorytm genetyczny
Programowanie genetyczne

W informatyce strategia ewolucji (ES) to technika optymalizacji oparta na ideach ewolucji . Należy do ogólnej klasy obliczeń ewolucyjnych lub metodologii sztucznej ewolucji .

Historia

Technika optymalizacji „strategii ewolucji” została stworzona na początku lat 60. XX wieku i dalej rozwijana w latach 70., a później przez Ingo Rechenberga , Hansa-Paula Schwefela i ich współpracowników.

Metody

jako operatory wyszukiwania naturalne reprezentacje zależne od problemu, a przede wszystkim mutacje i selekcję . Podobnie jak w przypadku algorytmów ewolucyjnych , operatory są stosowane w pętli. Iteracja pętli nazywana jest generacją. Sekwencja pokoleń jest kontynuowana aż do spełnienia kryterium zakończenia.

W przypadku przestrzeni poszukiwań o wartościach rzeczywistych mutacja jest wykonywana przez dodanie wektora losowego o rozkładzie normalnym . Wielkość kroku lub siła mutacji (tj. odchylenie standardowe rozkładu normalnego) jest często regulowana przez samoadaptację (patrz okno ewolucji ). Indywidualne rozmiary kroków dla każdej współrzędnej lub korelacje między współrzędnymi, które są zasadniczo określone przez podstawową macierz kowariancji , są w praktyce kontrolowane albo przez samoadaptację, albo przez adaptację macierzy kowariancji ( CMA-ES ). Kiedy krok mutacji jest rysowany z wielowymiarowego rozkładu normalnego przy użyciu ewoluującej macierzy kowariancji , postawiono hipotezę, że ta dostosowana macierz jest aproksymowana odwrotnością Hessiana krajobrazu wyszukiwania. Hipoteza ta została udowodniona dla modelu statycznego opartego na aproksymacji kwadratowej.

Selekcja (środowiskowa) w strategiach ewolucyjnych jest deterministyczna i opiera się wyłącznie na rankingach sprawności, a nie na rzeczywistych wartościach sprawności. Otrzymany algorytm jest zatem niezmienny w odniesieniu do monotonicznych przekształceń funkcji celu. Najprostsza strategia ewolucyjna działa na populacji o rozmiarze dwa: aktualny punkt (rodzic) i wynik jego mutacji. Tylko jeśli mutant jest co najmniej tak dobry, jak mutant w sprawności, staje się rodzicem następnego pokolenia. W przeciwnym razie mutant jest pomijany. To jest (1 + 1)-ES . Mówiąc bardziej ogólnie, mutanty λ mogą być generowane i konkurować z rodzicem, zwanym (1 + λ)-ES . W (1 , λ)-ES najlepszy mutant zostaje rodzicem następnego pokolenia, podczas gdy obecny rodzic jest zawsze pomijany. Dla niektórych z tych wariantów dowody zbieżności liniowej (w sensie stochastycznym ) zostały wyprowadzone na podstawie jednomodalnych funkcji celu.

Współczesne pochodne strategii ewolucyjnej często wykorzystują populację μ rodziców i rekombinację jako dodatkowy operator, zwany (μ/ρ+, λ)-ES . To czyni je mniej skłonnymi do osiedlania się w lokalnych optymach.

Zobacz też

Bibliografia

  • Ingo Rechenberg (1971): Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (praca doktorska). Przedrukowane przez Frommanna-Holzbooga (1973).
  • Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (praca doktorska). Przedrukowany przez Birkäusera (1977).
  • H.-G. Beyer i H.-P. Schwefel. Strategie ewolucji: kompleksowe wprowadzenie . Journal Natural Computing, 1 (1): 3–52, 2002.
  • Hans-Georg Beyer: Theory of Evolution Strategies: Springer 27 kwietnia 2001.
  • Hans-Paul Schwefel: Ewolucja i poszukiwanie optymalnego: Nowy Jork: Wiley & Sons 1995.
  • Ingo Rechenberg: Strategia ewolucji '94. Stuttgart: Frommann-Holzboog 1994.
  • J. Klockgether i HP Schwefel (1970). Eksperymenty z dwufazową dyszą i pustym rdzeniem . AEG-Forschungsinstitut. Grupa projektowa MDH Staustrahlrohr. Berlin, Republika Federalna Niemiec. Proceedings of 11. Symposium on Engineering Aspects of Magneto-Hydrodynamics, Caltech, Pasadena, Cal., 24.–26.3. 1970.
  • M. Emmerich, OM Shir i H. Wang: strategie ewolucji . W: Podręcznik heurystyki, 1-31. Międzynarodowe wydawnictwo Springer (2018).

Ośrodki badawcze

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Evolution_strategy&oldid=1111510483 ”