Optymalizacja z wykorzystaniem algorytmów ewolucyjnych


Metody optymalizacji realizowane w Optimization Toolbox służą do rozwiązywania zadań optymalizacyjnych nazywanych gładkimi, czyli zadań ciągłych i różniczkowalnych. Niestety gdy funkcja celu jest nieciągła, nieróżniczkowalna albo jest funkcją losową, metody te okazują się nieefektywne. Do rozwiązywania takich zadań zastosowanie znalazły algorytmy ewolucyjne.

Algorytmy genetyczne

Jednym z najbardziej rozpowszechnionych algorytmów ewolucyjnych jest algorytm genetyczny (GA). W Matlabie metody genetycznie mogą być używane na dwa sposoby:

Obecnie algorytm genetyczny wchodzi w skład Optimization Toolbox. W starszych wersjach Matlaba był w osobnym pakiecie Genetic Algorithm and Direct Search Toolbox

Ogólna forma funkcji:

[x, fval] = ga(@fitnessfun, nvars, options)

Podstawowe pojęcia

W algorytmach genetycznych stosuje się pojęcia zapożyczone z genetyki.
Istnieje populacja, która jest zbiorem rozwiązań. Każde rozwiązanie jest nazywane osobnikiem, reprezentowane przez jeden chromosom. Chromosom jest uporządkowanym ciągiem genów.
W populacji dokonuje się selekcji, wybierając lepiej przystosowane osobniki. Stosuje się również operatory genetyczne krzyżowanie i mutowania. Każdy krok iteracji algorytmu genetycznego to generacja. W każdej generacji za pomocą funkcji przystosowania(funkcji celu) oceniane jest przystosowanie każdego osobnika. Na tej podstawie tworzona jest nowa populacja osobników, która jest zbiorem potencjalnych rozwiązań problemu. Krzyżowanie i mutacja mieszają osobniki, dążąc w ten sposób do osiągnięcia globalnego rozwiązania.

Zadanie 1

Znajdź najlepszą wartość funkcji dopasowania dla podanej minimalizowanej funkcji: f(x1,x2,x3) = -(3x1+7x2+6x3).
Wyświetl wykresy: (użyj gaoptimset)

Indywiduum - określony punkt w którym możliwe jest znalezienie funkcji przystosowania.

Zadanie 2

Znajdź najlepszą wartość funkcji dopasowania dla podanej minimalizowanej funkcji: f(x1,x2) = 3x1+9x2.
Sprawdź pozostałe opcje rysowania - jakie inne wykresy możesz otrzymać i co one oznaczają ?

Zadanie 3

Znajdź najlepszą wartość funkcji dopasowanie dla podanej minimalizowanej funkcji:

Znajdź rozwiązanie w przedziale [0, 10].
Wygeneruj wykres funkcji i odczytaj na jego podstawie gdzie leży minimum i maksimum funkcji.

Zadanie 4

W toolboxie Matlaba zdefiniowana jest funkcja Rastrigina. Znajdź funkcję oraz wyświetl jej wykres powierzchniowy. Dla czytelności spróbuj również uzyskać wykres konturowy - po to by zobaczyć lokalne minima i globalne minimum.
Następnie wyszukaj minimum tej funkcji wiedząc, że rozmiar populacji wynosi 100. Co oznacza rozmiar populacji ?

Zadanie 5

Znajdź najlepszą wartość funkcji dopasowania dla podanej minimalizowanej funkcji: f(x1,x2) = 4x1+5x2 w przedziale [1;1.1]. Sprawdź co dzieje się gdy zmienimy maksymalną ilość generacji z standardowej na większą.
Następnie zmień także wartość która zatrzymuje algorytm w momencie gdy nie polepsza się funkcja celu. Ustal limit możliwych generacji na 100.

Zadanie 6

Znajdź najlepszą wartość funkcji dopasowania dla podanej minimalizowanej funkcji: f(x1,x2,x3) = -5sin(x1)sin(x2)sin(x3) + (-sin(5x1)sin(5x2)sin(x3) w przedziale [0;pi].

Zadanie 7

Dla funkcji f(x) = 0.2x3 + 0.1x2 - 8x wykonaj testy dla następujących konfiguracji algorytmu genetycznego:
Jakie parametry dają najlepsze rezultaty ? Zmiany, którego parametru mają największy wpływa na wynik działania algorytmu genetycznego ?