SNiASI/L/z2

From WikiZMSI

< SNiASI | L

Cel: rozwiązanie dyskretnego problemu plecakowego ( ang. 0/1 knapsack problem) z użyciem algorytmu genetycznego.

Spis treści

[edytuj]

Dyskretny problem plecakowy

Dane wejściowe: Dany jest ciąg n elementów Parser nie mógł rozpoznać (nieznany błąd): S=\{s_1, s_2,...,s_n\}\,\! 

gdzie Parser nie mógł rozpoznać (nieznany błąd): s_i
to para atrybutów Parser nie mógł rozpoznać (nieznany błąd): (w_i,c_i)

. Atrybut Parser nie mógł rozpoznać (nieznany błąd): w_i 

oznacza wagę (rozmiar) elementu, a Parser nie mógł rozpoznać (nieznany błąd): c_i
jego wartość. Parser nie mógł rozpoznać (nieznany błąd): C
to pojemność plecaka.

Problem: Znaleźć podzbiór Parser nie mógł rozpoznać (nieznany błąd): S^R \sub S 

taki, że suma wartości wszystkich elementów w podzbiorze Parser nie mógł rozpoznać (nieznany błąd): S^R (\sum_{j \in S^R} c_j)
jest maksymalizowana, a suma wag elementów z podzbioru Parser nie mógł rozpoznać (nieznany błąd): S^R
jest mniejsza lub równa Parser nie mógł rozpoznać (nieznany błąd): C (\sum_{j\in S^R} w_j \le C)


Interpretacja: Problem plecakowy pojawia się w każdej sytuacji, gdzie mamy do czynienia z wyborem elementów z ograniczeniem budżetu. Należy wówczas odpowiedzieć na pytanie: jakie produkty należy kupić, by nie przekroczyć wyznaczonego budżetu? Każdy przedmiot ma swój koszt i wartość, zatem będziemy poszukiwać najbardziej wartościowego przedmiotu o najniższym koszcie. Najczęściej problem plecakowy wyjaśnia się na przykładzie złodzieja, który może wynieść w swoim plecaku tylko ograniczoną wagą ilość przedmiotów, a jednak chciałby mieć z rabunku jak największy zysk.

Wariant dyskretny problemu: to taki, gdzie do plecaka nie można wkładać ułamkowych części elementów. Elementy mogą się w plecaku znaleźć (1) lub nie (0).

[edytuj]

Algorytm genetyczny - główne kroki projektowania

  1. Kodowanie rozwiązań w ciąg chromosomowy - należy rozważyć jak przedstawić potencjalne rozwiązanie rozpatrywanego problemu w postaci ciągu (liczb: np. binarnych, naturalnych, rzeczywistych; znaków), tak by proces odwrotny (dekodowanie) tworzył elementy z dozwolonej dziedziny.
  2. Skontruowanie funkcji przystosowania - Funkcja przystosowania wycenia jakość danego rozwiązania. Im lepsze rozwiązanie prezentuje dany osobnik, tym większa jest jej wartość. Funkcja musi uwzględniać wszystkie cele zadania.
  3. Określenie operatorów genetycznych - wybór typu krzyżowania i mutacji odpowiednio do wybranego kodowania chromosomów. Niekiedy zmiany (krzyżowanie, mutacja) w ciągach kodowych (chromosomach) mogą prowadzić do powstawiania rozwiązań spoza dziedziny (dobrze jest się wówczas zastanowić, czy nie da się zmienić kodowania). Należy wówczas dokonać modyfikacji operatorów genetycznych, bądź korekty ciągów chromosomowych, by znajdowały się w obrębie dziedziny.
  4. Wybór metody selekcji - dopasowanie metody selekcji w zależności od kodowania i rozwiązywanego problemu.
  5. Określenie warunku zatrzymania algorytmu genetycznego - generowanie nowych populacji może być zakończone po wykonaniu zadanej liczby iteracji lub po osiągnięciu np. zadanej wartości funkcji przystosowania.
[edytuj]

Zadanie

Wariant podstawowy zadania obejmuje zaprojektowanie i zaimplementowanie algorytmu genetycznego zgodnie z punktami wymienionymi powyżej. Należy wybrać jedną metodę selekcji, krzyżowania i mutacji.

Wariant rozszerzony to taki, gdzie zaimplementowano różne operatory genetyczne i metody selekcje, tak by porównać ich efektywność. Dodatkowo można rozwinąć problem na dyskretny problem wielu plecaków, gdzie zamiast jednego plecaka o pojemności C dane jest m plecaków o pojemnościach Parser nie mógł rozpoznać (nieznany błąd): \{C_1, C_2,...,C_m\}.


[edytuj]

Pliki testowe

  • Do pojedynczego problemu plecakowego dane należy wygenerować samodzielnie.
  • Do problemu wielu plecaków zbiory testowe wraz z wartością optymalną dostępne są na stronie Zuse Institute Berlin. W pliku readme opisana jest składnia benchmarków (suma constraints nie przekracza knapsack capacities a weights of objects maksymalizujemy).
[edytuj]

Zagadnienia na wejściówkę:

  • działanie algorytmu genetycznego
  • kodowanie chromosomów:
    • binarne
    • permutacyjne
    • wartościami (rzeczywiste, całkowite, znaki itp)
  • przystosowanie chromosomu, funkcja
  • reprodukcja
    • ruletka
    • ranking liniowy i nieliniowy
    • turniej z dyskryminatorem
    • elitaryzm
  • krzyżowanie
    • jednopunktowe
    • wielopunktowe
    • jednorodne (ang. uniform)
    • arytmetyczne
  • mutacja
Źródło: "http://wikizmsi.zut.edu.pl/wiki/SNiASI/L/z2"