Wie geht man über die Kreuzung von zwei Eltern, wenn die Kinder eine bestimmte Reihenfolge haben müssen?
Wenn Sie z. B. genetische Algorithmen auf das Traveling Salesman Problem in einem festen Graphen von Scheitelpunkten / Kanten anwenden, müssen Sie damit rechnen, dass nicht alle Scheitelpunkte zu anderen Scheitelpunkten wandern können. Dies macht den Übergang viel schwieriger, da im Gegensatz zu dem TSP, in dem alle Scheitelpunkte zu allen anderen Scheitelpunkten wandern können, wenn eine Überkreuzung durchgeführt wird, dies an einem Punkt erfolgen muss, der einen legalen Pfad erzeugt. Die Alternative ist, nur überkreuz zu gehen und illegale Pfade zu verwerfen, aber das Risiko ist groß, rechnerisch teuer und wenige bis keine legalen Pfade.
Ich habe über Permutations-Crossover gelesen, aber ich bin mir nicht ganz sicher, wie dies das Problem löst. Kann mir jemand in die richtige Richtung weisen oder beraten?
Die Bestellung sollte, soweit möglich, keine Einschränkung der genetischen Programmierung darstellen. Vielleicht sollten Sie darüber nachdenken, ein anderes Format für Ihre Lösungen zu wählen. Betrachten Sie beispielsweise in Ihrem TSP das Codon A- & gt; B.
Anstelle der Bedeutung "nimm die Kante von A nach B" könntest du dir den 'kürzesten Weg von A nach B' nehmen. So sind Ihre Lösungen immer machbar. Sie müssen nur eine Shortest-Path-Matrix als Vorverarbeitung vorberechnen.
Dies garantiert jedoch nicht, dass die Kandidaten nach dem Crossover zu realisierbaren Lösungen werden. Ihre Frequenzweiche sollte abgestimmt werden, um zu garantieren, dass Ihre Lösung noch machbar ist. Betrachten Sie zum Beispiel für den TSP die Sequenzen:
1: A B C D E F G H
2: A D E G C B F H
Wählen Sie zufällig einen Drehpunkt ( E in unserem Beispiel). Dies führt zu folgenden Abläufen:
1 ': A B C D E . . .
2 ': Ein D E . . . . .
Alle Ecken müssen besucht werden, um eine gültige Lösung zu haben. In 1 'müssen F, G und H besucht werden. Wir ordnen sie so an, wie sie in Sequenz 2 sind. In 2 'sind G, C, B, F und H wie in 1 umgeordnet:
1 ': A B C D E G F H
2 ': A D E B C F G H
Hoffe, das hilft.
Tags und Links algorithm genetic-algorithm