Optimisation multiobjectif

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

L'optimisation multiobjectif ( appelée aussi Programmation multi-objective ou optimisation multi-critère ) est une branche de l'optimisation mathématique traitant spécifiquement des problèmes d'optimisation ayant plusieurs fonctions objectifs. 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 de tenter d'optimiser des objectifs contradictoires. Ces problèmes peuvent être NP-difficile. 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 :

Nécessairement k est un entier tel que , est appelé la région admissible et correspond à l'ensemble des solutions réalisables. signifie donc que est une solution réalisable ou faisable. On note l'image de par telle que . est appelé point réalisable ou encore point faisable.

Exemple:

Min  

Min  

Min  

s.t.   

   

   

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 , 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 ;
  • les 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 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.

Voir aussi[modifier | modifier le code]