Algorithme 2-opt ou 3-opt? pour le pb de TSP
cotta
Messages postés
294
Date d'inscription
Statut
Membre
Dernière intervention
-
François Lucas -
François Lucas -
Bonjour,
je veux faire une comparaison entre l'algorithme 2-opt et 3-opt pour la programmation du problème de voyageur de commerce , sur google je trouve pas grand chose .
a votre avis c'est qui le plus optimisé pour ce genre du pb ?
je vous remercie d'avance ..
;)
je veux faire une comparaison entre l'algorithme 2-opt et 3-opt pour la programmation du problème de voyageur de commerce , sur google je trouve pas grand chose .
a votre avis c'est qui le plus optimisé pour ce genre du pb ?
je vous remercie d'avance ..
;)
A voir également:
- 2 opt
- Ai suite 3 - Télécharger - Optimisation
- Picasa 3 - Télécharger - Albums photo
- Photorecit 3 - Télécharger - Visionnage & Diaporama
- Imagen 3 - Accueil - Applications & Logiciels
- Zelda 3 - Accueil - Guide jeu vidéo
4 réponses
C'est peut être un peu tard pour te répondre, mais bon, on sait jamais ^^
En fait, tu ne peux pas vraiment comparer quel algorithme est le meilleur.
Les OPT sont des voisinages stochastiques, donc liés au hasard.
En fonction de ton problème, et du codage que tu lui auras appliqué, certains voisinages marcheront mieux que d'autres.
On va dire que le 3-opt "brasse" un peu plus tous tes éléments d'oméga ;)
En espérant avoir pu t'aider
En fait, tu ne peux pas vraiment comparer quel algorithme est le meilleur.
Les OPT sont des voisinages stochastiques, donc liés au hasard.
En fonction de ton problème, et du codage que tu lui auras appliqué, certains voisinages marcheront mieux que d'autres.
On va dire que le 3-opt "brasse" un peu plus tous tes éléments d'oméga ;)
En espérant avoir pu t'aider
Au fait 2Opt et 3Opt sont des heuristiques dites d'amélioration. Leur principe commun consiste, en partant d'une solution réalisable, à appliquer un certain nombre de changement sur la solution (changement aléatoires) de façon à l'améliorer. Cette méthode approchée, appartient à la famille k-opt d'une manière générale (de Lin et Kernergan), appliquée au TSP (surtout Euclidien) elle est efficace.
Maintenant, la différence entre 2 et 3 opt, c'est le nombre d'éléments à échanger respectivement 2 et 3) dans une itération. Toujours pour le PVC, il s'agira d'arêtes (arcs) ...
Méthode de recherche locale très efficace...
J'espère vous avoir apporter un petit plus et bon courage...
Maintenant, la différence entre 2 et 3 opt, c'est le nombre d'éléments à échanger respectivement 2 et 3) dans une itération. Toujours pour le PVC, il s'agira d'arêtes (arcs) ...
Méthode de recherche locale très efficace...
J'espère vous avoir apporter un petit plus et bon courage...
Bonjour,
J'ajoute moi aussi ma réponse aux deux précédents commentaires, ce qui pourrait servir à une personne débutant dans le domaine des heuristiques d'amélioration.
Il est impossible de dire lequel est le plus "optimisé", car cela dépend du critère d'efficacité recherché. Mais pour faire simple, 3-opt est plus efficace (optimise davantage le coût de la solution) mais prend plus de temps à s'exécuter. 2-opt est plus rapide, mais a un "potentiel d'amélioration" de la solution moindre.
3-opt nécessite une série de balayage de toutes les combinaisons de 3 arêtes (trois boucles donc), 2-opt deux boucles seulement. Pour de grosses instances d'un problème de voyageur de commerce, la différence de temps de calcul se fait clairement sentir, surtout si elle est appelée fréquemment comme amélioration dans un algorithme type métaheuristique ou ILS (iterated local search).
En espérant avoir éclairé quelque peu.
J'ajoute moi aussi ma réponse aux deux précédents commentaires, ce qui pourrait servir à une personne débutant dans le domaine des heuristiques d'amélioration.
Il est impossible de dire lequel est le plus "optimisé", car cela dépend du critère d'efficacité recherché. Mais pour faire simple, 3-opt est plus efficace (optimise davantage le coût de la solution) mais prend plus de temps à s'exécuter. 2-opt est plus rapide, mais a un "potentiel d'amélioration" de la solution moindre.
3-opt nécessite une série de balayage de toutes les combinaisons de 3 arêtes (trois boucles donc), 2-opt deux boucles seulement. Pour de grosses instances d'un problème de voyageur de commerce, la différence de temps de calcul se fait clairement sentir, surtout si elle est appelée fréquemment comme amélioration dans un algorithme type métaheuristique ou ILS (iterated local search).
En espérant avoir éclairé quelque peu.