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.

[bonjour69]

D'accord merci bien

[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.

[bonjour69]

Bonjour
J'utilise ce générateur :
avec X0 quelconque :
Xn+1 = 1103515245 * Xn + 12345 % 2^31


est-ce un bon générateur ou alors on peut faire beaucoup plus puissant ?

[jobherzt]

non, je ne pense pas que ca soit si solide...

il faut savoir qu'il y a (en gros) 2 familles de generateur aleatoires : ceux utilisé en cryptographie, qui sont tres difficile a "casser" mais qui n'ont pas forcement de "bonnes" propriétés statistiques, et les generateurs plutot orienté simulation / modelisation, qui sont parfois assez simple a "casser" mais qui reproduisent beaucoup mieux les propriétés du hasard...

tu serais donc plutot interet a taper dans la 2e categorie : regarde du coté de mersenne twister par exemple.

[bonjour69]

D'accord merci,


Par contre quand tu dis casser l'algorithme de génération aléatoire cela signifie de trouver la raison de la série ? de prévoir le nombre d'aprés ou le nombre d'avant et ainsi remonter toute la suite ?

[jobherzt]

oui, en gros c'est ca, mais si tu ne fais pas de crypto ca n'a aucune importance... et tu y gagnes en propriéts statistiques.

(en fait, plus precisement, ca veut dire : a partir d'une tres grande quantité de nombres produit par l'algo, on peut retrouver les parametres utilisés et predire les nombres suivants)

http://fr.wikipedia.org/wiki/Mersenne_Twister

[Matthieu Brucher]

Ce que tu as, c'est un simple générateur à congruence linéaire. C'est du hasard faible.
Mersenne Twister a de bonnes propriétés - grande dimension, statistiques, ... -.

[Jean-Marc.Bourguet]

Il existe deux types d'algo propabilistes:
- les algos de Monte Carlo qui donne une solution incorrecte (ou non optimale) mais proche de la réalité (ou de l'optimal) avec une probabilité bornée. Répéter des exécutions permet de s'approcher de diminuer la probabilité d'erreur.
- les algos de Las Vegas qui donne toujours une solution correcte mais avec un temps de calcul variable.

[bonjour69]

Merci pour toutes vos explications.
La génération de Mersenne Twister est trés pratique, je vais maintenant regarder du coté des algos de Las vegas.