Strona główna

Wstęp do Algorytmów Ewolucyjnych – egzamin 1


Pobieranie 10.4 Kb.
Data19.06.2016
Rozmiar10.4 Kb.
Wstęp do Algorytmów Ewolucyjnych – egzamin 1

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 turniejowa binarna i mutacja, nie ma natomiast krzyżowania.

Mutacja polega na dodaniu do mutowanego punktu wartości losowej opisanej rozkładem jednostajnym 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 {2,3,6,6,7}.

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

UWAGA: W książce „Wykłady z algorytmów ewolucyjnych” jest błąd w określeniu prawdopodobieństwa reprodukcji turniejowej. W rozwiązaniu zadania proszę wyprowadzić te prawdopodobieństwa.

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)

Jaka jest zależność od liczebności populacji nakładu obliczeń potrzebnego do przeprowadzenia reprodukcji:

(a) proporcjonalnej,

(b) turniejowej (wielkość turnieju s) ,

(c) progowej z progiem θ.


Odpowiedzi proszę krótko uzasadnić.


©snauka.pl 2016
wyślij wiadomość