Wykład 2

„Algorytmy ewolucyjne jako metody optymalizacji globalnej”

1. Definicja problemów ciągłej optymalizacji globalnej.

Przez
oznaczany będzie zbiór rozwiązań dopuszczalnych każdego z definiowanych poniżej problemów optymalizacji. Zakłada się, że
jest zwarty, czyli ograniczony (
) i domknięty.

Definicja 2.1. Funkcję
taką, że

będzie nazywana funkcją celu.

W szczególnych przypadkach zakłada się, że
jest ciągła oraz ma ciągłe pochodne do rzędu 2, to znaczy
.

Formułuje się trzy podstawowe problemy ciągłej optymalizacji globalnej:

(PI):	Znaleźć wszystkie punkty realizujące maksimum globalne funkcji Φ na .
(PII):	Znaleźć wszystkie punkty realizujące maksima lokalne funkcji Φ na .
(PIII):	Znaleźć wszystkie punkty realizujące maksima lokalne izolowane funkcji Φ na .

Wszystkie zdefiniowane problemy optymalizacji globalnej dotyczą znajdowania punktów realizujących maksima globalne i lokalne funkcji Φ na zbiorze
. Jeżeli jednak
jest stałą ograniczającą od góry wartość funkcji
na zbiorze
, to funkcja
dana wzorem

daje możliwość postawienia równoważnego zadania minimalizacji. Na odwrót, jeżeli
jest funkcją celu pewnego zadania minimalizacji, to funkcja
daje możliwość postawienia równoważnego zadania maksymalizacji. Należy zaznaczyć, że warunkiem koniecznym efektywnego konstruowania zadań równoważnych jest znajomość stałej

2. Podstawowe benchmarki optymalizacji globalnej

Efektywność metod optymalizacji sprawdzana jest na przykładowych funkcjach testowych, zwanych funkcjami benchmarkowymi.

2.1 Funkcja Rastrigina

Funkcja Rastrigina jest typowym przykładem liniowo niezależnej funkcji wielomodalnej. Została skonstruowana po raz pierwszy przez Rastrigina jako funkcja dwuwymiarowa.

Funkcja ta posiada wiele minimów lokalnych jednakowoż tylko jedno minimum globalne znajdujące się w punkcie [0,0]. Wartość funkcji w tym punkcie wynosi 0.

Dla n-wymiarów funkcja Rastrigina ma następującą postać:

;
;

Funkcja Rastrigina jest podstawową funkcją testową dla algorytmów genetycznych. Jej rozwiązanie za pomocą metod gradientowych jest bardzo trudne i skomplikowane z powodu dużej ilości ekstremów lokalnych oraz dużego obszaru poszukiwań. 20 - wymiarowa funkcja Rastrigina dana jest następującym wzorem:

,

2. Funkcja Griewanka

Funkcja Griewanka jest funkcją trudną do optymalizacjiz powodu silnej zależności wewnętrznej pomiędzy zmiennymi. 10 - wymiarową funkcję Griewanka definiuje się następującym wzorem:

,

3. Funkcja Schwefela

Funkcja Schwefela jest podobna w geometrycznej interpretacji do funkcji Rastrigina, jest jednak łatwiejsza w implementacji. Cechą charakterystyczną funkcji Schwefela jest to, że minimum globalne jest silnie odległe pod względem wartości funkcji od drugiego w kolejności. W tej funkcji minimum jest ujemną wartością wiec wprowadzona jest stała V, która służy nadaniu minimum globalnemu wartości 0 dla ułatwienia obliczeń. Dokładność stałej V jest zależna od wymaganej dokładności obliczeń. 10 - wymiarową funkcję Schwefela definiuje się następującym wzorem:

,

gdzie: V=4189,829101.

2.4 Funkcja Ackleya

Funkcja Ackleya jest typowym zadaniem minimalizacyjnym. Pierwotnie została napisana jako problem dwuwymiarowy, ale została rozszerzona do n - wymiarów. Optimum funkcji określone jest przez wektor v = (0,...,0), w którym wartość funkcji wynosi 0, F(v) = 0.

2.5 Funkcja Michalewicza

