Heuristique (informatique)

En optimisation mathématique et en informatique , une heuristique (du grec εὑρίσκω eurísko , « je trouve, je découvre » ) est une technique conçue pour résoudre plus rapidement les problèmes lorsque les méthodes classiques sont trop lentes pour trouver une solution exacte ou approchée, ou lorsqu'elles ne parviennent pas à trouver de solution exacte dans un espace de recherche . Elle consiste à privilégier la vitesse au détriment de l'optimalité, de l'exhaustivité, de l'exactitude ou de la précision . On peut la considérer comme un raccourci.

Une fonction heuristique , également appelée simplement heuristique , est une fonction qui classe les alternatives dans les algorithmes de recherche à chaque étape de branchement en fonction des informations disponibles afin de décider quelle branche suivre. Par exemple, elle peut approcher la solution exacte.

L'objectif d'une heuristique est de fournir, dans un délai raisonnable, une solution suffisamment satisfaisante pour résoudre le problème posé. Cette solution n'est pas nécessairement la meilleure possible, ni une simple approximation de la solution exacte. Elle reste néanmoins précieuse car sa recherche ne requiert pas un temps excessivement long.

Les heuristiques peuvent produire des résultats par elles-mêmes, ou elles peuvent être utilisées conjointement avec des algorithmes d'optimisation pour améliorer leur efficacité (par exemple, elles peuvent être utilisées pour générer de bonnes valeurs initiales).

Les résultats concernant la NP-difficulté en informatique théorique font des heuristiques la seule option viable pour une variété de problèmes d'optimisation complexes qui doivent être résolus régulièrement dans des applications du monde réel.

Les heuristiques sous-tendent tout le domaine de l'intelligence artificielle et de la simulation informatique de la pensée, car elles peuvent être utilisées dans des situations où il n'existe pas d'algorithmes connus .

One way of achieving the computational performance gain expected of a heuristic consists of solving a simpler problem whose solution is also a solution to the initial problem.

An example of approximation is described by Jon Bentley for solving the travelling salesman problem (TSP):

• "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

so as to select the order to draw using a pen plotter. TSP is known to be NP-hard so an optimal solution for even a moderate size problem is difficult to solve. Instead, the greedy algorithm can be used to give a good but not optimal solution (it is an approximation to the optimal answer) in a reasonably short amount of time. The greedy algorithm heuristic says to pick whatever is currently the best next step regardless of whether that prevents (or even makes impossible) good steps later. It is a heuristic in the sense that practice indicates it is a good enough solution, while theory indicates that there are better solutions (and even indicates how much better, in some cases).

Another example of heuristic making an algorithm faster occurs in certain search problems. Initially, the heuristic tries every possibility at each step, like the full-space search algorithm. But it can stop the search at any time if the current possibility is already worse than the best solution already found. In such search problems, a heuristic can be used to try good choices first so that bad paths can be eliminated early (see alpha–beta pruning). In the case of best-first search algorithms, such as A* search, the heuristic improves the algorithm's convergence while maintaining its correctness as long as the heuristic is admissible.

In their Turing Award acceptance speech, Allen Newell and Herbert A. Simon discuss the heuristic search hypothesis: a physical symbol system will repeatedly generate and modify known symbol structures until the created structure matches the solution structure. Each following step depends upon the step before it, thus the heuristic search learns what avenues to pursue and which ones to disregard by measuring how close the current step is to the solution. Therefore, some possibilities will never be generated as they are measured to be less likely to complete the solution.

Une méthode heuristique peut accomplir sa tâche en utilisant des arbres de recherche. Cependant, au lieu de générer toutes les branches de solution possibles, une heuristique sélectionne les branches les plus susceptibles de produire des résultats que les autres. Elle est sélective à chaque point de décision, choisissant les branches qui ont le plus de chances de mener à des solutions.

Les heuristiques sont au cœur de nombreux algorithmes de recherche informée et de techniques d'optimisation pour l'IA :

• L' algorithme de recherche A * est l'une des techniques de recherche heuristique les plus populaires grâce à sa capacité à trouver efficacement des solutions optimales. A* combine le coût réel du chemin et une estimation heuristique du coût restant pour atteindre l'objectif.

