Métaheuristiques

Les métaheuristiques sont des méthodes d’optimisation puissantes et flexibles, utilisées pour résoudre des problèmes complexes où les méthodes exactes sont inefficaces. Cet article s’adresse aux étudiants en informatique, mathématiques appliquées, recherche opérationnelle ou ingénierie, qui souhaitent comprendre les bases des métaheuristiques, leur fonctionnement, leurs classifications et quelques exemples importants.

La question

Le travail porte sur la résolution de problèmes d’optimisation, c’est-à-dire la recherche d’une solution s dans un ensemble S qui minimise une fonction objectif f(s). Trouver la solution optimale exacte est souvent impossible ou trop coûteux en temps de calcul, surtout pour des problèmes combinatoires complexes. Les métaheuristiques proposent donc une approche alternative : trouver rapidement des solutions de bonne qualité, proches de l’optimum, sans garantie absolue d’optimalité. Le défi est de concevoir des stratégies capables d’explorer efficacement l’espace des solutions, d’éviter les pièges des minima locaux et d’exploiter l’expérience accumulée pour améliorer la recherche.

Concepts de base

Le terme « métaheuristique » vient de la combinaison de « heuristique » (du grec heuriskein, « trouver ») et du préfixe « meta », signifiant « au-delà » ou « à un niveau supérieur ». Une métaheuristique est donc une stratégie de haut niveau qui guide une heuristique plus spécifique pour explorer l’espace des solutions.

Les métaheuristiques ont plusieurs propriétés fondamentales :

• Ce sont des stratégies qui orientent la recherche vers des solutions optimales ou quasi-optimales.
• Leur but est d’explorer efficacement l’espace de recherche, souvent très vaste, pour trouver rapidement de bonnes solutions.
• Elles peuvent aller de simples recherches locales à des processus d’apprentissage complexes.
• En général, elles sont non déterministes et ne garantissent pas d’optimalité.
• Elles intègrent souvent des mécanismes pour éviter d’être bloquées dans des minima locaux.
• Leurs concepts sont abstraits et applicables à une grande variété de problèmes.
• Elles contrôlent des heuristiques spécifiques au problème traité.
• Elles peuvent utiliser l’expérience accumulée pour mieux guider la recherche.

Un problème d’optimisation se définit formellement ainsi :

min f(s)
s.c. s ∈ S

où S est l’ensemble des solutions possibles et f une fonction mesurant la qualité (ou le coût) d’une solution. Une structure de voisinage N associe à chaque solution s un sous-ensemble de solutions voisines N(s). Une solution est un minimum local si aucune solution voisine n’a une meilleure valeur, et un minimum global si aucune solution dans S n’est meilleure.

Les métaheuristiques sacrifient la garantie d’optimalité pour espérer trouver rapidement des solutions très satisfaisantes.

Approche

Plusieurs classifications des métaheuristiques existent, selon leur inspiration, leur mode de fonctionnement ou leur mémoire :

• Inspiration naturelle ou non : Certaines s’inspirent de phénomènes naturels (algorithmes génétiques, colonies de fourmis), d’autres non (méthode Tabou).
• Population ou trajectoire : Certaines manipulent une population de solutions (méthodes évolutives), d’autres une seule solution à la fois (recherche locale, trajectoire).
• Utilisation de la fonction objectif : Métaheuristiques statiques travaillent directement sur f, tandis que dynamiques modifient la fonction pour changer la topologie de l’espace de recherche.
• Nombre de voisinages : Certaines utilisent un seul voisinage, d’autres plusieurs pour éviter les minima locaux liés à un voisinage unique.
• Mémoire : Certaines n’ont pas de mémoire (processus markoviens), d’autres utilisent une mémoire à court ou long terme pour guider la recherche.
• Diversification et intensification : La diversification explore largement l’espace, l’intensification exploite les régions prometteuses. Un bon équilibre est crucial.

