Strona główna

Wstęp do Algorytmów Ewolucyjnych – egzamin 3


Pobieranie 12.07 Kb.
Data19.06.2016
Rozmiar12.07 Kb.
Wstęp do Algorytmów Ewolucyjnych – egzamin 3

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 funkcję celu, podlegającą maksymalizacji, która jest określona wzorem



f(x)=max{-(x-3)2+8,-3(x-7)2+10,0}

Narzucone są ograniczenia kostkowe, przy czym dopuszczalne punkty są zawarte w odcinku [1.5,8].


W algorytmie ewolucyjnym wykorzystywana jest reprodukcja turniejowa binarna (ze zwracaniem) i mutacja, nie ma natomiast krzyżowania.

Mutacja polega na dodaniu do mutowanego punktu wartości losowej opisanej rozkładem jednostajnym na odcinku [-2,2]. Jeśli punkt, będący wynikiem mutacji, wykroczy poza ograniczenie, wówczas jest on zastępowany punktem, powstałym wskutek jego „odbicia” od ograniczenia.


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. Proszę wyprowadzić te prawdopodobieństwa „na piechotę”.

Zad. 2 (20)
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
(10) 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ść populacji, gdy

a) użyte zostanie dodatkowo krzyżowanie uśredniające, pozostałe elementy algorytmu bez zmian,



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

Zad. 3 (10)

W symulacji komputerowej dość często wykorzystuje się pojęcie „liczby losowej”. Ciągiem liczb losowych jest taki ciąg, którego sekwencja nie da się z góry przewidzieć. Czy komputer, którego używał(a) Pan(i) w czasie wykonywania projektu, był w stanie generować liczby losowe? Czy liczby losowe, czy pseudolosowe (tzn. „wyglądające jak losowe”, lecz generowane za pomocą deterministycznego algorytmu) były wykorzystywane w projekcie? Proszę także o wypowiedź, czy wybór generatora liczb losowych/pseudolosowych miał wg Pana(i) intuicji istotny wpływ na wnioski, wyciągane na podstawie statystyk wyników działania algorytmu ewolucyjnego, zebranych z wielu niezależnych symulacji?


©snauka.pl 2016
wyślij wiadomość