Ewolucja różnicowa - Differential evolution

Różnicowa ewolucja optymalizująca funkcję 2D Ackleya.

W obliczeń ewolucyjnych , ewolucja różnica ( DE ) to metoda, która optymalizuje problem przez iteracyjnie próbując poprawić rozwiązanie kandydata w odniesieniu do danego środka jakości. Takie metody są powszechnie znane jako metaheurystyki, ponieważ przyjmują niewiele lub nie przyjmują żadnych założeń dotyczących optymalizowanego problemu i mogą przeszukiwać bardzo duże przestrzenie potencjalnych rozwiązań. Jednak metaheurystyki, takie jak DE, nie gwarantują znalezienia optymalnego rozwiązania.

DE jest używany dla wielowymiarowych funkcji o wartościach rzeczywistych, ale nie wykorzystuje gradientu optymalizowanego problemu, co oznacza, że ​​DE nie wymaga różniczkowania problemu optymalizacji , jak jest to wymagane w klasycznych metodach optymalizacji, takich jak metody gradientu i quasi-niutona . Dlatego DE może być również stosowany w problemach optymalizacji, które nie są nawet ciągłe , są hałaśliwe, zmieniają się w czasie itp.

DE optymalizuje problem, utrzymując populację kandydujących rozwiązań i tworząc nowe kandydujące rozwiązania, łącząc istniejące zgodnie z prostymi formułami, a następnie utrzymując dowolne rozwiązanie kandydujące, które ma najlepszy wynik lub dopasowanie do danego problemu optymalizacji. W ten sposób problem optymalizacji jest traktowany jako czarna skrzynka, która stanowi jedynie miarę jakości danego potencjalnego rozwiązania, a zatem gradient nie jest potrzebny.

DE został wprowadzony przez Storn i Price w latach 90. XX wieku. Książki zostały opublikowane na teoretycznych i praktycznych aspektach korzystania DE w obliczeniach równoległych , optymalizacja wielokryterialna , ograniczonym optymalizacji , a książki zawierają również badań obszarów zastosowania. Ankiety dotyczące wieloaspektowych aspektów badawczych DE można znaleźć w artykułach w czasopismach.

Algorytm

Podstawowy wariant algorytmu DE działa na podstawie populacji rozwiązań kandydujących (zwanych agentami). Agenci ci są przemieszczani w przestrzeni wyszukiwania za pomocą prostych wzorów matematycznych, aby połączyć pozycje istniejących agentów z populacji. Jeśli nowa pozycja agenta jest poprawą, jest akceptowana i stanowi część populacji, w przeciwnym razie nowa pozycja jest po prostu odrzucana. Proces jest powtarzany i dzięki temu ma się nadzieję, ale nie gwarantuje się, że ostatecznie zostanie odkryte satysfakcjonujące rozwiązanie.

Formalnie niech będzie funkcja fitness, która musi zostać zminimalizowana (zauważ, że maksymalizację można wykonać, zamiast tego rozważając funkcję ). Funkcja przyjmuje rozwiązanie kandydata jako argumentu w postaci wektora z liczb rzeczywistych i tworzy rzeczywistą liczbę jako wyjście co wskazuje na przydatność danego rozwiązania kandydującego. Gradientu od nie jest znana. Celem jest znalezienie rozwiązania dla wszystkich w przestrzeni wyszukiwania, co oznacza, że jest to globalne minimum. ${\ Displaystyle f: \ mathbb {R} ^ {n} \ do \ mathbb {R}}$${\displaystyle h:=-f}$${\displaystyle f}$${\ Displaystyle \ mathbf {m} }$${\ Displaystyle f (\ mathbf {m} ) \ leq f (\ mathbf {p} )}$${\displaystyle \mathbf {p}}$${\ Displaystyle \ mathbf {m} }$

Wyznaczmy kandydata na rozwiązanie (agenta) w populacji. Podstawowy algorytm DE można wtedy opisać w następujący sposób: ${\ Displaystyle \ mathbf {x} \ w \ mathbb {R} ^ {n}}$

