Warum einen Crossover-Wert von nicht 0,5?

8

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?

Avrohom Yisroel
quelle
2
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 .
Enderland
1
Ich bin mir auch nicht sicher, warum diese Frage abgelehnt wurde - sie scheint perfekt zum Thema und zum Umfang zu gehören.
Enderland
1
Ich würde mir keine Sorgen um die Ablehnung machen ... Ich bekomme eine für fast jeden Beitrag, den ich hier mache.
Robert Harvey
2
@enderland: Würden Sie so weit gehen zu sagen, dass diese Werte zufällig mutiert sind und die besten Kombinationen überleben? ;-)
Jörg W Mittag
2
Ich möchte auch hinzufügen, dass Ihr Crossover-Wert nicht unbedingt statisch bleiben muss. Da ein Teil des Ziels von GAs darin besteht, eine große Varianz zu erzielen, um viele Pfade zu erkunden, kann es eine Option sein, einen zufälligen Crossover-Wert zwischen, auszuwählen. sagen wir 0,5 und 0,8. Vor allem, wenn Sie nicht unbedingt deterministisches Picking verwenden.
Delioth

Antworten:

5

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.

     _                d         ^ fitness
    / \              d \        |
   /   A            B   \       |
__/     \___ccc___dd     \____  |
-----------------------------------> chromosome space
     |                |
     |     valley     |
     |     of "meh"   |
1. optimum         2. optimum

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.

amon
quelle
@amon Danke für die Erklärung. Ich denke, wie bei den meisten dieser Sachen geht es darum,
herumzuspielen
Dies lässt mich denken, dass die Crossover-Rate möglicherweise jedes Mal zufällig ausgewählt werden sollte.
Fragen Sie nach Monica
2

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.

deong
quelle
Danke für die Antwort. Vielleicht habe ich mich nicht klar erklärt, aber so habe ich die beiden verstanden. Ich habe überhaupt nicht nach Mutation gefragt, sondern nur nach Crossover.
Avrohom Yisroel