Le recuit simulé est un algorithme qui s'inspire d'un mécanisme naturel pour trouver une solution optimum à un problème.

    Il se sert d'une exploration des solutions d'une manière à la fois aléatoire mais dirigée de façon à faire converger vers une solution optimale.

    Ce genre d'algorithme ne garantie pas de donner la meilleure solution possible à un problème, mais une solution très proche de celle-ci. Il est utilisé dans les cas de problèmes très complexes où l'étude de toutes les solutions ne peut pas être envisagé.

>UN MECANISME NATUREL

    Le recuit est une technique consistant à chauffer un matériau et à le refroidir dans certaines conditions. Lors du refroidissement les atomes de la matière s'organisent entre eux de manière à ce que les configurations de plus faible niveau d'énergie (les plus stables) soient privilégiées. Tant que le niveau d'énergie total du matériau (sa chaleur) reste élevé les atomes peuvent trouver l'énergie pour changer de configuration, quitte à passer par des configurations moins stables. Au fur et à mesure que la température baisse les atomes auront une ressource d'énergie plus faible pour passer dans des configurations plus instables.

    Pour une température T, la probabilité de passage d'un groupe atomes à un niveau d'énergie supérieur d'un écart dE, est fournie par l'équation de L. Boltzmann:

P = exp(-dE/T); (ou 'exp' est la fonction exponentielle).

l

    Pour ceux que les formules rebutent cela signifie que la chance pour un groupe d'atome de passer à une configuration de niveau d'énergie plus élevé sera d'autant plus grande que la différence d'énergie sera faible et que la température sera élevée.

>DES PROBLEMES INFORMATIQUES COMPLEXES

    Vous savez sans doute qu'en informatique l'on classe les problèmes à résoudre en fonction de la manière dont la quantité d'opérations à effectuer croit lorsque le nombre d'éléments à traiter augmente. C'est évidement la quantité d'opérations à effectuer qui va déterminer le temps de traitement.

    Une augmentation du nombre d'opérations proportionnelle au nombre d'éléments du problème est bien meilleure qu'une augmentation proportionnelle au carré du nombre d'éléments, etc. ...

    Il existe des problèmes dont les algorithmes de résolution croissent plus vite que n'importe quelle fonction polynomiale du nombre (N) d'éléments à traiter. C'est à dire que n'importe quelle puissance de N. Cela représente un tel taux d'accroissement du nombre d'opérations à effectuer qu'à partir d'un nombre d'éléments à traiter encore limité (de l'ordre de 15), le nombre d'opérations à effectuer atteint des quantités dépassant le milliard.

    L'exemple le plus classique de ce type de problème est celui dit du "Voyageur de commerce". Un commis voyageur doit se rendre dans N villes en partant de l'une d'elle. Il ne doit passer qu'une fois dans chaque ville et finir sa tournée en revenant dans la ville de départ. Le problème est de trouver l'itinéraire le plus court possible, connaissant les distances entre chaque ville.

    Il n'y a pas d'autre manière de trouver la solution que d'essayer tous les parcours (circuits) possibles en conservant le parcours minimal trouvé. Le problème est que pour N villes a parcourir il y a (N -1)! /2 circuits différents possibles. Soit pour 12 villes: 19 958 400 circuits !

>AMELIORATIONS SUCCESSIVES

    Si nous prenons le problème du voyageur de commerce, plutôt que d'étudier tous les circuits possibles nous pourrions imaginer trouver un algorithme qui partant d'un circuit quelconque trouverait les modifications nécessaires pour raccourcir le circuit jusqu'à obtenir le plus court possible.

    Voyons les moyens d'améliorer un circuit. Pour simplifier assimilons les villes à des points, la route entre 2 villes au segment qui les joint.

    Parmi les améliorations possibles de la longueur du circuit on peut en imaginer des quantités. En voici quatre:

