Recuit Simulé
Recuit Simulé
Recuit Simulé
Recherche Opérationnelle
2 Algorithme
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.
Début 1953
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
7
Diapositive 7
M1 MOUAD; 15/05/2017
Première résultat
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:
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 :
source : Université des Sciences et de la Technologie d’Oran - BENDAHOUA Sarah – thèse de Master2 RFIA
13
Algorithme du recuit simulé
2- Génération d’une
5- Décroissance de T solution aléatoire
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 */
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
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
La température finale
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
– 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é.
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
23
Problème d’ordonnancement de type JobShop
Déroulement de l’algorithme
Initialisation :
So = J3, J1, J4, J2
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
Sbest = S1
Fbest = F1
25
Problème d’ordonnancement de type JobShop
Déroulement de l’algorithme
2éme itération:
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:
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
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
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
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 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 :
Variable de décision :
1 si la tache j est exécutée par le processeur i
Xij = 0 sinon
Fonction Objectif :
36
Problème d’ordonnancement multiprocesseur
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.
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
41
Problème de Placement de composants
Formalisation
42
Problème de Placement de composants
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?