Modèles décisionnels dépendants du rang et des points de référence

La dominance de Lorenz

   La dominance de Lorenz permet d’introduire une notion de compromis plus poussée en privilégiant des solutions ayant des profils équilibrés entre les objectifs. Cette propriété est intéressante dans différents contextes. En décision multi-agents, il peut sembler naturel pour un décideur de rechercher une solution permettant un traitement équitable entre les différents agents considérés dans la décision. En decision dans l’incertain, en l’absence d’information sur la distribution de probabilités, il peut sembler pertinent de privilégier des profils de solutions ayant une performance similaire entre les différents scénarios. Dans des contextes impliquant plusieurs critères d’importance similaire pour le décideur, on recherche souvent des solutions ayant un profil équilibré entre ces derniers. Dans un contexte où l’ensemble des composantes sont de même importance, on peut alors s’intéresser au principe de transfert pour modéliser une préférence pour des solutions équitables

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

    La dominance stochastique du second ordre permet de généraliser l’utilisation des composantes de Lorenz à la présence d’une pondération sur les objectifs. Dans de nombreux contextes, on dispose d’une information de pondération qu’il est nécessaire de prendre en compte afin d’identifier un sous-ensemble de solutions intéressantes  pour le décideur. En décision multicritère, les différents critères peuvent être d’importance différente selon le contexte (par exemple, une entreprise en difficulté pourrait avoir tendance à mettre plus d’importance sur le coût de son produit que sur sa qualité). En décision multi-agents, les différents agents peuvent se voir accorder des importances différentes (en fonction de leur participation au projet ou de leur budget). En décision dans le risque et l’incertain, toute information sur la probabilité de réalisation des scénarios peut alors être prise en compte pour renforcer la robustesse de la décision.

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

   L’agrégation est une tâche consistant à combiner différentes composantes de même nature (performances, relations de préférences, relations binaires, évaluations partielles) afin d’obtenir une évaluation globale synthétisant l’information contenue dans chacune d’elles. Par exemple, dans un cadre multicritère, on agrège les performances de l’ensemble des critères afin d’obtenir une évaluation de la performance générale de l’alternative permettant alors d’établir une relation de préférence. En décision collective, la préférence de chaque agent est agrégée afin d’obtenir une préférence collective. Cette approche permet alors de mettre en place une règle d’agrégation permettant d’établir une relation de préférence plus discriminante que la dominance de Pareto, de Lorenz ou encore que la dominance stochastique du second ordre. De plus, de telles règles permettent souvent de proposer une modélisation des préférences du décideur afin de guider la décision et de lui proposer une solution optimale selon ces dernières.

Génération de l’ensemble de Pareto

   Dans ces approches, on cherche à générer, partiellement ou intégralement, les solutions de l’ensemble de Pareto. Cette méthode peut alors être utilisée pour réduire l’ensemble des solutions aux seules solutions Paretooptimales, permettant de réaliser un pré-filtre à la recherche d’une solution par d’autres approches ou simplement de proposer au décideur de choisir la solution qu’il préfère parmi cet ensemble. Cette approche ne nécessite l’utilisation d’aucune information préférentielle du décideur car elle repose simplement sur la notion de dominance de Pareto (voir 1.2, page 19). Néanmoins, ces approches présentent plusieurs limites à leur utilisation. Dans un premier temps, l’ensemble de Pareto peut être trop large pour permettre d’être généré intégralement. Rosinger [1991] montre que le nombre de cas d’incomparabilité entre alternatives croît avec le nombre d’objectifs ((5, -2) domine (4, -3) alors que (5, -2, 1) et (4,-3, 2) sont incomparables au sens de Pareto). Le nombre de solutions Pareto-optimales augmente donc rapidement avec le nombre d’objectifs.

