SI/L/z6

From WikiZMSI

< SI | L

Napisz w języku Python program porównujący dokładne rozwiązania dyskretnego problemu plecakowego (na podstawie indukcji programowania dynamicznego) z rozwiązaniami przybliżonymi zwracanymi przez algorytm genetyczny.

[edytuj]

Na zajęciach

  • Przygotuj funkcję generującą losowy dyskretny problem plecakowy (DKP). Argumentami wejściowymi powinny być liczba przedmiotów (n) oraz współczynnik skalujący (pozwalający na utrudnienie obliczeniowe przy rozwiązaniu dokładnym). Przykład: 
 items = np.ceil(scale * np.random.rand(n, 2)).astype("int32")
 C = int(np.ceil(0.5 * 0.5 * n * scale))
 v = items[:, 0]
 c = items[:, 1]
  • Zaimplementuj funkcję rozwiązującą DKP w sposób dokładny poprzez indukcję programowania dynamicznego. Funkcja ta powinna zwracać wartość najlepszego upakowania oraz samo rozwiązanie (w formie bitowej) - ten drugi wynik otrzymany poprzez śledzenie ścieżki rozwiązania wstecz.
[edytuj]

Do domu

  • Zgodnie z informacjami z wykładu przygotuj klasę Pythonową realizującą działanie algorytmu genetycznego (AG) dla pewnego dyskretnego problemu maksymalizacji. Konstruktor tej klasy powinien pozwalać na przekazanie do niej rozmiaru problemu (n) oraz nazwy funkcji przystosowania (wskaźnika na funkcję) wraz z jej argumentami.
  • W wariancie podstawowym opracowany algorytm genetyczny ma realizować: selekcję ruletkową, krzyżowanie jednopunktowe oraz mutację. Przyjmij domyślnie: prawdopodobieństwo krzyżowania 0.9 dla każdej pary rodziców oraz prawdopodobieństwo mutacji 0.001 na poziomie każdego bitu. W pierwszych eksperymentach przyjmij także: rozmiar populacji m = 1000, oraz T = 100 iteracji głównej pętli genetycznej.
  • Przy porównywaniu rozwiązania genetycznego i dokładnego raportuj: stosunek wartości upakowania genetycznego do dokładnego, procentową zgodność bitową rozwiązań, wykresy przystosowania populacji w trakcie pracy algorytmu.
  • W wariancie rozszerzonym AG powinien dodatkowo pozwalać na włączenie: selekcji rankingowej, krzyżowania dwupunktowego, oraz na porównanie dwóch różnych funkcji przystosowania (z drastyczną i miękką karą za naruszenie upakowania plecaka).
  • Wskazówka na rzecz selekcji: przydatne może być wykorzystanie funkcji choice z pakietu numpy.random (lub na rzecz obiektu numpy.random.RandomState) pozwalającej na czerpanie losowej próby zgodnie z pewnym obliczonym rozkładem pradowpodobieństwa.
  • W domowych eksperymentach przyjmij współczynnik skali (scale) na rzecz generowania wejściowego DKP równy 2000.
Źródło: "http://wikizmsi.zut.edu.pl/wiki/SI/L/z6"