a) Croiser deux segments: Soit 2 segments du circuit AB et CD, faire la somme de leur longueur. Comparer avec la somme des segments AC et BD.           b) Déplacer un point: Soit un point D situé dans le parcours entre C et E et un segment AB, placer D entre AB et joindre directement C et E. Comparer AB+CD+DE avec AD+DB+CE.           c) Inverser un segment: Soit une partie d'itinéraire ABCD, remplacer par ACBD. Comparer AB+CD avec AC+BD (BC reste commun).           e) Echanger deux segments: Soit deux segments BC et FG inclus chacun dans les deux tronçons ABCD et EFGH. Prendre les nouveaux tronçons AFGD et EBCH. Comparer les longueurs respectives avant et après échange.

l

    Dans chaque cas si le nouveau circuit est plus court: on modifie l'itinéraire en conséquence.

    Malheureusement en informatique tous les chemins ne mènent pas à Rome. (Je soupçonne le voyageur de commerce de ne pas être très catholique).

    Au bout d'une série d'améliorations on aboutit toujours à un circuit qui ne peut plus être amélioré. Ce n'est pas pour autant le circuit le plus court. C'est un peu comme un caillou qui roulerais d'un sommet, il descend tant qu'il peut, mais s'il tombe dans une cuvette, il s'arrête avant la plaine.

    On dit que l'on a obtenu un minimum local.

>LE RECUIT SIMULE

    Pour éviter le piège des minima locaux, c'est là ou intervient l'idée d'imiter le recuit.

    Il faudrait que le caillou bloqué ait de l'énergie pour remonter la pente qui l'arrête (un peu comme si on le remplaçait par un haricot sauteur).

    On ne peut cependant pas savoir si cette remontée qui est contraire à notre recherche du minimum va nous ouvrir le chemin d'une vallée plus basse ou non.

    Le recuit simulé est un algorithme qui imite le comportement des atomes de matière en refroidissement pour rechercher une solution minimale dans toutes sortes de problèmes.

    Pour résoudre un problème avec cet algorithme on peut partir d'une solution quelconque. Un facteur, nommé "température" par analogie avec le recuit naturel, est élevée au départ. La température représente le degrés de liberté d'évolution de la solution courante. On applique sur la solution une série de modifications.

    Le comportement du recuit est statistique. On privilégie les améliorations de la solution qui sont toujours acceptées. Les détériorations sont acceptées avec une probabilité qui est contrôlée par le facteur "température". Cette probabilité est déterminée par l'équation de Boltzmann.

    La diminution progressive de la température va limiter la liberté de la solution recherchée de s'écarter des améliorations. Ainsi la solution converge vers un optimum tout en ayant eu la possibilité d'explorer plusieurs chemins possibles, donc d'éviter de nombreux minima locaux.

    Cette technique n'assure pas d'obtenir la meilleure de toutes les solutions possibles au problème. Théoriquement si l'on baissait la température infiniment lentement on tendrait vers cette solution, comme l'on obtiendrait un cristal en refroidissant très lentement un métal après la fusion.

    Le but n'est pas de prolonger les calculs à l'infini et cela n'est pas utile. En réglant bien les paramètres du recuit simulé, on peut obtenir une solution qui se rapproche de quelques pour-cent de la solution idéale. Cela avec un temps de calcul bien plus limité que la méthode exhaustive qui n'est parfois même pas envisageable.

    Comme l'exemple du "voyageur de commerce" peut le suggérer la technique du recuit simulé peut être utilisée dans les problèmes tels que : l'optimisation de coût, la détermination de la topographie de réseaux, l'adaptation d'un réseau de neurones artificiels à un jeu d'essai, etc.

>L'ALGORITHME

    Le programme fonctionne donc globalement de la manière suivante:

    On part d'une configuration de départ qui peut être aléatoire.

    On détermine une température de départ, une température d'arrêt, un nombre de paliers de température et un taux de décroissance de la température.

    A chaque paliers on fait un nombre d'essai de modification proportionnel au nombre (N) d'éléments à traiter (les villes dans le voyageur de commerce).

    Si une modification augmente le coût de la configuration (dE) on calcule sa probabilité d'acceptation en fonction de la température courante par la fonction exp(-dE/T) , et l'on tire un aléa compris entre 0 et 1. Si l'aléa est inférieur à la probabilité on accepte cette modification.

    Apres tous les essais sur un palier on baisse la température du facteur de décroissance et l'on recommence, tant que la température d'arrêt n'est pas atteinte.

    On peut résumer ça ainsi:

