Discussion :

[bleach1234]

Bonsoir,

Je viens vers vous pour avoir quelques avis sur les méthodes de "résolution" du problème du voyageur de commerce.

J'applique pour le moment la méthode du récuit simulé pour trouver "l'ordre" des villes. Ensuite, j'applique dijkstra entre chaque ville pour trouver le chemin le plus court.

Pour une 50aine de villes, mon script met environ 2minutes à tourner. Pour gratter un peu en terme de performance, j'ai essayé de remplacer dijkstra par A*. J'ai réussi à grappiller quelques secondes, mais ce n'est suffisant.

Je voudrais au moins diviser le temps de calcul par 2, voir plus, tout en gardant des résultats assez cohérent.

Merci de vos réactions,
Nicolas.

[pseudocode]

Bonjour,

Je voudrais au moins diviser le temps de calcul par 2, voir plus, tout en gardant des résultats assez cohérent.

Quelle est ta définition de "résultats assez cohérent" ? Tu veux dire trouver un chemin aussi long (voir moins) dans le temps imparti ?

[bleach1234]

Tu veux dire trouver un chemin aussi long (voir moins) dans le temps imparti ?

Oui, exactement.

[pseudocode]

Comme je ne connais pas tes résultats actuels, c'est dur d'être catégorique sur la réponse.

Disons que pour trouver rapidement un bon parcours, je prendrais les colonies de fourmis. Mais le résultat final est moins bon qu'une approche itérative avec heurisitique (en particulier celle de Lin-Kernighan)

[bleach1234]

J'étais également en train de me pencher pour cet algorithme (colonies des fourmis). J'ai été lire le tutoriel, avant de faire n'importe quoi j'aimerais savoir si j'ai bien tout assimilé :

Pour réaliser cet algorithme, il faut :
- 1 tableau à 2dimensions contenant la distance (à vol d'oiseau) entre chaque villes.
- 1 tableau à 2dimensions contenant les phéromones entre chaque villes.

Chaque fourmi étudie, en fonction des phéromones, les chemins possibles. Une fois qu'une fourmi à terminer son parcours, il marque les villes de phéromones qu'il a parcouru en fonction de la distance parcourue.

Le chemin "le plus court" est celui qui a le plus de phéromones.

Globalement, est-ce bien le fonctionnement ?

[pseudocode]

Globalement oui.

Sauf que le chemin le plus court c'est... le chemin le plus court () trouvé jusqu'à présent.

Ce n'est pas forcément celui qui à le plus de phéromones, surtout au moment de sa découverte.

[moudy51]

Bonjour ,
je cherche à programmer un algorithme de fourmi sur matlab afin d'optimiser le cout d'une fonction dépendant de 3 sous systèmes en meme temps
je doit optimiser les temps de commutation entre les 3 sous systèmes t1 et t2.
j'ai choisi t1 et t2 chaccun comme vecteur de n ligne et une colonne .
avec 0<t1<t2<4
je croi que si je compare avec tsp ; mes t1 et t2 representeront les noeud et la distance optimiser sera égale au cout total des 3 sous systèmes optimisé.

1-est ce que c'est correct??
2-est ce je doit parcourir tous l'ensembles des cout au début afin d'implanté la formule de féramone ???

merci d'avance

[moudy51]

Bonjour ,
je cherche à programmer un algorithme de fourmi sur matlab afin d'optimiser le cout d'une fonction dépendant de 3 sous systèmes en meme temps
je doit optimiser les temps de commutation entre les 3 sous systèmes t1 et t2.
j'ai choisi t1 et t2 chaccun comme vecteur de n ligne et une colonne .
avec 0<t1<t2<4
je croi que si je compare avec tsp ; mes t1 et t2 representeront les noeud et la distance optimiser sera égale au cout total des 3 sous systèmes optimisé.

1-est ce que c'est correct??
2-est ce je doit parcourir tous l'ensembles des cout au début afin d'implanté la formule de féramone ???

merci d'avance