Problem plecakowy + algorytm genetyczny.

Witam,
Na cwiczeniach profesor kazal napisac nam progrma z zastosowaniem algorytmu genetycznego + problem plecakowy (2in1). W chwili obecnej mam juz napisany czesc programu tj. algorytm genetyczny dla losowej populacji skladajacej sie z 5 genow. Z tej populacji program losowo wybiera populacje i modyfikuje geny ("mutanty"). Moje wyniki sa zadowalajace bo po wyborze i mutacji wybieraz z nich coraz to lepsze rozwiazanie przy kazdej iteracji. Teraz mam pytanie jak to sprzegnac z problemem plecakowym. Nie mma zielonego pojecia jak to zaimplementowac. Podpowiadam, ze juz tez jestem po napisaniu samego programu dla problemu plecakowego (przedmioty+waga+wartosc przedmiotu) i tez mi dziala. Co wiecej dostalem za to 5 z cwiczen.
Bardzo prosze o podpowiedz jak to ugryzc bo nie mma zadnego pomyslu.

P.S. Jestem poczatkujacym i raczej nie wiaze przyszlosci z programowaniem. Robie to raczej na sztuke.

Masz tablicę przedmioty[]
Genem jest liczba oznaczająca index przedmiotu.
Genotyp składa się z genów i jest różnej długości. Jest naszym wynikiem.
Funkcja oceny polegać będzie na sumowaniu wartości przedmiotów w danym genotypie minus kara za przekroczenie dopuszczalnego wagi albo coś w tym guście.
Te które będą miały największą wartość przetrwają.

Tzn. ja myslalem o czyms takim:
Pi - to moj osobnik
Mi - to suma genow (od 0 do 5 - najlepszy)
Ci - to cena (suma genow / ilosc genow czyli 5) np. 4 / 5 = 0,8
Mmax - maksymalny udzwig plecaka

W chlili obecnej to mam napiasane w tablicy dwuwymiarowej. Osobnik[nurmer osobnika w zaleznosci od wyboru ilosci osobnikow][0,1,2,3,4 geny (1 lub 0), 6 - suma genow czyli Mi i Ci suma genow / 5 ].

Czy tak tez moze byc? Bo wydaje mi sie, ze waga jest nie adekwatna do problemu, poniewaz nie moze byc tak wysoka waga w stosunku do wartosci (ceny). Najlepiej to by bylo gdyby waga byla mniejsza a cena wieksza. Wtedy chyba wynik byl by lepszy, bo wiecej sie miesci osobnikow o lepszych genach i wartosci w plecaku.

Zapomnialem dodac, ze chodzi mi o problem plecakowy z wykorzystaniem algorytmu aproksymacyjnego - http://pl.wikipedia.org/wiki/Problem_plecakowy lub http://pl.wikipedia.org/w/index.php?title=Plik:Knapsack_greedy.svg&filetimestamp=20060808193357. I nie wiem czy ten wariant co wymyslilem jest OK czy duzo gorszy :( Z wykorzystaniem tego algorytmu tak napisalem program na poprzednie zaliczenie i okazal sie byc OK. Rowniez go przedstawilem z tym algorytmem w EXCEL'u z wykresami.

Czyli masz tablicę osobników i każdy osobnik ma 5 genów na 5 przedmiotów. Gen ma wartość 0 jak dany osobnik nie zabiera tego przedmiotu i 1 jak zabiera. No ok, tak też może być.

Swietnie, dzieki :)

Drogi p4w3le, czy moglbys sie podzielic swoim programem ? z zastosowaniem algorytmu genetycznego + problem plecakowy
moj mail [email protected]

napisz na pewno sie dogadamy, jakiegos browara postawie :-)

Jak ktos ma chwilke czasu na napisanie takeigo programu to bardzo prosze, dogadamy sie ;-)

browar to przenosnia, dogadamy sie zaplce przelewem z mbanku. masz kod to prosze napisz do mnie.