Exemple avec les parcours de graphe
Nous avons déjà vu dans le cours plusieurs parcours, dont le résultat est d’obtenir un arbre couvrant d’un graphe à partir d’un sommet donné.
Le fait d’utiliser un parcours plutôt qu’un autre peut être en soi une heuristique. Par exemple, considérons le problème suivant : à partir d’une page wikipedia (par exemple la page wikipedia sur Télécom Bretagne), nous souhaitons arriver à une autre page wikipedia (par exemple la page wikipedia sur le nombre 42) en suivant des liens hypertextes. Faut-il alors plutôt utiliser un parcours en largeur ou en profondeur ?
Il n’y a pas de doute que les deux méthodes arriveront aux résultats, étant donné la très grande connectivité du graphe des liens hypertextes de wikipedia, mais ils n’y arriveront pas de la même manière.
Qu’est-ce qu’une bonne heuristique ?
Une heuristique correspondant le plus souvent à une intuition, il n’est pas simple d’évaluer a priori sa qualité.
Globalement, une heuristique devrait avoir les qualités suivantes :
- Apporter un gain : une heuristique devrait permettre d’améliorer les performances d’un algorithme selon un critère donné et par rapport à d’autres heuristiques. Par exemple, imaginons que je souhaite me rendre en un minimum de pas d’une salle de cours à une autre, alors une heuristique possible pour m’y rendre consiste à me déplacer globalement dans la direction de la salle (en ignorant la présence de murs/obstacles). Très probablement cette heuristique est en général meilleure que de s’orienter de façon aléatoire. Mais dans certains cas, il n’est pas impossible de se retrouver dans un cul de sac, auquel cas le gain apporté par l’heuristique peut-être négatif.
- Avoir une complexité limitée. Si utiliser l’heuristique coûte aussi cher qu’explorer toutes les possibilités, alors autant ne pas l’utiliser ! Reprenons l’exemple précédent et supposons que pour trouver mon chemin j’explore tous les chemins possibles et compte le nombre de pas pour chacun d’entre eux. Je peux ensuite choisir le chemin le plus court, mais comme il a fallu auparavant tout explorer j’aurai au final marché bien plus que si j’avais choisi une heuristique plus simple.
Il est en général plus facile d’évaluer la qualité d’une heuristique a posteriori, c’est-à-dire en lançant un nombre important de tests et en comparant les résultats obtenus avec ceux correspondant au choix d’une autre heuristique.
Les métaheuristiques
Le préfixe méta indique que le mot auquel il est associé est mis à un niveau d’abstraction supérieur. Dans le cas présent, une métaheuristique est donc une heuristique qui servira elle-même à trouver des heuristiques pour résoudre un problème.
Les métaheuristiques permettent d’abstraire le problème de recherche de la bonne heuristique, en considérant l’heuristique comme une solution à un problème d’optimisation, dont l’objectif est de maximiser la précision sur le problème étudié, tout en limitant la complexité. Ainsi, une métaheuristique est un algorithme qui va parcourir l’espace des heuristiques possibles, et en choisir une qui sera jugée plus optimale que les autres selon certains critères (d’où la partie heuristique dans le mot).
Au delà de cet intérêt, les métaheuristiques font complètement abstraction du problème étudié, en considérant que l’heuristique cherchée est juste une fonction qu’il faut optimiser pour minimiser tel ou tel critère. Ainsi, une même métaheuristique pourra être utilisée pour produire des heuristiques répondant à un très grand nombre de problèmes.