Optimisation de fonctions d’agrégations non linéaires

   Malgré la difficulté de cette approche, l’utilisation de fonctions d’agrégation dans des contextes d’optimisation multi-objectifs sur domaine implicite permet de se ramener à un problème d’optimisation mono-objectif tout en prenant en compte les préférences du décideur. Nous proposons ici différentes approches ayant permis l’utilisation de fonction d’agrégation dans de tels contextes tout en contournant les limitations précédemment présentées. Nous présentons dans un premier temps différentes approches d’optimisation multiobjectifs lorsque les préférences sont représentées par le modèle OWA. Un premier modèle computationnel a été proposée par Ogryczak et Śliwiński [2003], utilisant la formulation de l’agrégateur par les composantes de Lorenz (proposition 1.1, page 29) pour formuler un problème d’optimisation OWA-optimal par un programme linéaire. Cette approche fait donc l’hypothèse que les préférences du décideur sont monotones avec la dominance de Lorenz généralisée (définition 1.7, page 21). Une seconde approche, proposée par Chassein et Goerigk [2015], permet de reformuler un problème d’optimisation OWA-optimal par un programme linéaire, lorsque les préférences sont monotones avec la dominance de Lorenz généralisée. Cette approche permet une diminution significative du nombre de variables et de contraintes ajoutées pour linéariser l’opérateur face à celle proposée par Ogryczak et Śliwiński [2003]. Dans un cadre plus général, Boland et al. [2006] ont proposé une linéarisation de l’opérateur OWA sans faire d’hypothèse sur les préférences du décideur (et ainsi sans se restreindre à des classes de jeux de poids w particuliers). Dans cette formulation, des variables binaires sont alors introduites pour modéliser la permutation appliquée aux composantes. L’ajout de variables binaires n’étaient pas nécessaire dans les deux approches précédente. Par ailleurs, différentes approches d’algorithmique discrète ont été proposées pour l’optimisation en présence de l’opérateur OWA. Galand et Spanjaard [2012] ont proposé un algorithme combinatoire pour la résolution du problème d’arbres couvrants multi-objectifs lorsque les préférences du décideur sont représentés par le modèle OWA. Chassein et al. [2020] ont proposé un algorithme approché garantissant un ratio d’approximation dans le pire cas pour l’optimisation OWA-optimale en s’appuyant sur une réduction du nombre de scénario en pré-traitement de l’optimisation. Ogryczak et Śliwiński [2007] se sont intéressés au modèle Weighted OWA [Torra, 1997], extension de l’OWA à la prise en compte d’une pondération sur les objectifs et modèle proche du modèle Rank Dependant Utility dans la décision dans le risque (voir définition 3.2, page 92). Cette approche reformule cet agrégateur en s’appuyant sur une extension pondérée des composantes de Lorenz, en faisant l’hypothèse que le décideur privilégie des solutions ayant un profil équilibré. De plus, différentes approches ont cherché à tirer parti de l’expressivité de l’intégrale de Choquet dans de tels contextes. Lesca et Perny [2010] ont proposé un premier modèle computationnel, se fondant respectivement sur une formulation de l’intégrale de Choquet par les masses de Möbius et par les probabilités du coeur pour formuler deux programmes linéaires (pour plus de détail voir section 2.1.1, page 52). Ces approches permettent une reformulation d’un problème d’optimisation Choquet optimal par un programme linéaire et peuvent être adaptées à de nombreux problème d’optimisation multi-objectifs sur domaine implicite pouvant se formuler par un programme mathématique linéaire (avec variables entières ou non). Néanmoins, souvent efficaces en pratique, ces approches demeurent limitées lorsque le nombre d’objectifs augmente, le nombre de variables et contraintes ajoutées afin de linéariser l’agrégateur dépendant souvent directement du nombre de points de vue considérés. D’autres méthodes de résolution peuvent être utilisées. Dans un premier temps, des procédures reposant sur une énumération ordonnée des solutions et une méthode de coupe ont été proposées [Galand et Perny, 2006, 2007]. Dans ces dernières, la résolution s’appuie sur une borne supérieure linéaire de la fonction d’agrégation pour énumérer les solutions et s’assurer que la solution retournée est bien optimale au sens des préférences du décideur (pour plus de détail voir algorithme 3.1 page 89). Reposant également sur l’utilisation d’une borne supérieure, des approches de type Branch&Bound ont également été proposées par Galand et al. [2010] pour l’optimisation Choquet-optimale. L’intégrale de Choquet a aussi été considérée pour représenter les préférences d’un décideur dans des modèles computationnels reposant sur des algorithmes génétiques [Magoč et Modave, 2014; Islam et al., 2019]. [Timonin, 2012a] ont proposés une approche exploitant une décomposition de l’intégrale de Choquet comme le maximum d’intégrales de Choquet avec des fonctions de croyance pour capacités. Ces derniers ont aussi proposés une seconde approche pour optimiser l’intégrale de Choquet sur un ensemble convexe, appliqués à des problèmes d’allocation de ressources, et reposant sur une décomposition de l’intégrale de Choquet et des méthodes de projection de gradient (dans le cas ou l’ensemble des solutions est convexe) [Timonin, 2012b]. Le problème de l’optimisation d’une intégrale de Choquet avec une capacité définie de manière imprécise est étudié dans [Timonin, 2013]. Au cours de ce chapitre, nous avons présenté plusieurs attitudes décisionnelles permettant de privilégier une solution ayant un profil équilibré entre les objectifs, comme la monotonie avec la dominance de Lorenz généralisée (théorème 1.1, page 21) ou encore la préférence pour les points intérieurs (définition 1.21, page 32). Il est fréquent de vouloir développer des modèles d’optimisation sur domaine implicite privilégiant de telles solutions et différents modèles computationnels présentés dans ce rapport feront des hypothèses similaires sur les préférences du décideur. Dans un cadre général, on parlera d’optimisation équitable pour désigner des problèmes d’optimisation où l’on cherche à privilégier des solutions ayant une forme d’équilibre ou d’équité entre les objectifs. Les différentes approches présentées dans cette section font l’hypothèse que les préférences du décideur sont connues avant la recherche d’une solution optimale par le modèle computationnel proposé. C’est une hypothèse forte et dans certains contextes, ces dernières doivent être élicitées afin de permettre la recommandation d’une solution optimale selon le décideur. Nous nous intéressons maintenant aux approches permettant d’éliciter les préférences d’une décideur, avant la recherche d’une solution optimale ou au cours de cette dernière.

