Naturalna ewolucja strategii - Natural evolution strategy

Strategie naturalnej ewolucji ( NES ) są rodziną numerycznych optymalizacji algorytmów czarna skrzynka problemów. W duchu podobnym do strategii ewolucyjnych , to iteracyjnie aktualizować (ciągły) parametry rozkładu wyszukiwania postępując zgodnie z naturalnych gradient w kierunku wyższej oczekiwanej sprawności.

metoda

Procedura ogólna jest następująca: parametryzowane rozkład wyszukiwania jest używany do produkcji partii punktów wyszukiwania, a funkcja przydatności oceniano w każdym takim punkcie. Parametry rozkładu (która obejmować parametry strategy ) umożliwiają algorytm adaptacyjny uchwycić (lokalny) Struktura funkcji fitness. Na przykład, w przypadku rozkładu Gaussa , to obejmuje średnią i macierz kowariancji . Z próbek, NES szacuje gradient wyszukiwania po parametrach kierunku wyższej oczekiwanej sprawności. NES wykonuje następnie stopniowym gradientem wynurzania wzdłuż naturalnych gradient , drugi sposób zamówienia, które, w przeciwieństwie do zwykłego gradientu renormalizes niepewność zmiana wrt. Ten etap ma decydujące znaczenie, ponieważ uniemożliwia drgania, przedwczesnego konwergencji i niepożądanych efektów wynikających z danego parametryzacji. Cały proces powtarza aż kryterium zatrzymania jest spełniony.

Wszyscy członkowie rodziny NES działają na podstawie tych samych zasad. Różnią się one od rodzaju rozkładu prawdopodobieństwa i gradientu aproksymacji metody. Różne przestrzenie wyszukiwania wymagają różnych rozkładów wyszukiwania; Na przykład, w małej wymiarowości może to być bardzo korzystne do modelowania pełnej macierzy kowariancji. W dużych rozmiarach, z drugiej strony, bardziej skalowalnym rozwiązaniem jest ograniczenie kowariancji do przekątnej tylko. Ponadto, bardzo multimodalne obowiązuje wyszukiwania mogą korzystać z większej liczby ciężkich bielik dystrybucji (takich jak Cauchy'ego , w przeciwieństwie do Gaussa). Ostatnim wyróżnieniem powstaje między dystrybucjami gdzie możemy obliczyć analitycznie naturalnego gradientu, jak i bardziej ogólnych rozkładów gdzie musimy oszacować ją z próbkami.

Szukaj gradienty

Niech oznaczają parametry rozkładu wyszukiwania i funkcji fitness, ocenianego na . NES następnie realizuje cel, jakim jest maksymalizacja oczekiwanej sprawności pod dystrybucji wyszukiwania${\ Displaystyle \} teta$${\ Displaystyle \ pi (x \, | \ \ theta)}$${\ Displaystyle f (x)}$${\ Displaystyle X}$

${\ Displaystyle J (\ theta) = \ OperatorName {E} _ {\ theta} [f (x)] = \ Int F (x) \; \ pi (x \, | \ \ theta) \; dx}$

przez wejście gradientu . Gradient można zapisać w postaci:

${\ Displaystyle \ nabla _ {\ theta} J (\ theta) = \ _ nabla {\ theta} \ Int F (x) \; \ pi (x \, | \ \ theta) \,} dx$

${\ Displaystyle = \ Int F (x) \; \ nabla _ {\ theta} \ pi (x \, | \ \ theta) \,} dx$

${\ Displaystyle = \ Int F (x) \; \ nabla _ {\ theta} \ pi (x \, | \ \ theta) \ {\ Frac {\ pi (x \, | \ \ theta)} {\ pi (x \, | \ \ theta)}} \;} dx$

${\ Displaystyle = \ int {\ Wielkie [} f (x) \; \ nabla _ {\ theta} \ log \ pi (x \, | \ \ theta) {\ Wielkie]} \; \ pi (x \ , | \, \ theta) \;} dx$

${\ Displaystyle = \ OperatorName {E} _ {\ theta} \ lewo [f (x) \; \ nabla _ {\ theta} \ log \ pi (x \, | \ \ theta) \ prawo]}$

to znaczy, że wartość oczekiwana w czasach dziennika pochodne w . W praktyce możliwe jest korzystanie z Monte Carlo przybliżenie na podstawie skończonej liczby próbek ${\ Displaystyle f (x)}$${\ Displaystyle X}$${\ Displaystyle \ N}$

${\ Displaystyle \ nabla _ {\ theta} J (\ theta) \ ok {\ Frac {1} {\ N}} \ suma _ {k = 1} ^ {\ N} f (x_ {k}) \; \ nabla _ {\ theta} \ log \ pi (x_ {k} \, | \, \ theta)}$,

Wreszcie, parametry rozkładu wyszukiwania mogą być aktualizowane iteracyjnie

${\ Displaystyle \ theta \ STRZAŁKA_W_LEWO \ teta + \ ri \ nabla _ {\ theta} J (\ theta)}$

Naturalne wznoszenie gradientu

Zamiast używania zwykłego gradientu stochastycznych o aktualizacje, NES następuje naturalne nachylenie , które, jak wykazano, posiada wiele zalet w stosunku do zwykłego ( wanilia ); gradient, na przykład:

• kierunek gradientu jest niezależna od parametryzacji rozkładu wyszukiwania
• Wielkości te aktualizacje są automatycznie dostosowywane na podstawie niepewności, z kolei przyspieszenie konwergencji na płaskowyże i grzbiety.

Aktualizacja NES jest zatem

${\ Displaystyle \ theta \ STRZAŁKA_W_LEWO \ teta + \ ri \ mathbf {M} ^ {- 1} \ nabla _ {\ theta} J (\ theta)}$,

gdzie jest informacja matrycy Fishera . Matryca Fisher może czasami być dokładnie obliczane, w przeciwnym razie jest szacowana na podstawie próbek ponowne dzienniku pochodne . ${\ Displaystyle \ mathbf {f}}$${\ Displaystyle \ nabla _ {\ theta} \ log \ pi (x | \ theta)}$

kształtowanie fitness

NES wykorzystuje rangę opartych biznesowe kształtowanie w celu nadania algorytm bardziej wytrzymałe i niezmienna pod monotonicznie rosnących przemian funkcji fitness. W tym celu, przydatność ludności przekształca zbiór użyteczności wartości . Niech oznaczają I ^th najlepszego osobnika. Wymiana sprawności za pomocą narzędzia, szacunek nachylenie staje ${\ Displaystyle u_ {1} \ geq \ kropki GEQ u _ \ {\ N}}$${\ Displaystyle x_ {i}}$

${\ Displaystyle \ nabla _ {\ theta} J (\ theta) = \ suma _ {k = 1} ^ {\ N} u_ {k} \; \ nabla _ {\ theta} \ log \ pi (x_ {k } \, | \, \ theta)}$,

Wybór funkcji użyteczności jest wolnym parametrem algorytmu.

Pseudo kod

input: ${\displaystyle f,\;\;\theta _{init}}$

1  repeat
   
2     for  ${\displaystyle k=1\ldots \lambda }$ do                                              // λ is the population size
       
3         draw sample ${\displaystyle x_{k}\sim \pi (\cdot |\theta )}$
       
4         evaluate fitness ${\displaystyle f(x_{k})}$
       
5         calculate log-derivatives ${\displaystyle \nabla _{\theta }\log \pi (x_{k}|\theta )}$
       
6     end
   
7     assign the utilities ${\displaystyle u_{k}}$                                          // based on rank
   
8     estimate the gradient ${\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )}$
   
