Élicitation des préférences fondée sur la minimisation directe des regrets

Télécharger le fichier original (Mémoire de fin d’études)

Optimisation multi-objectifs fondée sur des mo-dèles de décision

Un problème de décision multi-objectifs est caractérisé par la prise en compte ex-plicite de plusieurs objectifs à optimiser. On le définit de la manière suivante : on dis-pose d’un ensemble de solutions X défini explicitement (par exemple par un ensemble d’actions, d’objets ou de candidats) ou implicitement (par exemple, à l’aide d’un en-semble de contraintes linéaires sur des variables de décision). Dans le second cas, X contient un nombre exponentiel de solutions réalisables. L’ensemble X = X1 × • • • × Xp est appelé espace des solutions, et sa dimension p dépend du problème traité. Généra-lement, Xi ⊆ Rc, ∀i ∈ {1, . . . , p}, avec c ∈ N \ {0}. Toute solution x ∈ X s’écrit alors x = (x1, . . . , xp) et son évaluation selon les n objectifs considérés est donnée par son vecteur de performances noté u(x) = (u1(x), . . . , un(x)). Notons N = {1, . . . , n} l’ensemble des objectifs. Selon le contexte, la composante ui(x), i ∈ N, représente :
– la performance de la solution x sur le critère i (décision multicritère),
– la performance de la solution x pour l’agent i (décision multi-agents),
– la performance de la solution x dans le scénario i (décision dans le risque ou dans l’incertain).
Dans tous les cas, on définit l’image de X dans l’espace des objectifs par Y = {u(x) ∈ Rn, ∀x ∈ X }. La formulation précise du problème de décision multi-objectifs dépend ensuite de la problématique étudiée. Les trois problématiques principalement étudiées en aide à la décision sont [Roy, 1985] :
– le choix, ou la détermination d’une solution préférée,
– le tri, ou la répartition des solutions réalisables selon différentes catégories ou classes,
– le rangement, ou le fait d’ordonner toutes les solutions selon un ordre de préférences. Dans cette thèse, nous nous focalisons sur la problématique du choix qui consiste à déter-miner une solution préférée parmi l’ensemble des solutions de X . Dans ce cas, le problème de décision s’écrit : opt1 u1(x)
opt n )
x n(ou u(x) ∈ X ∈ Y
où opti désigne la maximisation ou la minimisation de ui(x) dans X . Dans le reste du do-cument (sauf mention contraire), nous supposerons que les objectifs sont tous à maximiser, i.e., opti = max, ∀i ∈ N. Cette hypothèse n’est pas restrictive puisque toute opération de minimisation peut être ramenée à une opération de maximisation par un simple chan-gement de signe. L’objectif est donc de trouver une solution x qui maximise au mieux chacun des n objectifs. Du fait de la nature souvent conflictuelle des objectifs, il arrive très souvent qu’améliorer la performance d’une solution sur un objectif dégrade sa perfor-mance sur un autre objectif (par exemple, améliorer la qualité d’un produit implique très souvent une augmentation de son prix). En d’autres termes, une solution optimale pour un objectif donné peut être largement battue sur un autre objectif. Il est donc très rare en pratique qu’il existe une solution qui optimise simultanément les n objectifs. L’exemple suivant illustre ce propos :
Exemple 1.1. Supposons que l’on dispose d’un ensemble de solutions dont les vecteurs de performances sont représentés par des ronds dans l’espace bi-objectifs de la figure 1.1. On peut facilement voir sur cette figure que les deux solutions dont les vecteurs de perfor-mances sont représentés par des ronds blancs optimisent chacune l’un des deux objectifs mais offrent une performance médiocre pour l’autre objectif. D’autre part, il est impos-sible de dire objectivement que l’une des solutions est meilleure que l’autre. Définir une préférence entre ces deux solutions dépend entièrement des préférences du décideur.
Sans informations préférentielles et sans outils supplémentaires, il est donc assez rare de pouvoir déterminer une solution optimale pour le décideur en utilisant uniquement les données du problème présentes dans la formulation (1.1). On peut tout de même On peut facilement voir sur cette figure que, par exemple, le vecteur de performances (0, 8) est Pareto-dominé à la fois par (3, 8), qui est meilleur pour le premier objectif, et par (0, 10) qui est meilleur pour le second objectif. On peut également donner l’exemple du vecteur (6, 3), qui est strictement Pareto-dominé par (6.5, 4) (meilleur sur les 2 critères à la fois). On peut également voir que pour toute solution Pareto-optimale, une amélio-ration sur un objectif se fait toujours au détriment de la performance sur l’autre objectif. Par exemple, on peut facilement trouver une solution dont le vecteur de performances est meilleur que (0, 10) sur le premier objectif, mais cette solution sera toujours moins performante sur le second objectif.
Même si la dominance de Pareto décrit un comportement rationnel, et qu’elle permet d’écarter des solutions dominées et donc inintéressantes pour le décideur, elle ne consti-tue pas une relation de préférence très riche. D’une part, elle ne définit pas un ordre total sur les solutions de X . D’autre part, elle ne possède pas une capacité descriptive très importante puisqu’elle ne traduit pas de comportements décisionnels autres que la rationalité des préférences. L’ensemble de Pareto peut contenir un très grand nombre de solutions dont beaucoup peuvent ne présenter aucun intérêt réel pour le décideur. On peut par exemple constater sur la figure 1.2 que l’ensemble de Pareto contient des solutions très différentes ne pouvant pas convenir à n’importe quel type de préférences : certaines privilégient (plus ou moins) le premier objectif alors que d’autres privilégient le second, certaines ont un vecteur de performances très déséquilibré alors que d’autres ont un vec-teur de performances parfaitement équilibré. Nous présentons maintenant une relation de dominance un peu plus riche permettant de privilégier les solutions ayant un vecteur de performances équilibré lorsque l’on sait que le décideur a une préférence pour de telles solutions : la dominance de Lorenz.

La dominance de Lorenz

Il existe différents contextes où le décideur privilégie les solutions ayant un vecteur de performances équilibré. En décision multi-agents, il semble assez naturel qu’un décideur supervisant une décision collective soit à la recherche d’une solution qui permette une répartition équitable de la satisfaction des différents agents. En décision multicritère, il arrive très souvent, lorsque les critères ont tous la même importance, de vouloir trouver une solution où les performances selon les différents critères sont équilibrées. Et finalement, en décision dans le risque, lorsque les scénarios ont la même probabilité, on cherche souvent à déterminer une solution robuste qui permet d’assurer une bonne performance quel que soit le scénario qui finit par se produire. Dans ces différents contextes, la dominante de Pareto ne suffit pas à traduire la notion d’équité/équilibre/robustesse.
La dominance de Lorenz caractérise une notion d’équilibre décrite par un axiome connu sous le nom de principe de transfert de Pigou-Dalton, e.g., [Shorrocks, 1983; Moulin, 1988]. Cet axiome formalise la notion d’équilibre par une idée très simple : le transfert d’une quantité 0 < ε ≤ ui(x) − uj(x) de la performance ui(x) vers la performance uj(x) offre une meilleure répartition des valeurs de performances. Notons que cette règle de dominance vient de la mesure des inégalités concernant des distributions de revenus. Plus formellement :
Définition 1.3. (Principe de transfert) Soit une solution x ∈ X dont le vecteur de performances u(x) ∈ Y est tel qu’il existe deux indices i ∈ N, j ∈ N pour lesquels ui(x) > uj(x). Pour tout ε tel que 0 < ε ≤ ui(x)−uj(x) on a : (u1(x), . . . , ui(x)−ε, . . . , uj(x)+ε, . . . , un(x)) u(x)
Ainsi, si ui(x) > uj(x) l’amélioration de la performance uj(x) (d’une quantité ε) au détriment de la performance ui(x) donne une solution au vecteur de performances plus équilibré si la quantité ε ne dépasse pas l’écart ui(x) −uj(x) (sinon le déséquilibre est accentué). Autrement dit, un tel transfert mène à une solution plus intéressante pour un décideur ayant une préférence pour des performances équilibrées.
Exemple 1.2. Soient x et y deux solutions associées aux vecteurs de performances u(x) = (5, 5) et u(y) = (0, 10). La solution x domine la solution y au sens de la règle de dominance induite par le principe de transfert de Pigou-Dalton. En effet, il existe un transfert de valeur ε = 5 menant de y à x : u(x) = (u1(y) + 5, u2(y) − 5) = (0 + 5, 10 − 5) = (5, 5).
Par définition de ce principe de transfert, la règle de dominance qu’il induit ne peut s’appliquer qu’à la comparaison de vecteurs de même moyenne. En pratique, un grand nombre de solutions reste donc impossible à comparer. Pour remédier à cela, on peut faire appel à une règle plus générale qui consiste à combiner le principe de transfert avec la dominance de Pareto. L’exemple suivant illustre ce propos assez simplement :
Exemple 1.3. Soient x et y deux solutions associées aux vecteurs de performances u(x) = (5, 5) et u(y) = (3, 6). Ces deux solutions ont une moyenne différente et, de ce fait, aucune ne peut être obtenue à partir de l’autre en effectuant un transfert de Pigou-Dalton. Par contre, on peut facilement voir que u(x) Pareto-domine (4, 5) qui à son tour domine u(y) au sens du principe de transfert car (4, 5) = (3 + 1, 6−1). On obtient alors par transitivité que u(x) u(y).
On peut donc déterminer l’existence ou non d’une relation de dominance entre deux solutions n’ayant pas nécessairement la même moyenne en déterminant l’existence d’une séquence de dominances de Pareto et de transferts de Pigou-Dalton. Néanmoins, on pour-rait craindre que le fait de déterminer l’existence d’une telle séquence soit une opération très fastidieuse. Toutefois il n’en est rien : il existe une caractérisation simple des vec-teurs pouvant être comparés de cette manière. Cette caractérisation utilise la notion de dominance de Lorenz généralisée [Marshall et al., 1979; Shorrocks, 1983] :
Définition 1.4. Soit une solution x ∈ X associée au vecteur de performances u(x) ∈ Y. Le vecteur de Lorenz associé à la solution x est défini par L(x) = (u(1)(x), u(1)(x) + u(2)(x), . . . , u(1)(x) + • • • + u(n)(x)) où u(i)(x) est la ie plus petite composante du vecteur u(x).
La dominance de Lorenz généralisée est définie à partir des vecteurs de Lorenz :
Définition 1.5. Soient x et y deux solutions de X . On a : x %L y ⇔ L(x) %P L(y) ⇔ ∀i ∈ N, u(j)(x) ≥ u(j)(y) j=1 j=1
on dit alors que x domine y au sens de Lorenz généralisé.
De la même manière que pour la dominance de Pareto, on définit la partie asymétrique de cette relation de dominance par : x L y ⇔ (x %L y et non(y %L x))
Le théorème suivant établit le lien entre la dominance de Lorenz généralisée et le transfert de Pigou-Dalton [Chong, 1976] :
Théorème 1.1. Pour toute paire de solutions (x, y) ∈ X 2 associées aux vecteurs de performances u(x) et u(y), si x P y ou si u(x) se déduit de u(y) par un transfert de Pigou-Dalton alors x L y. Inversement si x L y alors il existe une séquence de transferts de Pigou-Dalton et/ou d’améliorations au sens de Pareto qui permettent de transformer u(y) en u(x).
Exemple 1.3 (suite). Reprenons l’exemple précédent avec les deux solutions x et y associées aux vecteurs de performances u(x) = (5, 5) et u(y) = (3, 6). Les vecteurs de Lorenz sont L(x) = (5, 10) et L(y) = (3, 9). On peut facilement voir que L(x) P L(y) ; on en déduit alors que x L y sans avoir à déterminer la séquence de relations de dominance de Pareto et de transferts de Pigou-Dalton. Ainsi, la dominance de Lorenz généralisée nous permet d’identifier des solutions sus-ceptibles d’intéresser un décideur recherchant des performances équilibrées. Notons que la relation de dominance de Lorenz généralisée respecte la dominance de Pareto puisque x P y ⇒ x L y (conséquence du théorème 1.1). Cette relation de dominance est donc, en général, plus discriminante que la dominance de Pareto. Par conséquent, l’ensemble de solutions Lorenz-optimales, défini ci-dessous, est un sous-ensemble de l’ensemble de Pareto.
Définition 1.6. L’ensemble des solutions Lorenz-optimales NDL(X ) est défini par : NDL(X ) = {x ∈ X | y ∈ X , non(y L x)}
Exemple 1.1 (suite). Reprenons l’exemple 1.1. Sur la figure 1.3 les solutions Lorenz-optimales sont représentées par des ronds blancs :
Comme la dominance de Lorenz est un raffinement de la dominance de Pareto, on peut chercher les solutions Lorenz-optimales parmi celles qui sont Pareto-optimales dans X (voir la figure 1.2). On peut voir que les vecteurs (0, 10) et (10, 0) sont dominés au sens de Lorenz par (5, 5) car (0, 0+10) = (0, 10) P (5, 5+5) = (5, 10). Il en est de même pour le vecteur (8.5, 1), qui est également dominé au sens de Lorenz par (5, 5) car (1, 9.5) P (5, 10).
Notons que même si la dominance de Lorenz est plus discriminante que la dominance de Pareto, elle ne permet tout de même pas de définir un ordre total sur les solutions de X . En effet, cette relation de dominance ne décrit qu’un principe général d’équilibre mais ne permet pas une modélisation personnalisée des préférences du décideur. L’ensemble des solutions Lorenz-optimales peut contenir un très grand nombre de solutions incomparables au sens de cette relation. La dominance stochastique du second ordre, que nous présentons dans la suite peut être vue comme une extension pondérée de cette règle permettant de caractériser une relation de dominance un peu plus riche. Cette relation offre la possibilité d’accorder plus ou moins d’importance aux différents objectifs en plus de privilégier les solutions ayant un vecteur de performances équilibré.

La dominance stochastique du second ordre (Lorenz pondérée)

La dominance de Lorenz généralisée traite symétriquement les composantes d’un vec-teur de performances : une relation de préférences de la forme x L y entre deux solutions x et y n’est pas impactée par une opération de permutation des composantes de u(x) ou de u(y) puisque les éléments de ces vecteurs sont triés (afin de déterminer les vecteurs de Lorenz) avant d’être comparés. Cette symétrie semble naturelle lorsque l’on souhaite accorder la même importance à chaque objectif, mais il peut arriver que le problème traité nécessite d’accorder plus ou moins d’importance à un ou plusieurs objectif(s). Par exemple, en décision dans le risque ou (dans l’incertain), on peut avoir la certitude (ou la conviction) qu’un scénario est bien plus probable qu’un autre. On voudrait alors prendre en compte cette information dans la modélisation des préférences ainsi que dans la ré-solution du problème en attribuant une probabilité élevée au scénario en question. Une manière d’imposer une telle notion est d’utiliser une extension pondérée de la dominance de Lorenz que l’on définit ici.
Notons tout d’abord v : 2N → [0, 1] une fonction d’ensemble qui associe un poids à chaque sous-ensemble d’objectifs. En décision multicritère ou multi-agents, ces poids représentent l’importance accordée à chaque critère/agent ainsi qu’à chaque coalition de critères/agents. Dans le cas d’un problème de décision dans le risque, ce poids représente la probabilité qu’un état (événement) ou qu’un sous-ensemble d’états se produise. On associe ensuite à chaque solution x ∈ X une fonction cumulative Fx(z) indiquant le poids de la coalition formée par l’ensemble des objectifs pour lesquels la performance de x ne dépasse pas la valeur z : Fx(z) = v({i ∈ N | ui(x) ≤ z})
On définit alors la dominance stochastique du second ordre SSD (pour Second order Stochastic Dominance) par :
Définition 1.7. Soient x et y deux solutions de X . On a : x %SSD y ⇔ ∀z ∈ R, Fx2(z) ≤ Fy2(z) où Fx2(z) = Fx(t)dt. On dit alors que x domine y au sens de la dominance SSD.
La partie asymétrique de cette relation de dominance se définit par : x SSD y ⇔ (x %SSD y et non(y %SSD x))
Notons que l’on parle généralement de dominance stochastique lorsque la fonction v représente une distribution de probabilité. Par abus de langage, on utilisera le terme dominance stochastique qu’il s’agisse de décision multicritère, multi-agents ou de décision dans le risque.
Cette règle de dominance est considérée comme étant une généralisation de la domi-nance de Lorenz car lorsque v est définie de manière à ce que les objectifs aient tous la même importance, vérifier x SSD y revient à vérifier la relation de dominance x L y. On peut définir l’ensemble des solutions non-dominées au sens de la règle de dominance SSD :
Définition 1.8. L’ensemble de solutions SSD-optimales NDSSD(X ) est défini par : NDSSD(X ) = {x ∈ X |∀y ∈ X , non(y SSD x)}
Exemple 1.1 (suite). Reprenons toujours le même exemple bi-objectifs. Supposons que l’on accorde plus d’importance au premier objectif et que la fonction v soit définie par v(∅) = 0, v({1}) = 0.6, v({2}) = 0.4 et v({1, 2}) = 1. A titre d’exemple, on donne sur la figure 1.4 les courbes Fui (z) associées à 4 vecteurs Pareto optimaux : u1 = (3, 8), u2 = (5, 5), u3 = (6.5, 4) et u4 = (8, 3).
La relation x SSD y est vérifiée si l’intégrale de Fx de 0 à z (surface sous la courbe) est inférieure à l’intégrale de Fy de 0 à z (surface sous la courbe) pour toute valeur de z. On observe alors que (8, 3) SSD (3, 8) car la courbe Fu1 (z) est au-dessus de la courbe Fu4 (z) pour toute valeur z ∈ R. Notons que les vecteurs u1 et u 4 ont le même vecteur trié ; néanmoins le fait d’accorder plus d’importance au premier objectif donne l’avantage au vecteur (8, 3) sur le vecteur (3, 8).
La figure 1.5 représente l’ensemble des solutions SSD-optimales par des ronds blancs : Notons que la définition de v ne dépend pas toujours des préférences du décideur. Par exemple, lors de la prise de décision dans le risque, plusieurs scénarios sont pris en compte : la fonction v donne alors la probabilité objective que chaque scénario (ou sous-ensemble de scénarios) se produise. Elle peut donc, selon le contexte, être déterminée indépendamment des préférences particulières du décideur.
Nous venons de présenter trois règles de dominance très utilisées lors de la comparaison de solutions évaluées selon plusieurs objectifs. Elles définissent chacune un principe géné-ral de rationalité des préférences et/ou d’exigence d’équilibre dans les performances sur les différents objectifs, en incluant ou non une pondération sur ces objectifs. Néanmoins, comme nous avons pu le voir, ces règles sont souvent trop génériques et n’offrent pas la possibilité de personnaliser le comportement décisionnel. Elles induisent un ordre par-tiel sur les solutions réalisables et, par conséquent, l’ensemble des solutions non-dominées peut être très vaste et contenir un nombre trop important de solutions à comparer pour le décideur. Afin de résoudre ce problème, l’approche la plus communément utilisée en théorie de la décision consiste à raffiner ces relations de dominance en utilisant une fonc-tion d’agrégation f permettant à la fois d’enrichir la modélisation des préférences et de simplifier la formulation du problème de décision.

CLiCours.com :  Mémoire Online: Une architecture d'un réseau sur puce (NoC) dédiée au routage de paquets

 Agrégation et modélisation des préférences

L’agrégation des préférences est une opération de synthèse de l’information contenue dans les vecteurs de performances des solutions de X , les rendant plus faciles à comparer. Lorsque l’opérateur d’agrégation est bien choisi, il permet de modéliser fidèlement les préférences du décideur et de définir une règle de dominance personnalisée, plus discrimi-nante que la relation de dominance de Pareto, de Lorenz ou de Lorenz pondérée. L’intérêt d’utiliser une telle fonction est de simplifier la formulation et la résolution du problème de décision tout en ayant une bonne structuration des préférences du décideur.
On définit généralement une règle d’agrégation à l’aide d’une fonction h : X × X → R qui associe une valeur réelle à chaque couple (x, y) de solutions possibles. Cette valeur permet de déterminer un ordre de préférence entre x et y sur la base de l’agrégation et de la comparaison de leur vecteur de performances respectifs. On définit alors une règle de dominance sur la base de cette fonction d’agrégation : x %h y ⇔ h(x, y) ≥ 0
Il existe dans la littérature deux approches distinctes pour définir une règle de dominance en utilisant une fonction d’agrégation :
– La comparaison par valeurs : cette approche, également connue sous le nom de l’approche agréger puis comparer (AC) [Perny, 2000], consiste à associer une valeur scalaire f(x) à chaque solution x ∈ X afin d’évaluer sa qualité. La comparaison de deux solutions x, y ∈ X revient alors à comparer les valeurs f(x) et f(y). On définit la fonction h par : h(x, y) = ϕ(f(x), f(y)) ≥ 0 où ϕ : R × R → R définit la manière dont on compare f(x) et f(y). Généralement, on définit cette fonction par ϕ(a, b) = a − b, ∀a, b ∈ R.
Exemple 1.4. La règle de dominance suivante entre dans le cadre de l’approche AC : x % y ⇔ ui(x) ≥ ui(y) i=1 i=1 Ici f(x) = Pni=1 ui(x), ∀x ∈ X , et ϕ(a, b) = a − b, ∀a, b ∈ R.
Notons que l’approche AC consiste à combiner les performances d’une solution selon différentes fonctions objectifs. Afin que cette opération ait du sens, elle né-cessite la commensurabilité des valeurs de performances. Or, cette hypothèse n’est pas toujours initialement respectée, c’est notamment le cas lorsque les différents objectifs représentent des critères d’évaluation de natures différentes : par exemple, certains critères peuvent être quantitatifs alors que d’autres sont qualitatifs. Dans ce cas, obtenir une nouvelle mesure des performances qui respecte l’hypothèse de commensurabilité peut poser un problème pratique. En effet, l’intérêt que le déci-deur porte aux différentes alternatives, et selon chaque objectif, n’est pas toujours linéaire. Ainsi, l’interclassement des importances accordées à chaque niveau de performances selon les différents objectifs peut différer d’un décideur à l’autre. Un processus d’interaction entre le décideur et le système de décision doit alors être mis en place afin de ramener les évaluations selon les différents objectifs sur une même échelle, ce qui peut souvent être long et cognitivement éprouvant pour le décideur. Dans cette thèse, on supposera que les valeurs de performances sont commensu-rables (par définition du problème, ou en supposant que le travail de changement d’échelle a été effectué en amont). Hormis cet inconvénient, l’approche AC offre de nombreux avantages, parmi lesquels :
– la relation %h est transitive, ce qui traduit une forme de rationalité dans les préférences que l’on modélise,
– la relation %h définit un ordre total sur les solutions de X puisque f associe à chaque solution x ∈ X une valeur dans R évaluant sa qualité.
Une telle relation permet donc de reformuler le problème de choix multi-objectifs comme un problème d’optimisation mono-objectif.
– La comparaison par vecteurs : cette approche, également appelée approche comparer puis agréger (CA) [Perny, 2000], consiste à d’abord comparer les vecteurs de performances de x et y (ou une transformation de ces vecteurs) composante par composante, puis à agréger les résultats de ces comparaisons. On écrit : h(x, y) = f(ϕ1(g1(x), g1(y)), . . . , ϕn(gn(x), gn(y))) ≥ 0 où ϕi : R×R → R désigne le ie indice de préférence entre x et y, et où gi(x) désigne une performance agrégée partielle calculée à partir de u(x). La fonction g(x) = (g1(x), . . . , gn(x)) peut être la fonction identité, une opération de permutation ou toute autre opération fondée sur un calcul impliquant uniquement les composantes de u(x) (voir les deux exemples suivants).
Ici, l’idée n’est pas (toujours) de comparer l’intensité de la différence entre les performances individuelles de x et de y mais (souvent) de déterminer l’ordre de préférence entre ces performances, comme le montre l’exemple 1.5 ci-dessous. Ainsi, l’information nécessaire sur le système de valeurs du décideur est beaucoup moins précise que dans l’approche AC, ce qui a pour avantage d’imposer au décideur un effort cognitif moins important lors de l’élicitation du modèle de préférence.
Exemple 1.5. La règle de dominance suivante entre dans le cadre de l’approche CA : x % y ⇔ ϕi(ui(x), ui(y)) ≥ 0 i=1 avec pour tout i ∈ N et pour tout a, b ∈ R : ϕi(a, b) = 1 si a > b 0 si a = b −1 sinon ci, les fonctions gi, i ∈ N et f sont définies par : gi(x) = ui(x), et∀c ∈ Rn, f(c1 n , . . . , cn) = ci i=1
Exemple 1.6. Les dominances de Pareto, de Lorenz et de Lorenz pondérée entrent dans le cadre de l’approche CA. Par exemple, la dominance de Pareto peut être définie de manière similaire à la règle de l’exemple 1.5 en remplaçant la définition de f par : f(c1, . . . , cn) = ci − n i=1
Il en est de même pour la dominance de Lorenz en utilisant la même fonction f et en définissant gi, pour tout i ∈ {1, . . . , n}, par : gi(x) = u(j)(x) j=1
Souvent, la fonction ϕi est utilisée pour comparer les performances de deux solu-tions sur un même critère (comparer ui(x) et ui(y)). Dans ce cas, cette approche ne nécessite pas que les valeurs des performances selon les différentes fonctions objectifs soient commensurables. On peut alors l’utiliser directement lorsque l’éva-luation des solutions porte, par exemple, sur des critères qui ne sont pas de même nature (certains quantitatifs et d’autres qualitatifs). Il arrive tout de même, dans certains cas, que la fonction ϕi soit utilisée pour comparer les performances de x et de y sur des objectifs différents, comme dans le cas de la dominance de Lorenz par exemple (cf. exemple 1.6 ci-dessus). Dans ce cas, la commensurabilité des valeurs de performances est évidemment nécessaire.
Dans tous les cas, une telle fonction ne garantit pas toujours la transitivité de la relation de préférences % (par exemple, la relation de l’exemple 1.5 n’est pas tran-sitive), ce qui peut poser problème lorsque l’on souhaite déterminer une solution préférée. De plus, cette approche ne définit pas toujours une règle d’agrégation in-duisant un ordre total sur les solutions de X , ce qui peut également poser problème lorsque l’on tente de résoudre une problématique de choix.
Le choix entre AC et CA dépend principalement du type de comportement décision-nel que l’on souhaite modéliser, des informations préférentielles dont on dispose, mais également du type de problème que l’on souhaite résoudre. Pour résumer, comme nous avons pu le voir plus haut, AC force la commensurabilité des valeurs de performances, la complétude et la transitivité des préférences, contrairement à CA qui ne force aucune des trois propriétés. Notons que ces propriétés nécessitent souvent la présence d’une in-formation très riche sur le système de valeurs du décideur. En particulier, les valeurs ui(x), ∀i ∈ N. Celles-ci doivent être déterminées de manière précise pour AC, alors que l’approche CA nécessite souvent uniquement une information ordinale entre deux valeurs ui(x), uj(x), i 6= j.
Dans le cadre de ce travail de thèse, on se place dans une problématique de choix. Il est donc nécessaire de disposer d’une règle d’agrégation transitive qui définit un ordre total sur les solutions de X afin de garantir l’existence d’une solution optimale. Nous nous focaliserons donc sur l’approche AC. Le problème de décision défini par 1.1 revient à un problème d’optimisation de la forme : max f(x) x ∈ X (1.2)
Dans la suite du document, nous supposons que l’on dispose des valeurs précises des performances ui(x), ∀i ∈ N et que les valeurs ui(x), uj(x), ∀i 6= j, sont commensurables (voir le paragraphe de la section 1.3 concernant l’élicitation des valeurs ui).
On se pose maintenant la question de la définition formelle de la fonction f. Celle-ci dépend entièrement de la nature et de la complexité du comportement décisionnel que l’on souhaite modéliser. De nombreux modèles décisionnels plus ou moins sophistiqués ont été proposés dans la littérature. Ces modèles vérifient des propriétés axiomatiquement garan-tissant une forme de rationalité et une bonne modélisation des préférences. On mentionne ici certaines propriétés intéressantes que l’on souhaite souvent retrouver dans un modèle décisionnel : – idempotence : une fonction f : Rp → R est idempotente si est seulement si pour tout x ∈ Rp on a : ∀i ∈ {1, . . . , n}, ui(x) = r ⇒ f(x) = r
Cette propriété traduit une idée assez intuitive qui consiste à dire que lorsque les performances d’une solution sont les mêmes pour tous les objectifs (performances équivalentes sur tous les critères, unanimité des agents, ou performance inchangée quel que soit le scénario considéré) alors la valeur agrégée du vecteur de perfor-mances doit être égale à la performance sur chaque objectif.
– monotonie : une fonction f : Rp → R est monotone par rapport à une règle de dominance R si et seulement si pour tout couple x, y ∈ Rp : x R y ⇒ f(x) > f(y)
Cette propriété signifie que les préférences représentées par f doivent refléter la notion de préférence définie par R. Par exemple, on souhaite que le modèle utilisé respecte le principe de rationalité défini par la règle de dominance de Pareto. On veut alors que la fonction f soit monotone par rapport à la dominance de Pareto. Si l’on souhaite modéliser une préférence pour les solutions ayant un vecteur de performances équilibré, on peut imposer que f soit monotone par rapport à la dominance de Lorenz.
– symétrie : une fonction f : Rp → R est symétrique si et seulement si pour tout couple x, y ∈ Rp : u(y) = σ(u(x)) ⇒ f(x) = f(y) où σ(u(x)) est une permutation des composantes du vecteur de performances u(x). Cette propriété traduit le fait que le décideur accorde la même importance aux différents objectifs considérés. Elle est pertinente lorsque l’on résout un pro-blème d’optimisation multi-agents ou d’optimisation dans l’incertain lorsque les agents/scénarios ont tous la même importance.
Le choix de la fonction d’agrégation à utiliser pour modéliser les préférences du déci-deur dépendra donc des propriétés souhaitées en fonction du comportement décisionnel du décideur. De manière générale, la monotonicité par rapport à Pareto est toujours exigée. On donne maintenant quelques exemples de modèles décisionnels issus de la littérature.

Table des matières

Introduction 
1 Modélisation et élicitation de préférences en décision multi-objectifs 
1.1 Introduction
1.2 Optimisation multi-objectifs fondée sur des modèles de décision
1.2.1 Règles de dominance
1.2.2 Agrégation et modélisation des préférences
1.2.3 Optimisation d’une fonction d’agrégation
1.3 Élicitation des préférences
1.3.1 Approche d’élicitation utilisant des exemples
1.3.2 Approche d’élicitation incrémentale des préférences
1.4 Conclusion du chapitre
2 Élicitation des préférences par réduction de l’espace des paramètres 
2.1 Introduction
2.2 Solutions potentiellement optimales et élicitation des préférences avec les modèles OWA et WOWA
2.2.1 Calcul de solutions potentiellement OWA-optimales sur domaine explicite
2.2.2 Calcul de solutions potentiellement WOWA-optimales sur domaine explicite
2.2.3 Élicitation partielle des préférences
2.2.4 Extension de l’approche sur domaine combinatoire
2.3 Combiner élication et optimisation sur domaine combinatoire avec les modèles OWA et WOWA
2.3.1 Résolution par énumération partielle des solutions du problème
2.3.2 Algorithmes de ranking pour la recherche d’une solution OWAoptimale
2.3.3 Algorithmes de ranking pour la recherche d’une solution WOWAoptimale
2.3.4 Algorithme de Branch and Bound interactif
2.4 Conclusion du chapitre
3 Élicitation des préférences fondée sur la minimisation directe des regrets
3.1 Introduction
3.2 Une approche exploitant les sommets de l’espace des paramètres
3.2.1 Programmation linéaire pour le calcul des regrets sur domaine combinatoire
3.2.2 Algorithme d’exploration et d’élicitation
3.2.3 Expérimentations numériques
3.3 Résolution de grandes instances par classes de satisfaction
3.4 Conclusion du chapitre
4 Élicitation incrémentale par mise à jour Bayésienne d’une densité de probabilité 
4.1 Introduction
4.2 Élicitation incrémentale par régression linéaire Bayésienne sur domaine explicite
4.2.1 Algorithme d’élicitation incrémentale
4.2.2 Mise à jour d’une distribution de probabilité par régression linéaire Bayésienne
4.2.3 Régression linéaire Bayésienne pour OWA et Choquet
4.2.4 Expérimentations numériques
4.3 Élicitation incrémentale par régression linéaire Bayésienne sur domaine combinatoire
4.3.1 Linéarisation de l’expression du PER par l’introduction de variables binaires
4.3.2 Algorithme de calcul du MMER
4.3.3 Amélioration du temps de calcul des regrets par clustering
4.3.4 Algorithme d’élicitation incrémentale des préférences
4.3.5 Expérimentations numériques
4.4 Conclusion du chapitre
5 Élicitation incrémentale par mise à jour Bayésienne fondée sur des polyèdres d’optimalité 
5.1 Introduction
5.2 Représentation de l’incertitude sur les pramètres préférentiels via des polyèdres d’optimalité
5.3 Algorithme d’élicitation incrémentale
5.3.1 Stratégie d’élicitation incrémentale
5.3.2 Mise à jour Bayésienne de la distribution de probabilité
5.4 Expérimentations numériques
5.5 Conclusion du chapitre
Conclusion 
A Opérations sur des distributions Gaussiennes
A.1 Produit de deux distributions Gaussiennes multivariées
A.2 Somme de deux distributions Gaussiennes multivariées

Télécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *