Heuristique (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir heuristique.

Une heuristique est une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d'optimisation difficile. C'est un concept utilisé entre autres en optimisation combinatoire, en théorie des graphes, en théorie de la complexité des algorithmes et en intelligence artificielle. Une heuristique diffère d'un algorithme, en ce sens que l'algorithme apporte la garantie de trouver la solution ou une solution optimale pour le problème. Une heuristique diffère également d'un algorithme d'approximation, dans le sens où ce dernier apporte une garantie quant à la qualité de la solution, à défaut de garantir une solution exacte.

Quand les algorithmes de résolution exacte sont de complexité exponentielle, il peut être plus judicieux de faire appel à des méthodes heuristiques pour des problèmes difficiles. L'usage d'une heuristique est pertinent pour calculer une solution approchée d'un problème et aussi pour accélérer le processus de résolution exacte. Généralement une heuristique est conçue pour un problème particulier, en s'appuyant sur sa structure propre, mais les approches peuvent contenir des principes plus généraux. On parle de métaheuristique pour les méthodes approximatives générales, pouvant s'appliquer à différents problèmes (comme le recuit simulé par exemple).

Qualité d'une heuristique[modifier | modifier le code]

Elle peut s'évaluer selon deux critères  :

  1. Critère pratique, ou empirique : on implémente l'algorithme approximatif et on évalue la qualité de ses solutions par rapport aux solutions optimales (ou aux meilleures solutions connues). Ceci passe par la mise en place d'un banc d'essai (en anglais benchmark, ensemble d'instances d'un même problème accessible à tous).
  2. Critère mathématique : il faut démontrer que l'heuristique garantit des performances. La garantie la plus solide est celle des algorithmes approchés, sinon il est intéressant de démontrer une garantie probabiliste, lorsque l'heuristique fournit souvent, mais pas toujours, de bonnes solutions.

Ces deux critères peuvent être contradictoires. Un exemple frappant est celui du transversal minimum. L'algorithme 2-approché pour ce problème est dans une imposante majorité des cas nettement moins efficace que l'heuristique des plus hauts degrés. Celle-ci consiste à former une solution réalisable en sélectionnant à chaque itération le sommet couvrant un maximum de sommets. Cette heuristique peut pourtant fournir des solutions aussi mauvaises que l'on veut, dans le sens que pour tout  \rho > 1 on peut construire une instance pour laquelle l'heuristique donne une solution dont la valeur est supérieure à  \rho fois celle de l'optimum. Ironiquement, la principale difficulté de la résolution exacte d'un problème d'optimisation combinatoire est non pas de trouver une solution optimale, ce qui souvent arrive assez rapidement lors du processus de résolution, mais de démontrer qu'une solution est bien la meilleure possible, c'est-à-dire de réaliser que l'on a la solution optimale. Le critère mathématique est surtout important car l'information qu'il donne est exploitable dans un processus de résolution exacte. Par exemple, si l'heuristique 2-approchée pour le transversal minimum donne une solution réalisable de valeur 100, on sait que la valeur de la solution optimale est au minimum 50, on peut donc stopper un processus d'énumération (par exemple séparation et évaluation) dès que l'on possède une solution réalisable atteignant cette borne. Dans ce contexte il devient motivant d'élaborer l'algorithme 2-approché le plus mauvais qui soit, donnant la solution la plus éloignée de l'optimum, pour prouver une meilleure borne. On utilise donc un couplage maximum, alors qu'un couplage maximal suffit, pour cet algorithme 2-approché. Pour résumer, l'heuristique est la logique d'esprit d'un algorithme[réf. nécessaire].

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) C. Papadimitriou & K. Steiglitz, Combinatorial optimization: algorithms and complexity, Englewoods Cliffs, Prentice Hall, 1982.

Articles connexes[modifier | modifier le code]

Sur les autres projets Wikimedia :

Notes et références[modifier | modifier le code]