Funkcja Michalewicza jest funkcją wielomodalną, w której ilość ekstremów silnie zależy od wymiaru funkcji. Trudność rozwiązywania jest wprost proporcjonalna do wielkości parametru m. Ma on wpływ na ”stopniowość” dolin i krawędzi funkcji.

2.6 Funkcja de Jonga

Funkcja de Jonga jest najprostszą z funkcji benchmarkowych. Posiada ona jedno ekstremum lokalne będące zarazem ekstremum globalnym. Określana jest wzorem

3. Cechy metod ewolucyjnych

Metody ewolucyjne wyróżniają się kilkoma ważnymi założeniami na tle innych metod optymalizacji. Najważniejsze cechy algorytmów ewolucyjnych można zdefiniować jako cztery następujące reguły:

• nie analizuje się bezpośrednio parametrów zadania, tylko zakodowaną ich postać,

• poszukiwanie rozwiązania optymalnego rozpoczyna się z pewnego zbioru rozwiązań dopuszczalnych,

• korzysta się tylko z definiowanej funkcji celu

• stosuje się stochastyczne a nie deterministyczne reguły wyboru

4. Funkcja fitness i metoda selekcji proporcjonalnej

Miarą przystosowania osobników w populacjach jest funkcja fitness (funkcja przystosowania). Funkcja ta jest zawsze maksymalizowana w trakcie działania algorytmu ewolucyjnego lub genetycznego. Osobniki, dla których wartość funkcji fitness jest większa są lepszymi kandydatami na rozwiązania zadania optymalizacji, które jest pierwotnie definiowane. Przystosowanie osobników nie może być mierzone liczbami ujemnymi, dlatego fitness musi być tak zdefiniowana, aby nie przyjmowała wartości ujemnych.

Niech
oznacza funkcję celu dla zadania minimalizacji oraz niech

Funkcja fitness f może być dla takiego zadania zdefiniowana w następujący sposób:

Wartości funkcji fitness dla osobników w danej populacji są podstawą do sformułowania metody selekcji z tej populacji najlepiej przystosowanych osobników do tzw. puli rodzicielskiej, tzn. populacji na której przeprowadzane są operacje genetyczne.

Selekcja

Selekcja polega na losowaniu ze zwracaniem osobników z populacji bazowej do populacji rodzicielskiej. Losowanie odbywa się metodą probabilistyczną za pomocą współczynnika prawdopodobieństwa obliczanego za pomocą wartości funkcji przystosowania. Jest to typowy mechanizm naturalny odrzucający słabsze osobniki, dający największą szansę przetrwania osobnikom najlepiej przystosowanym. W prostym algorytmie genetycznym prawdopodobieństwo znalezienia się osobnika w populacji potomnej jest wprost proporcjonalne do wartości jego funkcji przystosowania.

Najczęściej stosowaną metodą selekcji jest metoda koła ruletki. Polega ona na n - krotnym losowaniu osobników ze starej do nowej populacji. Ilość osobników w starej i nowej populacji jest jednakowa (równa n). Dla każdego osobnika ze starej populacji przypisane jest różne prawdopodobieństwo wylosowania.

Niech P oznacza populację n-elementową złożoną z osobników
tzn.

Prawdopodobieństwo, że osobnik
będzie wylosowany do populacji rodzicielskiej obliczana jest z następującego wzoru:

Metoda selekcji proporcjonalnej jest najczęściej implementowana w postaci reguły koła ruletki. Zakłada się, że powierzchnia koła ( nazywanego dalej kołem ruletki) jest równa sumie wartości przystosowania dla wszystkich osobników w danej populacji. Powierzchnia koła dzielona jest na tyle części, ile jest osobników w populacji ( n), powierzchnia każdej z tych części jest proporcjonalna do wartości przystosowania dla poszczególnych osobników.

Kręcimy ruletką tyle razy, ile osobników ma liczyć populacja rodzicielska. Za każdym razem notujemy osobnika, któremu odpowiada wylosowany obszar na kole. Osobniki o większym przystosowaniu mają zarezerwowane większe kawałki powierzchni koła i stąd mają większe prawdopodobieństwo bycia wylosowanym do puli rodzicielskiej.

---