Discussion :

[membreComplexe12]

Bonjour tous,

je vous écris car j'aimerai savoir si vous avez deja programmé un algorithme de recuit stimulé.

si oui, pourriez vous m'expliquez un peu comment ça marche "en pratique" car j'ai regardé un peu wikipedia et des trucs dans ce genre et ce n'est pas très clair pour moi:
-> j'ai l'impression qu'il y a pas mal de choses à choisir qui me paraissent compliquées (temperature de depart, vitesse de refroidissement, paliers...Etc)

de plus j'ai pas vraiment compris si il y a une vitesse de convergence elevée ou non...

bref, je suis un peu pommé avec cet algo et si quelqu'un l'a deja utilisé/le connait, j'aimerai bien avoir son avis sur la question.

je vous remercie

[Obsidian]

Bonjour,

Ce n'est pas « recuit stimulé » mais « recuit simulé ». Ça s'appelle ainsi parce que c'est une simulation informatique de ce qui se passe lorsque tu chauffes un métal au point de le fondre puis que tu le refroidis lentement pour laisser le temps à ses atomes de se réorganiser proprement. On comprend que c'est effectivement de cette manière qu'ils vont se réagencer le plus efficacement. L'idée étant d'appliquer le même procédé à n'importe quel cas d'étude.

C'est beaucoup plus clair si tu imagines une boîte dans laquelle tu ferais couler du sable : il va y former un monticule. Si ensuite tu veux que ton sable se répartisse uniformément dans ta boîte (et que la surface soit bien plate), tu vas secouer tranquillement celle-ci, éventuellement par à-coups. À chaque petit choc, les grains de sables vont virevolter et se déplacer dans un rayon limité autour de leur position individuelle. Au bout d'un moment, ils vont converger vers l'équilibre, c'est-à-dire un état où ils sont tous plus ou moins semblables les uns par rapports aux autres.

D'autre part, un tas de sable contient de l'énergie potentielle : ce n'est que la friction et les interblocages entre les grains qui le fait tenir mais si c'était un liquide, il s'effondrerait instantanément pour devenir une flaque. C'est dans ce sens qu'on dit que l'on cherche à minimiser l'énergie, ce qui est assez courant en physique. En ce sens, l'optimum est souvent le minimum. Dans le cas présent, l'opération ne va pas faire qu'uniformiser la répartition des grains : elle va aussi permettre aux plus petits de se glisser dans les moindres interstices, chose qu'ils ne font pas naturellement parce qu'ils se gênent entre eux.

Si je laisse ma boîte tranquille, il ne se passera rien de spontané. Si je la secoue par à-coups, je vais progressivement converger vers l'état le plus stable, donc optimum. Par contre, si je la remue comme un forcené, je n'arriverai à rien non plus. Je ne ferai que mélanger mon sable à travers toute la boîte et chaque grain pourra à chaque mouvement se retrouver dans n'importe quelle position dans ma boîte. Il y a donc un juste milieu à trouver.

En perfectionnant le procédé, tu peux t'en servir pour trier des éléments de différentes tailles, par exemple du sable, des gravillons et du gravier : tu commences par secouer fort pour faire couler les gros morceaux, puis tu réduis doucement l'intensité pour n'affecter que les blocs plus petits.

L'intensité de mes secousses, c'est ce que l'on traduit par « température » puisque c'est exactement ce qui se passe au niveau moléculaire quand elle augmente et qu'à dire vrai, c'est la définition même de la chaleur. Chaque à-coup correspond à une itération dans ton algorithme.

C'est une heuristique assez proche, dans le principe, des algorithmes génétiques, dans lequel on forme des « chromosomes » qui sont en fait des ensembles d'individus initialement tirés au hasard, puis que l'on va « croiser » avec les chromosomes voisins en retenant la moitié des individus de chacun d'eux, et en sélectionnant ceux qui donnent le meilleur résultat.

On s'aperçoit que, dans les deux cas, on converge effectivement assez vite et que c'est assez surprenant. Dans le cas d'une boîte à moitié remplie de sable fin, si on considère le nombre de grains qu'elle contient, il est intéressant de remarquer qu'on obtient un résultat satisfaisant au bout de dix à quinze secousses seulement.

[membreComplexe12]

merci obsidian pour ta réponse très détaillé.

j'ai compris à présent le principe mais d'un point de vu pratique j'ai un peu de mal à comprendre quels sont les paramètres, comment on les choisit....

aurais tu un exemple très simple de ce type d'implémentation ?

[Alexis.M]

Si cela t'intéresse tu dois avoir une implémentation commentée du recuit simulé dans le "Numerical Recipes". Les explications sont généralement claires et pédagogiques. Après suivant l'implémentation les paramètres peuvent varier.

[membreComplexe12]

effectivment Alex, je viens de regarder et ça s'y trouve bien!

merci pour les infos

A+