Czy algorytmy genetyczne są odpowiednie do problemów takich jak problem Knutha?
Wszyscy wiemy, że algorytmy genetyczne mogą zapewnić optymalne lub prawie optymalne rozwiązanie. Tak więc w przypadku niektórych problemów, takich jak problemy NP-trudne, przy kompromisie między czasem a optymalnym rozwiązaniem, prawie optymalne rozwiązanie jest wystarczająco dobre.
Ponieważ nie ma gwarancji znalezienia optymalnego rozwiązania, czy AH uważa się za dobry wybór do rozwiązania problemu Knutha?
Według Artificial intelligence: A modern approach (trzecia edycja), sekcja 3.2 (s. 73):
Knuth przypuszczał, że zaczynając od liczby 4, sekwencja operacji silni, pierwiastka kwadratowego i podłogi osiągnie dowolną dodatnią liczbę całkowitą.
Na przykład do 5 można dotrzeć z 4:
floor (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Tak więc, jeśli mamy liczbę (5) i chcemy poznać sekwencję operacji 3 wymienionych, aby osiągnąć podaną liczbę, każdy gen chromosomu będzie liczbą reprezentującą określoną operację z dodatkową liczbą dla (brak operacji), a funkcja przystosowania będzie bezwzględną różnicą między podaną liczbą a liczbą, którą otrzymamy stosując operacje w określonej kolejności dla każdego chromosomu (do min). Weźmy pod uwagę, że liczba iteracji (pokoleń) jest wykonywana bez optymalnego rozwiązania, a najbliższa liczba, jaką mamy, to 4 (przy sprawności 1), problem polega na tym, że możemy uzyskać 4 z braku operacji na 4, podczas gdy dla 5 potrzebujemy wiele operacji, więc prawie optymalne rozwiązanie nie jest nawet bliskie rozwiązania.
Czy zatem AH nie nadaje się do tego rodzaju problemów? A może sugerowana reprezentacja chromosomów i funkcja przystosowania nie są wystarczająco dobre?
Odpowiedzi
Zanim spróbuję odpowiedzieć na Twoje pytanie bardziej bezpośrednio, pozwól, że coś wyjaśnię.
Ludzie często używają terminu algorytmy genetyczne (GA), ale w wielu przypadkach tak naprawdę mają na myśli algorytmy ewolucyjne (EA), czyli zbiór populacyjnych (tj. Wiele rozwiązań jest utrzymywanych w tym samym czasie) algorytmów optymalizacji i podejścia inspirowane darwinizmem i przetrwaniem najlepiej przystosowanych . GA jest jednym z tych podejść, w którym chromosomy są binarne i masz zarówno mutację, jak i operację krzyżowania. Istnieją inne podejścia, takie jak strategie ewolucyjne lub programowanie genetyczne .
Jak również zauważyłeś, EA są metaheurystykami i chociaż istnieją badania nad ich właściwościami zbieżności [ 1 ], w praktyce mogą się one nie zbierać. Jednak gdy jakiekolwiek inne potencjalne podejście zawiodło, EA mogą być zdecydowanie przydatne.
W twoim przypadku problemem jest naprawdę znalezienie wyrażenia w formie zamkniętej (lub analitycznej ) funkcji, która składa się z innych mniejszych funkcji. To jest właśnie to, do czego stworzono programowanie genetyczne (w szczególności GP oparty na drzewach). W rzeczywistości problem Knutha jest szczególnym przykładem problemu regresji symbolicznej , który jest typowym problemem, do którego stosuje się GP. Tak więc lekarz ogólny jest prawdopodobnie pierwszym podejściem, które powinieneś wypróbować.
W międzyczasie wdrożyłem w DEAP prosty program, który próbuje rozwiązać problem Knutha. Sprawdź to tutaj . Dopasowanie najlepszego rozwiązania, które znalazł do tej pory (z pewnym ziarnem), wynosi 4, a rozwiązanie to floor(sqrt(float(sqrt(4))))(tutaj floatpo prostu konwertuje dane wejściowe na liczbę zmiennoprzecinkową, aby zapewnić bezpieczeństwo typu). Użyłem różnicy jako funkcji sprawności i uruchomiłem algorytm GP dla 100 pokoleń z 100 osobnikami w każdym pokoleniu (co nie jest dużo!). Nie poprawiałem zbytnio hiperparametrów, więc być może przy odpowiednim ziarnie i hiperparametrach można znaleźć właściwe rozwiązanie.
Aby rozwiązać swoje obawy, w zasadzie możesz użyć tego kodowania, ale, jak zauważyłeś, GA rzeczywiście może wrócić $4$ jako najlepsze rozwiązanie (które nie jest tak dalekie od $5$), which you could avoid my killing, at every generation, any individuals that have just that value.
I didn't spend too much time on my implementation and thinking about this problem, but, as I said above, even with genetic programming and using only Knuth's operations, it could get stuck in local optima. You could try to augment my (or your) implementation with other operations, such as the multiplication and addition, and see if something improves.