Algorithmes de descente randomise et de recuit simul
INF6953
Le recuit simul
Sommaire
Pour faire mieux que la descente avec relances Lalgorithme damlioration itrative randomise Lalgorithme de recuit simul : historique Schma dalgorithme de recuit simul Le critre de Metropolis Paramtre de temprature Schma de refroidissement Rglage des paramtres du recuit simul Algorithmes dacceptation avec seuil
INF6953
Le recuit simul
Pour faire mieux que la descente avec relances
On sinspire du principe de lalgorithme de descente, mais on ajoute en permanence de lalatoire en permettant certains mouvements qui dgradent la fonction de cot. Ide 1 : On panache les itrations qui effectuent des mouvements de descente avec dautres qui effectuent des mouvements alatoires : algorithme de descente randomise. Ide 2 : Lors dune itration, on tend prfrer les mouvements qui amliorent mais on peut accepter des mouvements qui dgradent la fonction de cot : algorithme du recuit simul, dacceptation avec seuil.
INF6953
Le recuit simul
Lalgorithme damlioration itrative randomise
Lide consiste panacher les itrations qui effectuent des mouvements de descentes avec dautres qui effectuent des mouvements alatoires. Selon une certaine probabilit p (paramtre de la mthode), on effectue un mouvement alatoire. Sinon, on effectue un mouvement de descente. Le paramtre p (compris entre 0 et 1) dtermine le degr de randomisation p=0 : que des mouvements de descente = pure descente p=1 : que des mouvements alatoires = marche alatoire
INF6953
Le recuit simul
Lalgorithme damlioration itrative randomise
Mouvement de descente = meilleure amlioration ou premire amlioration (ou ). Cette technique a t principalement applique dans le cas de la rsolution des CSP avec la technique dite de Min-Conflict+Random Walk (MC+RW). Dans MC+RW, les mouvements de descentes sont des mouvements de type Min-Conflict.
INF6953
Le recuit simul
Schma de lalgorithme damlioration itrative randomise
Engendrer une configuration initiale S0 S := S0 Rpter Selon une probabilit p, appliquer un mouvement alatoire S Sinon, appliquer un mouvement de descente S Jusqu <condition fin> Retourner la meilleure configuration trouve
INF6953
Le recuit simul
Lalgorithme de recuit simul : historique
Le recuit physique Ce processus est utilis en mtallurgie pour amliorer la qualit d'un solide. On cherche atteindre un tat d'nergie minimale qui correspond une structure stable du mtal. En partant d'une haute temprature laquelle la matire est devenue liquide, la phase de refroidissement conduit la matire retrouver sa forme solide par une diminution progressive de la temprature.
INF6953
Le recuit simul
Lalgorithme de recuit simul : historique
Le recuit simul (Simulated Annealing) Expriences ralises par Metropolis et al. dans les annes 50 pour simuler l'volution de ce processus de recuit physique (Metropolis53). Lutilisation pour la rsolution des problmes d'optimisation combinatoire est beaucoup plus rcente et date des annes 80 (Kirkpatrick83,Cerny85). Le recuit simul est la premire mtaheuristique qui a t propose.
INF6953
Le recuit simul
Principes gnraux
Lide est deffectuer un mouvement selon une distribution de probabilit qui dpend de la qualit des diffrents voisins : Les meilleurs voisins ont une probabilit plus leve ; Les moins bons ont une probabilit plus faible. On utilise un paramtre, appel la temprature (note T) : T leve : tous les voisins ont peu prs la mme probabilit dtre accepts. T faible : un mouvement qui dgrade la fonction de cot a une faible probabilit dtre choisi. T=0 : aucune dgradation de la fonction de cot nest accepte. La temprature varie au cours de la recherche : T est leve au dbut, puis diminue et finit par tendre vers 0.
Le recuit simul 9
INF6953
Schma dalgorithme de recuit simul
Engendrer une configuration initiale S0 de S ; S := S0 Initialiser T en fonction du schma de refroissement Rpter Engendrer un voisin alatoire S de S Calculer = f(S) f(S) Si CritMetropolis(, T), alors S := S Mettre T jour en fonction du schma de refroissement Jusqu <condition fin> Retourner la meilleure configuration trouve
INF6953
Le recuit simul
10
Le critre de Metropolis
fonction CritMetropolis (, T) Si 0 renvoyer VRAI Sinon - avec une probabilit de exp( - / T ) renvoyer VRAI - Sinon renvoyer FAUX Un voisin qui amliore (<0) ou cot gal (=0) est toujours accept. Une dgradation faible est accepte avec une probabilit plus grande quune dgradation plus importante. La fonction CritMetropolis(d, T) est une fonction stochastique : appele deux fois avec les mmes arguments, elle peut renvoyer tantt vrai et tantt faux.
Le recuit simul 11
INF6953
Paramtre de temprature
Dans la fonction CritMetropolis(, T), le paramtre T (temprature) est un rel positif. La temprature permet de contrler lacceptation des dgradations : Si T est grand, les dgradations sont acceptes avec une probabilit plus grande. A la limite, quand T tend vers linfini, tout voisin est systmatiquement accept. Inversement, pour T=0, une dgradation nest jamais accepte. La fonction qui spcifie lvolution de la temprature est appel le schma de refroidissement.
INF6953
Le recuit simul
12
Schma de refroidissement
La fonction qui spcifie lvolution de la temprature est appel le schma de refroidissement (cooling schedule). Dans le recuit simul standard la temprature dcrot par paliers. Par exemple, on pourrait avoir trois paramtres : la temprature initiale, la longueur dun palier (nombre ditrations avant de changer la temprature) et le coefficient de dcroissance (si dcroissance gomtrique). On peut aussi utiliser dautres schmas de refroidissement : On peut faire dcrotre la temprature chaque itration. On utilise parfois une temprature constante (algorithme de Metropolis). On peut utiliser des schmas plus complexes, dans lesquels la temprature peut parfois remonter.
Le recuit simul 13
INF6953
Algorithme de recuit simul (avec paliers et refroidissement gomtrique)
Engendrer une configuration initiale S0 ; S := S0 T := T0 Rpter nb_moves := 0 Pour i := 1 iter_palier Engendrer un voisin S de S Calculer = f(S) f(S) Si CritMetropolis(, T), alors S := S; nb_moves := nb_moves + 1 acceptance_rate := i / nb_moves T := T * coeff Jusqu <condition fin> Retourner la meilleure configuration trouve
Le recuit simul 14
INF6953
Rglage des paramtres du recuit simul
Dans le cas du recuit simul classique (avec refroidissement), le rglage des paramtres nest pas vident. Pour rgler les paramtres, il peut tre utile dobserver le pourcentage dacceptation (acceptance rate) au cours de la recherche = nombre de mouvements rellement excuts / nombre ditrations Temprature initiale : Si la temprature initiale est trop leve, le dbut de la recherche ne sert rien. Critre darrt : Il est inutile de poursuivre si le pourcentage dacceptation devient trs faible, la fonction dvaluation cesse dvoluer
INF6953
Le recuit simul
15
Rglage des paramtres du recuit simul : implantation de Johnson et al
Temprature initiale Un paramtre fixe le pourcentage dacceptation initial. Longueur dun palier Un paramtre borne le nombre dessais (itrations) par palier Un autre paramtre borne le nombre changements (mouvements) pour le dbut de la recherche Critre darrt Un compteur sert dterminer si lalgorithme stagne. Le compteur est fix zro au dbut La recherche sarrte quand le compteur atteint un certain seuil. A la fin dun palier, le compteur est - incrment si le pourcentage dacceptation est infrieur un seuil. - remis zro si la qualit de la meilleure solution a volu au cours du palier
Le recuit simul 16
INF6953
Implmentation du recuit simul
Quand on utilise le recuit simul avec des paliers et que la fonction de cot prend des valeurs entires, on peut utiliser un tableau qui mmorise la probabilit dacceptation associe chaque valeur de .. Limplmentation naturelle du recuit simul consiste engendrer un mouvement, puis appliquer le critre de Metropolis. Une implmentation quivalente (en termes de configurations engendres) est le recuit sans rejet (Rejectless Annealing). Il consiste calculer la probabilit de chaque mouvement, puis appliquer la roulette biaise.
INF6953
Le recuit simul
17
Le recuit simul : conclusions
Mthode importante historiquement Facile implmenter Possde des proprits de convergence intressantes mais de peu dutilit en pratique
INF6953
Le recuit simul
18
Algorithmes dacceptation avec seuil
Les algorithmes dacceptation avec seuil constituent une variante dterministe du recuit simul. La fonction CritMetropolis (, T) est remplace par un critre dterministe. fonction AcceptationSeuil (, ) Si max renvoyer VRAI Sinon renvoyer FAUX
INF6953
Le recuit simul
19
