Strategia ewolucji - Evolution strategy
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. i rozwinięta w latach 70., a później przez Ingo Rechenberga , Hansa-Paula Schwefela i ich współpracowników.
Metody
Strategie ewolucji wykorzystują naturalne reprezentacje zależne od problemu, a przede wszystkim mutacje i selekcję jako operatory wyszukiwania. Podobnie jak w algorytmach ewolucyjnych , operatory są stosowane w pętli. Iteracja pętli nazywana jest generacją. Sekwencja pokoleń jest kontynuowana aż do spełnienia kryterium terminacji.
W przypadku przestrzeni poszukiwań o wartościach rzeczywistych mutację wykonuje się przez dodanie losowego wektora o rozkładzie normalnym . Wielkość kroku lub siła mutacji (tj. odchylenie standardowe rozkładu normalnego) często zależy od samoadaptacji (patrz okno ewolucji ). Wielkości poszczególnych kroków dla każdej współrzędnej lub korelacje między współrzędnymi, które są zasadniczo zdefiniowane przez podstawową macierz kowariancji , są w praktyce kontrolowane albo przez samoadaptację, albo przez adaptację macierzy kowariancji ( CMA-ES ). Gdy krok mutacji jest wyciągany z wielowymiarowego rozkładu normalnego przy użyciu ewoluującej macierzy kowariancji , postawiono hipotezę, że ta dostosowana macierz jest przybliżoną odwrotnością hesjanu krajobrazu poszukiwań. Hipoteza ta została potwierdzona dla modelu statycznego opartego na przybliżeniu kwadratowym.
Wybór (środowiskowy) w strategiach ewolucyjnych jest deterministyczny i opiera się wyłącznie na rankingach sprawności, a nie na rzeczywistych wartościach sprawności. Otrzymany algorytm jest więc niezmienniczy względem monotonicznych przekształceń funkcji celu. Najprostsza strategia ewolucji działa na populacji o rozmiarze dwa: aktualny punkt (rodzic) i wynik jego mutacji. Tylko jeśli sprawność mutanta jest co najmniej tak dobra jak rodzica, staje się rodzicem następnego pokolenia. W przeciwnym razie mutant zostanie zignorowany. To jest (1+1)-ES . Bardziej ogólnie, mutanty λ mogą być generowane i konkurować z rodzicem, zwanym (1 + λ)-ES . W (1 , λ)-ES najlepszy mutant staje się rodzicem następnego pokolenia, podczas gdy obecny rodzic jest zawsze pomijany. W przypadku 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 sprawia, że są mniej skłonni do osiedlania się w lokalnym optimie.
Zobacz też
- Strategia ewolucji adaptacji macierzy kowariancji (CMA-ES)
- Optymalizacja bez pochodnych
- Obliczenia ewolucyjne
- Algorytm genetyczny
- Strategia naturalnej ewolucji
- Ewolucyjna teoria gier
Bibliografia
Bibliografia
- Ingo Rechenberg (1971): Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (rozprawa doktorska). Przedruk Frommann-Holzboog (1973).
- Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (rozprawa doktorska). Przedruk Birkhäuser (1977).
- H.-G. Beyera i H.-P. Schwefel. Strategie ewolucji: kompleksowe wprowadzenie . Journal Natural Computing, 1 (1): 3-52, 2002.
- Hans-Georg Beyer: Teoria strategii ewolucji: Springer 27 kwietnia 2001 r.
- Hans-Paul Schwefel: Ewolucja i optymalne poszukiwanie: Nowy Jork: Wiley & Sons 1995.
- Ingo Rechenberg: Strategia ewolucji '94. Stuttgart: Frommann-Holzboog 1994.
- J. Klockgether i HP Schwefel (1970). Eksperymenty z dyszą dwufazową i strumieniem z pustym rdzeniem . AEG-Forschungsinstitut. Grupa projektowa MDH Staustrahlrohr. Berlin, Republika Federalna Niemiec. Materiały XI Sympozjum Inżynierskich Aspektów Magnetohydrodynamiki, Caltech, Pasadena, Cal., 24.–26.3. 1970.
- M. Emmerich, OM Shir i H. Wang: Strategie ewolucji . W: Handbook of Heuristics, 1-31. Wydawnictwo Springer International (2018).