Raport, Edukacja, studia, Semestr VII, Ewolucyjne Metody Optymalizacji


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

0x01 graphic

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

0x01 graphic

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

0x01 graphic

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

0x01 graphic

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

0x01 graphic

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

0x01 graphic

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



Wyszukiwarka

Podobne podstrony:
raczynski 2, Edukacja, studia, Semestr VII, Komputerowe Systemy Automatyki
IRZI, Edukacja, studia, Semestr VII, Innowacyjne Rozwiązywanie Zadań Inżynierskich
spis2, Edukacja, studia, Semestr VII, Komputerowe Systemy Automatyki
pytania przykBadowe, Edukacja, studia, Semestr VII, Komputerowe Systemy Automatyki
PU Ant pytania zal 2007 01 17 HL, Edukacja, studia, Semestr VII, Przetworniki Ultradźwiękowe
raczynski 2, Edukacja, studia, Semestr VII, Komputerowe Systemy Automatyki
raczynski2, Edukacja, studia, Semestr VII, Komputerowe Systemy Automatyki
Układ 8, Edukacja, studia, Semestr III, Metodyka Projektowania i Technika Realizacji, Laboratorium
Wybierz, Edukacja, studia, Semestr VIII, Kultura Języka Polskiego, CD1 - 2006 KJP-1 INFORMATYKA, KJP
rodzaje', Edukacja, studia, Semestr VIII, Kultura Języka Polskiego, CD1 - 2006 KJP-1 INFORMATYKA, KJ
Skróty-etc, Edukacja, studia, Semestr VIII, Kultura Języka Polskiego, CD1 - 2006 KJP-1 INFORMATYKA,
ksa4, Edukacja, studia, Semestr VIII, Komputerowe Systemy Automatyki, KSA-lab
materiały 5, Edukacja, studia, Semestr III, Inżynieria Materiałowa, Laboratorium, Materiały 5
TECHNIKA MIKROPROCESOROWA (1), Edukacja, studia, Semestr IV, Technika Mikroprocesorowa
spis tresci zarz, Edukacja, studia, Semestr VIII, Zarządzanie, zarzadzanie, zarzadzanie, zarzadzanie
liniowkaWKLEPANE PYTANIA, Edukacja, studia, Semestr IV, Układy Elektroniczne

więcej podobnych podstron