4.5.2.
Applications
Les métas- heuristiques sont souvent inspirées
par des systèmes naturels, qu'ils soient pris en physique (les
méthodes de voisinage comme le recuit simulé et la
recherche tabou), en biologie de l'évolution (les algorithmes
évolutifs comme les algorithmes génétiques et les
stratégies d'évolution) ou encore en étiologie (les
algorithmes de colonies de fourmis).
4.5.2.1. Méta- heuristique
à recuit simulé
La méthode de recuit simulé s'inspire du
processus de recuit physique [23,24]. Ce processus utilisé en
métallurgie pour améliorer la qualité d'un solide cherche
un état d'énergie minimale qui correspond à une structure
stable du solide. Les origines du recuit simulé remontent aux
expériences réalisées par Metropolis et al dans les
années 50 pour simuler l'évolution d'un tel processus de recuit
physique. Metropolis et al utilisent une méthode stochastique pour
générer une suite d'états successifs du système en
partant d'un état initial donné. Tout nouvel état est
obtenu en faisant subir un déplacement (une perturbation)
aléatoire à un atome quelconque.
L'utilisation d'un tel processus du recuit simulé pour
résoudre des problèmes d'optimisation combinatoire a
été reportée dans. Le recuit simulé peut être
vu comme une version étendue de la méthode de descente. Le
processus du recuit simulé répète une procédure
itérative qui cherche des configurations de coût plus faible tout
en acceptant de manière contrôlée des configurations qui
dégradent la fonction de coût. A chaque nouvelle itération,
un voisin de la configuration courante est
généré de manière aléatoire. Selon les cas,
ce voisin sera soit retenu pour remplacer celle-ci, soit rejeté. Si ce
voisin est de performance supérieure ou égale à celle de
la configuration courante, il est systématiquement retenu. Dans le cas
contraire, il est accepté avec une probabilité qui dépend
de deux facteurs : d'une part l'importance de la dégradation (les
dégradations plus faibles sont plus facilement acceptées),
d'autre part un paramètre de contrôle, la température (une
température élevée correspond à une
probabilité plus grande d'accepter des dégradations). La
température est contrôlée par une fonction
décroissante qui définit un schéma de refroidissement. Les
deux paramètres de la méthode définissent la longueur des
paliers et la fonction permettant de calculer la suite décroissante des
températures. En pratique, l'algorithme s'arrête et retourne la
meilleure configuration trouvée lorsque aucune configuration voisine n'a
été acceptée pendant un certain nombre d'itérations
à une température ou lorsque la température atteint la
valeur zéro.
La performance du recuit simulé dépend largement
du schéma de refroidissement utilisé. De nombreux schémas
théoriques et pratiques ont été proposés. De
manière générale, les schémas de refroidissement
connus peuvent être classés en trois catégories :
- réduction par paliers : chaque température est
maintenue égale pendant un certain nombre d'itérations, et
décroît ainsi par paliers.
- réduction continue: la température est
modifiée à chaque itération.
- réduction non- monotone: la température
décroît à chaque itération avec des augmentations
occasionnelles.
Il existe des schémas qui garantissent la convergence
asymptotique du recuit simulé. En pratique, on utilise des
schémas relativement simples même s'ils ne garantissent pas la
convergence de l'algorithme vers une solution optimale.
Le recuit simulé constitue, parmi les méthodes
de voisinage, l'une des plus anciennes et des plus populaires. Il a acquis son
succès essentiellement grâce à des résultats
pratiques obtenus sur de nombreux problèmes NP- difficiles. La preuve de
convergence a également contribué à cette
popularité, bien que cette preuve n'ait pas de portée en
pratique.
| 
