Optimisation multi-objectif

Un article de Wikipédia, l'encyclopédie libre.
Cette page est en cours de réécriture ou de restructuration importante.
Vous êtes invité à en discuter en page de discussion et à participer à son amélioration en apportant des modifications.
Consultez l’historique des modifications pour voir les modifications récentes.

L'optimisation multiobjectif est 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 raisonables devient nécessaire et alimente une partie des chercheurs travaillant dans la recherche opérationnelle.

[modifier] 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 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 une graphique le coût et la durée de chaque combinaison de transports pouvant vous amener à Tunis, on obtient les points suivants : (faire une dessin)

[modifier] Approche naïve

  • combinaison des objectifs
  • introduire le décideur

Pour en revenir à l'exemple : ce qui 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.

[modifier] Qualités des solutions recherchée

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 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. 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 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

Autres langues