Erhöht die Übersetzung der Gene in ein Chromosom für einen genetischen Algorithmus für eine kombinatorische Funktion die Vielfalt der Kandidaten?

Question

Ich bin neu in genetischen Algorithmen und schreibe Code für das Traveling Salesman Problem. Ich verwende Zyklus-Crossover, um neue Nachkommen zu generieren, und ich habe festgestellt, dass dies dazu führt, dass einige der Nachkommen den gleichen Phänotyp behalten wie ein Elternteil, selbst wenn die beiden Elternteile unterschiedlich sind. Würde das Übersetzen der Chromosomen dies vermeiden?

Mit übersetzen ich meine ein Chromosom mit Phänotyp ABCDE Verschiebung über zwei auf DEABC. Sie wären gleichwertige Antworten und hätten die gleiche Fitness, könnten aber mehr unterschiedliche Nachkommen haben.

Lohnt sich das auf lange Sicht, oder verschwendet es nur Rechenzeit?

Answer 1

Zyklus-Crossover (CX) basiert auf der Annahme, dass es wichtig ist, die absolute Position von Städten zu erhalten (eine Stadt erbt vorzugsweise ihre Position von jedem Elternteil) und die präventive "Übersetzung" widerspricht dem Geist von CX.

Wie auch immer mehrere Studien (z.B. 1) haben gezeigt, dass für TSP der Schlüssel ist, um die relative Position von Städten und die Ränder zu bewahren.

So könnte es funktionieren, aber Sie müssen experimentieren. Eine Form der Mutation ist eine andere Möglichkeit.

Wahrscheinlich, wenn die Eigenschaften von CX nicht befriedigend sind, ist ein anderer Crossover-Operator eine bessere Wahl: Bleiben Sie bei einfachen Operatoren, einer der erfolgreichsten ist der Crossover (z. B. 2).

---

1. L. Darrell Whitley, Timothy Starkweather, D'Ann Fuquay - Scheduling problems and traveling salesmen: The genetic edge recombination operator - 1989.
2. Pablo Moscato - On Genetic Crossover Operators for Relative Order Preservation.