Optimisation multiobjectif

L'optimisation multiobjectif est une branche de l'optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d'un même problème (contre un seul objectif pour l'optimisation combinatoire classique). Elle se distingue de l'optimisation multidisciplinaire par le fait que les objectifs à optimiser portent ici sur un seul problème.

Les problèmes multiobjectifs ont un intérêt grandissant dans l'industrie. où les responsables sont contraints à tenter d'optimiser des objectifs contradictoires. Ces problèmes peuvent être NP-complets même si la version mono-objectif ne l'est pas (c'est le cas du problème d'affectation par exemple). Leur résolution en des temps raisonnables devient nécessaire et alimente une partie des chercheurs travaillant dans la recherche opérationnelle.

Présentation

Pour prendre un exemple assez proche de monsieur « tout le monde », supposons que vous vous apprêtiez à partir en voyage en Tunisie. Vous pouvez partir à pied ou en auto-stop, économisant ainsi votre monnaie au détriment de la durée, ou alors partir en première classe dans un avion sur une compagnie luxueuse, profitant ainsi d'un temps de voyage minimum, au détriment de votre porte monnaie. Ou encore, vous pouvez trouver une combinaison intermédiaire (vélo, train puis bateau puis voiture, etc.).

D'un point de vue mathématique, un problème linéaire d'optimisation multiobjectif se décrit ainsi :

soit le vecteur des variables de notre problème. On cherche à résoudre :

• « opt »  : m est le nombre d'objectifs à optimiser.
• sous contrainte AX = b.

A est la matrice des coefficients, opt indique le sens de l'optimisation : maximiser ou minimiser (cela peut être différent pour chaque objectif) et b (retrouver son nom).

Continuons sur l'exemple. Vous souhaitez rejoindre Tunis en partant de Paris. Vous avez accès aux moyens de transports suivants :

Si l'on considère dans un graphique le coût et la durée de chaque combinaison de transports pouvant vous amener à Tunis, on obtient les points suivants : (faire un dessin)

Approche naïve

• combinaison des objectifs
• introduire le décideur

Pour en revenir à l'exemple : ce qu'il est important de comprendre, c'est que c'est bien vous qui êtes le seul à pouvoir décider du compromis entre le confort et le coût de votre voyage.

Qualités des solutions recherchées

Nous l'avons vu ci dessus, il est impossible de définir ce qu'est la valeur optimale d'un problème d'optimisation multiobjectif en toute généralité. À vrai dire, d'une manière générale, il y a un ensemble de valeur optimales, formant une frontière de Pareto.

Pour déterminer si une solution est meilleure qu'une autre, il convient de définir une notion de dominance :

Soit X et Y deux solutions. On dira que X domine Y si, pour tout objectif j, on a , avec au moins une inégalité stricte.

On distingue ensuite deux types de solutions optimales :

• les solutions supportées sont celles dont l'image se situe sur la fermeture convexe de l'ensemble des solutions ; on peut les trouver en résolvant des combinaisons linéaires des objectifs.
• solutions non supportées sont plus difficiles à trouver. Elle ne sont pas sur la fermeture convexe, mais ne sont pas dominées pour autant.

En définissant le critère de dominance dans l'espace des objectifs, on a tendance à oublier que plusieurs solutions peuvent avoir les mêmes coordonnées. Il s'agit alors de plusieurs combinaisons de valeurs des paramètres x_i qui mènent à des valeurs d'objectifs similaires et donc à un même point dans l'espace des objectifs. Il convient alors de définir quel type d'ensemble de solutions on recherche :

• l'ensemble complet minimal ne contient qu'une seule solution pour chaque point non dominé dans l'espace des objectifs ;
• l'ensemble complet maximal contient toutes les solutions équivalentes pour chaque point non dominé dans l'espace des objectifs.

+ une image représentant la frontière de Pareto avec tous les types de points présentés ci-dessus

• Portail des mathématiques