Elicitation du paramètre du modèle décisionnel à partir d’exemples

   Dans ces méthodes, on commence par récolter un ensemble d’informations préférentielles, qui est ensuite utilisé pour estimer les préférences du décideur selon un modèle décisionnel donné. On peut alors scinder cette approche en deux phases :
– élicitation : Analyse des informations préférentielles obtenues afin de déterminer des valeurs de paramètres permettant de représenter ses préférences.
– résolution : Utilisation du modèle décisonnel représentant les  préférences du décideur afin d’aider le décideur dans son problème décisionnel
Ces procédures tentent alors de déterminer les paramètres ω d’une fonction d’agrégation fω expliquant au mieux les informations recueillies auprès du décideur. Par exemple, la méthode UTA (UTilité Additive) [Jacquet-Lagreze et Siskos, 1982] apprend une fonction d’utilité additive par programmation linéaire à partir d’une base de données contenant des informations ordinales recueillies auprès du décideur. Nous présentons ici des méthodes similaires pour l’apprentissage de paramètres de modèles décisionnels. Dans un premier temps, elles se distinguent par la nature des données exploitées. Les informations préférentielles obtenues peuvent être constituées d’un petit ensemble d’alternatives (pouvant être fictif), d’informations de dominance ou encore d’intensités de préférence entre différentes alternatives. Ces données collectées sont ensuite utilisées pour contraindre le modèle décisionnel, en se fondant sur l’utilisation d’une fonction de coût permettant d’évaluer la fidélité des préférences modélisées face aux informations préférentielles obtenues. Par exemple, il a été proposé de minimiser des écarts d’utilité [Jacquet-Lagreze et Siskos, 1982; Sobrie et al., 2018] ou encore de minimiser un critère d’erreur quadratique [Mori, 1989; Grabisch et al., 1995; Meyer et Roubens, 2006] similairement à ce qui est utilisé classiquement en apprentissage supervisé. Cette fonction de coût sert alors à identifier les différents jeu de paramètre ω compatibles avec la base de données préférentielles. Signalons que certains logiciels d’optimisation mettent actuellement en oeuvre ces techniques d’élicitation [Marichal et al., 2005; Grabisch et al., 2008]. Le processus d’élicitation ne dépend pas ici des alternatives du problème que l’on cherche à résoudre mais d’un ensemble d’informations obtenu préalablement. Les préférences apprises lors de ce processus peuvent alors être réutilisées pour aider le décideur dans d’autres problèmes décisionnels ou pour résoudre d’autres instances du même problème, sans nécessiter l’utilisation d’interactions supplémentaires avec le décideur. Néanmoins, les informations préférentielles fournies impactent alors fortement l’efficacité du procedé d’élicitation : plus ces dernières sont riches, mieux les préférences sont approchées. Cependant, en considérant un plus grand nombre d’informations préférentielles, le risque de rencontrer des incohérences dans ces dernières devient plus élevé. De plus, l’élicitation des préférences et la résolution du problème décisionnel considéré sont séquentiels dans ces approches. Ainsi, si la recommandation fournie au décideur ne lui convient pas, il n’est pas possibile d’interagir avec lui afin d’ajuster les préférences apprises pour l’instance considérée. Il est important de noter que l’objectif d’une procédure d’élicitation des préférences n’est pas nécessairement de déterminer le jeu de paramètre modélisant les préférences du décideur de manière précise. En effet, dans certains contextes, il suffit de réduire l’incertitude de manière suffisante afin de pouvoir proposer une recommandation optimale pour le décideur pour le problème décisionnel considéré. On peut alors s’intéresser à des approches ne considérant qu’un ensemble d’informations préférentielles nécessaires pour trouver une solution optimale selon notre décideur dans un problème décisionnel donné. On présente alors des approches entremêlant recherche d’une solution et élicitation afin de trouver une solution optimale selon les préférences du décideur à un coût computationnel et cognitif minimal.

