Discussion :

[dinver]

je cherche un algorithme de résolution du prb du voyageur de commerce par la méthode du recuit simulé.
l'idée est un peu clair mais il me reste des points que j'arrive pas à résoudre.
La fonction objectif étant le calcul de la distance parcourus.
Je dois permuter l'ordre de visite de ces villes et évaluer de nouveau la fonction objective. Ce qui me pose un problème c'est selon quelle loi je dois permuter l'ordre de visite des villes ? Je permute par 2, 4, ou n villes ? Le choix du nombre de permutations comment se fait ?
Le deuxième point c'est parois malgrès que la fonction objective augmente on doit accepter la solution pour ne pas se piéger par un minimum local (c'est par définition de l'algo). On accepte cette solution avec la probabilité exponentiel(-delta E/ T) où
delta E est la différence entre l'ancienne et l'actuelle valeur de la fonction objective.
En faite, en terme de programmation, il faut tirer un nombre au hasard appartenant au type de la valeur objective ? càd un nombre entre 0 et Float si ma fonction d'energie est de type float ?
Enfin, le terme température représente quoi dans le cas du PVC ?
Et quelle est la condition d'arrêt de l'algorithme ?

J'espère que mon message est mis dans le bon endroit puisqu'il y a des question à propos de l'algo recuit simulé et un peu de programmation.

Merci

[victorracine]

Salut caso,

Le recuit simulé est un paralelle entre une methode de thermodynamique et des problèmes d'obtimisation combinatoire (comme le problème du voyageur de commerce).
Quand tu fais une simulation de gaz par exemple, tu vas:
1 placer tes molecules dans ton espace
2 les faire aller vers un etat d'equilibre thermodynamique
3 etudier ton système à l'equilibre
C'est le principe de Metropolis.
Tu sais que tes molecules vont avoir un mouvement (brownien) dut à l'agitation thermique: kT (k est la constante de bolzmann). Plus la temperature est grande plus les molecules vont bouger dans tous les sens. Dans le recuit, on cherche à placer l'ensemble des molecules de la maniere la plus stable possible (c'est à dire tel que son energie soit la plus faible). Si les molecules sont de nature complexe (ex polymere), on comprend bien que le travail n'est pas facile. Dans la plupart des cas à basse temperature on va etre dans un etat de vitreux. La technique utiliser est donc de faire chauffer le système fortement afin que chacunes des molecules puissent bouger dans tous les sens. Puis petit à petit diminuer la temperature du systeme. Cette diminution doit etre tres lente. Si la diminution est trop rapide, on va se retrouver dans une etat vitreux (c'est à dire que la structure est amorphe ou presque, est qu'on ne peut plus en bouger, on est hors de l'equlibre thermodynamique). A haute temperature la structure generale du systeme va s'organiser , et à basse temperature c'est les structures tres locales qui vont s'organiser.

Dans le problème du voyageur de commerce, ton système est constitué de l'ensemble de tes villes et de ton parcour. L'energie que tu veux minimiser est la distance de ton parcours. Tu parts d'un etat quelconque (tiré aleatoirement... peu importe), tu vas donner à ton système du "bruit interne" comme une agitation thermique (relatif au parametre T), c'est à dire que tu vas permetre à ton système de changer tout seul. Pour faire cela, tu vas faire une transformation, calculer son delat(E). Si delta(E) est negatif, cela veut dire que tu as amelioré ton système, donc tu "appliques" la transformation. Si delta(E)>0 alors tu appliques ta transformation avec une probabilité de exp(-delta(E)/T). Si tu es en dehors de cette proba, tu ne dois pas faire cette transformation. Ce principe est basé sur les chaines de Markov, cela simule l'equilibre thermodynamique relatif à la temperature T. Plus ton T est grand plus tu risques de faire ta transformation. Donc pour un grand T, ton parcour va changer quasiement à chaque fois, meme si tu augmentes ton energie. A basse T, tres peut de transformation à delta(E)>0 seront acceptées.
Tu dois donc choisir un gand T.
A ce T fixé, tu dois aller vers ton equilibre thermo, c'est à dire tester un grand nombre de transformation.
Ensuite tu diminues T, et tu recommences à aller vers de nouvel etat d'equilibre (relatif un nouveau T).
Et tu continues comme ca jusqu'à atteindre T=0.
Plus tu vas aller lentement, meilleur sera ton resultat.

Il reste à choisir une transformation. La condition de validité d'une transfo est que tous les parcours possibles de ton systeme doivent etre accesibles, à partir de n'importe quelle solution initiale. Donc tu peux permuter, faire des decalages, tout ca est permit . Par contre chaque type de transformation ne va pas permetre d'aller à l'equilibre thermody aussi rapidement. Il faut les essayer toutes, elles dependent de ton problème, pas de la methode du recuit.

Pour finir tout ca, le recuit est une bonne methode, est permet de resoudre un tres grand nombre de problème. La methode est robuste. Je la trouve souvent plus interessante que les methodes bases sur les algo genetiques car il y a tres peut de parametre à gerer.
Par contre pour un problème precis comme le problème du voyageur de commerce, c'est n'est surement pas la methode la plus optimale. Il parait que les algo les plus efficace pour ce problème serait un complexe melange de toutes les methodes de combinatoire (collonies de fourmis, parcours tabou... ). Mais cette methode te donnera de bon resultat.

Petit deniere chose dont je n'ai pas parlé, c'est que tu n'aurras bien sur pas de solution exacte à ton problème, tu n'as pas convergence( ).


J'espere que je t'ai un peut eclairé sur la question, n'esites pas a bien bien comprendre le principe thermodynamique et la simulation qu'on en faire (cf metropolis ) avant de te metre à ton algo.

Aller au boulot.

A+
Vic

[dinver]

Je te remercie.
Mais il faut dire que pour le choix de permutations tu m'as dis que tout est permis et c'est la seule chose que j'ai eu de plus. Et d'ailleur est ce que je dois choisir un type de permutation qui me permettera d'avoir tous les chemin ?
: sinon pour la méthode de recuit je la comprends très bien reste pour le problème de voyageur de commerce je comprends pas concrétement la température représente quoi ?
pour la fonction objective c'est clair que c'est la distance parcourus.
delta E c'est la difference de distance après avoir fait une permutation.

[victorracine]

Il faut que tes permutations permettent d'engendrer toutes les solutions possibles de ton système.
La temperature represente la facilité avec laquelle tu va accepter une transformation. Au debut (grand T) tu vas quasiement tout accepter (sauf si le delta(E) est vraiment tros grand). Statistiquement la structure generale de ton système se mette en place et la structure locale elle, ne va pas arreter de changer. En faisant desendre la temperature petit à petit, la structure globale va rester à peu pres fixé et la structure locale va s'affiner. Lorsque T=0 tu ne fera qu'ameliorer les plus petites structures en diminuant ta fonction energie a chaque fois.
delta E c'est bien la difference de distance après avoir fait une permutation.

a+
Vic

[chahrazed15]

salut:
je cherche un algorithme de résolution du probleme du voyageur de commerce par la méthode du recuit simulé. g vu que tu a le meme probleme que moi alors si tu a réussis a le resousre je seré trés reconnaissante de m'envoyé ce que ta réussi de faire stp envoit moi dans mmon email merci et a la prochaine