Composantes d’un problème d’optimisation multicritère

La plupart des problèmes d’optimisation combinatoire issus des problèmes réels impliquent plusieurs critères (objectifs), on parle alors de problèmes de décision multicritères ou d’optimisation multicritère. De plus, ces critères sont généralement incommensurables et contradictoires (e.g. minimiser les coûts et maximiser la productivité). L’optimisation multicritère apparaît donc comme un outil d’aide à la décision, conçu pour satisfaire des besoins conflictuels.

Commençons par détailler les composantes [Grabisch, 2005b] d’un problème d’optimisation multicritère. L’ensemble des alternatives (objets ou actions) est l’ensemble des solutions potentielles d’intérêt pour le décideur. Cet ensemble peut être décrit en extension en énumérant les solutions dans une liste finie, ou en compréhension en explicitant un ensemble de contraintes caractérisant les solutions. Chaque alternative est décrite par un ensemble d’attributs (descripteurs ou points de vue) spécifiant ses caractéristiques mesurables. Un critère est l’association d’une préférence sur les valeurs possibles de l’attribut. Différentes approches de décision multicritère ont vu le jour, en combinant une opération de comparaison et une opération d’agrégation. Nous détaillerons ces éléments de base dans la suite de cette section.

Notion de préférence et de fonction d’utilité

Le concept de décision est difficilement séparable de celui de préférence. Les préférences sont l’expression, de la part d’une personne confrontée à une situation de choix, de l’attrait que présente chaque alternative envisageable [Lumet, 2012]. Les préférences apparaissent dans plusieurs domaines, comme l’économie, la psychologie, les sciences politiques, les statistiques, etc.

La notion de préférence dépasse bien le cadre d’une simple décision. En économie par exemple, les préférences reflètent le prix qu’une personne peut payer afin d’obtenir un objet [Bouyssou et Vincke, 2006]. En psychologie, elle s’interprète comme l’attitude d’une personne face à un ensemble d’objets.

L’un des principaux sujets qui ont émergé dans le domaine de la recherche de décision comportementale [Lichtenstein et Slovic, 2006], au cours des trois dernières décennies, est le traitement des préférences des décideurs. Ces préférences sont souvent construites suivant un processus d’élicitation utilisant des algorithmes et des procédures cognitives de recherche des préférences du décideur.

Les préférences d’un décideur (définies sur un ensemble fini d’alternatives) portent une sémantique particulière. Ces préférences peuvent être représentées de différentes manières, exprimées sous la forme d’une relation mathématique binaire sur les alternatives.

Décision multicritère

La décision multicritère traite des problèmes liés à plusieurs points de vue ou attributs. Par exemple, considérons une situation d’un décideur face à une problématique d’achat d’un appareil photo numérique. L’ensemble des alternatives est celui des appareils photo numérique disponibles dans le commerce. Au fait, un appareil photo numérique est caractérisé par plusieurs attributs, à savoir le nombre de méga-pixels, le poids, la plage de zoom maximal, etc. Ainsi, le décideur est amené à raisonner sur ces attributs pour se fixer sur son achat. Plus généralement, nous avons besoin de définir la notion d’attributs .

Dans cette thèse, nous considérons les méthodes de type « agréger puis comparer ». Nous supposons, sans perte de généralité, que chaque critère est à maximiser du point de vue du preneur de décision (DM). Dans le processus de décision multicritère de type « agréger puis comparer », le problème multicritère est transformé en un problème monocritère, en utilisant une fonction d’agrégation, afin de bénéficier des méthodes classiques d’optimisation mono-critère. Ainsi, nous supposons l’existence d’une fonction d’utilité globale U qui représente la relation de préférence globale ≥, que tout DM tente de maximiser  ∀a, b ∈ A, a ≥ b ⇔ U(a) ≥ U(b).

Cette fonction d’utilité globale U doit dépendre seulement des critères U(a) = f(a1, …, an). Cette fonction d’agrégation permet au décideur de trouver une bonne solution de compromis selon ses préférences. On se pose ainsi la question clé : quelle est la fonction d’agrégation la mieux adaptée ? et comment la paramétrer ? La réponse à cette question dépendra nécessairement des propriétés des critères et de la relation de préférence globale .

Les préférences du décideur sont implicitement ou explicitement traduites en termes de paramètres de la méthode multi-objectif choisie (cf., [Delecroix et al., 2012 ; Boutilier et al., 2010 ; Escoffier et al., 2008 ; Roy et Bouyssou, 2002]). Ensuite, la fonction d’agrégation est combinée avec les paramètres acquis pour résoudre le problème multiobjectif, et obtenir la solution de meilleur compromis du point de vue du décideur. Il existe de nombreuses méthodes d’agrégation multicritère pour résoudre des problèmes de décision. Cependant, le choix le plus approprié d’une méthode multicritère bien adaptée à un problème multicritère est subjectif (cf. [Grabisch et al., 1997]), et est lui même un problème compliqué.

De la littérature on peut relever deux méthodes principales liées à deux points de vue opposés : la fonction Somme et la fonction Minimum, correspondant respectivement aux concepts d’utilitarisme classique et égalitarisme  . L’approche utilitariste traite l’aspect multicritère du problème avec une approche de scalarisation simple et efficace, avec laquelle on agrège toutes les fonctions objectifs pour former un problème avec une seule fonction objectif (appelée fonction d’agrégation). Ainsi, une décision optimale est l’une de celles qui maximisent cette fonction. Cependant, ce genre de fonctions d’agrégation n’est pas très pertinent dans le contexte du partage “équitable” [Nieto, 1992 ; Moulin, 2004].

Par contre, la deuxième approche (égalitariste) est spécialement bien adaptée aux problèmes pour lesquels la propriété d’équité joue un rôle central. Cette approche est utilisée surtout en décision multi-agents [Burkard et al., 2009], où les critères représentent les préférences de différents agents (e.g., problème de partage d’un ensemble fini de ressources entre plusieurs agents). Suivant la fonction Minimum, une décision optimale est celle qui maximise la satisfaction de l’agent le moins satisfait. Néanmoins, cette fonction d’agrégation est entravée par l’effet de noyade [Dubois et Fortemps, 1999], puisqu’elle ne peut pas distinguer entre des solutions ayant la même composante minimale. Ainsi, par exemple, les deux solutions (alternatives) h0, 1, 1, 1i et h1000, 1000, 1000, 0i, pourtant très différentes, sont indiscernables suivant la fonction Minimum. Cette fonction peut toutefois être modifiée pour avoir un comportement plus expressif. L’idée clé consiste à proposer des raffinements du Minimum, e.g., les opérateurs Discrimin et Leximin, la norme de Chebycheff, etc. Le but étant de réduire l’ensemble des alternatives indifférentes et d’assurer la propriété d’efficacité.