Algorithmes génétiques - Vendeur ambulant

Question

Je vais à travers un papier d'examen passé et je suis en train de comprendre la question suivante:

Supposons que vous avez des villes N. Il est possible d'aller de chaque ville à l'une des autres villes. Supposons que vous avez des informations complètes sur les distances entre les villes sous forme de tableau. La distance entre le numéro de ville k et le numéro de ville l est donnée par d (k, l); Ainsi, par exemple, la distance de la troisième ville à la neuvième ville est donnée par d (3,9). Notez que d (k, l) = d (l, k). Un vendeur itinérant doit visiter toutes les N villes et veut trouver l'itinéraire le plus court qui relie toutes les villes. Utilisez un algorithme génétique pour résoudre ce problème. Question: Définissez une fonction de remise en forme appropriée pour ce problème et indiquez si la condition physique est bonne ou faible.

Est-ce que quelqu'un sait ce que je dois faire pour cette question? J'ai vraiment du mal à savoir par où commencer et j'ai besoin de direction.

Answer 1

Avec le TSP vous voulez minimiser la distance parcourue. Il y a beaucoup de façons différentes de voyager dans les villes n; N!/2 pour être exact. Donc, si vous avez N = 4, vous voulez un tableau des entiers 1-4, chacun ne se produisant qu'une seule fois. Ainsi, certaines options possibles seraient:

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

Vous évaluez ensuite le score en allant de la ville i-i+1 dans la liste, calcul de la distance. Faites ceci pour chaque ville i dans la liste (mais la dernière) et vous avez la distance totale; c'est ton score!

Donc, pour les exemples ci-dessus les résultats seraient:

// 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) 

Vous voulez minimiser la distance, minimiser ainsi le score.

---

Vous pouvez le faire en créant des fonctions de mutation qui échangent deux villes dans une liste, par exemple:

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

This video montre un excellent exemple d'implémentation Javascript d'optimiser la distance grâce à un algorithme génétique.