Table des matières

Introduction
1 Modélisation de préférences, optimisation et élicitation en présence de plusieurs objectifs et points de référence dans les préférences d’un décideur 
1.1 Introduction
1.2 Optimisation multi-objectifs fondée sur des modèles de décision 
1.2.1 Problème de décision
1.2.2 Règles de dominance
1.2.3 Agrégation et modélisation des préférences
1.3 Optimisation en présence de plusieurs objectifs
1.3.1 Un aperçu des approches standards
1.3.2 Utilisation d’une fonction d’agrégation
1.4 Élicitation des préférences 
1.4.1 Elicitation du paramètre du modèle décisionnel à partir d’exemples
1.4.2 Elicitation incrémentale
1.5 Utilisation de points de références dans un modèle décisionnel 
1.6 Conclusion du chapitre 
2 Modèles computationnels pour l’intégrale de Choquet et son extension bipolaire 
2.1 Programmation mathématique pour l’intégrale de Choquet 
2.1.1 Modèles computationnels classiques pour l’intégrale de Choquet
2.1.2 Programmation mathématiques et génération de contraintes
2.2 Intégrale de Choquet bipolaire et programmation mathématique 
2.2.1 Définition du modèle de l’intégrale de Choquet bipolaire
2.2.2 Modèles computationnels pour l’intégrale de Choquet bipolaire
2.3 Conclusion du chapitre 
3 Cas particuliers de l’intégrale de Choquet bipolaire et modèles computationels d’optimisation équitable sur domaine implicite 
3.1 Le modèle biOWA pour l’optimisation équitable en présence d’échelles de valuations bipolaires
3.1.1 biOWA : un OWA pour les échelles bipolaires
3.1.2 Optimisation équitable et biOWA
3.2 Optimisation dans un contexte de risque en présence de gains et de pertes 
3.2.1 Cumulative Prospect Theory : un modèle décisionnel dans le risque pour la prise en compte des gains et des pertes
3.2.2 Modèles computationnels pour l’optimisation CPT-optimale
3.3 Conclusion du chapitre 
4 Élicitation incrémentale de préférences avec des intégrales de Choquet bipolaires 
4.1 Introduction 
4.2 Elicitation incrémentale d’une intégrale de Choquet bipolaire par minimisation des regrets 
4.3 Élicitation incrémentale du modèle Cumulative Prospect Theory par minimisation des regrets 
4.4 Élicitation incrémentale du modèle biOWA par minimisation des regrets 
4.5 Elicitation d’une intégrale de Choquet bipolaire avec bicapacité
4.6 Conclusion 
5 Amélioration de coût minimal et stabilité de gain maximal dans des méthodes de tri multicritère sur domaine combinatoire 
5.1 Introduction
5.2 Méthode de tri multicritère
5.3 Problèmes d’optimisation et formulations par des programmes mixtes
5.3.1 Le problème d’amélioration de coût minimum
5.3.2 Le problème de stabilité de gain maximum
5.3.3 Le problème de séquence améliorante de coût minimum
5.3.4 Formulations par des programmes mixtes
5.4 Quelques applications 
5.4.1 Un problème de transport
5.4.2 Un problème d’affectation
5.4.3 Un problème de sac à dos
5.5 Conclusion 
Conclusion

Télécharger le rapport complet