Une question de détail lors de l'application de l'algorithme génétique au vendeur itinérant

Question

J'ai lu diverses choses à ce sujet et je comprends le principe et les concepts impliqués, cependant, aucun de papier ne mentionne les détails de la façon de calculer l'aptitude d'un chromosome (qui représente une voie) impliquant des villes adjacentes (dans le chromosome) qui ne sont pas directement connectées par un bord (dans le graphique).

Par exemple, étant donné un chromosome 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, dans lequel chaque gène représente l'indice d'une ville sur le graphique / carte, comment calculons-nous sa forme physique (c'est-à-dire la somme totale de Distances parcourues) Si, disons, il n'y a pas de bord / lien direct entre la ville 2 et 8. Suivons-nous une sorte d'algorithme gourmand pour déterminer une route entre 2 et 8, et ajouter la distance de cette route au total?

Ce problème semble assez courant lors de l'application de GA au TSP. Quiconque l'a fait avant de partager votre expérience. Merci.

Answer 1

S'il n'y a pas de lien entre 2 et 8 sur votre graphique, alors tout chromosome avec 2 | 8 ou 8 | 2 dedans est invalide Pour le problème des vendeurs de voyage classique. Si vous trouvez un autre itinéraire entre 2 et 8, vous allez probablement violer l'exigence "Visitez chaque emplacement".

Une solution vraiment douteuse mais pragmatique consiste à inclure des bords entre ces nœuds avec des distances incroyablement élevées, ou même + Inf si votre langue le prend en charge. De cette façon, votre fonction de fitness minimisant standard les taillera naturellement.

Je pense que la formulation originale du problème comprend des bords entre tous les nœuds, c'est donc un non-problème.

Answer 2

Il s'agit du type exact de problème, des méthodes de croisement et de mutation spécialisées ont été appliquées pour des solutions basées sur GA aux problèmes TSP. Regarde ça question.

Answer 3

Si la chromosone ne représente pas une solution valide, il est complètement impropre à résoudre le problème. Donc, selon la façon dont vous commandez la forme physique. c'est-à-dire que si un nombre inférieur représente plus de forme physique (peut-être une bonne idée lorsque la forme physique représente le coût total), vous lui attribueriez une valeur maximale et cassez tout autre calcul de fitness sur cette chromosone lorsque vous arriverez à une séquence de gènes invalide.

(ou vice versa, attribuez-lui une forme physique de zéro si une forme physique plus élevée signifie qu'une chromosone est plus apte au travail)

Cependant, comme d'autres l'ont souligné, il pourrait être préférable de s'assurer que les chromosones non valides ne se produisent pas. Cependant, si cela est lui-même un processus trop compex, en leur permettant et en veillant à ce que les chromosones cassées soient peu susceptibles de conclure des générations successives pourraient être une approche acceptable.