Przejdź do treści
Wróć do wyników wyszukiwania

Ewolucja Różnicowa — Globalny Optymalizator Stochastyczny

Autor metody
Rainer Storn & Kenneth Price
Rok
1997
Typ
Population-based stochastic metaheuristic

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Ewolucja Różnicowa (DE), wprowadzona przez Rainera Storna i Kennetha Price'a w 1997 roku, jest stochastycznym algorytmem optymalizacyjnym opartym na populacji, przeznaczonym dla ciągłych przestrzeni parametrów.

Generuje ona kandydatów na rozwiązania poprzez łączenie różnic wektorowych między istniejącymi członkami populacji, co czyni ją potężną i mało zasobożerną alternatywą dla algorytmów genetycznych i optymalizacji rojem cząstek, gdy krajobraz poszukiwań jest niewypukły, wielomodalny lub słabo przystosowany do metod gradientowych.

Intuicja stojąca za metodą

Wyobraźmy sobie grupę odkrywców rozproszonych po nieznanym terenie, poszukujących najniższej doliny. Na każdym kroku każdy odkrywca obserwuje trzech losowo wybranych kolegów, porusza się w kierunku sugerowanym przez różnicę między dwoma z nich, przeskalowaną przez współczynnik kroku, a następnie decyduje, czy nowa pozycja, czy stara jest lepszym terenem. Po wielu rundach cała grupa stopniowo skupia się wokół najgłębszej doliny, którą wspólnie znalazła. Ewolucja Różnicowa działa dokładnie w ten sposób: „różnica” między dwoma wektorami populacji działa jako kierunek poszukiwań, a współczynnik skali F kontroluje śmiałość każdego kroku.

Historia

Ewolucja Różnicowa została wprowadzona przez Rainera Storna i Kennetha Price'a w ich przełomowym artykule z 1997 roku w Journal of Global Optimization. Algorytm wyewoluował z wcześniejszych prac Price'a nad wyżarzaniem genetycznym i eksperymentów Storna z krzyżowaniem zmiennoprzecinkowym. Oryginalny wariant, obecnie nazywany DE/best/1/bin, okazał się konkurencyjny — a często lepszy — od ówczesnych strategii ewolucyjnych i algorytmów genetycznych na standardowych benchmarkach. Obszerny przegląd autorstwa Das, Mullick i Suganthan (2016) skatalogował ponad dwie dekady wariantów, schematów adaptacyjnych i zastosowań, ustanawiając DE jako jedną z fundamentalnych metod w literaturze metaheurystycznej.

Kiedy stosować

Ewolucja Różnicowa jest odpowiednia, gdy funkcja celu jest ciągła, potencjalnie niedyskretna lub wielomodalna, a granice poszukiwań dla wszystkich parametrów są znane z góry. Nie wymaga informacji o gradiencie ani założeń o normalności, dzięki czemu nadaje się do projektowania inżynierskiego, dostrajania hiperparametrów, kalibracji modeli symulacyjnych i wszelkich zadań optymalizacji typu „czarna skrzynka”. Rozmiar populacji wynoszący około 10 razy więcej niż liczba parametrów jest częstym punktem wyjścia. DE nie powinno być stosowane do problemów czysto dyskretnych lub kombinatorycznych; wymaga również co najmniej 1 000 iteracji do niezawodnej zbieżności — jeśli budżet ewaluacji funkcji jest bardzo ograniczony, optymalizacja bayesowska jest bardziej efektywnym pod względem liczby próbek alternatywą.

