Discussion :

[bonjour69]

Bonjour,


Je connais la méthode de Monte-Carlo et le problème du voyageur de commerce par contre je ne vois pas comment lier les deux.
J'ai juste d'aprés mes recherches observé que la solution résultant de ces deux méthodes combinées ne pouvait donner qu'une solution approchée et non vérifiable.

j'aimerais donc savoir si vous pouvez confirmer cela ?
et aussi savoir si vous pouvez indiquer vers des documents ( ou pas vous-même ) montrant comment mettre en place cette algorithme.

Merci

[jobherzt]

je ne suis pas sur que la methode de monte carlo soit en soi une methode efficace pour resoudre le TSP. tu devrais t'orienter plutot vers un algo génétique, dans ce cas tu peux employer des methodes "a la monte carlo" pour des optimisations locales, mais la encore c'est en complement d'autre chose.

[bonjour69]

ReBonjour,

Oui en effet je sais que ce n'est absolument pas le meilleur moyen d'obtenir une solution mais je m'interesse à cette méthode de prés.
Alors bon si Monte-Carlo consiste à générer des possibilités et ensuite en s'appuyant sur la loi des grands nombres tirait des conclusions probabilistiques. J'imagine que pour un TSP il serait question de générer des chemins au hasard ?

ou alors ce serait plus une résolution graphique avec une equation de courbe ou autre..

[jobherzt]

ben oui, du monte carlo tout seul ca reviendrait a tirer des chemins au hasard ce qui n'aurait pas vraiment d'efficacité.... ca s'utiliserait plutot comme methode d'optimisation locale : tu prends un chemin, tu permutes quelques points au hasard et tu regardes si ca ameliore le chemin, dans ce cas tu gardes. mais ca doit se faire en complement d'une heuristique type algo genetique.

[bonjour69]

Je regarderais donc du coté des algos génétiques et sinon Monte Carlo peut être utiliser pour modéliser quel phénoméne ? apart pour calculer pi :p

[jobherzt]

je ne suis pas tres calé sur la question mais je pense que ca s'utilise en modelisation, genre si tu bricoles des nuages de particules et que tu veux avoir un comportement global (genre evolution d'un gaz).. mais je me trompe peut etre.

pour les algos genetiques, il faut savoir qu'il ne font pas tout le boulot : c'est le paradoxe des meta heuristiques, elles ne fonctionnent bien que couplées a des optimisations locales.

en fait, le genetique fait le fond du boulot, le brassage, c'est lui qui empeche de tomber dans un minima local. mais 90% du temps de calcul est en fait pris par les optis locales. regarde par exemple du coté des 2-opt.

[Zavonen]

Monte-Carlo est surtout utilisée pour calculer des intégrales (aires volumes).
L'ensemble à mesurer est placé dans un ensemble simple de mesure connue (parallélogramme, parallélépipède). On simule un tir uniformément distribué sur le contenant;le rapport (coups au but)/(nbre de tirs) donne une mesure approximative du rapport M1/M2, M1 étant la mesure à trouver, M2 la mesure connue du contenant.
Monte-Carlo vaut ce que vaut le générateur pseudo-aléatoire.