Définitions

Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile pour lesquels on ne connaît pas de méthode classique plus efficace.

Les principales caractéristiques des métaheuristiques sont les suivantes :

• Ce sont des stratégies qui permettent de guider la recherche d’une solution optimale.
• Le but visé par les métaheuristiques est d’explorer l’espace de recherche efficacement afin de déterminer des solutions (presque) optimales.
• Les techniques qui constituent des algorithmes de type métaheuristique vont de la simple procédure de recherche locale à des processus d’apprentissage complexes.
• Les métaheuristiques sont en général non-déterministes et ne donnent aucune garantie d’optimalité.
• Les métaheuristiques peuvent contenir des mécanismes qui permettent d’éviter d’être bloqué dans des régions de l’espace de recherche.
• Les concepts de base des métaheuristiques peuvent être décrits de manière abstraite, sans faire appel à un probléme spécifique.
• Les métaheuristiques peuvent faire appel à des heuristiques qui tiennent compte de la spécificité du problème traité, mais ces heuristiques sont contrôlées par une stratégie de niveau supérieur.
• Les métaheuristiques peuvent faire usage de l’expérience accumulée durant la recherche de l’optimum, pour mieux guider la suite du processus de recherche.

On peut classer les métaheuristiques en deux catégories :

• Les méthodes de trajectoire ;

Elles manipulent une seule solution à la fois et tentent itérativement d’améliorer cette solution. Elles construisent une trajectoire dans l’espace des solutions en tentant de se diriger vers des solutions optimales.

Les principales méthodes de trajectoire sont :

• • La recherche locale
  • Le recuit simulé
  • La recherche tabou
  • La recherche à voisinages variables
• Les méthodes basées sur une population.

Avec ce type de méthodes, on dispose en tout temps d’une base de plusieurs solutions appelée population. L’exemple le plus connu est celui des algorithmes génétiques.

Recuit Simulé

Le recuit simulé est l’utilisation pour la résolution de problèmes d’optimisation combinatoire, des expériences réalisées par Metropolis et Al. dans les années 50 pour simuler l’évolution du processus de recuit physique (un processus utilisé en métallurgie pour améliorer la qualité d’un solide)

Recherche à voisinages variables

La Recherche à voisinage variable (RVV) est une métaheuristique récente pour la résolution de problèmes d’optimisation combinatoire et globale, dont l’idée de base est le changement systématique de voisinage au sein d’une recherche locale.

Des applications de cette métaheuristique comprennent la résolution approchée d’un ensemble de problèmes d’optimisation, des manières d’accélérer les algorithmes exacts et d’analyser le processus de résolution des heuristiques ainsi qu’un système automatique de découverte de conjectures en théorie des graphes.

L’heuristique RVV utilise les constats suivants :

• Un minimum local par rapport à un voisinage n’en est pas nécessairement un par rapport à un autre

• Un minimum global est un minimum local par rapport à tous les voisinages possibles

• Pour de nombreux problèmes, les minimaux locaux par rapport à un ou à plusieurs voisinages sont relativement proches les uns des autres.

Recherche avec tabou

La recherche avec tabou est une méthode heuristique de recherche locale utilisée pour résoudre des problèmes complexes et/ou de très grande taille. Son principe de base est de poursuivre la recherche de solutions même lorsqu’un optimum local est rencontré et ce, en permettant des déplacements qui n’améliorent pas la solution en utilisant le principe de mémoire pour éviter les retours en arrière (mouvements cycliques)

Algorithmes génétiques

Les Algorithmes Génétiques sont basés sur la théorie de l’évolution de Darwin. Ils consistent à faire évoluer une population de dispositifs à l’aide de différents opérateurs : sélection, croisements, mutations. Ils sont en particulier utilisés pour les problèmes d’optimisation comportant de nombreux paramètres et des objectifs multiples.