Ograniczenia i uwagi

  • Zbieżność może być powolna, jeśli liczba iteracji jest niewystarczająca; mniej niż 1 000 generacji często daje suboptymalny wynik.
  • Wydajność jest wrażliwa na wybór F i CR — źle dobrane parametry mogą prowadzić do przedwczesnej zbieżności lub nadmiernie powolnego postępu.
  • Nie jest przeznaczony do czysto dyskretnych lub kombinatorycznych przestrzeni poszukiwań; istnieją dyskretne rozszerzenia, ale są one mniej standardowe.
  • Każda iteracja wymaga oceny funkcji celu NP razy, co może być kosztowne, gdy każda ocena jest obliczeniowo kosztowna.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Nie wymaga informacji o gradiencie — działa z dowolną funkcją celu typu „czarna skrzynka”, w tym z niedyskretnymi i zaszumionymi.
  • Bardzo niewiele parametrów kontrolnych (F, CR, NP) w stosunku do jego mocy poszukiwawczej, co czyni go stosunkowo łatwym do skonfigurowania.
  • Naturalnie radzi sobie z wielomodalnymi krajobrazami, gdzie optymalizatory gradientowe zbiegają do lokalnych optimów.
  • Ewaluacje populacji są niezależne i mogą być łatwo zrównoleglone, skracając czas rzeczywisty na systemach wielordzeniowych.
  • Konkurencyjny z algorytmami genetycznymi i optymalizacją rojem cząstek na wielu benchmarkach, przy jednoczesnym użyciu prostszej reguły aktualizacji.

Zastosowania

  • Kalibracja modeli symulacyjnych i agentowych, których funkcje celu są nieanalityczne.
  • Optymalizacja hiperparametrów dla potoków uczenia maszynowego, gdy przestrzeń poszukiwań jest ciągła i ograniczona.
  • Problemy projektowania inżynierskiego, takie jak projektowanie anten, optymalizacja konstrukcji i strojenie regulatorów.
  • Trenowanie sieci neuronowych i dopasowywanie modeli nieliniowych w inżynierii i naukach przyrodniczych.
  • Optymalizacja wag portfela i estymacja parametrów w modelach finansowych szeregów czasowych.

Jak to działa

Jak to działa

1

Populacja NP wektorów-kandydatów na rozwiązania jest losowana jednostajnie z rozkładu jednostajnego w ramach zdefiniowanych granic poszukiwań dla każdego parametru. Granice poszukiwań muszą być określone przez użytkownika przed rozpoczęciem algorytmu; DE nie może ich wywnioskować z problemu. Dobra populacja początkowa pokrywa całą dopuszczalną przestrzeń, aby algorytm nie przegapił obiecujących regionów na samym początku.

2

Dla każdego wektora docelowego w populacji losuje się trzy różne wektory. Wektor mutant jest tworzony przez dodanie przeskalowanej różnicy dwóch z nich do trzeciego: v = x_r1 + F*(x_r2 - x_r3), gdzie F jest współczynnikiem skali (zazwyczaj 0,4–1,0). Ten krok oparty na różnicy odróżnia DE od innych algorytmów ewolucyjnych i zapewnia mu samoadaptacyjną informację kierunkową bez konieczności obliczania gradientu.

3

Wektor próbny jest budowany poprzez mieszanie wektora mutant i oryginalnego wektora docelowego element po elemencie. Każdy element jest pobierany z mutanta z prawdopodobieństwem CR (współczynnik krzyżowania, zazwyczaj 0,5–1,0), a w przeciwnym razie z wektora docelowego; co najmniej jeden element jest zawsze pobierany z mutanta. Ten krok kontroluje równowagę między eksploracją a eksploatacją: wysokie CR sprzyja mutantowi, niskie CR zachowuje więcej z obecnego rozwiązania.

4

Wektor próbny jest oceniany na podstawie funkcji celu i porównywany z wektorem docelowym. Jeśli próba osiągnie równą lub lepszą wartość celu, zastępuje ona cel w następnej generacji; w przeciwnym razie cel pozostaje niezmieniony. Ta zachłanna selekcja jeden do jednego zapobiega pogorszeniu się populacji i zapewnia monotoniczną poprawę najlepszego znalezionego rozwiązania.

5

