WsdSI/LS/z5

From WikiZMSI

Algorytmy genetyczne (optymalizacja)

• Napisać skrypt do losowania problemu plecakowego dla zadanej liczby przedmiotów - n.

• Napisać ogólny skrypt realizujący ewolucję algorytmu genetycznego. Parametrami dla skryptu powinny być m.in.: rozmiar populacji, liczba iteracji, wskaźnik na funkcję przystosowania, wskaźnik na funkcję selekcji, wskaźnik na funkcję krzyżowania, wskaźnik na funkcję mutacji.

• Napisać funkcję (skrypt) obliczającą dla całej populacji wektor wartości przystosowania dla problemu plecakowego.

• Napisać funkcje realizujące: selekcję ruletkową, krzyżowanie jednopunktowe, mutację (wszystkie te funkcje powinny przyjmować na wejście całą populację).

Do domu

• Napisać dodatkowe dwie funkcje selekcyjne realizujące: selekcję rankingową i turniejową.

• Napisać funkcję do krzyżowania dwupunktowego.

• Dla wylosowanego problemu plecakowego przeprowadzić ewolucję algorytmu genetycznego. W każdej iteracji odnotować: (1) średnie przystosowanie populacji, (2) przystosowanie najlepszego osobnika w danym pokoleniu, (3) przystosowanie najlepszego osobnika wykrytego w dotychczasowej historii. Wielkości (2) i (3) nie zawszę muszą się pokrywać.

• Napisać skrypt rozwiązujący problem plecakowy poprzez indukcję (opartą na kracie) w sposób dokładny - zgodnie z wiadomościami podanymi na wykładzie. Dla wylosowanego problemu plecakowego (lub kilku) sprawdzić, czy algorytm genetyczny zwraca ten sam wynik, co rozwiązanie dokładne.