Algorithmes, Applications

La recherche heuristique

Écrit par Ilyes Talbi · 3 min lecture >

En philosophie, l’heuristique est souvent décrite comme l’art de la découverte. La recherche heuristique est une approche mathématique permettant de trouver une solution acceptable à un problème complexe en un temps raisonnable. C’est une méthode souvent utilisée en optimisation et elle constitue un sujet de recherche courant en machine learning. Dans cet article, je vous explique les principes de base de cette méthode, ses applications et j’introduirais quelques notions théoriques.


Exemple d’utilisation pratique de la recherche heuristique : Google Maps


Pour vous proposer l’itinéraire le plus court pour votre trajet, l’algorithme de Google Maps utilise une méthode de recherche heuristique. Admettons que l’on recherche l’itinéraire à parcourir entre deux villes. On commence par modéliser l’environnement (je vous passe les subtilités liées aux propriétés de l’environnement), sous forme d’un graphe comme le graphe ci-dessous. On part de n0 et on souhaite atteindre n6.

À chaque arrête de ce graphe, on associe un coût qui représente une mesure de la distance entre deux sommets. Une façon de faire serait de tester tous les chemins, d’évaluer leurs coûts respectifs et de garder le chemin dont le coût est le plus faible. Il se trouve que cette méthode fonctionne dans ce cas, on voit directement qu’il y a 4 chemins possibles et que n0->n3->n4->n6 est le chemin le moins coûteux.

Le problème est que dans le cas de Google Maps, le nombre de chemins possibles pour un itinéraire donné est immense (surtout si vous allez à Rome 😊). Il faut donc faire autrement mais je ne voudrais pas vous dévoiler la troisième partie tout de suite…

La recherche heuristique

Limites de l’approche intuitive pour les problèmes d’optimisation


Intuitivement, pour résoudre un problème de ce type, on commence par modéliser le problème. On ramène souvent le problème à une recherche dans un graphe comme dans l’exemple précédent, puis on énumère toutes les possibilités. Après avoir évalué toutes les solutions on est en mesure de choisir la meilleure.

Malheureusement, dans la majorité des cas ce n’est pas si simple. Le temps de calcul d’une méthode de ce genre peut vite devenir énorme. À titre d’exemple, parlons du problème du voyageur de commerce. Dans ce problème, un voyageur doit parcourir un certain nombre de villes en minimisant les coûts de déplacements, donc en minimisant la distance de son trajet.

Si on considère que le voyageur a 30 villes à parcourir, l’approche intuitive prendrait des dizaines de millions d’années avec nos ordinateurs actuels, ce qui, pour des raisons évidentes, n’est pas réalisable. Heureusement, pour pallier ce problème, il existe des algorithmes que l’on appelle recherche heuristique comme l’algorithme A* (que l’on prononce A star).


Principe de l’heuristique et présentation de l’algorithme A*


Un algorithme de recherche heuristique couramment utilisé est l’algorithme A*. Le principe de cet algorithme est qu’à chaque itération on sélectionne le nœud du graphe qui semble le ‘’plus proche’’ du nœud objectif. Cet algorithme est simple à mettre en place et ne nécessite pas beaucoup de mémoire.

Avant toute chose, il faut préciser que l’algorithme A* est fait pour trouver une solution ‘’acceptable’’ rapidement qui n’est pas toujours optimale (il peut donc y avoir de meilleures solutions), il n’est donc pas adapté à toutes les applications.

L’algorithme A* est une extension de l’algorithme de Dijkstra, c’est la ‘’version heuristique’’ de cet algorithme.

Il est temps de définir ce qu’est une heuristique en mathématique. Une heuristique est une fonction d’estimation du coût restant pour arriver à notre destination partant d’un nœud donné.

En d’autres termes, l’heuristique h(n) nous donne une estimation du coût restant entre le nœud n et le nœud objectif. Évidemment, l’heuristique h constitue une prédiction qui est rarement exacte, elle est fondée sur les caractéristiques de l’environnement extérieur. L’algorithme A* permet d’éliminer successivement des chemins pour lesquels l’estimation h(n) est élevée. L’heuristique est un paramètre fixé par la personne qui programme l’algorithme, elle peut permettre de réduire de façon conséquente le temps de calcul du programme.


Fonctionnement de l’algorithme


Comme je l’ai déjà mentionné, pour exécuter l’algorithme A*, nous partons de la modélisation de notre environnement par un graphe. La première étape est de fixer le nœud de départ. Par exemple, sur Google Maps ce nœud correspondra à votre position GPS.

Ensuite on définit une fonction heuristique h. Cette étape est primordiale, il est clair que si l’heuristique est mal choisie, l’algorithme ne sera pas toujours assez rapide pour être exécutable. Un critère courant pour le choix de la fonction heuristique est la distance à vol d’oiseau. Ce critère découle du fait que si 2 villes sont proches à vol d’oiseau, on suppose que le trajet entre elles est court (ce qui n’est pas toujours vérifié mais cela constitue une bonne base pour construire notre heuristique).


Pour un nœud n donné du graphe, on a une formule importante : f(n)=h(n)+g(n). La fonction f nous donne une estimation du coût du trajet total entre le nœud d’origine et le nœud d’arrivée en passant par le nœud n. La fonction h est la valeur de l’heuristique au nœud n, et la fonction g donne le coût du chemin parcouru depuis le début (du nœud de départ au nœud n).

Pour décider vers quel nœud il doit se diriger, l’algorithme compare les valeurs de f pour tous les cas possibles et il choisit le nœud qui a la plus faible valeur. Au nœud suivant, on réitère le calcul et on reste dans la même direction tant que la valeur du coût total reste inférieure à celle de l’étape précédente. On continue ces calculs jusqu’à atteindre le nœud d’arrivée. Heureusement que Google Maps le fait pour vous, non ?

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *