Sprawozdanie z pracy projektowej

1. Cel projektu

Celem projektu było stworzenie programu, który pozwalałby na rozwiązanie problemu załadunku (plecakowego) z wykorzystaniem podejścia ewolucyjnego.

2. Parametry projektowe (założenia)

Przy tworzeniu projektu przyjęto następujące założenia:
- możliwość płynnego ustalania ilości przedmiotów w zakresie od 20 do 200,
- możliwość płynnego ustalania ilości generacji działania algorytmu (100 do 500),
- możliwość definiowania prawdopodobieństwa krzyżowania i mutacji,
- wagi przedmiotów generowane losowo z przedziału [1,10] (liczby całkowite),
- ważności przedmiotów generowane losowo z przedziału [1,10] (liczby całkowite),
- liczba osobników w populacji wynosi 8,
- ładowność plecaka równa połowie sumy wag przedmiotów + 10%,
- rozwiązanie problemu klasycznym algorytmem genetycznym lub z zastosowaniem
strategii elitarnej,
- graficzne zobrazowanie wyników.

3. Wnioski z przeprowadzonych symulacji

W celu sprawdzenia działania algorytmu przeprowadzono serię symulacji odpowiednio dla 20, 100 i 200 przedmiotów w plecaku przy odpowiednio 100, 200 i 500 generacjach działania algorytmu oraz przy założonym w każdym przypadku prawdopodobieństwie krzyżowania wynoszącym 0,9 oraz prawdopodobieństwie mutacji 0,01. Wszystkie powyższe przypadki rozpatrzono przy zastosowaniu algorytmu klasycznego oraz z zastosowaniem strategii elitarnej. Wykresy ilustrujące przeprowadzone symulacje znajdują się na końcu niniejszego opracowania.
We wszystkich przeprowadzanych symulacjach bardzo wyraźnie daje się zauważyć duże wahania wartości średniej funkcji przystosowania, można je ograniczyć poprzez zmniejszenie prawdopodobieństwa mutacji, jednakże niesie to ze sobą ryzyko wpadnięcia algorytmu w minimum lokalne.
Kolejnym niemal równie oczywistym wnioskiem jest fakt poprawienia się działania algorytmu przy zastosowaniu strategii elitarnej. W tych przypadkach gdzie została ona wprowadzona algorytm zdecydowanie rzadziej gubi najlepsze rozwiązanie - właściwie dzieje się to tylko w przypadku zmutowania osobnika o maksymalnej funkcji przystosowania w populacji.

Widać również, że nie ma potrzeby zbytniego zwiększania liczby generacji działania algorytmu, gdyż ryzykujemy zgubienie najlepszego rozwiązania, jako że z każdą następną generacją rośnie prawdopodobieństwo, że mutacji zostanie poddany najlepszy osobnik. Tym niemniej nie należy również przeprowadzać obliczeń na zbyt małej liczbie iteracji, gdyż możemy nie osiągnąć optymalnego poziomu.

4. Wykresy ilustrujące obliczenia

Rys1. N = 20, G = 100, bez strategii elitarnej, 6 osobników w ostatnim pokoleniu
z przystosowaniem 60

Rys2. N = 100, G = 200, bez strategii elitarnej, 3 osobniki w ostatnim pokoleniu
z przystosowaniem 296

Rys3. N = 200, G = 500, bez strategii elitarnej, 7 osobników w ostatnim pokoleniu
z przystosowaniem 640

Rys4. N = 20, G = 100, ze strategią elitarną, 4 osobników w ostatnim pokoleniu
z przystosowaniem 63

Rys5. N = 100, G = 200, ze strategią elitarną, 1 osobnik w ostatnim pokoleniu
z przystosowaniem 351

Rys6. N = 200, G = 500, ze strategią elitarną, 3 osobników w ostatnim pokoleniu
z przystosowaniem 748

Grzegorz Barnik EMO - Algorytm plecakowy ISD sem.7 Wydział ETiI, PG

Raport 1 / 4 2007-01-29 13:49:00

---