Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Meta Heuristique
Filière : MP
EL BOUNI FATIMA-ZAHRA
elbouni97@[Link]
Classes préparatoires aux grandes écoles
Lycée Moulay Ali Cherif-ERRACHIDIA
December 16, 2024
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 1 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
1 Introduction
2 Définition et Concepts de base
3 Algorithme de Recuit Simulé
4 Exemple d’application
Problème du voyageur de commerce
Implémentation de recuit simulé appliqué au TSP en Python
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 2 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
1 Introduction
2 Définition et Concepts de base
3 Algorithme de Recuit Simulé
4 Exemple d’application
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 3 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Introduction
Les problèmes NP-difficiles sont des problèmes d’optimisation complexes, car
aucun algorithme exact n’est connu pour les résoudre en temps polynomial.
Ces problèmes se manifestent dans des domaines variés, tels que la planification
d’itinéraires, la conception de réseaux ou encore le placement de composants
électroniques...
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 4 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Introduction
Dans les approches étudiées jusqu’ici, chacune présente des forces, mais
également des limites :
Algorithmes gloutons : Bien que rapides et simples à implémenter, ils ne
garantissent pas toujours une solution optimale.
Programmation dynamique : Elle est efficace pour certains problèmes, mais peut
entraîner une consommation élevée de mémoire et des temps de calcul importants
lorsque le nombre de sous-problèmes devient très grand (problème d’explosion
combinatoire).
Ces limites justifient la recherche d’autres solutions approchées comme les
heuristiques qui sont des solutions de bonne qualité obtenues en un temps
raisonnable, même si elles ne sont pas garanties comme optimales.
Les heuristiques sont des méthodes basées sur des règles simples et empiriques,
souvent issues de l’expérience ou d’analogies avec des problèmes similaires.
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 5 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
1 Introduction
2 Définition et Concepts de base
3 Algorithme de Recuit Simulé
4 Exemple d’application
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 6 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Définition et Concepts de base
Définition
Les méta-heuristiques sont des algorithmes d’optimisation avancés et souvent
stochastiques, qui combinent différentes approches heuristiques pour mieux explorer
l’espace des solutions.
En plus de rechercher des solutions de haute qualité, les méta-heuristiques visent à
éviter les minima locaux et à s’approcher de l’optimum global, en équilibrant
exploration et exploitation.
Il existes des méthodes peuvent être appliquées à une large gamme de problèmes
complexes, avec une flexibilité élevée telles que :
Le recuit simulé.
Les algorithmes génétiques.
Colonie de fourmis (Ant Colony Optimization)...
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 7 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Définition et Concepts de base
Formalisation
Soit S un ensemble de solutions à un problème d’optimisation et soit f une
fonction qui mesure la qualité f (s) de chaque solution s ∈ S.
Le but des méta-heuristiques est de déterminer une solution s ∈ S de valeur f (s)
minimale. En d’autres termes, le problème est de déterminer la valeur suivante :
min f (s)
(s∈S)
Un voisinage est une fonction N qui associe un sous-ensemble de S à tout solution
s ∈ S.
Une solution s′ ∈ N(s) est dite voisine de s.
Une solution s ∈ S est un minimum local relativement à N si f (s) ≤ f (s′ ) pour tout
s′ ∈ N(s), alors qu’il s’agit d’un minimum global si f (s) ≤ f (s′ ) pour tout s ∈ S.
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 8 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
1 Introduction
2 Définition et Concepts de base
3 Algorithme de Recuit Simulé
4 Exemple d’application
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 9 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Recuit Simulé
La méthode de de Recuit Simulé est inventée en 1983 par S. Kirkpatrick et ses
collègues chez (IBM).
Son principe repose sur la technique expérimentale du recuit(réchauffage),
employée par les métallurgistes pour obtenir un état solide "bien ordonné",
d’énergie minimale, en évitant les structures métastables.
Cette technique consiste à porter le matériau à haute température, puis à abaisser
lentement celle-ci.
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 10 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Recuit Simulé
Principe :
Initialisation : Commence par un état aléatoire du système avec une énergie
initiale et une température élevée T .
Processus Itératif : A chaque itération, une petite modification est apportée à l’état
actuel, générant un nouvel état:
Si le nouvel état a une énergie inférieure (meilleure solution), il est accepté (p = 1).
Si l’énergie est supérieure (solution de moindre qualité), il peut être accepté avec une
∆f (x)
probabilité p = e− T .
Refroidissement : La température est progressivement diminuée, réduisant la
probabilité d’accepter des solutions de moins bonne qualité.
Critère d’Acceptation : La probabilité diminue au fur et à mesure du
refroidissement. Cela permet d’éviter de rester bloqué dans un minimum local,
favorisant ainsi l’exploration de l’espace des solutions de manière plus exhaustive.
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 11 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Recuit Simulé
Pseudo-code
i := i0 (* Solution initiale *)
T := T0 (* Température initiale *)
Tant que la condition d’arrêt n’est pas vérifiée
Tant que la fin du palier n’est pas atteinte
Générer une nouvelle solution j et Calculer ∆ = e(j) − e(i)
Si ∆ < 0 alors
i := j
Sinon
i := j avec une probabilité p = exp − ∆
¡ ¢
T
Fin si
Fin tant que
Abaisser T
Fin tant que
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 12 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Implémentation de l’algorithme en Python
1 import math
2 import random
3 def R_S (F , int_solv , int_tmp , cool_rate , stop_tmp , max_iter ) :
4 i = int_solv
5 T = int_tmp
6 while T > stop_tmp :
7 for _ in range ( max_iter ) :
8 j = i + random . uniform ( - 1 , 1)
9 delta = F ( j ) - F ( i )
10 if delta < 0:
11 i = j
12 else :
13 if random . random () < math . exp ( - delta / T ) :
14 i = j
15 T *= cool_rate
16 return i
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 13 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Exemple
On souhaite trouver le minimum global de la fonction :
1 |x−0.5| 2 |x+0.5|
f (x) = − e− 0.5 − e− 0.2 , x ∈ R
3 3
On utilisant l’algorithme recuit simulé sur l’espace d’états E discret défini par :
E = {xk }1≤k≤N . Où N ≥ 2 est un entier, et x1 < x2 < ... < xN est une suite croissante de réels
régulièrement espacés sur l’intervalle [−2, 2] avec x1 = −2 et xN = 2.
Le graphique ci-dessus illustre la convergence de l’algorithme du recuit simulé vers le
minimum global.
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 14 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
1 Introduction
2 Définition et Concepts de base
3 Algorithme de Recuit Simulé
4 Exemple d’application
Problème du voyageur de commerce
Implémentation de recuit simulé appliqué au TSP en Python
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 15 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
1 Introduction
2 Définition et Concepts de base
3 Algorithme de Recuit Simulé
4 Exemple d’application
Problème du voyageur de commerce
Implémentation de recuit simulé appliqué au TSP en Python
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 16 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Problème du voyageur de commerce
Le problème du voyageur de commerce (TSP) consiste à trouver le plus court
itinéraire permettant à un vendeur de visiter un ensemble de villes, en partant
d’une ville donnée, en visitant chaque ville une seule fois, et en revenant à la ville
de départ.
Formulation du problème : Soit un ensemble de n villes V = {v1 , v2 , . . . , vn } et une
matrice de distances D où D(i, j) représente la distance entre la ville vi et la ville vj .
L’objectif est de trouver un itinéraire C = (v1 , v2 , . . . , vn , v1 ) qui minimise la distance
totale parcourue :
n−1
X
Distance totale = D(vi , vi+1 ) + D(vn , v1 )
i=1
où vn+1 = v1 .
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 17 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Recuit Simulé appliqué au TSP
Représentation de la solution :
Une solution au TSP peut être représentée par une permutation des villes
π = (π1 , π2 , . . . , πn ), où πi est l’indice de la ville visitée à la i-ème position.
Énergie (coût) de la solution :
Le coût de la solution est la distance totale parcourue par le vendeur.
Il s’agit de la somme des distances entre chaque paire de villes successives dans la
permutation, avec le retour à la ville de départ.
n−1
D(πi , πi+1 ) + D(πn , π1 )
X
E(π) =
i=1
Où D(i, j) est la distance entre les villes vi et vj .
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 18 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Recuit Simulé appliqué au TSP
Transition
À chaque itération, on génère une solution voisine en modifiant légèrement la
permutation actuelle.
Une façon courante de faire cela est d’échanger deux villes dans la permutation.
Critère d’acceptation
Si la nouvelle solution est meilleure (coût réduit), on l’accepte toujours.
Si elle est moins bonne (coût plus élevé), elle est acceptée avec une probabilité
donnée par la fonction de Boltzmann :
∆E
µ ¶
P(∆E) = exp −
T
Où ∆E est l’augmentation du coût et T est la température actuelle.
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 19 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
1 Introduction
2 Définition et Concepts de base
3 Algorithme de Recuit Simulé
4 Exemple d’application
Problème du voyageur de commerce
Implémentation de recuit simulé appliqué au TSP en Python
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 20 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Implémentation de recuit simulé appliqué au TSP en Python
Calcul de la distance :
1 def euc_dis ( v1 , v2 ) :
2 return math . sqrt (( v1 [0] - v2 [0]) **2+( v1 [1] - v2 [1]) **2)
1 def dis_mat ( villes ) :
2 n = len ( villes )
3 dist_matrix = [[0] * n for _ in range ( n ) ]
4 for i in range ( n ) :
5 for j in range ( n ) :
6 if i != j :
7 dist_matrix [ i ][ j ] = euc_dis ( villes [ i ] ,
villes [ j ])
8 return dist_matrix
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 21 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Implémentation de recuit simulé appliqué au TSP en Python
Calcul de la distance totale :
1 def total_dist ( permutation , dis_mat ) :
2 tot_dis = 0
3 for i in range ( len ( permutation ) - 1) :
4 tot_dis += dis_mat [ permutation [ i ]][ permutation [ i + 1]]
5 tot_dis += dis_mat [ permutation [ - 1]][ permutation [0]]
6 return tot_dis
La fonction qui permet de proposer un trajet voisin :
1 def Voisin ( permutation ) :
2 voisin = permutation [:]
3 i , j = random . sample ( range ( len ( permutation ) ) , 2)
4 voisin [ i ] , voisin [ j ] = voisin [ j ] , voisin [ i ]
5 return voisin
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 22 / 23
Introduction Définition et Concepts de base Algorithme de Recuit Simulé Exemple d’application
Implémentation de recuit simulé appliqué au TSP en Python
La fonction recuit simulé pour TSP:
1 def S_R_TSP ( d_mat , init_tmp , cool_rate , max_itr ) :
2 n = len ( d_mat ) , perm = list ( range ( n ) )
3 random . shuffle ( perm )
4 cout = total_dist ( perm , d_mat ) , tmp = init_tmp
5 P = perm [:] , C = cout
6 while tmp > 1 e - 3:
7 for _ in range ( max_itr ) :
8 v_p = Voisin ( perm ) , v_c = total_dist ( v_p , d_mat )
9 dt_ct = v_c - cout
10 if dt_ct <0 or random . random () < math . exp ( - dt_ct / tmp ) :
11 perm = v_p , cout = v_c
12 if cout < C :
13 P = perm [:] , C = cout
14 tmp *= cool_rate
15 return P , C
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Meta Heuristique December 16, 2024 23 / 23
