Ich baue einen genetischen Algorithmus, um das Problem des reisenden Verkäufers zu lösen. Leider treffe ich Spitzen, die über tausend Generationen lang aufrechterhalten werden können, bevor ich aus ihnen mutiere und bessere Ergebnisse erziele. Welche Crossover- und Mutationsoperatoren funktionieren in diesem Fall im Allgemeinen gut?Empfohlene GA-Betreiber für ein TSP-Problem?
Könnten Sie bitte klären
„Leider habe ich getroffen Spitzen, die über tausend Generationen aufrecht erhalten kann, bevor er aus sie mutieren und immer bessere Ergebnisse“?
Sie könnten die Crossover-Operatoren überprüfen, die sicherstellen, dass Sie keine wiederholenden Knoten in den Kinderchromosomen haben. Einige dieser Crossover-Operatoren sind die Order-Crossover (OX) - und die Edge-Crossover-Operatoren.
Mutation kann so einfach sein wie einfach zwei Positionen in einem einzigen Chromosom zu vertauschen.
BTW, da Sie "python" markiert haben, werfen Sie einen Blick auf Pyevolve, es hat auch ein TSP-Beispiel.
Geordnete Mutation und geordnete Kreuzung (siehe this article). Standard-Mutations- und Crossover-Operationen führen normalerweise zu ungültigen Lösungen (d. H. Doppelte und/oder fehlende Städte in einer Route).
Kürzlich gab es eine similar question.
Ich habe a Java applet that implements the TSP using ordered cross-over and mutation, wenn Sie daran interessiert sind, die Leistung Ihrer Implementierung zu vergleichen.
Wenn Ihr Problem darin besteht, dass Peaks für mehr als eintausend Generationen bestehen bleiben, liegt das Problem möglicherweise nicht bei den Crossover- und Mutationsoperatoren. Sie werden Ihrer Bevölkerung möglicherweise nicht genügend Variation beibringen oder sie beibehalten: Ich würde die Proportionen von Kreuzungen, Mutationen und Überlebenden von einer Generation zur nächsten untersuchen und möglicherweise den Anteil an Mutationen erhöhen.
http://stackoverflow.com/questions/1544055/rossover-operation-in-genetic-algorithm-for-tsp könnte helfen. –