maja Temat założony przez niniejszego użytkownika |
[Algorytmy genetyczne] Problem plecakowy » 2013-02-20 17:44:14 Zakładam temat w tym dziale, ponieważ mój problem nie dotyczy bezpośrednio języka c++, a jedynie algorytmu.
Piszę program rozwiązujący problem plecakowy (1-0) algorytmem genetycznym. Właściwie program mam już praktycznie skończony zastanawiam się jedynie nad wyborem sposobu obliczania dopasowania poszczególnych osobników. Nie potrafię znaleźć żadnego konkretnego opisu określania dopasowania dla problemu plecakowego.
Na razie przyjęłam taką prostą zasadę:
Najwartościowsze ułożenie przedmiotów dostaje najwięcej punktów, a kolejne coraz mniej. Później w populacji szukam ułożenia najbliższego maksymalnemu udźwigowi plecaka (wartość bezwzględna z udźwigPlecaka-waga) i to ułożenie dostaje najwięcej punktów, a kolejne coraz mniej. Następnie ułożenia cięższa od maksymalnego udźwigu dostają niewielkie kary.
Ilość przyznanych punktów zależy od liczebności populacji i jest liczbą z przedziału 0-1. To powoduje, że przedmiot najwartościowszy, ale najbardziej oddalony od maksymalnego udźwigu otrzymuje łącznie zero punktów.
Zastanawiam się czy warto w ogóle brać pod uwagę odległość od maksymalnego udźwigu. Może wystarczą tylko kary za przekroczenie go?
Byłabym wdzięczna gdyby ktoś podał mi jakiś lepszy sposób obliczania dopasowania (najlepiej z jakiegoś wzoru, bo a razie liczę to tak prowizorycznie).
Z góry dziękuję za wszelką pomoc. |
|
DejaVu |
» 2013-02-20 22:00:29 Algorytmy genetyczne nie służą do wyszukiwania najlepszego rozwiązania, tylko do wyszukiwania akceptowalnego rozwiązania :) Algorytmy genetyczne mają metody wyboru osobników do kolejnej populacji np. metoda ruletki, metoda rankingowa itp. W algorytmie genetycznym oceniasz każdego osobnika i po iluś pokoleniach wybierasz najlepsze poprawne rozwiązanie w populacji stwierdzając 'to rozwiązanie jest najlepsze z tych, które zostały przeszukane'. Poczytaj sobie: http://www.k0pper.republika.pl/geny.htm. /edit: Wracając jeszcze do Twojego pytania... algorytm genetyczny w uproszczeniu sprowadza się do: 1) wypełnienia n-przedmiotami plecaka 2) ocenie czy plecak jest prawidłowo załadowany i ile pozostało luzu Algorytm genetyczny nie stara się szukać rozwiązania. W praktyce genotyp może opisywać rozwiązania zarówno poprawne jak i rozwiązania niepoprawne (np. przeładowany plecak). /edit2: Upraszając więc Tobie sprawę - masz np. 50 przedmiotów to tworzysz genotyp mający 50 pól bool. Każde pole 'bool' określa czy dany przedmiot ma być w plecaku czy też nie. Taki genotyp poddajesz później ocenie/mutacjom/krzyżowaniom itp. i to wszystko. |
|
maja Temat założony przez niniejszego użytkownika |
» 2013-02-20 22:13:48 Zdaję sobie sprawę z tego, że algorytm wcale nie musi mi zwrócić poprawnego rozwiązania.
Selekcji dokonuję na zasadzie "rankingu liniowego", choć nie za bardzo widzę sens wprowadzania w tym konkretnym miejscu losowości.
Tak czy inaczej muszę wcześniej określić jakość dopasowania i w tym właśnie tkwi problem. Na razie robię to tak jak opisałam wyżej. Ale nie wiem czy tak to powinno wyglądać.
/edit
Bardzo dziękuję za uproszczenie, ale wiem jak to zrobić. :) Problem tkwi w samym obliczaniu dopasowania. Nie wiem czy mój sposób jest dobry.
|
|
DejaVu |
» 2013-02-20 22:18:40 Jakość rozwiązania jest przecież znana. Im więcej plecak waży tym lepiej :) Czyli funkcja oceny może wyglądać tak: int ocena( int ileMiejsca, int ileZaladowano )
{
if( ileZaladowano > ileMiejsca )
return 999999;
return ileMiejsca - ileZaladowano;
}
Im mniejsza wartość jest zwracana przez powyższą funkcję tym lepsze masz rozwiązanie. PS. Oceniasz rozwiązanie tj. cały plecak i jego załadowanie, a nie pojedyncze przedmioty ;) |
|
maja Temat założony przez niniejszego użytkownika |
» 2013-02-20 22:33:59 Tak prosto i wygodnie? To nie może być takie proste :) Liczyłam na sposób obliczania zawierający w nazwie słowo "hamiltona", "Gaussa", "Eulera" albo chociaż "Cayleya" :)
W każdym razie to rozwiązanie bierze pod uwagę tylko czy przedmioty się mieszczą i czy wykorzystują całe dostępne miejsce. A wykorzystanie całego miejsca nie ma zbyt dużego związku z najlepszym rozwiązaniem - przedmioty mogą być bardzo duże (większe niż połowa pojemności), a najwartościowszym może być najmniejszy z nich. Dlatego chciałam jakoś uwzględnić wartość przedmiotów.
Czy losowość przy wyborze najlepszych osobników faktycznie jest przydatna?
Tak, oceniam konkretny załadunek. |
|
DejaVu |
» 2013-02-20 22:45:41 AAaaaa :P Bo przedmioty mają jeszcze swoją wartość :P No to wymyśl sobie jakiś fajny wzorek :) Wystarczy, że sprawdzisz czy rozwiązanie jest poprawne, a potem policzysz jaką wartość mają przedmioty. Wówczas możesz napisać: int ocenaRozwiazania( int iPojemnoscPlecaka, int iWagaPrzedmiotow, int iWartoscPrzedmiotow )
{
if( iWagaPrzedmiotow > iPojemnoscPlecaka )
return - 1;
return iWartoscPrzedmiotow;
}
koniec :P Oczywiście im większa wartość zwracana przez powyższą funkcję tym lepsze rozwiązanie masz :) |
|
maja Temat założony przez niniejszego użytkownika |
» 2013-02-20 22:52:42 No dobra, chyba pójdę w tę stronę.
Chociaż wcześniej uznałam żeby nie skreślać tak całkowicie szans tych trochę za ciężkich ułożeń (stąd te czary opisane w pierwszym poście).
No i ostatnia kwestia: czy warto przy tym wyborze stosować losowość, czy lepiej po prostu wziąć najlepiej dopasowane. |
|
DejaVu |
» 2013-02-21 18:30:24 Idea algorytmów genetycznych to niemalże losowe krzyżowanie dwóch genotypów, a nie krzyżowanie najlepszych osobników. |
|
| « 1 » 2 |