Méthodes de trajectoire (Recherche Locale)

La recherche locale explore l’espace des solutions en se déplaçant de solution en solution voisine, selon une structure de voisinage N et une fonction objectif f.

Méthode de descente :

1. Choisir une solution s ∈ S
2. Trouver s’ ∈ N(s) minimisant f(s’)
3. Si f(s’) < f(s), poser s := s’ et retourner à 2, sinon arrêter

Cette méthode s’arrête dès qu’un minimum local est atteint, ce qui est un inconvénient majeur.

Recuit Simulé : Pour éviter d’être bloqué dans un minimum local, cette méthode accepte parfois des solutions moins bonnes selon une probabilité dépendant d’une température T qui décroît au cours du temps.

1. Choisir une solution s ∈ S et une température initiale T
2. Tant que le critère d’arrêt n’est pas atteint :
   a. Choisir aléatoirement s’ ∈ N(s)
   b. Générer r ∈ [0,1]
   c. Si r < p(T,s,s’) alors s := s’
   d. Mettre à jour T

La fonction p(T,s,s’) est généralement la distribution de Boltzmann :

p(T,s,s’) = exp(-(f(s’) - f(s)) / T)

Ce qui signifie que les mouvements vers des solutions meilleures sont toujours acceptés, et ceux vers des solutions moins bonnes sont acceptés avec une probabilité décroissante avec la température.

La température diminue progressivement pour réduire les mouvements vers des solutions moins bonnes, favorisant ainsi la convergence.

Recherche Tabou : Cette méthode choisit toujours la meilleure solution voisine, même si elle est moins bonne que la solution actuelle, mais interdit de revenir immédiatement sur des solutions récemment visitées grâce à une liste taboue (mémoire à court terme).

1. Choisir s ∈ S, T := ∅, s* := s
2. Tant que le critère d’arrêt n’est pas atteint :
   a. Trouver s’ ∈ NT(s) minimisant f(s’)
   b. Si f(s’) < f(s*) alors s* := s’
   c. Poser s := s’ et mettre à jour T

NT(s) est l’ensemble des solutions voisines non taboues ou dont le statut tabou est levé par un critère d’aspiration (par exemple, si la solution est meilleure que la meilleure rencontrée).

La liste taboue empêche les cycles et encourage la diversification. Des variantes existent avec des listes taboues de taille variable ou réactives, ajustant la longueur de la mémoire selon le comportement de la recherche.

La Recherche Tabou peut aussi intégrer une mémoire à long terme, qui mémorise la fréquence des visites, la qualité des solutions ou l’influence des décisions, afin d’orienter la recherche de manière plus intelligente.

GRASP (Greedy Randomized Adaptive Search Procedure) : Méthode itérative combinant une phase constructive et une phase d’amélioration. La phase constructive construit une solution pas à pas en choisissant aléatoirement parmi les meilleures composantes candidates (liste RCL). La phase d’amélioration applique une méthode locale (descente, recuit simulé, recherche tabou) pour améliorer la solution.

Recherche à Voisinages Variables (RVV) : Cette méthode utilise plusieurs structures de voisinage différentes pour éviter les minima locaux spécifiques à un voisinage. Elle alterne entre ces voisinages pour diversifier la recherche et intensifier l’exploration dans des régions prometteuses.

Recherche Locale Guidée : Elle modifie dynamiquement la fonction objectif en ajoutant un terme pondéré qui pénalise les attributs des solutions déjà visitées, rendant ainsi les minima locaux précédents moins attractifs et encourageant l’exploration de nouvelles régions.

Méthodes basées sur les populations (Méthodes évolutives)

Ces méthodes font évoluer une population d’individus (solutions ou fragments de solutions) selon des règles d’adaptation et de coopération. À chaque itération, de nouveaux individus sont créés et une sélection est opérée pour constituer la population suivante.

Les caractéristiques principales sont :

