Evaluation des heuristiques - Complex systems and AI

Contenus

Méthodes d’évaluation des heuristiques

Le problème de l’évaluation des heuristiques est crucial. En effet, les heuristiques n’offrent aucune garantie d’optimalité : elles peuvent trouver l’optimum pour certaines données, ou en être très éloignées.

Performance relative

Supposons qu’on étudie un problème combinatoire pour lequel on dispose déjà d’une méthode exacte (optimale) de référence. Pour une heuristique H et une donnée d, on note H(d) le coût de la solution heuristique et OPT(d) le coût optimal. On appelle performance relative de H sur d le quotient : R_H (d) = H(d) / OPT(d).

Pour un problème de minimisation, R_h (d) ≥ 1. Nous pouvons aussi parler de distance à l’optimum en pourcentage avec la formule : 100*(R_H (d) – 1). La performance relative est une évaluation des heuristiques qui peut être bornée a priori (avec les tests) ou imprévisible a posteriori (après les tests).

Évaluation a priori

On appelle performance relative au pire (worst case performance ratio) P_H d’une heuristique H sa plus mauvaise performance relative sur l’ensemble des données possibles : P_H = max{R_H (d), pour tout d valide}.

Il s’agit d’une garantie de performance obtenue par analyse théorique de H. Pour cela on borne R_H (d) pour toute donnée d, puis on construit une donnée montrant que ce pire cas peut être effectivement atteint. Ce résultat est très difficile à obtenir, et n’est souvent pas possible à calculer notamment pour toutes les heuristiques ne comportant pas de caractères de choix mathématique.

Prenons un exemple d’une heuristique de minimisation avec P_H = 1,5. Cela signifie que quelles que soient les données d’entrée, l’heuristique ne donnera jamais de résultat de plus de 50% au-dessus de l’optimum global. « jamais » puisque cela a été prouvé mathématiquement.

Évaluation a posteriori : bornes inférieures

Lorsque l’évaluation des heuristiques avant exécution est impossible, il est tout de même possible d’évaluer les résultats après exécution de l’heuristique H. Nous avons vu la performance relative, mais cette méthode ne s’applique que s’il est possible de connaître l’optimum global.

On peut cependant obtenir une évaluation si on dispose d’une évaluation par défaut B(d) pour l’optimum OPT(d) avec : R_H (d) = H(d)/OPT(d) ≤ H(d)/B(d). En particulier, si H(d) = B(d), alors on a atteint l’optimum global. Il est toujours possible de trouver une borne à l’optimum global par méthode naïve ou gloutonne.

Évaluation statistique

Les évaluations des heuristiques a priori et a posteriori posent tout de même un problème : quand est-il des problèmes de très grandes tailles ? L’évaluation des heuristiques la plus simple consiste à comparer des solutions avec celles données dans des benchmarks ou des méthodes très largement répandues. La valeur de la solution, sur un grand ensemble de tests, comparée à des méthodes connues, donne une bonne approximation de l’efficacité de l’heuristique.