Strategia ewolucji - Evolution strategy

Część serii na
Algorytm ewolucyjny
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. 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ż

Bibliografia

Bibliografia

Ośrodki badawcze