Algorytm genetyczny na plecaku optiproblem

Question

Mam problem z optymalizacją, próbuję rozwiązać za pomocą algorytmu genetycznego. Zasadniczo istnieje lista 10 powiązanych zmiennych o wartościach rzeczywistych (-1 < = x < = 1) i muszę zmaksymalizować niektóre funkcje tej listy. Połów jest taki, że tylko do 4 zmiennych na liście może być! = 0 (warunek podzbioru).

Matematycznie rzecz biorąc: pewnego funkcji F: [1, 1]^10 -> R min f (x) S.t. | {var in X with var! = 0} | < = 4

Niektóre tła na f: funkcja NIE jest podobna do jakiejkolwiek funkcji celu plecakowego, takiej jak Suma x * lub coś podobnego.

Co próbowali dotychczas:

tylko podstawowe algorytm genetyczny przez genomu [1, 1]^10, z 1-pkt zwrotnicy i niektóre Gaussa mutacja zmiennych. Próbowałem zakodować warunek podzbioru w funkcji fitness, używając tylko pierwszych 4 niezerowych (zero jak w wystarczająco blisko wartości 0). Takie podejście nie działa tak dobrze, a algorytm utknął na 4 pierwszych zmiennych i nigdy nie wykorzystuje wartości przekraczających tę. Widziałem pewnego rodzaju GA dla problemu z plecakiem 01, w którym to podejście działało dobrze, ale najwyraźniej działa to tylko ze zmiennymi binarnymi.

Co poleciłbyś mi spróbować?

Answer 1

Możesz spróbować kroku "przestawnego": wybierz jedną z istniejących niezerowych wartości, aby uzyskać zero, i zastąp ją, ustawiając jedną z istniejących zerowych wartości, aby stała się niezerowa. (Moje "przestawne" pojęcie pochodzi z programowania liniowego, w którym oś jest podstawowym krokiem w metodzie simplex).

Najprostszym przypadkiem byłoby równomierne losowanie przy wyborze każdej z tych wartości; możesz wybrać losową wartość lub wiele wartości dla nowej niezerowej zmiennej. Bardziej lokalnym krokiem byłoby użycie kroku Gaussa tylko na istniejących niezerowych zmiennych, ale jeśli jedna z tych zmiennych przekracza zero, odradza się wariacje, które przestawiają się na jedną z zerowych wartości. (Pamiętaj, że nie wykluczają się wzajemnie, ponieważ możesz łatwo dodać oba rodzaje kroków).

Jeśli masz jakieś informacje na temat lokalnego zachowania swojego wyniku fitness, możesz spróbować użyć tego, by poprowadzić swój wybór. Fakt, że aktualna ewolucja nie patrzy na funkcję fitness, nie oznacza, że ​​nie możesz ...

Answer 2

Jeśli Twoja funkcja fitness jest szybka i brudna do oceny, to taniej jest zwiększyć całkowity rozmiar populacji.

Problem polega na tym, że próbujesz wybrać dwie zupełnie różne rzeczy jednocześnie. Chcesz wybrać, które 4 genomy Ci odpowiadają, a następnie jakie wartości są optymalne.

Widzę dwa sposoby, aby to zrobić.

1. Tworzysz 210 różnych "gatunków". Każdy gatunek jest określony przez 4 z 10 genomów, z których mogą korzystać. Następnie możesz uruchomić algorytm genetyczny dla każdego gatunku osobno (albo seryjnie, albo równolegle w obrębie klastra).

2. Każdy organizm ma tylko 4 wartości genomu (przy tworzeniu losowego potomstwa wybiera się losowo wybrane genomy). Kiedy łączą się dwa organizmy, przechodzisz tylko na odpowiadające im genomy.Jeśli twoja para organizmów zawiera 3 wspólne genomy, możesz losowo wybrać, który z genomów może być preferowany jako czwarty. Możesz także, jako heurystyk, unikać organizmów godowych, które wydają się być zbyt genetycznie różne (tj. Para, która dzieli dwa lub mniej genomów może powodować złe potomstwo).

Mam nadzieję, że daje ci to kilka pomysłów, z którymi możesz pracować.

Answer 3

Czy Twoje GA dobrze rozwiązuje problem bez ograniczenia podzbioru? Jeśli nie, możesz najpierw rozwiązać ten problem.

Po drugie, możesz zmiękczyć swoje ograniczenia zamiast twardych: Penalizować przydatność rozwiązania dla każdej zmiennej o wartości zerowej, której ma, powyżej 4. (Możesz zacząć od poluzowania ograniczenia jeszcze dalej, pozwalając na 9 zmiennych o wartości 0, następnie 8 itd. i upewnienie się, że GA jest w stanie obsłużyć te warianty problemu, zanim utrudni to zadanie).

Po trzecie, może spróbuj zastosować 2-punktowe lub wielopunktowe skrzyżowanie zamiast 1-punktowego.

Nadzieję, że pomaga.

-Ted