Température = TempératureDépart Essais = (N/2)^2 TantQue Température > TempératureArret Faire           Pour I = 1 Jusqu'à Essais Faire                     dE = coût_modification                     Si dE < 0 Faire                               modifier_recuit                     Sinon Faire                               A = aléa(0..1)                               Si A <= exp(-dE/T) Faire                                         modifier_recuit                               FinSi                     FinSi           FinPour           Température = Température * Facteur_refroidissement FinTantQue

l

 

>REGLAGE DES PARAMETRES

    Afin que le calcul converge le plus rapidement possible il est nécessaire de bien régler certains paramètres.

    La température d'arrêt détermine l'arrêt (nécessaire) du programme et le niveau d'acceptation des augmentations de coût à ce moment là.

    La température de départ détermine le temps de refroidissement pour atteindre la température d'arrêt et le nombre de paliers de température.

    Expérimentalement on considère que les valeurs optimales sont:

    De 30 à 50 paliers. Un facteur de refroidissement proche de 0.93. Un nombre d'essais par palier de (N/2)^2 pour N éléments. Une température de départ telle que 50% des modifications détériorant le résultat soient acceptées au départ. Une température d'arrêt telle que plus aucune détérioration significative du résultat ne puisse plus être acceptée.

>LE PROGRAMME

    Les sources d'un programme d'exemple sont jointes elles ont l'avantage de:

    proposer une implémentation, présenter une visualisation du déroulement de l'algorithme.

    Il est écrit en C sous DOS avec utilisation des drivers BGI de Borland.

    Il s'agit de l'application de la méthode au problème du voyageur de commerce.

    Le nombre de ville doit être entré comme argument de la ligne de commande.

    Pour chacune un point sur l'écran est tiré au hasard.

    Le circuit est représenté en interne par une permutation circulaire. C'est une forme de représentation dans un tableau. A l'indice I est rangé le numéro de la ville qui suit la ville I dans l'itinéraire.

    Pour éviter de recalculer les distances elles sont rangées dans un tableau dynamique à 2 dimensions. Comme les distances sont égales dans les 2 sens il est possible de gagner la moitié de la place mémoire. On range et cherche une distance entre 2 villes en partant toujours de la ville de numéro le plus petit.

    Il y a N villes donc N-1 entrée. Chaque entrée correspondant à la première ville, elle ouvre donc sur un tableau du nombre de ville de numéro plus grand.

    La compilation en modèle Small permet d'allouer jusqu'à environ 150 villes. Pour en avoir plus compilez en modèle Huge.

    Le reste suit l'algorithme décrit plus haut.

>MODIFICATIONS POSSIBLES

    Vous pouvez:

    Ajouter l'affichage d'une barre de couleur qui diminue en même temps que la température.

    Essayer de modifier les constantes définies.

    Ajouter un premier palier à haute température durant lequel vous pourrez faire des mesures (nombre d'allongements, leur coût, etc.). Cela vous permettra d'avoir une idée statistique du comportement du réseau, et de calculer de manière plus efficace la température de départ et le taux de refroidissement.

    Ajouter vos propres fonctions d'amélioration du circuit.

    Comparer le résultat et le temps de traitement avec une version du programme qui calcule tous les circuits possibles.

>REFERENCES

    On peut trouver une explication claire et détaillée du principe de l'algorithme dans l'article "Le recuit simulé" de E. Bonomi et J.L. Lutton, dans le recueil "Le calcul intensif" aux éditions Belin - Pour la Science.

    Ce livre (ainsi que a reçu les meilleures critiques de SVM. Pour les amateurs ce petit livre (et son frère "Récréation informatique", chez le même éditeur) est une vraie mine d'idées stimulantes de programmes. Cependant il ne s'y trouve aucune ligne de code.

    Pour approfondir le sujet il est également possible de consulter le chapitre correspondant dans "Dynamique des systèmes complexes" de G. Weisbuch, chez InterEdition.

Ce document est la propriété de Bernerd Pradie. La rédaction ainsi que l'auteur déclinent toutes résponsabilité vis-â-vis des conséquences que pourrait entrainer le contenu de cet article.