Evaluation des méthodes multicritères Pareto

Tests de performances

Difficulté d’évaluer les méthodes multicritères Nécessité d’une approche multi-expert Evaluation de l’algorithme sur différentes classes de problèmes Intérêt des principaux « modules » de l’algorithme d’orchestration Nous terminons cette partie avec un chapitre consacré à l’évaluation quantitative de notre algorithme d’orchestration.

Nous commençons par montrer en quoi l’évaluation des méthodes multicritères est une tâche particulièrement délicate, et discutons brièvement les approches en général adoptées dans la littérature. Nous proposons alors un cadre multi-expert dans le quels les performances de notre méthode sont mesurées selon plusieurs « points de vue ».

Nous montrons l’intérêt, selon chaque point de vue, des différents « modules » de l’algorithme d’orchestration : crossover, mutation, réparation des configurations initiales par CDCSolver, maintien de la diversité par la méthode PADE.

Evaluation des méthodes multicritères

Les méthodes multicritères récentes reposent sur la dominance de Pareto. Nous avons vu à la section 5.2 que cet ordre partiel sur l’espace de recherche empêche de comparer toute paire de configurations. Cette indécidabilité entre deux solutions se répercute, de manière décuplée, sur la comparaison des performances de métaheuristiques.

Lorsqu’on a en effet recours à des méthodes incomplètes, celles-ci ne retournent en général jamais le front de Pareto théorique du problème, mais en donnent une approximation. Se pose alors la question de comparer deux approximations PA et PB retournées par deux métaheuristiques différentes A et B. D’un point de vue formel, on serait tenté de dire que la méthode A est meilleure que B si et seulement si tout élément de PB est dominé par au moins un élément de PA.

Or cette condition est si forte qu’en pratique elle n’est, dans un sens comme dans l’autre, presque jamais observée. Il suffit qu’un seul élément de PB ne soit dominé par aucun élément de PA (et vice versa) pour que A et B soient incomparables.

La figure 11.1 représente deux approximations du front de Pareto obtenues avec deux méthodes multicritères différentes pour le même problème. A strictement parler, A et B sont incomparables : il existe des points de A non-dominés par B comme il existe des points de B non dominées par A. Il semble pourtant que l’on puisse en dire un peu plus en abandonnant le strict cadre de la dominance de Pareto. Il est en effet clair que A est meilleur que B sur 159 1

1. En outre, il existe une portion de l’espace des critères (le cône de dominance en gris) sur laquelle B domine totalement A, alors que l’inverse n’est pas vrai. Autrement dit, il existe un ensemble de fonctions scalarisantes de Tchebycheff pour lesquelles les éléments de B obtiennent une meilleure fitness que ceux de A.

Si en général deux approximations ne peuvent être comparées selon la dominance de Pareto, on peut donc choisir de les considérer selon un « point de vue » particulier. Se concentrer sur une région de l’espace des critères peut constituer un tel point de vue. Comme nous aurons l’occasion de le voir, il en existe bien d’autres.

Cette approche est celle retenue par la plupart des auteurs, qui en général ne font pas intervenir la dominance de Pareto (pour les raisons évoquées ci-dessus) dans leurs processus d’évaluation, mais proposent un certain nombre de « mesures de qualité ».

Une mesure de qualité est une fonction M (le plus souvent unaire ou binaire) sur l’ensemble des approximations, à valeurs dans R. Elle s’accompagne d’une fonction d’interprétation, en général implicite, permettant de décider, en fonction des valeurs prises par M(A) et M(B) (ou M(A,B) et M(B,A) dans le cas d’une mesure binaire), si l’approximation A est meilleure ou moins bonne que B.

Lorsque le front de Pareto théorique est connu, on peut par exemple utiliser la métrique T (appelée aussi generational distance) de Veldhuizen [vV99], qui renvoie la moyenne des distances euclidiennes entre chaque point de l’approximation et le vrai front. On rencontre de nombreuses mesures de qualité dans la littérature.

Outre la métrique T , les plus connues sont l’error ratio de Veldhuizen [vV99], les métriques S (hypervolume) et C (coverage) [ZT98b] [ZT98a] ainsi que l’epsilon indicator [ZTL+03] de Zitzler et al., et les indicateurs R1, R2 et R3 de Hansen et Jaszkiewicz [HJ97]. Certaines d’entre elles, que nous utilisons dans notre processus d’évaluation, seront détaillées à la section suivante.

Pour les autres, nous renvoyons le lecteur aux travaux de Zitzler et al. [Zit99] [ZTL+03], Knowles et al. [KFTZ05], Hansen et Jaszkiewicz [HJ97], Grosan [Gro05] ou encore Deb [DJ02]