Jakiś czas temu padło pytanie o rozwiązywanie problemu plecakowego przy użyciu algorytmu genetycznego. Zaciekawiłem się tym zadaniem, przeprowadziłem kilka eksperymentów, postanowiłem to pokrótce opisać i podzielić się wniosami:
Jak wiadomo, problem plecakowy stanowi problem NP-trudny, choć istnieją dobre i proste heurystyki:
https://pl.wikipedia.org/wiki/Problem_plecakowy
https://en.wikipedia.org/wiki/Knapsack_problem
W pobieżnych eksperymentach algorytm genetyczny, ku mojemu szczeremu zaskoczeniu, nie wypadał najgorzej. Myślę, że siłą algorytmu genetycznego w tym zadaniu jest kodowanie pozycyjne - jeśli dany przedmiot korzystnie wpływa na przystosowanie jednego osobnika, to istnieje duże prawdopodobieństwo, że również korzystnie wpłynie na przystosowanie innego osobnika.
Widząc pewne sukcesy algorytmu genetycznego, postanowiłem zrobić więcej eksperymentów. Po pierwsze utrudniłem zadanie, rozszerzyłem je do problemu pakowania wielu plecaków. Algorytm genetyczny uzbroiłem w dodatkowe heurystyki: dodałem diploidalność, nawroty do najlepszej kopii genów, sortowanie przedmiotów. Ponadto usunąłem kilka cech z klasycznego algorytmu genetycznego, które w moich eksperymentach zawsze stanowiły wadę. Te cechy to np. wymiana całej populacji pomiędzy pokoleniami, losowanie metodą ruletki, funkcja przeżywalności. W zasadzie z algorytmu genetycznego w mojej implementacji zostało niewiele, bo nawet krzyżowanie najlepiej się sprawuje gdy zachodzi bardzo rzadko, np. raz na kilkaset, albo nawet raz na milion mutacji. Po takich zmianach niektórzy by powiedzieli że moja implementacja jest przeciwieństwem algorytmu genetycznego, bo głównie mutuje i przywraca geny, zamiast krzyżować. Jednak ja wiele razy obserwowałem, że malutki dodatek krzyżowań, bardzo korzystnie wpływa na wyniki algorytmu, natomiast algorytm oparty głównie o krzyżowanie działa kiepsko, jest trudny w kontrolowaniu, traci moc obliczeniową na częste liczenie tej samej funkcji oceny i ma jeszcze więcej innych wad.
Teraz o tym co najważniejsze, czyli jakie uzyskałem wyniki? Otóż po dobraniu parametrów, wzmocniony algorytm genetyczny znajduje optymalne rozwiązanie dla 10 plecaków i 116 przedmiotów w zaledwie 0.6s na jednym rdzeniu zwykłego taniego procesora. Z tych 116 przedmiotów 86 musi trafić do plecaków, pozostałe są dodatkiem mającym utrudnić zadanie. Wystarczyła pula 128 osobników i 8000 pokoleń aby uzyskać optymalne rozwiązanie. W rzeczywistości każdy osobnik ma kopię swoich genów (diploidalność), w pewnym sensie ilość osobników w całym programie jest równa dwa razy więcej, czyli 256.
Jestem pod wrażeniem że (co prawda wzmocniony) algorytm genetyczny potrafi optymalnie rozmieścić 86 przykładowych przedmiotów w 10 plecakach.
Jakby ktoś chciał sam przeprowadzić eksperymenty, udostępniam kod źródłowy:
https://pastebin.com/g0nPdRtD
Tutaj przykładowe dane dla 10 plecaków:
https://pastebin.com/4XJfN6eM
Dane trzeba zapisać w pliku input.txt
Tutaj kompilacja i przykładowe uruchomienie:
https://pastebin.com/qM0mFfC5
c++ -std=c++11 -O3 main.cpp -o genetic
time cat input.txt | ./genetic
Pozdrawiam
