Heuristique (mathématiques)

Au sens le plus large, l'heuristique est la psychologie de la découverte, abordée par différents mathématiciens.

En algorithmique, 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.

Heuristique au sens large

Aspect psychologique

On distingue en général plusieurs temps

la prise en compte du problème (question, contexte : données, contraintes, acteurs, tenants et aboutissants)
l'incubation, recherche de solution, rumination parfois très longue ; la méthode du problème résolu peut ici dégager les conditions nécessaires à respecter.
l'illumination (ou découverte de solution)
l'explicitation, qui descend dans les détails
la validation (qui doit relancer le processus en cas d'échec)

En mathématiques

Pólya a abordé ces questions sous l'angle des mathématiques.

Il distingue les niveaux opératoires, tactiques et stratégiques. Le premier regroupe des savoir-faire élémentaires, le dernier est le plus intuitif et le plus difficile. Mais l'expérience rend les niveaux inférieurs de plus en plus riches et efficaces.

Une fois le problème bien cerné (question, contexte : données, contraintes, tenants et aboutissants), selon les cas

c'est un problème connu (ou un cas particulier) ;
c'est un problème qu'on peut ramener à une combinaison de problèmes plus simples ;
c'est un problème ressemblant à un problème qu'on sait traiter.

Le premier cas se produit d'autant plus souvent qu'on a plus d'expérience ; il peut demander une adaptation, afin de ne pas "écraser une noisette avec un marteau-pilon".

Le second cas correspond à une analyse cartésienne, et utilise le premier comme critère d'arrêt.

Le troisième cas est le plus intuitif, fertile mais incertain, car les problèmes analogues ont souvent, mais pas toujours, des solutions analogues ; de plus, si l'analogie est trop lointaine, on peut devoir la fragmenter en plusieurs stades intermédiaires.

Finalement, lorsqu'un plan d'action a été trouvé, on l'explicite pour le mettre en œuvre.

Si le résultat n'est pas bon, on remet en cause la démarche.

Si le résultat est correct, il est bon de voir si on peut faire mieux, plus efficace ou plus général, afin d'enrichir son expérience.

Arguments heuristiques

En théorie des nombres, on parle de raisonnement heuristique pour une approche non rigoureuse (et ne démontrant par conséquent rien) remplaçant par exemple les nombres premiers par une distribution aléatoire, et montrant que le résultat cherché a une probabilité égale à 1.

En théorie des nombres, de nombreuses conjectures reposent sur des arguments, dits heuristiques, consistants à estimer la probabilité de la conjecture en supposant par exemple les nombres premiers comme répartis au hasard ; on obtient ainsi parfois des estimations extrêmement précises, comme celles de la conjecture de Bateman-Horn, qui sont bien confirmées expérimentalement. Cette technique ne doit pas être confondue avec la méthode probabiliste, qui, malgré son nom, fournit des démonstrations rigoureuses et des résultats certains.

Heuristique au sens de l'algorithmique

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, en intelligence artificielle, dans la programmation des jeux (comme les échecs ou go), dans la primalité des nombres entiers et dans la démonstration de théorème.

Une heuristique s'impose quand les algorithmes de résolution exacte sont impraticables, à savoir de complexité polynomiale de haut degré, exponentielle ou plus^{[note 1]}. Généralement, une heuristique est conçue pour un problème particulier, en s'appuyant sur sa structure propre, mais il existe des approches fondées sur des principes 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).

Herbert Simon, prix Nobel d'économie 1978 et pionnier de l'intelligence artificielle, est considéré comme le père des heuristiques en algorithmique. Pour lui, il s’agissait de méthodes pour arriver à des solutions satisfaisantes avec des quantités modestes de calcul.

Qualité d'une heuristique

Une heuristique peut s'évaluer selon divers critères :

Qualité du résultat :
1. on se place dans une théorie fondée sur les probabilités et on démontre mathématiquement quelques propriétés pertinentes,
2. si l'on ne peut pas établir une théorie, on implémente l'heuristique et on évalue la qualité de ses solutions par rapport aux solutions optimales (ou aux meilleures solutions connues), soit en termes de distance, soit en termes de probabilité de réussite. Ceci passe par la mise en place d'un jeu d'essai ou benchmark, ensemble d'instances d'un même problème, choisies pour couvrir le plus largement le spectre des instances^{[note 2]}.
Coût de l'heuristique : complexité (temps, espace) de l'heuristique.
Étendue du domaine d'application (domaine d'optimalité et domaine d'admissibilité des solutions).

On peut mettre en concurrence diverses heuristiques pour profiter de l'ensemble de leurs domaines d'activités, ce qui est, en soi, une nouvelle heuristique.

Notes

↑ La décision de l'arithmétique de Presburger est doublement exponentielle, mais des solveurs comme SMT Z3 ou oméga de Coq exhibent des démonstrations dans tous les cas pratiques.
↑ Là encore la théorie de probabilités va jouer un rôle, pour distribuer aléatoirement le jeu de données.

Voir aussi

Bibliographie

Nicolas Pinel, La méthode heuristique de mathématiques : enseigner les mathématiques autrement à l'école, 2e éd., Éditions du Net, 2020.
George Pólya, Comment poser et résoudre un problème, Dunod 1965, traduction de How to solve it, Princeton University Press, 1945; réédition J. Gabay.
(en) Lane A. Hemaspaandra et Ryan Williams, « An atypical survey of typical-case heuristic algorithms », SIGACT News, vol. 43(4),‎ 2012, p. 70-89
(en) Heiner Müller-Merbach, « Heuristics and their design: a survey », uropean Journal of Operational Research, vol. 8(1),‎ septembre 1981, p. 1-23
(en) C. Papadimitriou & K. Steiglitz, Combinatorial optimization: algorithms and complexity, Englewoods Cliffs, Prentice Hall, 1982.
(en) Terence Tao, Solving Mathematical Problems: A Personal Perspective, Oxford University Press, 2006 (ISBN 9780199205608)
Imre Lakatos, Preuves et Réfutations (en) : essai sur la logique de la découverte mathématique. Notamment concernant les heuristiques permettant d'obtenir le théorème de Descartes-Euler, $s-a+f=2$ , pour certains polyèdres et de le réfuter pour d'autres.