Mutacja, krzyżowanie i selekcja powtarzają się przez wystarczającą liczbę generacji (zazwyczaj 1 000 lub więcej), aż do spełnienia kryterium zbieżności — na przykład, zmiana najlepszej wartości celu spadnie poniżej progu tolerancji lub zostanie osiągnięta maksymalna liczba iteracji. Najlepszy wektor w ostatecznej populacji jest rozwiązaniem algorytmu.

Częste pułapki

  • Uruchamianie DE z zbyt małą liczbą iteracji (poniżej ~1 000) jest najczęstszym błędem — algorytm nie miał wystarczającej liczby generacji do zbieżności, a wynik należy traktować jako wstępny; przełącz się na optymalizację bayesowską, jeśli budżet ewaluacji jest ograniczony.
  • Ustawienie współczynnika skali F zbyt nisko powoduje przedwczesne załamanie różnorodności; ustawienie go zbyt wysoko uniemożliwia zbieżność. Zacznij od F w zakresie [0,4, 1,0] i dostrajaj empirycznie.
  • Pominięcie lub błędne określenie granic poszukiwań jest krytycznym błędem — DE używa granic do inicjalizacji populacji i da bezsensowne wyniki, jeśli granice są zbyt wąskie lub nieobecne.
  • Traktowanie DE jako jednorazowego uruchomienia jest ryzykowne na wielomodalnych krajobrazach — uruchom kilka niezależnych prób z różnych losowych ziaren i zgłoś najlepsze rozwiązanie znalezione we wszystkich uruchomieniach.

Najczęściej zadawane pytania

Jak wybrać współczynnik skali F i współczynnik krzyżowania CR?

Najczęściej cytowane wartości domyślne to F = 0,8 i CR = 0,9 dla strategii DE/best/1/bin. W praktyce F kontroluje wielkość kroku — typowe wartości to około 0,4–1,0 — a CR kontroluje, jak bardzo mutant zastępuje cel. Jeśli populacja zbiega zbyt szybko, zwiększ F lub zmniejsz CR. Adaptacyjne warianty DE (jDE, JADE) automatycznie dostosowują te parametry podczas działania, co jest rozsądnym wyborem, gdy ręczne dostrajanie jest niepraktyczne.

Ile generacji jest potrzebnych?

Zgodnie z zasadą kciuka zaleca się co najmniej 1 000 generacji. W przypadku problemów o dużej wymiarowości (wiele parametrów) lub złożonych krajobrazów, może być konieczne więcej iteracji. Obserwuj wartość celu najlepszego rozwiązania w kolejnych generacjach: jeśli nie zmieniła się przez setki iteracji, DE prawdopodobnie zbiegło — lub utknęło, w takim przypadku zaleca się ponowne uruchomienie z nowym losowym ziarnem.

Jak DE wypada w porównaniu z algorytmami genetycznymi i optymalizacją rojem cząstek?

Wszystkie trzy są metaheurystykami opartymi na populacji dla optymalizacji ciągłej. DE zazwyczaj używa mniej parametrów kontrolnych niż GA i ma prostszą, deterministyczną regułę aktualizacji w porównaniu do PSO. Na wielu standardowych benchmarkach DE jest konkurencyjny lub przewyższa oba, ale wydajność zależy od problemu. Wybór często sprowadza się do znajomości i dostępnych implementacji, a nie do uniwersalnego rankingu.

Czy DE może obsługiwać parametry całkowite lub kategoryczne?

DE jest przeznaczony do przestrzeni ciągłych. Parametry całkowite można uwzględnić, zaokrąglając rozwiązanie ciągłe do najbliższej liczby całkowitej po każdej aktualizacji, ale jest to przybliżenie. Problemy czysto kategoryczne lub kombinatoryczne — takie jak harmonogramowanie czy trasowanie — są lepiej obsługiwane przez metody przeznaczone do przestrzeni dyskretnych, takie jak optymalizacja koloni mrówek czy wyszukiwanie tabu.

Pokrewne metody

Źródła

  1. Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.

    Otwórz odnośnik DOI
    Skopiowano.