Calcul exact d'hypervolume exclusif pour l'optimisation multi-objectif

Session : SS2-1 / SS2 : Application et théorie de l’optimisation multiobjectif
Mercredi 10 février 11:00 - 12:20 Salle : RP8
Arthur Chambon, Matthieu Basseur et Frédéric Saubion

Nombre de problèmes combinatoires pratiques relèvent de l’optimisation multicritères puisqu’en réalité le décideur doit bien souvent atteindre un compromis entre plusieurs objectifs (coût économique, impact environnemental, délais de production...). Ces objectifs sont souvent contradictoires et peu ou non corrélés. Il est dès lors difficile de pouvoir comparer deux solutions. Intuitivement, la notion de dominance au sens de Pareto semble simple mais comme il s’agit d’une relation non totale sur l’ensemble des solutions, plusieurs solutions peuvent être non dominées au sens de Pareto (i.e., non comparables). Cet ensemble constitue le front de Pareto dont le calcul est souvent difficile. Afin de l’approximer rapidement il est possible d’utiliser des algorithmes de type heuristiques. Ainsi, pour déterminer si un sous-ensemble du front de Pareto est meilleur qu’un autre, plusieurs indicateurs sont proposés, dont celui de l’hypervolume. Cet indicateur consiste simplement à calculer le volume dominé par le sous-ensemble trouvé. Cependant, le calcul de l’hypervolume est non polynomial. Le travail présenté ici consiste à trouver un moyen d’améliorer les algorithmes heuristiques de calcul du front Pareto en déterminant quelle solution contribue le moins à l’hypervolume dominé. L’objectif étant de retourner un sous-ensemble du front maximisant l’hypervolume dominé. Pour cela, nous introduisons la notion d’hypervolume exclusif, ou contribution d’un point, comme étant l’hypervolume dominé par un point et par lui seul.

Mots clés :