Quelle approche produit la tournée plus courte dans le problème TSP: voisin le plus proche ou algorithmes génétiques?

Question

Au cours des derniers jours, j'ai noté quelques des sites qui ont démontré solution TS en utilisant des algorithmes génétiques.

Quelle est l'approche produit la tournée plus courte dans le problème TSP: voisin le plus proche ou les algorithmes génétiques

Answer 1

Puisque ni technique garantit une solution optimale, votre kilométrage peut varier. Avec un peu de chance, que ce soit technique peut surclasser l'autre. Les deux techniques ont des avantages et des inconvénients.

voisin le plus proche: + rapide, + simple, -généralement pas optimale

algorithme génétique: -slower, complexe -Plus, + solutions tendance optimale au fil du temps

La grande différence est que les algorithmes probabilistes comme recuit simulé et les algorithmes génétiques peuvent continuer à améliorer au fil du temps - plus vous laisser courir, plus les chances que vous avez pour une solution optimale (mais il n'y a aucune garantie).

Comme NN est rapide, il n'y a rien qui vous empêche de combiner les techniques. Exécutez NN pour trouver une solution de départ peut-mieux-que-aléatoire. Ensuite, nourrir cette solution dans votre algorithme génétique et le laisser fonctionner aussi longtemps que vous vous sentez est approprié.

Si vous êtes intéressé par des solutions optimales, consultez le Lin-Kernighan heuristique et de programmation linéaire. Tous deux ont été utilisés pour trouver des solutions optimales pour les grands circuits, y compris cette solution 85900 visite de la ville et 24978 ville Suède tournée .

Le site de Georgia Tech TSP est une excellente ressource.