Recuit Simulé

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 46

RECUIT SIMULE

Recherche Opérationnelle

Encadré par Mme Lebbar


Plan :
1 Présentation Générale

2 Algorithme

Applications aux problèmes


3 classiques et industriels

2
Présentation
générale
Introduction
Le recuit simulé est une méthode empirique (métaheuristique) inspirée
d'un processus utilisé en métallurgie. On alterne dans cette dernière des
cycles de refroidissement lent et de réchauffage (recuit) qui ont pour effet
de minimiser l'énergie du matériau. Cette méthode est transposée
en optimisation pour trouver les extrema d'une fonction.

Source : Cours de recuit simulé – Mr Moez


HAMMAMI 4
Historique

Début 1953

Expériences réalisées par


Metropolis pour simuler l'évolution
de ce processus de recuit 1983 Mise au point par la société
physique. 1985 IBM
L’utilisation pour la résolution des
problèmes d'optimisation
History 3 2004 combinatoire.
(Kirkpatrick83,Cerny85)
Le recuit simulé est la première
métaheuristique qui a été
proposée.
5
Origine: Recuit thermique

Diminution progressive de la
Partir d’une haute température Etat d’énergie minimale
température
 Chauffer le matériau et le  Refroidissement lent de la  Chercher à atteindre un état
porter à l’état liquide (énergie température en marquant d'énergie minimale qui
élevée). des paliers de température correspond à une structure
de durée suffisante. stable du métal.

6
M1

Origine: Recuit thermique

L’algorithme s’appuie sur 2


résultats de la physique
statistique Boltzmann.

7
Diapositive 7

M1 MOUAD; 15/05/2017
Première résultat

À Température élevée, P(E) tend vers 1


pour
tous les états d’énergie.

La probabilité d’accepter un état à énergie


élevée est faible a faible Température.

Source : Thèse optimisation du traitement de l’ordre de fabrication


Dans l’industrie textile
8
Deuxième résultat

Si le nombre d’itérations est


 suffisamment long, le système aboutit
à l’équilibre thermodynamique pour la
température T:
il aboutit à la distribution de Boltzmann.

Source: Métaheuristiques pour l'optimisation difficile,


édition Eyrolles
9
Recuit thermique et Recuit simulé

Recuit thermique:
 Les états du solide.
 Les énergies des états.
 L’état à énergie minimale.
 Le refroidissement rapide.

Recuit simulé:
 Les solutions réalisables.
 Les valeurs de la fonction objectif calculées sur ces solutions.
 Solution minimale du problème.
 Recherche locale.
Source : Thèse optimisation du traitement de l’ordre de fabrication
Dans l’industrie textile
10
Algorithme du
recuit simulé
Algorithme du recuit simulé

Critère du Métropolis:

Dans l'algorithme de Metropolis, on part d'une configuration donnée, et on


lui fait subir une modification aléatoire. Si cette modification fait diminuer
la fonction objectif (ou énergie du système), elle est directement acceptée
; Sinon, elle n’est pas acceptée qu’avec une probabilité égale à
𝒆𝒙𝒑( ∆𝑬⁄ )[avec
𝑻 E : énergie, et T : température], cette règle est appelé
critère de Metropolis.

source : Université des Sciences et de la Technologie d’Oran - BENDAHOUA Sarah – thèse de Master2 RFIA

12
Algorithme du recuit simulé

Critère du Métropolis :

Le recuit simulé applique itérativement l’algorithme de Metropolis,


pour engendrer une séquence de configurations qui tendent vers
l'équilibre thermodynamique.

source : Université des Sciences et de la Technologie d’Oran - BENDAHOUA Sarah – thèse de Master2 RFIA

13
Algorithme du recuit simulé

4- Traitement des cas 3- Calcul de la variation

2- Génération d’une
5- Décroissance de T solution aléatoire

1- Choix des paramètres


6- L’arrêt de l’algorithme initiaux(s0 , T0)

Algorithme du recuit simulé

14
Début Pseudo code
Engendrer la solution initiale s(0)
Mini = s(0)
Répéter
Choix de s(i) є V(s(i))
Calcul de ∆d = f(s(i)) - f(Mini)
Si ∆d < 0
Alors Mini = s(i) /* idem algorithme de la descente */

Sinon tirer p dans [0,1] suivant une distribution uniforme


