Ocena przystosowania chromosomów w populacji - problem plecakowy

0

Witam serdecznie.
Piszę program rozwiązujący problem plecakowy z wykorzystaniem algorytmów genetycznych. Niestety mam z tym spory problem.
Nie do końca wiem jak poprawnie ocenić przystosowanie chromosomów w populacji. Kieruję się zasadą, że jeżeli łącza waga przedmiotów jest mniejsza lub równa pojemności całego plecaka to przystosowanie jest łączną wartością wszystkich elementów, a jeśli waga jest większa to przystosowanie = 0.
Metoda byłaby ok gdyby nie to, że dokonuję selekcji chromosomów trochę upośledzoną metodą turniejową, gdzie dochodzi do momentu, w którym wszystkie chromosomy mają wartość przystosowania = 0. Przez to nie mogę wybrać żadnego chromosomu do dalszego rozrodu.
Jakieś rady jak uporać się z tym problemem?

0

A może (jakiś X- abs( pojemność plecaka - waga przedmiotów))?

0

@jarekr000000: mógłbyś rozwinąć?

0

To tylko pomysł liczenia dostosowania, abyś nie miał nagle skokowo 0.

Teraz widzę, że jako dopasowanie wybrałbym sobie [ abs( pojemność plecaka - waga przedmiotów) + kara za przekroczenie] . (im mniej tym lepiej - ty chyba wybierasz max).
Czyli tak, żeby Ci co troche wystają nadal byli brani pod uwage. kara za przekroczenie to też różnica (tylko np. razy 5).

W ten sposób zawsze ktoś jest najlepszy w grupie turniejowej.
Ale może za mało wiem o tym jak to robisz.

0

@jarekr000000 Hmm. U mnie problemem jest to, że każdy przedmiot w plecaku ma wagę i wartość. I muszę upchać wszystko tak, żeby wartość przedmiotów była jak największa. Czyli określanie adaptacji Twoim sposobem chyba się nie uda :( Trochę źle się wyraziłem w pierwszym poście. Przepraszam.

0

Rozumiem. W takim razie maxymalizujesz wartość i odejmujesz karę za przekroczenie wagi (proporcjonalnie /kwadratowo). (chodzi o to żebyś nie miał skokowo zer).
Może dynamicznie powiększać karę (współczynnik) co ileś pokoleń - tak, żeby na koniec zostały odrzucone wszystkie "wystające" rozwiązania ?

1 użytkowników online, w tym zalogowanych: 0, gości: 1