• Types d’individus : Ils peuvent être des solutions complètes, des fragments ou des objets facilement transformables en solutions.
• Type d’évolution : Remplacement générationnel (population renouvelée entièrement) ou stationnaire (seulement une partie change).
• Structure de voisinage : Population non structurée (communication libre) ou structurée (communication limitée selon une topologie).
• Sources d’information : Nombre de parents pour créer un enfant, utilisation de l’historique des populations précédentes.

Ces méthodes s’inspirent souvent de la biologie (algorithmes génétiques) ou du comportement collectif (algorithmes de colonies de fourmis).

Résultats

Le travail montre que les métaheuristiques, bien que ne garantissant pas l’optimalité, permettent d’obtenir rapidement des solutions de qualité pour des problèmes complexes. Des méthodes comme le Recuit Simulé ont des garanties théoriques de convergence vers l’optimum global sous certaines conditions, mais ces conditions sont souvent trop coûteuses en pratique. Les variantes pratiques privilégient la rapidité au détriment de garanties strictes.

La Recherche Tabou, avec sa mémoire à court et long terme, améliore la capacité à échapper aux minima locaux et à diversifier la recherche. GRASP combine construction aléatoire et amélioration locale pour explorer efficacement l’espace des solutions. La Recherche à Voisinages Variables exploite la complémentarité des voisinages pour une meilleure robustesse.

Les méthodes évolutives, en manipulant une population, permettent une exploration plus large et une coopération entre solutions, ce qui peut améliorer la qualité des résultats.

Limites et questions ouvertes

Les métaheuristiques ne garantissent pas la découverte de l’optimum global, et leur performance dépend fortement des paramètres choisis (température, taille de la liste taboue, structures de voisinage, etc.). La sélection et l’adaptation de ces paramètres restent un défi.

La classification des métaheuristiques n’est pas toujours claire, notamment concernant l’inspiration naturelle ou non, ou la frontière entre mémoire à court et long terme. Certaines méthodes récentes sont difficiles à classer.

La gestion de la mémoire, notamment dans la Recherche Tabou, peut être coûteuse en espace et en temps, et nécessite des compromis entre efficacité et complexité.

Enfin, la conception de fonctions objectives modifiées (comme en Recherche Locale Guidée) et la définition de voisinages complémentaires efficaces restent des sujets de recherche active.

Glossaire

• Métaheuristique : Stratégie de haut niveau guidant une heuristique pour explorer efficacement un espace de solutions.
• Heuristique : Méthode approximative pour trouver une solution satisfaisante à un problème.
• Fonction objectif (f) : Fonction mesurant la qualité ou le coût d’une solution.
• Voisinage (N) : Ensemble des solutions proches d’une solution donnée selon une structure définie.
• Minimum local : Solution meilleure que toutes ses voisines, mais pas forcément la meilleure globale.
• Recuit Simulé : Métaheuristique acceptant parfois des solutions moins bonnes pour échapper aux minima locaux, avec une température décroissante.
• Recherche Tabou : Métaheuristique utilisant une mémoire à court terme (liste taboue) pour éviter les cycles et encourager la diversification.
• GRASP : Métaheuristique combinant une phase constructive aléatoire et une phase d’amélioration locale.
• Recherche à Voisinages Variables (RVV) : Méthode utilisant plusieurs structures de voisinage pour diversifier la recherche.
• Recherche Locale Guidée : Méthode modifiant dynamiquement la fonction objectif pour pénaliser les solutions déjà visitées.
• Méthodes évolutives : Métaheuristiques manipulant une population d’individus évoluant selon des règles d’adaptation et de coopération.
• Liste taboue : Mémoire à court terme interdisant le retour immédiat à certaines solutions ou mouvements.
• Diversification : Exploration large de l’espace de recherche pour éviter le piégeage dans des régions locales.
• Intensification : Exploitation approfondie des régions prometteuses identifiées dans l’espace de recherche.