Heuristique

Infos
Heuristique (du grec heuriskêin, « trouver ») est un terme de didactique qui signifie l'art d'inventer, de faire des découvertes (Littré). C'est en sociologie, une discipline qui se propose de dégager les règles de la recherche scientifique (Larousse). En optimisation combinatoire, Théorie des graphes et Théorie de la complexité, une heuristique est un algorithme qui fournit rapidement (en temps polynomial) une solution réalisable, pas né
Heuristique

Heuristique (du grec heuriskêin, « trouver ») est un terme de didactique qui signifie l'art d'inventer, de faire des découvertes (Littré). C'est en sociologie, une discipline qui se propose de dégager les règles de la recherche scientifique (Larousse). En optimisation combinatoire, Théorie des graphes et Théorie de la complexité, une heuristique est un algorithme qui fournit rapidement (en temps polynomial) une solution réalisable, pas nécessairement optimale, pour un problème d'optimisation NP-difficile. Une heuristique, où méthode approximative, est donc le contraire d'un algorithme exact qui trouve une solution optimale pour un problème donné. L'intérêt de l'heuristique étant que pour les problèmes NP-difficiles, les algorithmes exacts connus sont tous de complexité exponentielle et donc sans aucun intérêt en pratique (ni en théorie d'ailleurs). On utilise presque systématiquement une heuristique pour obtenir une première solution réalisable dans un 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). La qualité d'une heuristique peut s'évaluer selon deux critères scientifiques : :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 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. C'est un fait que 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 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 cette algorithme 2-approché.

Références

C. H. Papadimitriou & K. Steiglitz, "Combinatorial optimization: algorithms and complexity", Englewoods Cliffs, Prentice Hall, 1982 ===
Sujets connexes
Algorithmique   Complexité algorithmique   Empirisme   Métaheuristique   Optimisation   Optimisation combinatoire   Recuit simulé   Sociologie   Séparation et évaluation   Théorie de la complexité   Théorie des graphes   Théorème de König (théorie des graphes)  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^