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
1
A może (jakiś X- abs( pojemność plecaka - waga przedmiotów))?
0
@jarekr000000: mógłbyś rozwinąć?
1
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.
1
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 ?