Genetische Algorithmen - Reisen Verkäufer

Question

Ich bin durch eine Vergangenheit Prüfung Papier gehen und ich versuche, die folgende Frage zu verstehen:

Angenommen, Sie N Städte haben. Es ist möglich, von jeder Stadt zu einer der anderen Städte zu gehen. Angenommen, Sie haben vollständige Informationen über die Entfernungen zwischen Städten in tabellarischer Form. Die Entfernung zwischen der Stadt k und der Stadt l ist gegeben durch d (k, l); so ist zum Beispiel die Entfernung von der dritten Stadt zur neunten Stadt durch d (3,9) gegeben. Beachten Sie, dass d (k, l) = d (l, k).

Ein reisender Verkäufer muss alle N Städte besuchen und möchte die kürzeste Route finden, die alle Städte verbindet. Verwenden Sie einen genetischen Algorithmus, um dieses Problem zu lösen.

Frage: Definieren Sie eine geeignete Fitness-Funktion für dieses Problem und sagen Sie, ob hohe oder niedrige Fitness besser ist.

Weiß jemand, was ich für diese Frage tun muss? Ich habe wirklich Probleme damit anzufangen und brauche eine Richtung.

Answer 1

Mit dem TSP möchten Sie die zurückgelegte Strecke minimieren. Es gibt viele verschiedene Möglichkeiten, die n Städte zu reisen; N!/2 um genau zu sein. Wenn Sie N = 4 haben, möchten Sie ein Array der Ganzzahlen 1-4, die jeweils nur einmal vorkommen. So würden einige mögliche Optionen sein:

[1,4,2,3] 
[4,1,2,3] 
[3,1,4,2] 

Sie bewerten dann die Punktzahl durch von Stadt gehen i-i+1 in der Liste, um den Abstand zu berechnen. Tun Sie dies für jede Stadt i in der Liste (aber die letzte) und Sie haben die Gesamtdistanz; Das ist deine Punktzahl!

So für die obigen Beispiele die Bewertung wäre:

// Please note that the integers 1-4 represent cities 
score([1,4,2,3]) = d(1,4) + d(4,2) + d(2,3) 
score([4,1,2,3]) = d(4,1) + d(1,2) + d(2,3) 
score([3,1,4,2]) = d(3,1) + d(1,4) + d(4,2) 

Sie wollen den Abstand minimieren, so dass die Gäste zu minimieren.

---

Sie können dies tun, indem Mutation Funktionen schaffen, die zum Beispiel in einer Liste zwei Städte tauschen:

[1,4,2,3] -> [4,1,2,3] 
[1,2,3,4] -> [1,3,2,4] 

This video zeigen ein hervorragendes Beispiel für eine Javascript Implementierung des Abstand durch einen genetischen Algorithmus zu optimieren.