Recuit simulé
Un article de Wikibot.
Sommaire |
[modifier] Généralités
Le recuit simulé est une méthode d'optimisation inspirée de la métallurgie. Elle permet de trouver des solutions, non optimales, mais souvent satisfaisantes, en un temps définit à l'avance.
En faisant fondre un alliage, lors de sa solidification des cristaux se forment à partir des impuretés présentes dans le métal en fusion. La forme et la taille de ces cristaux conditionneront les caractéristiques mécaniques de la pièce solide.
Pour modifier les caractéristiques mécaniques de la pièce on effectue souvent une opération que l'on nomme recuit.
C'est à dire que l'on chauffe à nouveau la pièce métallique proche du point de fusion, puis on refroidit à nouveau. Les anciens cristaux métalliques, sont en partie remplacés par d'autres ce qui constitue donc un nouvel arrangement de la matière, et donc de nouvelles propriétés mécaniques.
La méthode du recuit simulé s'inspire de ce processus.
[modifier] Descente stochastique
Dans un ensemble de solutions, faire une descente stochastique, c'est prendre une solution au hasard, évaluer son efficacité. On évalue ensuite chacune des solutions avoisinantes, et si elles sont meilleures que la solution originale, alors elle est choisie comme référence. On effectuera d'autres itérations autour de cette solution, jusqu'à arriver à un optimum local.
[modifier] Recuit simulé
Dans le recuit simulé, on part d'une descente stochastique, mais cette fois, on s'autorise de choisir des solutions dont le score est moins intéressant que la solution courante. Le delta que l'on s'autorise entre la solution retenue et la meilleure solution est fonction d'une température, à l'image de la température d'un métal en cours de refroidissement. Cette température diminue avec le temps. Lorsque cette température est suffisamment proche de 0 alors cela revient à terminer l'algorithme de descente stochastique.
Une solution souvent plus pertinente que l'algorithme de descente stochastique est trouvée.
[modifier] Exemple appliqué au voyageur de commerce
A faire: A présenter
[modifier] Exemple de code
A faire: Code en java