Si p ≤ e (-∆d/T)
Alors Mini = s(i) /* solution moins bonne */

Sinon s(i) est rejetée


T = g(T) /* avec g décroissante, par exemple T=0.9995 . T */
Jusqu’à ce que T proche de 0
Fin
source : Université des Sciences et de la Technologie d’Oran - BENDAHOUA Sarah – thèse de Master2 RFIA
15
Algorithme du recuit simulé

Solution initiale

La solution initiale peut être prise au hasard dans l'espace des solutions
possibles. À cette solution correspond une énergie initiale . Cette énergie
est calculée en fonction du critère que l'on cherche à minimiser.

16
Algorithme du recuit simulé

La température initiale

La température est généralement choisie élevé. On peut utiliser la démarche suivante:

Faire perturber le système 100 fois au hazard calculer la moyenne de la variation de E <∆E>
Choisir le taux d’acceptation initial 𝛉ₒ selon la qualité supposée de la configuration initiale : 50% si
la qualité est médiocre

20% si la qualité est bonne Tₒ = -<∆E>/ log(𝛉ₒ)

Source : Cours de recuit simulé – Mr Moez


HAMMAMI 17
Algorithme du recuit simulé

La température finale

Généralement, On s’arrête quand T atteint un seuil fixe ε, proche de 0,


mais pratiquement, on n’atteint pas le zéro.

18
La décroissance de la température

Source : thèse de doctorat Algorithmes Heuristiques et Evolutionnistes : Application à la Résolution du Problème de Placement de Formes
Irrégulières.
Algorithme du recuit simulé

La température

Le paramètre T (température) est un réel positif.

La température permet de contrôler l’acceptation des dégradations :

– Si T est grand, les dégradations sont acceptées avec une probabilité plus grande.

– A la limite, quand T tend vers l’infini, tout voisin est systématiquement accepté.

– Inversement, pour T=0, une dégradation n’est jamais acceptée.

La fonction qui spécifie l’évolution de la température est appelée le schéma de refroidissement.

20
Applications
Problème d’ordonnancement
de type Job Shop
Le problème d’ordonnancement de Job Shop consiste à réaliser un
ensemble de taches sur un ensemble de ressources en cherchant
d’atteindre certains objectifs.

22
Problème d’ordonnancement de type JobShop

On considère le calendrier suivant :


jobs 1 2 3 4
Énoncé du problème pj
dj
9
10
9
8
12
5
3
28
wj 14 12 1 12

- Appliquons l’algorithme du recuit simulé à ce problème en commençant par


3, 1, 4, 2 comme séquence initiale.
- Voisinage: toute séquence pouvant être obtenue par permutation de deux
jobs consécutifs. On Choisit aléatoirement un voisin parmi le voisinage.
- Diminution linéaire de la température avec comme paramètre : (t) = 0.9
- La température initiale : t0 = 0.9
- On utilise ses nombres choisit de façon aléatoire: 0.17, 0.91, ...

23
Problème d’ordonnancement de type JobShop

Déroulement de l’algorithme

Initialisation :
So = J3, J1, J4, J2

Fo = wjTj = 1·7 + 14·11 + 12·0+ 12 ·25 = 461

t0 = 0.9

Sbest = So

Fbest = Fo

24
Problème d’ordonnancement de type JobShop

Déroulement de l’algorithme
1er itération:
S1 = J1, J3, J4, J2

F1 = 316 < Fbest

Sbest = S1

Fbest = F1

t = 0.9 · 0.9 = 0.81

25
Problème d’ordonnancement de type JobShop

Déroulement de l’algorithme
2éme itération:

S2 = J1, J3, J2, J4

F2 = 340 > Fbest

340 316

P2 = 0.17 > e 0.81
= 1.35*10-13

t = 0.729

26
Problème d’ordonnancement de type JobShop

Déroulement de l’algorithme
3éme itération:

S3 = J1, J4, J3, J2


F3 = 319 > Fbest

340 316

P3 = 0.015 < e 0.81
= 0.016

Sbest= S3
Fbest = F3
t = 0.6561

27
Problème de voyageur de
commerce

28
Problème de voyageur de commerce

Énoncé du problème

Une société de distribution implanté à Rabat désire procéder à la livraison d’un ensemble
de commandes effectuées par ses clients à travers les différentes villes du Royaume.
Inhabituellement la société décide d’engager un seul moyen de transport pour satisfaire les
besoins de tous ses clients.

