Eine Detailfrage bei der Anwendung des genetischen Algorithmus auf reisende Verkäufer

Question

Ich habe verschiedene Dinge dazu gelesen und verstehe das Prinzip und die beteiligten Konzepte. Keines Papier erwähnt jedoch die Details zur Berechnung der Eignung eines Chromosoms (das eine Route darstellt), an der benachbarte Städte (im Chromosom) beteiligt sind, die nicht direkt verbunden sind durch eine Kante (in der Grafik).

Zum Beispiel ein Chromosom 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, in dem jedes Gen den Index einer Stadt auf dem Diagramm/Karte darstellt, wie berechnen wir seine Fitness (dh die Gesamtsumme von Entfernungen, die gereist sind) Wenn beispielsweise keine direkte Kante/Verbindung zwischen Stadt 2 und 8 gibt, folgen wir einem gierigen Algorithmus, um eine Route zwischen 2 und 8 zu erarbeiten und die Entfernung dieser Route in die Gesamtzahl hinzuzufügen?

Dieses Problem scheint bei der Anwendung von GA auf TSP ziemlich häufig zu sein. Jeder, der es vor dem Voraus erledigt hat, teilen Sie bitte Ihre Erfahrungen mit. Vielen Dank.

Answer 1

Wenn es keinen Zusammenhang zwischen 2 und 8 in Ihrem Diagramm gibt, ist ein Chromosom mit 2 | 8 oder 8 | 2 ungültig Für das Problem des klassischen Reisebereiches Problem. Wenn Sie eine andere Route zwischen 2 und 8 finden, werden Sie wahrscheinlich gegen die Anforderung "jeden Standort besuchen" verstoßen.

Eine wirklich zwielichtige, aber-pragmatische Lösung besteht darin, Kanten zwischen diesen Knoten mit unglaublich hohen Entfernungen oder sogar +Infs einzubeziehen, wenn Ihre Sprache sie unterstützt. Auf diese Weise wird Ihre Standardminimierung der Fitnessfunktion sie natürlich beschnitten.

Ich denke, die ursprüngliche Formulierung des Problems umfasst Kanten zwischen allen Knoten, also ist dies kein Problem.

Answer 2

Dies ist die genaue Art von Problem, spezialisierte Crossover- und Mutationsmethoden wurden für GA -basierte Lösungen für TSP -Probleme angewendet. Sieh dir das an Frage.

Answer 3

Wenn das Chromoson keine gültige Lösung darstellt, ist es völlig unfähig, das Problem zu lösen. Also je nachdem, wie Sie Fitness bestellen. dh wenn eine niedrigere Zahl mehr Fitness darstellt (möglicherweise eine gute Idee, wenn die Fitness die Gesamtkosten darstellt), würden Sie ihm einen maximalen Wert zuweisen und jede weitere Fitness -Berechnung auf diesem Chromoson brechen, wenn Sie eine ungültige Gensequenz erreichen.

(oder umgekehrt weisen Sie ihm eine Fitness von Null zu, wenn eine höhere Fitness bedeutet, dass ein Chromoson mehr für den Job geeignet ist)

Wie andere darauf hingewiesen haben, könnte es jedoch besser sein, sicherzustellen, dass ungültige Chromosone nicht auftreten. Wenn dies jedoch selbst ein übermäßig komplexer Prozess ist, kann es wahrscheinlich ein akzeptabler Ansatz sein, sie zu aufeinanderfolgenden Generationen zu ermöglichen, und sicherzustellen, dass es unwahrscheinlich ist, dass kaputte Chromosone es zu aufeinanderfolgenden Generationen schaffen.