• Recherche gloutonne du meilleur d'abord : cet algorithme explore le nœud le plus proche de l'objectif en se basant uniquement sur la fonction heuristique (h(n)), sans tenir compte du coût du chemin parcouru. Il est rapide, mais ne garantit pas une solution optimale.
• Recherche locale (ou recherche locale par escalade ) : algorithme qui se déplace itérativement de l’état actuel vers un état voisin plus favorable. Simple à implémenter, il peut cependant se retrouver piégé dans des optima locaux (solutions sous-optimales, meilleures que leurs voisines immédiates mais pas la meilleure solution globale). Une fonction objectif (comme un gradient pour les espaces continus) détermine la direction à suivre.
• Recuit simulé : Le recuit simulé est une technique de recherche heuristique qui explore l’espace de recherche en acceptant occasionnellement des solutions moins performantes afin d’éviter de rester bloqué dans des maxima locaux. Inspiré du procédé de recuit en métallurgie, cet algorithme réduit progressivement la probabilité d’accepter des solutions moins performantes au fur et à mesure de la recherche. En autorisant l’exploration de solutions sous-optimales, le recuit simulé permet d’échapper aux maxima locaux et de trouver une meilleure solution globale. Il est couramment utilisé dans les problèmes d’optimisation où l’espace de recherche est vaste et complexe.
• Algorithmes génétiques : Inspirés par la sélection naturelle, ils utilisent des processus tels que la sélection, le croisement et la mutation pour faire évoluer une population de solutions candidates au fil des générations.
• Optimisation par colonies de fourmis : une méthode d'intelligence collective inspirée par la façon dont les fourmis trouvent des chemins vers les sources de nourriture, utilisant des « phéromones » artificielles pour guider la recherche.

Les logiciels antivirus utilisent souvent des règles heuristiques pour détecter les virus et autres logiciels malveillants . L'analyse heuristique recherche des schémas de code et/ou de comportement communs à une classe ou une famille de virus, chaque virus suivant un ensemble de règles différent. Si un fichier ou un processus en cours d'exécution contient des schémas de code correspondants et/ou effectue ces activités, l'analyseur en déduit que le fichier est infecté. L'atout majeur de l'analyse heuristique comportementale réside dans sa capacité à lutter contre les virus polymorphes , hautement aléatoires et auto-modificateurs , difficiles à détecter par les méthodes d'analyse de chaînes de caractères classiques. L'analyse heuristique a le potentiel de détecter les futurs virus sans qu'il soit nécessaire de les détecter au préalable ailleurs, de les soumettre au développeur de l'antivirus pour analyse, puis de fournir une mise à jour aux utilisateurs de l'antivirus.

Certaines heuristiques reposent sur une théorie sous-jacente solide ; elles sont soit dérivées de manière descendante de cette théorie, soit élaborées à partir de données expérimentales ou issues du monde réel. D’autres ne sont que des règles empiriques fondées sur l’observation ou l’expérience, sans aucun fondement théorique. Ces dernières sont plus sujettes aux écueils.

Lorsqu'une heuristique est réutilisée dans divers contextes parce qu'elle a montré son efficacité dans un contexte donné, sans avoir été mathématiquement prouvée comme répondant à un ensemble d'exigences donné, il est possible que l'ensemble de données actuel ne représente pas nécessairement les ensembles de données futurs (voir : surapprentissage ) et que les prétendues « solutions » s'avèrent être comparables à du bruit.

Une analyse statistique peut être menée lors de l'utilisation d'heuristiques pour estimer la probabilité de résultats incorrects. Pour utiliser une heuristique afin de résoudre un problème de recherche ou un problème du sac à dos , il est nécessaire de vérifier son admissibilité . Étant donné une fonction heuristique destinée à approximer la distance optimale réelle au nœud but dans un graphe orienté contenant un total de nœuds ou de sommets étiquetés , « admissible » signifie approximativement que l'heuristique sous-estime le coût vers le but, ou formellement que pour tout où .

If a heuristic is not admissible, it may never find the goal, either by ending up in a dead end of graph