Récuit simulé

[souhailamir]

bonjours
Qui peut me donner des informations et programe sous matlab ou c du methode de récuit simulé.

[Yann]

Bonjour Souhailamir,

Je ne suis malheureusement pas un expert du recuit simulé, mais pour avoir eu à l'utiliser en situation concrète deux ou trois fois, j'ai dû me faire une idée de son principe de fonctionnement (faut dire qu'au début cette méthode paraît un peu magique). J'espère que ces quelques explications pourront t'aider et que quelqu'un me corrigera si je dis des bêtises.

Le principe du recuit simulé est de minimiser un expression, mettons par exemple : , où est un vecteur de . L'objectif consiste à créer une chaîne de markov, c'est à dire une suite de nombres telle que à partir d'un donné, on sait parfaitement calculer . La méthode utilisée repose sur l'algorithme de Metropolis-Hastings, qui permet de nous assurer que lorsque est suffisamment grand, les valeurs de la suite suivent une distribution de probabilité donnée. L'objectif consiste alors à passer une distribution de probabilité "cible" telle que l'on peut avoir, sous certaines conditions, des garanties de convergence vers le minimum de .

Ces conditions font intervenir un taux de décroissance d'un paramètre que l'on appelle usuellement température, et la solution optimale trouvée par l'algorithme est atteinte lorsque cette température atteint la valeur nulle. Pour pouvoir être assuré de trouver le minimum de , on sait que la température ne doit pas descendre trop rapidement (il me semble que la condition impose une décroissance au plus logarithmique). En pratique cette solution n'est pas réalisable (trop coûteux en temps de calcul). On utilise plutôt une décroissance géométrique, et on perd la garantie de convergence. Donc au final, l'algorithme de recuit simulé tel qu'utilisé en pratique est un algorithme stochastique : il nous dit seulement qu'à l'issue de la chaîne, la solution obtenue a de "fortes chances" d'être le celle qui minimise globalement mais on ne peut pas en être totalement sûr.

En pratique, relancer plusieurs fois l'algorithme (à partir de différents points de départs ) et conserver la solution qui donne la valeur la plus faible , donne de bons résultats (pas nécessairement optimaux, mais pas loin).

Pour ce qui est de l'implémentation informatique, ce n'est pas très compliqué, tu peux t'inspirer des pages wikipédia sur le recuit simulé et Metropolis-Hastings.

https://fr.wikipedia.org/wiki/Recuit_simul%C3%A9
https://fr.wikipedia.org/wiki/Algorithm ... s-Hastings

Si tu exposes ton problème d'optimisation, je peux te donner plus d'indications sur la marche à suivre.

Je n'ai malheureusement pas de codes en Matlab ni en C, mais au cas où, j'ai un bout de code en R qui génère une distribution normale avec Metropolis-Hastings. N'hésite pas à demander si tu as besoin.

Sinon, si ton problème est plus compliqué (en particulier par exemple dans le cas transdimensionnel, c'est-à-dire si tu ne connais pas a priori la taille du vecteur qui minimisera ), il serait plus raisonnable de faire appel à des librairies spécialisées.

Tu peux également trouver un exemple tout fais ici (sur la cas du problème du voyageur de commerce) :
http://www.codeproject.com/Articles/267 ... ng-Salesma

Voilà, j'espère que ça te sera utile

Bon courage