Ewolucja Różnicowa: Optymalizator Bez Obliczeń Pochodnych

Optymalizacja bez gradientu

Gradient Descent wymaga różniczkowalnej funkcji celu i, idealnie, dobrze zachowanej. Wiele rzeczywistych celów nie spełnia tych kryteriów – pochodzą z czarnej skrzynki symulacji, zawierają decyzje dyskretne lub są po prostu zbyt skomplikowane do różniczkowania. Ewolucja Diferencyjna (DE), wprowadzona przez Rainera Storna i Kennetha Price'a w 1997 roku, omija to całe zagadnienie: ocenia funkcję celu tylko w punktach, nigdy jej pochodnej, a całą populację rozwiązań kandydatów przemieszcza wykorzystując jedynie arytmetykę na samej populacji.

Wariant DE/rand/1/bin

Klasyczny i najczęściej używany wariant, nazwany DE/rand/1/bin ze względu na jego styl mutacji i krzyżowania, robi trzy rzeczy z każdym elementem populacji za każdym pokoleniem:

dla każdego wektora docelowego x_i w populacji: wybierz r1, r2, r3 niezależne od siebie, różne od i oraz losowe spośród populacji mutacja v = x_r1 + F * (x_r2 - x_r3) // F: waga różnicowa próbka u_j = v_j jeśli rand() < CR (lub j == losowy indeks) = x_i_j w przeciwnym razie // CR: współczynnik krzyżowania jeśli f(u) jest lepsze niż f(x_i): x_i (następne pokolenie) = u w przeciwnym razie: x_i (następne pokolenie) = x_i // selekcja Krok mutacji to nazwany nim ruch: różnica między dwoma losowo wybranymi członkami populacji, przeskalowana przez F, staje się zakłóceniem dodanym do trzeciego. Krzyżowanie następnie miesza mutant z oryginalnym wektorem docelowym, krok po kroku wzdłuż wymiarów, kontrolowane przez CR. Selekcja jest krótkowzroczna – próbka zastępuje cel tylko wtedy, gdy poprawia ona ściśle wartość celu, więc najlepsza znana fitness populacji nigdy nie pogarsza się z pokolenia na pokolenie.

for each target vector x_i in the population:
  pick r1, r2, r3 distinct, all != i, at random from the population

  mutant  v = x_r1 + F * (x_r2 - x_r3)          // F: differential weight

  trial u_j = v_j  if rand() < CR (or j == random index)
            = x_i_j  otherwise                   // CR: crossover rate

  if f(u) is better than f(x_i):  x_i (next gen) = u
  else:                            x_i (next gen) = x_i   // selection

Dlaczego wektor różnicy ma odpowiedni zakres

Elegancki charakter mutacji w DE polega na tym, że krok uwzględniający jest samoregulowany bez potrzeby dodatkowych mechanizmów: na wczesnym etapie poszukiwań, gdy populacja jest szeroko rozproszona po przestrzeni poszukiwań, różnice między x_r2 a x_r3 są duże i mutacja podejmuje duże, eksploracyjne kroki. W miarę jak populacja zbliża się do obiecującego obszaru, te same różnice automatycznie maleją, a mutacja naturalnie doprecyzowuje poszukiwania za pomocą mniejszych kroków. Nie jest wymagany oddzielny harmonogram chłodzenia, jak w przypadku symulowanego wyżarzania – własna zróżnicowanie populacji dostarcza go.

Samonastawiane warianty

Klasyczny DE nadal pozostawia F i CR jako stałe hiperparametry, które muszą być dostrajane dla każdego problemu. Późniejsze warianty eliminują nawet to: SaDE (samonastawiający się DE) i JADE kodują F i CR jako ewoluujące cechy dołączone do każdego osobnika, próbkowane z rozkładu, który sam adaptuje się na podstawie wartości F i CR, które generowały udane wektory testowe w ostatnich pokoleniach. To całkowicie zamyka pętlę – algorytm uczy się własnego harmonogramu kroku i współczynnika mieszania na podstawie kształtu rozwiązywanego problemu, kosztem niewielkiej dodatkowej pracy administracyjnej na każde pokolenie.

Porównywanie wyników na standardowych funkcjach testowych

DE jest regularnie oceniane na niewielkim zestawie funkcji testowych zaprojektowanych w celu symulacji problemów. Funkcja Rosenbroka charakteryzuje się wąskim, zakrzywionym dołem prowadzącym do minimum – łatwo jest znaleźć dół, ale powolne przemieszczanie się po nim. Funkcja Rastrigina posiada regularnie rozmieszczone lokalne minima na gładkiej misce, testując, czy optymalizator może uniknąć utknięcia. Funkcja Ackleya jest prawie płaska w odległości od początku, z ostrym centralnym dołem, testując, czy optymalizator może znaleźć sygnał na dużym, niemal pozbawionym cech plateau. DE niezawodnie znajduje globalne minimum wszystkich trzech podanych funkcji po odpowiedniej liczbie generacji, choć jego konwergencja w przypadku Rosenbroka jest szczególnie powolna w porównaniu z metodą gradientową, która mogłaby wykorzystać lokalny zwężony kształt dołka bezpośrednio – to sprawiedliwa cena za brak potrzeby istnienia lub obliczenia tego zwężonego kształtu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Differential Evolution Optimizer i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.