Sind genetische Algorithmen für Probleme wie das Knuth-Problem geeignet?
Wir alle wissen, dass genetische Algorithmen eine optimale oder nahezu optimale Lösung liefern können. Bei einigen Problemen wie NP-harten ist die nahezu optimale Lösung mit einem Kompromiss zwischen Zeit und optimaler Lösung gut genug.
Wird GA als eine gute Wahl zur Lösung des Knuth-Problems angesehen, da es keine Garantie gibt, die optimale Lösung zu finden?
Nach künstlicher Intelligenz: Ein moderner Ansatz (dritte Ausgabe), Abschnitt 3.2 (S. 73):
Knuth vermutete, dass ab der Zahl 4 eine Folge von Fakultäts-, Quadratwurzel- und Bodenoperationen jede gewünschte positive ganze Zahl erreichen wird.
Zum Beispiel kann 5 von 4 erreicht werden:
Etage (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Wenn wir also eine Zahl (5) haben und die Reihenfolge der Operationen der drei genannten wissen möchten, um die angegebene Zahl zu erreichen, ist jedes Gen des Chromosoms eine Zahl, die eine bestimmte Operation mit einer zusätzlichen Zahl für darstellt (keine Operation) und die Fitnessfunktion sind die absolute Differenz zwischen der angegebenen Zahl und der Zahl, die wir erhalten, wenn wir die Operationen in einer bestimmten Reihenfolge für jedes Chromosom (bis min) anwenden. Nehmen wir an, dass die Anzahl der Iterationen (Generationen) ohne optimale Lösung erfolgt und die nächste Zahl 4 ist (mit Fitness 1). Das Problem ist, dass wir 4 erhalten können, wenn wir keine Operation auf 4 anwenden, während wir für 5 benötigen viele Operationen, so dass die nahezu optimale Lösung nicht einmal in der Nähe der Lösung ist.
Ist GA also nicht für diese Art von Problemen geeignet? Oder sind die vorgeschlagene Chromosomendarstellung und Fitnessfunktion nicht gut genug?
Antworten
Lassen Sie mich etwas klarstellen, bevor Sie versuchen, Ihre Frage direkter zu beantworten.
Menschen verwenden häufig den Begriff genetische Algorithmen (GAs), aber in vielen Fällen meinen sie wirklich evolutionäre Algorithmen (EAs), eine Sammlung populationsbasierter (dh mehrere Lösungen werden gleichzeitig beibehalten) Optimierungsalgorithmen und Ansätze, die vom Darwinismus und dem Überleben der Stärksten inspiriert sind . GAs ist einer dieser Ansätze, bei denen die Chromosomen binär sind und Sie sowohl die Mutations- als auch die Crossover-Operation durchführen. Es gibt andere Ansätze wie Evolutionsstrategien oder genetische Programmierung .
Wie Sie auch bemerkt haben, handelt es sich bei EAs um Meta-Heuristiken, und obwohl einige Untersuchungen zu ihren Konvergenzeigenschaften [ 1 ] durchgeführt wurden, können sie in der Praxis möglicherweise nicht konvergieren. Wenn jedoch ein anderer potenzieller Ansatz fehlgeschlagen ist, können EAs definitiv nützlich sein.
In Ihrem Fall besteht das Problem darin, einen geschlossenen (oder analytischen ) Ausdruck einer Funktion zu finden, der sich aus anderen kleineren Funktionen zusammensetzt. Genau dafür wurde die genetische Programmierung (insbesondere der baumbasierte GP) entwickelt. Tatsächlich ist das Knuth-Problem eine besondere Instanz des symbolischen Regressionsproblems , bei dem es sich um ein typisches Problem handelt, auf das GP angewendet wird. GP ist also wahrscheinlich der erste Ansatz, den Sie ausprobieren sollten.
Inzwischen habe ich in DEAP ein einfaches Programm implementiert, das versucht, das Knuth-Problem zu lösen. Überprüfen Sie es hier . Die Eignung der besten Lösung, die bisher gefunden wurde (mit etwas Startwert), ist 4 und die Lösung ist floor(sqrt(float(sqrt(4))))(hier wird floatnur die Eingabe in eine Gleitkommazahl konvertiert, um die Typensicherheit zu gewährleisten). Ich habe den Unterschied als Fitnessfunktion verwendet und den GP-Algorithmus für 100 Generationen mit 100 Personen für jede Generation ausgeführt (was nicht viel ist!). Ich habe die Hyperparameter nicht viel optimiert, also können Sie vielleicht mit dem richtigen Startwert und den richtigen Hyperparametern die richtige Lösung finden.
Um Ihre Bedenken auszuräumen, könnten Sie im Prinzip diese Codierung verwenden, aber wie Sie bemerken, könnte die GA tatsächlich zurückkehren $4$ als die beste Lösung (die eigentlich gar nicht so weit entfernt ist $5$), die Sie vermeiden könnten, dass ich bei jeder Generation Personen töte, die genau diesen Wert haben.
Ich habe nicht zu viel Zeit mit meiner Implementierung und dem Nachdenken über dieses Problem verbracht, aber wie ich oben sagte, könnte es selbst mit genetischer Programmierung und nur mit Knuths Operationen in lokalen Optima stecken bleiben. Sie könnten versuchen, meine (oder Ihre) Implementierung durch andere Operationen wie Multiplikation und Addition zu erweitern und festzustellen, ob sich etwas verbessert.