Optimisation multiobjectif

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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 X = (x_1, \dots, x_n), x_i \in N \forall i \in \{1, \dots, n\} le vecteur des variables de notre problème. On cherche à résoudre :

  • « opt » f^j(X), j \in \{1, \dots, m\} : 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 :

Transport Départ Destination Prix Durée
Taxi Chez vous Gare 0 0
Taxi Chez vous Aéroport 0 0
Bus Chez vous Gare 0 0
Bus Chez vous Aéroport 0 0
Avion Paris Tunis 0 0
Avion Paris Marseille 0 0
Train Paris Marseille 0 0
Bateau Marseille Tunis 0 0

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)

Qualités des solutions recherchées[modifier | modifier le code]

Nous l'avons vu ci dessus, il est impossible de définir la valeur optimale d'un problème d'optimisation multiobjectif en toute généralité. Il existe plutôt un ensemble de valeurs 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 z^j(X) \le z^j(Y), 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. Elles 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.