Donc quel est le meilleur trajet que le chauffeur doit suivre afin de livrer tous les clients et
revenir à la société en parcourant le plus court chemin possible.

29
AGADIR
AL HOCEIMA 1091
BENI MELLAL
Matrice des distances
467 564

CASABLANCA 511 536 210


DAKHLA 1173 2264 1640 1684

EL JADIDA 417 632 271 99 1590


ERRACHIDIA 681 616 375 545 1854 506
ESSAOUIRA 173 887 370 351 1346 252 745

FES 756 275 289 289 1920 388 364 640


FIGUIG 1076 669 770 920 2249 1001 395 1081 719
KENITRA 596 435 122 131 1769 360 292 499 160 687

KHENIFRA 642 400 300 299 1815 230 480 482 166 875 254
KHOURIBGA 507 614 90 120 1680 181 425 410 333 820 169 245

LAAYOUNE 649 1740 1116 1160 524 1066 1330 822 1396 1725 1245 1291 1156
LAGOUIRA 1645 2736 2112 2156 472 2062 2326 1818 2392 2721 2241 2287 2152 996
MARRAKECH 273 758 194 238 1446 197 510 176 483 905 234 369 234 922 1918

MEKNES 740 335 278 229 1913 328 346 580 60 741 153 130 322 1389 2389 467
NADOR 1095 175 628 628 2260 727 510 9979 339 515 323 497 672 1736 2732 822 399
OUARZAZATE 375 922 398 442 1548 399 306 380 687 701 527 573 438 1024 2020 204 652 816

OUJDA 1099 293 632 632 2272 731 514 983 343 326 503 507 676 1748 2744 826 403 104 820
RABAT 602 445 260 91 1775 190 482 442 198 877 40 289 205 1251 2247 321 138 535 528 541

SAFI 294 792 351 256 1467 157 683 129 545 1078 480 387 328 943 1939 157 486 884 361 888 347
SETTAT 439 608 157 72 1612 117 512 296 361 907 238 203 69 1088 2084 166 292 969 370 698 157 201
TANGER 880 323 538 369 2053 468 608 720 303 988 620 238 483 1529 2525 598 267 1086 811 609 278 625 433

TAN-TAN 331 1422 798 842 842 748 1012 504 1087 1407 927 973 838 318 1314 504 1071 1426 705 1430 933 625 770 1211
TAZA 876 173 409 409 2049 508 760 120 599 286 453 280 1525 2521 603 180 219 790 223 318 665 474 423 1217 1420
TETOUAN 892 278 536 385 2065 484 604 736 281 931 411 254 499 1541 2537 675 258 437 280 555 294 641 450 57 1223 370
BENI MELLAL

CASABLANCA
AL HOCEIMA

MARRAKECH

RABAT
LAAYOUNE

MEKNES
EL JADIDA
DAKHLA

KHOURIBGA

LAGOUIRA
FIGUIG

TAN-TAN

TETOUAN
SETTAT
SAFI
OUARZAZATE
FES

TANGER
AGADIR

NADOR
KENITRA

OUJDA

TAZA
ERRACHIDIA

ESSAOUIRA

KHENIFRA

30
Problème de voyageur de commerce

Formalisatio
n
N : nombre de villes ( N=27 ) ;
i Є {1,2, … , 27} indice des villes ;
V : la liste des villes ;
D : matrice des distances inter-villes
T : un trajet

Donc il s’agit de minimiser la fonction : Z = ∑ D[Ti,Ti+1]

31
Problème de voyageur de commerce

Paramétrage de l’algorithme

Trajet initiale : To Utilisation d’un algorithme Gloutan pour trouver un trajet initiale

Voisinage : un voisinage s’obtient par permutation aléatoire de deux villes au sein du trajet

La température initiale : ti =100

La température finale : tf=5

Schéma de refroidissement : Refroidissement linéaire d’un facteur de α : tk+1 = α tk

avec α Є [0,1] (on prend α = 0.9 ) ;

Critère d’arrêt : soit tf atteint soit stabilité de la solution après un certain temps

32
Problème de voyageur de commerce

Implémentation

33
Problème
d’ordonnancement
multiprocesseur

34
Problème d’ordonnancement multiprocesseur

Énoncé du problème

