Crossover-operator für Permutationen
ich versuche das problem zu lösen crossover bei genetischen Algorithmus auf meiner Permutationen.
Sagen wir, ich habe zwei Permutationen von 20 zahlen. Ich möchte crossover, Sie bekommen zwei Kinder. Eltern haben die gleichen ganzen zahlen drin, aber die Reihenfolge ist anders.
Beispiel:
Parent1:
5 12 60 50 42 21 530 999 112 234 15 152 601 750 442 221 30 969 113 134
Parent2:
12 750 42 113 530 112 5 23415 60 152 601 999 442 221 50 30 969 134 21
Lassen Sie es so sein - wie kann ich Kinder der beiden?
- Denn ich will, um dieses problem zu lösen mit der Genetik.
- Jede genetische Algorithmus verfügt über einen fitness-test, wo man festlegen von Regeln, um zu entscheiden, welche Kinder überleben und welche sterben werden. Das war es, was ich wissen wollte.
- Wow, wusste nicht, dass : ] ich wählte die Eltern, dass Sie "die besten" - ich wollte nur ein effizienter Weg, um zu berechnen, Kinder mit keine wiederholten Elemente jetzt.
- Wie wäre das anders läuft eine einfache permutation entweder Parent1, oder Parent2?
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Was Sie suchen, ist bestellt crossover. Gibt es eine Erklärung für das Problem des fahrenden Handlungsreisenden hier.
Hier ist einige Java-code, die die teilweise mapped crossover (PMX) Variante.
Die Wahl der Frequenzweiche hängt davon ab, ob die Bestellung oder die absolute position der ganzen zahlen ist wichtig, um die fitness. In HeuristicLab (C#) haben wir implementiert einige der beliebtesten in der Literatur gefunden, die Folgendes umfassen: OrderCrossover (2 Varianten), OrderBasedCrossover, PartiallyMatchedCrossover, CyclicCrossover (2 Varianten), EdgeRecombinationCrossover (ERX), MaximalPreservativeCrossover, PositionBasedCrossover und UniformLikeCrossover. Ihre Umsetzung können gefunden werden, zusammen mit dem Verweis auf eine wissenschaftliche Quelle, in der HeuristicLab.Codierungen.PermutationEncoding plugin. ERX macht nur Sinn für die TSP oder TSP-wie Probleme. Die CX-position-basiert, das PMX ist teilweise position teilweise um-basiert, aber mehr in Richtung position. Der OCHSE ist allein die Reihenfolge.
Beachten Sie, dass unsere Implementierungen gehen von einem kontinuierlichen nummeriert permutation mit Ganzzahlen von 0 bis N-1. Sie haben, um Ihre Zuordnung zu diesem Bereich ersten.
Nach meinen Recherchen und Implementierungen von genetischen Operatoren. Viele Arten von crossover-Operatoren existieren für die um-Codierung (Wiederholung von Genen nicht erlaubt, wie in TSP). Im Allgemeinen, ich denke, es gibt zwei Familien:
ERX-Familie
Eine Liste der Nachbarschaft verwendet wird, zum speichern der Nachbarn jedes Knotens in der beide Eltern. Dann, Das Kind wird erzeugt, indem nur die Liste. ERX bekannt ist,respektvoll und Allele übertragung, was im Grunde bedeutet, dass die links zwischen Genen sind nicht wahrscheinlich, um gebrochen zu werden.
Beispiele von ERX-wie Operatoren gehören: Edge-Recombination (ERX), Edge-2 Edge-3, Rand-4, und Generalisierte Partition Crossover (GPX).
OX-wie Frequenzweichen
Zwei crossover-Punkte gewählt werden. Dann die Gene, die zwischen die Punkte sind vertauscht zwischen den beiden Eltern. Da Wiederholungen sind nicht erlaubt, jeder crossover schlägt vor, eine Technik zur Vermeidung/Beseitigung von Wiederholungen. Diese crossover-Operatoren sind mehr störend als ERX.
Beispiel von OX-wie Frequenzweichen: Order crossover (OX), Maximale Konservierungsmittel Crossover (MPX), und Teilweise-Mapped Crossover (PMX).
Die erste Familie (ERX) eine bessere Leistung in einfachen genetischen algorithmen. Während die zweite Familie ist geeignet, in einen Hybriden genetischen Algorithmus oder memetischen Algorithmus (verwenden der lokalen Suche). Dieses Papier erklärt es im Detail.
Reisen Salesrep-Problem (TSP), die Reihenfolge zu besuchen, wird eine Liste von Städten, und Sie möchten, besuchen Sie jede Stadt genau einmal. Wenn Sie Kodieren die Städte direkt im Genom, dann eine naive crossover oder mutation erzeugen oft eine ungültige Route.
Einmal kam ich mit einem neuartigen Ansatz zur Lösung dieses Problems: Statt der Codierung der Lösung direkt in das Genom, die ich stattdessen codiert, eine transformation, würde wieder bestellen kanonischen Liste von Werten.
Angesichts der Genom -[1, 2, 4, 3, 2, 4, 1, 3], Sie würde anfangen mit der Liste der Städte, die in einer willkürlichen Ordnung, sagen alphabetischer:
Würden Sie dann machen würde, jedes paar von Werten aus der Genom-und tauschen Sie die Städte in diesen Positionen. So, für die Genom-oben würde Sie tauschen diese in 1 und 2 und dann die 4 und die 3 und dann die 2 und 4, und schließlich diejenigen, die in 1 und 3. Sie würde am Ende mit:
Mit dieser Technik, die Sie verwenden können, jede Art von crossover oder mutation Betrieb und noch immer eine gültige tour. Wenn das Genom ist lange genug, dann die ganze Lösung Platz erforscht werden können.
Ich habe diese verwendet werden, für TSP und andere Optimierungsprobleme mit viel Erfolg.