Der größte Teil der Literatur, die ich über GAs gelesen habe, schlägt vor, einen Crossover-Wert von etwa 0,7 zu verwenden. Sie nehmen also die ersten 70% der Gene eines Chromosoms und die letzten 30% des anderen, um ein neues Chromosom zu produzieren.
Wenn Sie die Elternchromosomen auswählen, indem Sie die ersten beiden (nach Fitness geordnet) nehmen, kann ich die Logik hier sehen, da Sie den Genen des höher bewerteten Chromosoms mehr Gewicht beimessen. Wenn Sie jedoch eine stochastische Methode (z. B. ein Roulette-Rad) verwenden, um die Eltern auszuwählen, was bringt es dann, etwas anderes als 0,5 als Crossover-Wert zu verwenden? Angesichts der Tatsache, dass Sie die Chromosomen A und B wie die Eltern ausgewählt haben, ist es genauso wahrscheinlich, dass Sie zuerst A und dann B als B und A auswählen, nicht wahr?
Bisher habe ich nur eine GA geschrieben (immer noch ganz unten in der Lernkurve, aber dank einer großen Hilfe hier schnell aufwärts!), Aber Experimente dazu zeigen, dass 0,5 eine schnellere Konvergenz der Lösung ergibt als jeder andere Wert.
Oder fehlt mir etwas?
quelle
Most of the literature I've read about GAs suggests using a crossover value of around 0.7<- Eine Sache, die zu beachten ist, ist, dass viele dieser Arten von Werten bei der heuristischen Optimierung mehr oder weniger darauf basieren, welche Werte zu guten Ergebnissen zu führen schienen (und nicht zu einer empirischen Ableitung). Ich bin mit GA weniger vertraut, aber ich weiß, dass bei anderen populationsbasierten Optimierungsmethoden die Konstanten ziemlich willkürlich bestimmt wurden, indem einige Forscher einige grundlegende Experimente durchführten, Werte fanden, die besser funktionierten, und diese Werte dann von der Optimierungsgemeinschaft insgesamt übernommen wurden .Antworten:
Die ideale Frequenzweiche hängt stark vom Problembereich ab. Die zugrunde liegenden Annahmen evolutionärer und genetischer Algorithmen sind, dass zwei gute Lösungen manchmal zu einer besseren Lösung kombiniert werden können - gute Lösungen ähneln anderen guten Lösungen. Dies ist intuitiv sinnvoll, wenn der Problemraum ein einziges Optimum hat, zu dem jede nachfolgende Generation konvergiert.
Wenn es mehrere Optima gibt, ist der Abstand zwischen diesen Optima per Definition nicht optimal. Wenn wir ein Chromosom A nehmen, das nahe an einem Optimum liegt, und es mit einem Chromosom B nahe einem anderen Optimum kombinieren, landen wir dazwischen und haben wahrscheinlich ein resultierendes Chromosom c, das schlechter ist als seine Eltern. Näher an dem einen oder anderen Elternteil zu bleiben, erhöht die Wahrscheinlichkeit, ein Chromosom d zu erhalten, das besser oder zumindest nicht viel schlechter ist als die Eltern.
Der Crossover-Wert ist nur ein Algorithmusparameter, den Sie an Ihre Problemstruktur anpassen können. Manchmal sehen Sie eine schnellere Konvergenz mit einem niedrigen Crossover-Wert, manchmal mit einem sehr hohen Crossover-Wert. Bei sehr hohen Werten wäre dies jedoch weniger eine Überkreuzung, sondern nur eine sehr geringe Änderung wie eine Mutation. Anstatt einen Wert in der Nähe von 1,0 zu verwenden, möchten Sie lieber die Crossover-Rate reduzieren und die Mutationsrate erhöhen.
quelle
Verwirrenderweise werden Crossover-Rate und Mutationsrate, obwohl sie ähnlich benannt sind, typischerweise unterschiedlich interpretiert.
Mutationsrate von x% ==> Sie führen den Mutationsoperator mit einer Wahrscheinlichkeit von 1,0 aus, und jede Anwendung dieses Operators ändert x% der Bits des mutierten Individuums.
Crossover-Rate von x% ==> Sie wählen, Crossover überhaupt mit der Wahrscheinlichkeit x durchzuführen .
Eine Crossover-Rate von 70% bedeutet also nicht, dass Sie 70% der Bits von Eltern 1 und 30% von Eltern 2 übernehmen. Dies bedeutet, dass Sie in 70% der Fälle den von Ihnen gewählten Crossover-Operator ausführen. In den verbleibenden 30% der Zeit geben Sie die Eltern unverändert in den Nachwuchspool weiter.
quelle