Le problème d’ordonnancement multiprocesseur consiste à trouver une distribution


optimale de tâches sur un ensemble de processeurs. Chaque processeur fonctionne
indépendamment, mais chacun ne peut exécuter qu'une tâche à la fois. Nous appelons une
cession de tous les emplois de processeurs disponibles un « calendrier ».

Le but du problème est de déterminer le calendrier le plus court pour le jeu de tâches.

35
Problème d’ordonnancement multiprocesseur

Données :

i : indice des processeurs, i Є {1, … , nP} ;


Formalisatio j : indice des tâches, j Є {1, … , nT} ;
n dij : temps d’exécution de la tâche j par le processeur i;

D : matrice des temps d’exécution , D = {dij};

Variable de décision :
1 si la tache j est exécutée par le processeur i
Xij = 0 sinon

Fonction Objectif :

Min Z = max ( ∑ Xij * dij )


i Є {1,.., nP} j Є {1,.., nT}

36
Problème d’ordonnancement multiprocesseur

Adaptation au recuit simulé

L’énergie du système : c’est la fonction a minimiser : max ( ∑ Xij * dij )

Voisinage : enlever une tache d’un processeur et l’affecter à un autre

La température initiale : To =100

Critère d’arrêt : Stabilisation du système

Schéma de refroidissement : Refroidissement linéaire d’un facteur de α : Tk+1 = α Tk

avec α Є [0,1] (on prend α = 0.99 ) ;

37
Placement de
composants
Ce problème est aussi appelé Placement-Routage (Place and Route).

Travaux Pratiques sur les Méta-heuristiques pour l’optimisation difficile. PATRICK SIARRY
38
Problème de Placement de composants

Énoncé
L’intégration à très grande échelle (VLSI - Very-Large-Scale Integration) est une
technologie de circuit intégré dont la densité d’intégration permet de supporter plus de
100 000 composants électroniques sur une même puce.

Le problème de placement de composants électronique dans un circuit est l’un


des principaux problèmes rencontres dans cette technologie d’intégration.

Dans ce problème on doit positionner les composants électroniques dans une


grille de positions prédéterminées de façon à minimiser la quantité de fils nécessaire
pour effectuer l’interconnexion des composants du circuit.

39
Problème de Placement de composants

Énoncé
C’est un problème qui a beaucoup de solutions mais qui reste ouvert, parmi
ces objectifs :
 la minimisation des longueurs de connexions.
 la minimisation de la chaleur dissipée par les composants électroniques.
 La minimisation de temps de calcul.
 Réduire le coût d’interconnexions entre les composants.
 Garantir la « routabilité ».
 Atteindre la plus grande densité possible.
 Minimiser la consommation.

40
Problème de Placement de composants

Formalisation

l’estimation des distances de fils dans les circuits électroniques utilise la


géométrie Manhattan

À chaque composant i on associe un couple de coordonnées (xi,yi), la distance


Manhattan est calculée comme suite : d(u1,u2)=|x1-x2|+|y1-y2|

Où u1 et u2 sont deux composants électroniques.

41
Problème de Placement de composants

Formalisation

Fonction à minimiser : Cost = ∑ ∑ d(ui,uj)


Solution initiale : génération d’un placement initial aléatoire
Voisinage : La permutation des positions de deux composants.
Caractéristiques du recuit :
 Tinit : 20 x l'écart-type du coût après n échanges
 Pour chaque T, évaluer 10.n échanges
 Règle d'évolution de T : Tnew = α * Told ; (α=0,9)
 Fin quand T< 0.005 x Cost

42
Problème de Placement de composants

Simulation du comportement de l’algorithme

43
SWOT Analysis

Strengths Weaknesses
• Solution de bonne qualité dans un temps
compétitif
• Facile à implémenter.
S W •

Difficulté du choix des différents paramètres
L'impossibilité de savoir si la solution trouvée
est optimale.
• Utilisable dans la plupart des problèmes • Coûteux en temps de calcul.
d'optimisation.
Opportunities Threats
• Parallélisassions du recuit simulé;
• Hybridation des algorithmes;.
O T • non-convergence en cas de mauvais choix des
paramètres ;
• La concurrence imposée par d’autres méta-
heuristique : l’algorithme génétique , la colonie
de fourmis…

44
Thank you!
Any questions?

Vous aimerez peut-être aussi