À retenir
- C'est une méthode pour trouver une « très bonne » solution quand la solution « parfaite » est trop longue à calculer.
- Elle repose souvent sur des analogies avec la nature (biologie, physique).
- Elle est indispensable pour résoudre les problèmes dits « NP-difficiles » (très complexes).
Une métaheuristique est une stratégie de résolution pour des problèmes mathématiques ou informatiques extrêmement complexes, où il est impossible de tester toutes les possibilités une par une. Imaginez que vous cherchiez le sommet le plus haut dans un massif montagneux inconnu en pleine nuit : au lieu de parcourir chaque centimètre carré, vous utilisez une méthode astucieuse (comme toujours grimper vers le haut ou suivre un guide) pour trouver un sommet très élevé le plus vite possible, même si ce n'est pas forcément le point culminant absolu.
Étymologie
Le terme provient du grec méta (au-delà, qui chapeaute) et eurisko (trouver). En informatique, cela désigne une méthode de recherche de haut niveau qui guide d'autres règles plus simples pour sortir des impasses et explorer efficacement de vastes ensembles de solutions.
Exemples d'usage
- Les algorithmes génétiques : ils imitent la sélection naturelle en faisant « croiser » les meilleures solutions entre elles pour en créer de nouvelles encore plus performantes.
- Le recuit simulé : inspiré de la métallurgie, cette méthode accepte parfois de mauvaises solutions temporaires pour éviter de rester bloqué dans un creux et mieux repartir vers un sommet.
- L'optimisation par essaims particulaires : elle simule le mouvement d'un banc de poissons ou d'un vol d'oiseaux cherchant de la nourriture.
Cas d'usage
On utilise les métaheuristiques dans la logistique (calculer le trajet optimal d'un camion de livraison), la gestion d'emplois du temps (agencer les cours d'une université sans conflits) ou encore dans la conception de puces électroniques où les combinaisons possibles sont astronomiques.
Bonnes pratiques
Il est important de trouver le bon équilibre entre « exploration » (chercher dans de nouvelles zones) et « exploitation » (approfondir une zone prometteuse). Un mauvais réglage peut conduire l'algorithme à tourner en rond ou à se contenter d'une solution médiocre.
Synonymes
Antonymes
Conseil
Si vous commencez à programmer ces algorithmes, ne cherchez pas la perfection immédiate. L'intérêt d'une métaheuristique est d'être « robuste » et de fournir un résultat satisfaisant en un temps court, pas de trouver le zéro absolu ou le maximum parfait à chaque coup.
Questions fréquentes
Une métaheuristique donne-t-elle toujours la même réponse ?
Pas forcément. Beaucoup d'entre elles utilisent une part de hasard (stochastique), ce qui signifie que deux lancements peuvent aboutir à des résultats légèrement différents.
Est-ce mieux qu'un algorithme classique ?
C'est mieux uniquement quand le problème est trop vaste pour un algorithme classique. Si une solution exacte peut être trouvée rapidement, la métaheuristique n'a pas d'intérêt.