• Wybierz parametry , i . to wielkość populacji, tj. liczba kandydatów na agentów lub „rodziców”; klasyczne ustawienie to 10 . Parametr nazywa się prawdopodobieństwem krzyżowania, a parametr nazywa się wagą różniczkową . Ustawienia klasyczne to i . Te wybory mogą mieć duży wpływ na wydajność optymalizacji; patrz poniżej.${\displaystyle {\text{CR}}\w [0,1]}$${\displaystyle F\w [0,2]}$${\ Displaystyle {\ tekst {NP}} \ geq 4}$${\displaystyle {\tekst{NP}}}$${\ Displaystyle n}$${\displaystyle {\text{CR}}\w [0,1]}$${\displaystyle F\w [0,2]}$${\ Displaystyle F = 0,8}$${\ Displaystyle CR = 0,9}$
• Zainicjuj wszystkich agentów z losowymi pozycjami w przestrzeni wyszukiwania.${\displaystyle \mathbf {x}}$
• Dopóki nie zostanie spełnione kryterium zakończenia (np. liczba wykonanych iteracji lub osiągnięta odpowiednia sprawność), powtarzaj następujące czynności:
  • Dla każdego agenta w populacji wykonaj: ${\displaystyle \mathbf {x}}$
    • Wybierz trzech agentów i losowo z populacji muszą się różnić od siebie oraz od agenta . ( nazywa się wektorem „bazowym”).${\displaystyle \mathbf {a},\mathbf {b}}$${\displaystyle \mathbf {c}}$${\displaystyle \mathbf {x}}$${\displaystyle \mathbf {a}}$
    • Wybierz losowy indeks, w którym znajduje się wymiar optymalizowanego problemu.${\ Displaystyle R \ w \ {1, \ ldots, n \}}$${\ Displaystyle n}$
    • Potencjalną nową pozycję agenta oblicz w następujący sposób: ${\ Displaystyle \ mathbf {y} = [y_ {1}, \ ldots, y_ {n}]}$
      • Dla każdego wybierz losową liczbę równomiernie rozłożoną${\ Displaystyle i \ w \ {1, \ ldots, n \}}$${\ Displaystyle R_ {i} \ Sim U (0,1)}$
      • Jeśli lub następnie ustaw inaczej ustaw . (Pozycja indeksu jest zastępowana na pewno.)${\displaystyle r_{i}<CR}$${\displaystyle i=R}$${\ Displaystyle y_ {i} = a_ {i} + F \ razy (b_ {i}-c_ {i})}$${\ Displaystyle y_ {i} = x_ {i}}$${\ Displaystyle R}$
    • Jeśli następnie zastąp czynnik w populacji ulepszonym lub równym kandydatem na rozwiązanie .${\ Displaystyle f (\ mathbf {y} ) \ leq f (\ mathbf {x} )}$${\displaystyle \mathbf {x}}$${\displaystyle \mathbf {y}}$
• Wybierz agenta z populacji, który ma najlepszą kondycję i zwróć go jako najlepsze znalezione rozwiązanie kandydata.

Wybór parametrów

Krajobraz wydajności pokazujący, jak podstawowy DE działa łącznie w problemach porównawczych Sphere i Rosenbrocka przy zmianie dwóch parametrów DE i , oraz utrzymywaniu stałego = 0,9.${\displaystyle {\tekst{NP}}}$${\ Displaystyle {\ tekst {F}}}$${\displaystyle {\tekst{CR}}}$

Wybór parametrów DE i może mieć duży wpływ na wydajność optymalizacji. Dobór parametrów DE dających dobre osiągi był więc przedmiotem wielu badań. Praktyczne zasady doboru parametrów opracowali Storn i in. oraz Liu i Lampinen. Matematyczną analizę zbieżności dotyczącą doboru parametrów przeprowadził Zaharie. ${\ Displaystyle F {\ tekst {CR}}}$${\displaystyle {\tekst{NP}}}$

Warianty

Warianty algorytmu DE są stale rozwijane w celu poprawy wydajności optymalizacji. W podstawowym algorytmie podanym powyżej możliwych jest wiele różnych schematów przeprowadzania krzyżowania i mutacji agentów, patrz np.

Zobacz też

• Algorytm optymalizacji Mayfly
• Algorytm sztucznej kolonii pszczół
• CMA-ES
• Strategia ewolucji
• Algorytm genetyczny

Bibliografia