Heuristiques et métaheuristiques
Objectifs
Comprendre les limitations des méthodes exactes face à des problèmes complexes, et maîtriser les concepts d'heuristiques et de métaheuristiques pour obtenir des solutions satisfaisantes en un temps acceptable.
Prérequis
Notions de complexité algorithmique, problèmes NP-difficiles, optimisation combinatoire.
Dans de nombreux problèmes informatiques réels, il est impossible ou trop coûteux de calculer une solution optimale exacte dans un temps raisonnable. C'est notamment le cas pour :
- Les problèmes NP-difficiles (ordonnancement, tournées, allocation de ressources)
- Les problèmes de grande taille
- Les problèmes soumis à des contraintes complexes et évolutives
Pour répondre à ces limitations, on introduit des stratégies approchées appelées heuristiques et métaheuristiques, qui permettent d'obtenir des solutions satisfaisantes en un temps acceptable.
Notion d'heuristique
Une heuristique est une méthode de résolution basée sur des règles empiriques, des approximations ou des connaissances spécifiques du problème, visant à produire rapidement une solution acceptable, sans garantie d'optimalité.
Une heuristique ne cherche pas nécessairement la meilleure solution, mais une bonne solution, obtenue efficacement.
Domaines d'application
Les algorithmes basés sur des heuristiques sont largement utilisés dans divers domaines :
- Recherche opérationnelle : Problèmes de planification, d'acheminement et d'allocation des ressources.
- Intelligence artificielle : Jeux (échecs, Go), planification et apprentissage automatique.
- Informatique : Compilateurs, conception de réseaux et ingénierie logicielle.
- Bioinformatique : Alignement de séquences et repliement des protéines.
Caractéristiques des algorithmes heuristiques
- Simplicité et rapidité : Conçus pour être plus rapides et plus simples que les algorithmes exacts.
- Variabilité de la qualité : La qualité de la solution peut varier selon l'heuristique utilisée et l'instance particulière du problème.
- Spécificité : Souvent adaptées aux caractéristiques spécifiques du problème en question.
- Compromis : Impliquent généralement des compromis entre rapidité et précision, ou simplicité et complexité.
Familles d'algorithmes heuristiques
Face à la complexité de nombreux problèmes d'optimisation, différentes stratégies heuristiques ont émergé. Chacune adopte une approche distincte pour trouver une solution de bonne qualité en un temps raisonnable, sans garantir l'optimalité.
Algorithmes gloutons (Greedy algorithms)
Un algorithme glouton suit une logique simple et déterminée : à chaque étape de la construction de la solution, il sélectionne l'option qui offre le meilleur bénéfice immédiat, selon un critère local. Une fois un choix effectué, il n'est jamais remis en question.
- Avantages : Extrêmement rapides, faciles à comprendre et à implémenter.
- Limite majeure : L'absence de vision globale peut conduire à des solutions sous-optimales, car une suite de bons choix locaux ne garantit pas un résultat global optimal.
Rendre 30€ avec des pièces de 20€, 15€ et 1€
Prendre la plus grande pièce ≤ 30 → 20€ Reste 10€ → prendre 1€ (10 fois) Solution : 20€ + 10×1€ (11 pièces) Optimal : 2×15€ (2 pièces)
Recherche locale (Local search)
La recherche locale part d'une solution initiale et cherche à l'améliorer progressivement en explorant son voisinage. Une solution voisine est obtenue par une petite modification de la solution courante. L'algorithme évolue vers une solution de meilleure qualité.
- À partir d'une solution courante, on définit et explore son voisinage (ensemble des solutions très similaires).
- Si une solution voisine est meilleure, elle devient la nouvelle solution courante.
- Le processus se répète jusqu'à ce qu'aucun voisin améliorant ne soit trouvé.
L'algorithme peut se bloquer dans un optimum local – une solution meilleure que toutes ses voisines immédiates, mais pas nécessairement la meilleure du problème entier.
Algorithmes de construction (Constructive heuristics)
Les algorithmes de construction assemblent une solution pièce par pièce. C'est une famille plus large qui englobe les algorithmes gloutons, mais qui peut intégrer des logiques plus nuancées.
Ces algorithmes produisent une solution progressivement, en partant :
- soit d'une solution vide à laquelle on ajoute des éléments,
- soit d'une solution partielle initiale que l'on étend ou améliore.
- Initialisation : on commence avec une structure vide ou une solution partielle.
- Itération de construction : à chaque étape, un nouvel élément est ajouté à la solution en cours. Le choix de cet élément est dicté par une règle de sélection.
- Terminaison : l'algorithme s'arrête lorsque la solution est complète ou qu'un critère d'arrêt est atteint.
La puissance et le caractère de l'algorithme dépendent entièrement de sa règle de sélection. Celle-ci peut être :
- Gloutonne : on choisit systématiquement l'élément le plus prometteur localement. Un algorithme glouton est donc un cas particulier d'algorithme de construction à règle déterministe.
- Aléatoire : l'élément est choisi au hasard, ce qui permet de générer des solutions variées.
- Stochastique-guidée : le choix combine une part de hasard et une part guidée par une heuristique.
Algorithmes métaheuristiques
Une métaheuristique est une stratégie générale d'optimisation qui guide une heuristique afin d'explorer intelligemment l'espace de recherche.
Le terme, issu du grec meta (au-delà) et heuriskein (trouver), signifie qu'elle agit comme un cadre directeur (framework) qui orchestre des procédures plus simples pour naviguer dans des espaces de recherche vastes et irréguliers.
Une métaheuristique ne dépend pas directement d'un problème particulier, mais fournit un cadre générique adaptable.
Caractéristiques principales
- Flexibilité (boîte noire) : Les métaheuristiques sont conçues comme des "boîtes noires". Elles manipulent des solutions sans nécessairement connaître la nature profonde du problème. Seule la fonction de coût (fitness) est nécessaire pour évaluer la qualité d'une solution.
- Exploration et exploitation : C'est le cœur de l'efficacité d'une métaheuristique :
- Exploration (Diversification) : Capacité de l'algorithme à visiter des zones éloignées et inconnues de l'espace de recherche pour ne pas passer à côté du maximum global.
- Exploitation (Intensification) : Capacité à se concentrer sur le voisinage d'une bonne solution actuelle pour l'affiner et trouver le sommet local précis.
- Utilisation de mémoire et apprentissage : Certaines métaheuristiques utilisent une mémoire à court ou long terme pour :
- Enregistrer les dernières solutions visitées afin d'éviter de tourner en boucle.
- Identifier les caractéristiques communes des meilleures solutions trouvées pour orienter la recherche future.
- Composante stochastique (le hasard dirigé) : L'intégration du hasard permet de simuler des comportements naturels (évolution, refroidissement thermique, mouvement social) et surtout de donner à l'algorithme une probabilité de choisir une solution moins bonne temporairement pour s'extraire d'un optimum local.
Métaheuristiques vs Heuristiques
| Caractéristiques | Heuristiques simples | Métaheuristiques |
|---|---|---|
| Spécificité\\ | Conçues sur mesure pour un problème précis (ex: règle du plus proche voisin).\\ | Cadres génériques adaptables à diverses contraintes.\\ |
| Complexité\\ | Souvent simples, rapides et intuitives.\\ | Algorithmes plus sophistiqués nécessitant un réglage de paramètres.\\ |
| Stratégie\\ | Suivent une règle fixe sans vue d'ensemble.\\ | Orchestrent la recherche avec des mécanismes de rétroaction.\\ |
| Robustesse\\ | Très sensibles à la configuration initiale des données.\\ | Capables de traiter des fonctions de coût bruitées ou discontinues.\\ |
| Sortie des optima locaux\\ | S'arrêtent dès qu'aucune amélioration immédiate n'est possible.\\ | Utilisent des mécanismes (sauts, mutations, mémoire) pour franchir les barrières.\\ |
Exemples d'algorithmes métaheuristiques
Le paysage des métaheuristiques est extrêmement varié, s'inspirant tour à tour de la biologie, de la physique ou des sciences cognitives. Bien que leurs mécanismes diffèrent, elles partagent toutes un but commun : maintenir un équilibre fragile entre l'exploration (visiter de nouvelles zones) et l'exploitation (approfondir autour des meilleures solutions).
Recherche avec tabou (Tabu Search)
La recherche avec tabou est une extension de la recherche locale qui utilise une mémoire à court terme, appelée liste tabou, pour interdire temporairement certains mouvements, évitant ainsi de revenir sur des solutions récemment visitées.
- Initialiser une solution courante \(S\)
- Générer les solutions voisines
- Choisir la meilleure solution admissible \(S'\)
- Vérifier si \(S'\) est tabou :
- oui → l'ignorer,
- non → l'adopter et mettre à jour la liste tabou
- Tester le critère d'arrêt
La liste tabou permet d'éviter de tourner en boucle et force l'algorithme à explorer de nouvelles régions de l'espace de recherche.
Algorithmes génétiques (Genetic Algorithms)
Les algorithmes génétiques transposent les lois de la survie du plus apte au monde du calcul numérique. Au lieu de travailler sur une seule solution, on fait évoluer une population entière de candidats.
Ces algorithmes transposent en informatique les mécanismes de :
- Sélection naturelle : les individus les mieux adaptés à leur environnement ont une plus grande probabilité de survivre et de se reproduire.
- Reproduction (croisement) : le patrimoine génétique des parents est combiné pour créer une nouvelle génération.
- Mutation : des modifications aléatoires du matériel génétique introduisent de la diversité.
Population initiale (aléatoire)
↓
Évaluation (fitness)
↓
Sélection des meilleurs
↓
Croisement (crossover)
↓
Mutation
↓
Nouvelle génération
Génération 1 : fitness = 45 Génération 2 : fitness = 52 Génération 3 : fitness = 67 ... Génération 100 : fitness = 98
Recuit simulé (Simulated Annealing)
Le recuit simulé est une méthode probabiliste inspirée de la thermodynamique et du processus de recuit en métallurgie (chauffage puis refroidissement contrôlé d'un métal pour éliminer ses défauts).
Contrairement aux algorithmes "gloutons" qui n'acceptent que des améliorations immédiates, le recuit simulé accepte parfois de mauvaises solutions pour éviter de rester bloqué dans un optimum local. La probabilité d'accepter une moins bonne solution diminue avec le temps (température).
La probabilité d'accepter une solution moins bonne est donnée par :
\[ P(\Delta E, T) = e^{-\Delta E / T} \]où \(\Delta E\) est la dégradation de la qualité et \(T\) la température courante.
À haute température, on accepte facilement des solutions moins bonnes (exploration). À basse température, on devient plus sélectif et on ne garde que les améliorations (exploitation).
Récapitulatif des métaheuristiques
| Métaheuristique | Inspiration | Mécanisme clé | Application typique |
|---|---|---|---|
| Recherche Tabou\\ | Intelligence humaine / mémoire\\ | Liste tabou (mémoire à court terme)\\ | Optimisation de tournées, ordonnancement\\ |
| Algorithmes génétiques\\ | Évolution biologique\\ | Population, croisement, mutation\\ | Optimisation multi-objectifs, apprentissage\\ |
| Recuit simulé\\ | Métallurgie (recuit)\\ | Acceptation probabiliste des mauvaises solutions\\ | Problèmes d'optimisation combinatoire\\ |
| Colonie de fourmis\\ | Comportement des fourmis\\ | Phéromones, chemins préférentiels\\ | Problèmes de routage, graphes\\ |
| Essaim particulaire\\ | Comportement social (oiseaux, poissons)\\ домаћинствима, interaction sociale\\ | Optimisation continue, apprentissage\\ |
L'essentiel en bref
- Les méthodes exactes sont parfois trop coûteuses pour des problèmes NP-difficiles ou de grande taille.
- Une heuristique est une méthode spécifique, rapide, qui donne une bonne solution sans garantie d'optimalité.
- Les principales familles d'heuristiques sont : gloutons, recherche locale et algorithmes de construction.
- Une métaheuristique est un cadre générique qui orchestre des heuristiques pour explorer efficacement l'espace de recherche.
- L'équilibre exploration / exploitation est fondamental pour la qualité des solutions.
- Exemples de métaheuristiques : Recherche Tabou, Algorithmes génétiques, Recuit simulé.
- Utilisez une heuristique gloutonne pour un premier résultat rapide, même s'il n'est pas optimal.
- Si la qualité doit être améliorée, appliquez une métaheuristique à partir de la solution gloutonne.
- Le choix de la métaheuristique dépend du problème : recuit simulé pour l'optimisation combinatoire, algorithmes génétiques pour les espaces complexes, recherche tabou pour éviter les cycles.
- N'oubliez pas d'ajuster les paramètres (température, taille de population, longueur de liste tabou) pour chaque problème.
Un peu d'histoire
Le terme "heuristique" a été introduit par George Pólya dans son ouvrage "How to Solve It" (1945). Le recuit simulé a été proposé par Scott Kirkpatrick en 1983. Les algorithmes génétiques ont été popularisés par John Holland dans les années 1970. La recherche tabou a été développée par Fred Glover en 1986. Ces méthodes ont révolutionné la résolution de problèmes d'optimisation complexes et sont aujourd'hui utilisées dans l'industrie, la finance, et la recherche.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.