Strona główna

Wstęp do Algorytmów Ewolucyjnych – egzamin 2


Pobieranie 13.24 Kb.
Data19.06.2016
Rozmiar13.24 Kb.
Wstęp do Algorytmów Ewolucyjnych – egzamin 2

Czas pisania: 90 minut.

Dozwolone korzystanie z pisemnych pomocy – notatek i książek. Ściąganie skutkuje oceną zero!

Zadań proszę nie przepisywać. Proszę podpisać wszystkie oddawane kartki.


Zad. 1 (20)

Rozważmy algorytm ewolucyjny działający w zbiorze liczb rzeczywistych. W algorytmie tym wykorzystywana jest reprodukcja progowa ze współczynnikiem progu równym 0.5 i mutacja z krzyżowaniem uśredniającym. Prawdopodobieństwo krzyżowania wynosi 0.5.

Mutacja polega na dodaniu do mutowanego punktu wartości losowej opisanej rozkładem trójkątnym na odcinku [-1,1].

Funkcja celu, podlegająca maksymalizacji, jest określona wzorem q(x)=max{-(x-3)2+8,-3(x-7)2+10,0}

Załóżmy, że populacja bazowa zawiera punkty {1,2,3,6,6,7}.

Proszę wyprowadzić i narysować wykres funkcji gęstości prawdopodobieństwa rozkładu próbkowania uzyskiwanego dla takiej populacji.




Zad. 2 (15)

Rozważmy algorytm ewolucyjny optymalizujący funkcję q:Rn R, w którym jest wykorzystywana reprodukcja turniejowa binarna, sukcesja prosta, mutacja gaussowska, bez krzyżowania.


Załóżmy również, że funkcja celu q jest stała. Dla obu rozważanych algorytmów proszę wyprowadzić wzór opisujący wartość możliwie najdokładniej szacującą prawdopodobieństwo zdarzenia, że

a (7) wszystkie punkty w populacji w iteracji numer t pochodzą od dokładnie jednego punktu z populacji t-1 b (8) wszystkie punkty w populacji w iteracji numer t pochodzą od dokładnie jednego punktu z populacji początkowej.


Wielkość populacji bazowej oznaczmy przez μ, liczbę wymiarów – przez n, zaś mutacja ma jednostkową macierz kowariancji.
(dodatkowe zadanie, trudne, za 25 punktów) Proszę odpowiedzieć na pytanie b) zakładając bardziej realistyczny przypadek, że funkcja celu ma różne wartości dla każdego punktu populacji.

Zad. 3 (15)

Załóżmy, że algorytm ewolucyjny został zaimplementowany w postaci programu. Algorytm ten przeprowadza optymalizację w Rn i wykorzystuje mutację rozkładem normalnym, reprodukcję proporcjonalną oraz sukcesję elitarną. W skład elity wchodzi cała populacja bazowa. Funkcja celu ma wartości większe od zera. Zbiór dopuszczalny jest kostką [-1,1]n


(5) Czy wynik działania programu będzie zawsze jednakowy, czy też może się zmieniać z uruchomienia na uruchomienie, jeśli inicjacja populacji zachodzi

a) z rozkładem jednostajnym w kostce [-1,1]n,

b) poprzez powielenie jednego punktu, będącego środkiem układu współrzędnych.


Odpowiedź proszę uzasadnić dla dwóch wariantów:
a) funkcja celu jest wypukła,
b) funkcja celu jest wielomodalna.
(5) Czy rozważany program będzie miał zdolność osiągania otoczenia maksimum lokalnego niezależnie od populacji początkowej wówczas, gdy funkcja celu jest wielomodalna oraz

a) użyta zostanie mutacja rozkładem jednostajnym na kostce [-0.1,0.1]n, pozostałe elementy algorytmu bez zmian,

b) użyta zostanie sukcesja prosta pozostałe elementy algorytmu bez zmian.
(5) Jak zmieni się różnorodność genetyczna populacji, gdy

a) użyte zostanie dodatkowo krzyżowanie uśredniające



b) użyta zostanie sukcesja prosta, pozostałe elementy algorytmu bez zmian.


©snauka.pl 2016
wyślij wiadomość