9     estimate ${\displaystyle \mathbf {F} \leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }\nabla _{\theta }\log \pi (x_{k}|\theta )\nabla _{\theta }\log \pi (x_{k}|\theta )^{\top }}$           // or compute it exactly 
   
10    update parameters ${\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J}$                        // η is the learning rate

11 until stopping criterion is met

Zobacz też

• obliczenia ewolucyjne
• Macierz kowariancji adaptacja strategii Evolution (CMA-ES)

Bibliografia

• D. Wierstra T. Schaul J. i Peters, J. Schmidhuber (2008). Naturalna ewolucja Strategies . IEEE Kongres obliczeń ewolucyjnych (CEC).
• Y. Sun, D. Wierstra T. Schaul Schmidhuber J. (2009). Stochastic wyszukiwanie za pomocą naturalnych gradient . Międzynarodowa Konferencja na temat uczenia maszynowego (ICML).
• T. Glasmachers T. Schaul Y. Sun, D. Wierstra Schmidhuber J. (2010). Wykładniczy naturalna ewolucja Strategies . Genetyczne i obliczeń ewolucyjnych Conference (GECCO).
• T. Schaul T. Glasmachers Schmidhuber J. (2011). Wymiary wysokie i ciężkie ogony dla naturalnej ewolucji strategii . Genetyczne i obliczeń ewolucyjnych Conference (GECCO).
• T. Schaul (2012). Naturalna ewolucja Strategie zbiegają się funkcji Sphere . Genetyczne i obliczeń ewolucyjnych Conference (GECCO).

Linki zewnętrzne

• Kolekcja NES wdrożeń w różnych językach