40
ANALYSE MULTICRIT ` ERE POUR LAIDE ` A LA D ´ ECISION ANTOINE ROLLAND , Universit ´ e LYON II 18 emes journ´ ees GDR MACS St-Etienne, 11 octobre 2013

Agregation Multicritere Rolland STP

Embed Size (px)

DESCRIPTION

Agregation Multicritere Rolland STP

Citation preview

  • ANALYSE MULTICRITE`RE

    POUR LAIDE A` LA DECISION

    ANTOINE ROLLAND , Universite LYON II

    18emes journees GDR MACSSt-Etienne, 11 octobre 2013

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    BIBLIOGRAPHIE

    Quelques ouvrages en francais pour une premie`re approchePh Vincke, LAide Multicrite`re a` la Decision, Editions deUniversite de Bruxelles - Editions Ellispses , 1989B. Roy et D. Bouyssou, Aide Multicrite`re a` la Decision :Methodes et Cas, Economica 1993D. Bouyssou, D. Dubois, M. Pirlot, H. Prade, Concepts etmethodes pour laide a` la decision, 3 volumes, Herme`s2006M. Grabisch and P. Perny. Agregation multicrite`re. InLogique floue, principes, aide a` la decision, B.Bouchon-Meunier, C. Marsala (eds), Herme`s, 2003

    A. Rolland analyse multicrite`re pour laide a` la decision 2 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    PRENDRE UNE DECISION EST DIFFICILE QUAND...

    il y a trop de possibilites a` comparer Optimisationcombinatoireil y a plusieurs decideurs Theorie du Choix Socialles consequences des actes ne sont pas suresDecision dans lincertainplusieurs crite`res rentrent en compte aide multicrite`rea` la decision

    A. Rolland analyse multicrite`re pour laide a` la decision 3 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    ON PEUT COMBINER !

    multicrite`re et combinatoireincertain et decision de groupemulticrite`re et decision de groupe (vacances entre amis ?)...

    A. Rolland analyse multicrite`re pour laide a` la decision 4 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    CADRE FORMEL

    Choix social Multicrite`re IncertainCandidats Alternatives Actions

    Votants Crite`res Etats de la natureRangs Valeurs Consequences

    (Nombre) (Poids) (Probabilites)

    Choix social : preferences individuelles preferencesglobalesMulticrite`re : preferences sur les crite`res preferencessur les alternativesIncertain : preferences sur les consequencespreferences sur les actions

    A. Rolland analyse multicrite`re pour laide a` la decision 5 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    PRENDRE UNE DECISION EST DIFFICILE QUAND...

    il y a trop de possibilites a` comparer Optimisationcombinatoireil y a plusieurs decideurs Theorie du Choix Socialles consequences des actes ne sont pas sures Decisiondans lincertainplusieurs crite`res rentrent en compte aidemulticrite`re a` la decision

    A. Rolland analyse multicrite`re pour laide a` la decision 6 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    DEFINITION DES CRITE`RES [ROYBOUYSSOU96]

    crite`re= attribut muni dune relation binaire totale : ordre,preordre, ordre dintervalle...

    Une famille de crite`re doit etre :comple`te pour decrire le proble`me (exhaustivite)coherente vis-a`-vis des preference globaleaussi independante que possible (non redondance)

    A. Rolland analyse multicrite`re pour laide a` la decision 7 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    DEFINITION DES PROBLEMATIQUES [ROYBOUYSSOU96]

    problematique de la modelisation de la decision [Tsoukias07]problematique du choixproblematique du rangementproblematique du tri

    A. Rolland analyse multicrite`re pour laide a` la decision 8 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    NOTATIONS

    X est lensemble des alternatives x , y , . . .N = {1, . . . ,n} est lensemble des crite`resgi : X R, i N sont les fonctions crite`resgi(x) est la valeur prise par lalternative x sur le crite`re i ,notee aussi xi

    A. Rolland analyse multicrite`re pour laide a` la decision 9 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    DEUX APPROCHES STRUCTURANTES [GRABISCHPERNY03]

    x = (x1, . . . , xn)y = (y1, . . . , yn)

    a a(x),a(y) c c

    c(x1, y1), . . . , c(xn, yn)c(y1, x1), . . . , c(yn, xn)

    a P(x , y)

    lapproche quantitative agreger puis comparer (crite`reunique de synthe`se)lapproche qualitative comparer puis agreger(surclassement de synthe`se)

    A. Rolland analyse multicrite`re pour laide a` la decision 10 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    CHOISIR UN APPAREIL PHOTO

    A. Rolland analyse multicrite`re pour laide a` la decision 11 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    CHOISIR UN APPAREIL PHOTO

    crite`re appareil 1 appareil 2 appareil 3Nb Pixel 20m 12m 16msensibilite 125-6400 80-12800 100-12800vitesse 30s-1/2000 15s-1/4000 30s-1/4000Macro 10cm 15cm XPrix 490 C 450 C 1200 C

    A. Rolland analyse multicrite`re pour laide a` la decision 12 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    Methodes a` base dutilite

    A. Rolland analyse multicrite`re pour laide a` la decision 13 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    BIBLIOGRAPHIE

    Fishburn Utility theory for Decision Making, 1970, WileyKeeney-Raiffa Decisions with multiple objectives ;preferences and trade-off, 1976, WileyMarichal, Aggregation Operators for Multicriteria DecisionAid, Institute of Mathematics, University of Lie`ge, 1998M. Ehrgott. Multicriteria Optimization. Second edition.Springer, Berlin, 2005.

    A. Rolland analyse multicrite`re pour laide a` la decision 14 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    fonctions dagregation additivesmoyenne ponderee

    fonctions dagregation non additivesmaximin, minimax, minimin maximaxOWAintegrale de Choquet

    distancesoptimisation multiobjectif

    A. Rolland analyse multicrite`re pour laide a` la decision 15 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    HYPOTHE`SES

    les valeurs sur les differents crite`res sontcommensurablesles valeurs sur les differents crite`res peuvent secompenserles valeurs de toutes les alternatives sur tous les crite`ressont parfaitement connueson veut obtenir une relation de preference comple`te ettransitive

    A. Rolland analyse multicrite`re pour laide a` la decision 16 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTION DUTILITES

    0

    0.2

    0.4

    0.6

    0.8

    1

    1.2

    0 0.2 0.4 0.6 0.8 1 1.2

    G(X)

    0

    0.2

    0.4

    0.6

    0.8

    1

    1.2

    0 0.2 0.4 0.6 0.8 1 1.2

    G(X)

    0

    0.2

    0.4

    0.6

    0.8

    1

    1.2

    0 0.2 0.4 0.6 0.8 1 1.2

    G(X)

    0

    0.2

    0.4

    0.6

    0.8

    1

    1.2

    0 0.2 0.4 0.6 0.8 1 1.2

    G(X)

    A. Rolland analyse multicrite`re pour laide a` la decision 17 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    CHOISIR UN APPAREIL PHOTO

    crite`re appareil 1 appareil 2 appareil 3Nb Pixel 10 6 8sensibilite 3 10 9vitesse 5 5 10Prix 9 10 4

    A. Rolland analyse multicrite`re pour laide a` la decision 18 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTION DAGREGATION ADDITIVES

    MOYENNE PONDEREE

    x % y WS(x) WS(y)WS(x) =

    i

    wi fi(x)

    facile a` comprendre et a` utilisermais ne favorise pas les solutions de compromis(ex : A(18,3) ; B(3,18), C(10,10))

    A. Rolland analyse multicrite`re pour laide a` la decision 19 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTION DAGREGATION ADDITIVES

    MOYENNE PONDEREE

    x % y WS(x) WS(y)WS(x) =

    i

    wi fi(x)

    crite`re coef appareil 1 appareil 2 appareil 3Nb Pixel 0.2 10 6 8sensibilite 0.3 3 10 9vitesse 0.1 5 5 10Prix 0.4 9 10 4Score 7 8.7 6.9

    A. Rolland analyse multicrite`re pour laide a` la decision 20 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTIONS DAGREGATION NON ADDITIVES (1)

    MAX ET MINmaximin (pessimiste prudent)

    x % y mini

    (fi(x)) mini

    (fi(y))

    maximax (optimiste joueur)

    x % y maxi

    (fi(x)) maxi

    (fi(y))

    etc...

    crite`re appareil 1 appareil 2 appareil 3Nb Pixel 10 6 8sensibilite 3 10 9vitesse 5 5 10Prix 9 10 4Min 3 6 4Max 9 10 10

    A. Rolland analyse multicrite`re pour laide a` la decision 21 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTIONS DAGREGATION NON ADDITIVES (2)

    OWA [YAGER98]

    x % y OWA(x) OWA(y)OWA(x) =

    i

    wi f(i)(x)

    avec f(1)(x) f(2)(x) . . . f(3)(x)

    les poids sont affectes aux rangs des valeurs et non auxcrite`respermet de retrouver (et composer) tous les indicesstatistiques de position

    A. Rolland analyse multicrite`re pour laide a` la decision 22 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTIONS DAGREGATION NON ADDITIVES (2)

    OWA [YAGER98]

    x % y OWA(x) OWA(y)OWA(x) =

    i

    wi f(i)(x)

    avec f(1)(x) f(2)(x) . . . f(3)(x)

    crite`re appareil 1 appareil 2 appareil 3Nb Pixel 10 6 8sensibilite 3 10 9vitesse 5 5 10Prix 9 10 4OWA 6.2 7.3 7.4

    Avec le jeu de poids (0.3 ;0.3 ;0.2 ;0.2)

    A. Rolland analyse multicrite`re pour laide a` la decision 23 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTIONS DAGREGATION NON ADDITIVES (3)

    INTEGRALE DE CHOQUET [CHOQUET53]

    x % y C(x) C(y)C(x) =

    i

    (Ai)(f(i)(x) f(i+1)(x)

    )avec f(1)(x) f(2)(x) . . . f(3)(x) une mesure sur 2N et Ai = {1, . . . , i}.

    integrale vis-a`-vis dune mesure non additive (capacite oumesure floue)permet de modeliser les interactions entre crite`resinclue WS, OWA, etc...

    A. Rolland analyse multicrite`re pour laide a` la decision 24 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    FONCTIONS DAGREGATION NON ADDITIVES (3)

    Exemple de capacite (4 crite`res=16 parame`tres) :

    ({c1}) = 0.2 ({c2}) = 0.1 ({c3}) = 0.2 ({c4}) = 0.1({c1, c2}) = 0.3 ({c1, c3}) = 0.6 ({c1, c4}) = 0.2 ({c2, c3}) = 0.6({c2, c4}) = 0.2 ({c3, c4}) = 0.3 ({c1, c2, c3}) = 0.7 ({c1, c2, c4}) = 0.4

    ({c1, c3, c4}) = 0.5 ({c2, c3, c4}) = 0.4 ({c1, c2, c3, c4}) = 1 () = 0

    crite`re appareil 1 appareil 2 appareil 3Nb Pixel 10 6 8sensibilite 3 10 9vitesse 5 5 10Prix 9 10 4Choquet Int. 5 6.2 7.6

    A. Rolland analyse multicrite`re pour laide a` la decision 25 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    OPTIMISATION MULTICRITE`RE

    PRINCIPE

    x % y d(x , z) d(y , z)ou` d(, ) est une distance et z un point ideal

    Exemple : methode TOPSIS [Hwang& Yoon81]

    calcul du point ideal et du point anti-ideal

    calcul de la distance d au point ideal

    calcul de la distance d au point anti-ideal

    calcul du score : s = d

    d+d

    A. Rolland analyse multicrite`re pour laide a` la decision 26 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    OPTIMISATION MULTICRITE`RE

    PRINCIPE

    x % y d(x , z) d(y , z)ou` d(, ) est une distance et z un point ideal

    crite`re appareil 1 appareil 2 appareil 3 Ideal Anti-IdealNb Pixel 10 6 8 10 6sensibilite 3 10 9 10 3vitesse 5 5 10 10 5Prix 9 10 4 10 4

    A. Rolland analyse multicrite`re pour laide a` la decision 27 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    Methodes a` base de surclassement

    A. Rolland analyse multicrite`re pour laide a` la decision 28 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    BIBLIOGRAPHIE

    B. Roy et D. Bouyssou, Aide Multicrite`re a` la Decision :Methodes et Cas, Economica 1993D. Bouyssou, D. Dubois, M. Pirlot, H. Prade, Concepts etmethodes pour laide a` la decision, volume 3, Herme`s2006

    A. Rolland analyse multicrite`re pour laide a` la decision 29 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    HYPOTHE`SES

    acte de decision = processus delaboration progressivedune structure de preferencelacceptation de lidee dincomparabilite des actionsavoir comme resultat une structure de preferencebeaucoup moins stricte quun pre-ordre total en vuedeclairer le DM sur son choix

    A. Rolland analyse multicrite`re pour laide a` la decision 30 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    RELATION DE SURCLASSEMENT

    PRINCIPE

    x % y C(x , y) DN C(y , x)avec C(x , y) = {i N|xi %i yi}

    A. Rolland analyse multicrite`re pour laide a` la decision 31 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    LA METHODE ELECTRE [ROY68]

    RELATION DE SURCLASSEMENTx surclasse y (xSy ) si C(x , y) > SC et j N, non yjVjxj

    xSy et non ySx : x est prefere a` y (xPy ou x y )xSy et ySx : x et y sont indifferents (xIy ou x y )non xSy et non ySx : x et y sont incomparables (xRy )

    La relation S donne un graphe des preferences sur X

    Alors que fait-on ?Electre analyse une situation mais ne resout pas tous lesproble`mes !on peut reduire le graphe en fusionnant les cycles en unenouvelle alternativeon peut faire varier les seuils pour une analyse desensibilite

    A. Rolland analyse multicrite`re pour laide a` la decision 32 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    LA METHODE ELECTRE [ROY68]

    crite`re appareil 1 appareil 2 appareil 3Nb Pixel 20m 12m 16msensibilite 125-6400 80-12800 100-12800vitesse 30s-1/2000 15s-1/4000 30s-1/4000Macro 10cm 15cm XPrix 490 C 450 C 1200 C

    crite`re appareil 1 appareil 2 appareil 3appareil 1 0.4 0.4appareil 2 0.6 0.4appareil 3 0.4 0.4

    avec w1 = w2 = w3 = w4 = w5 = 0.2

    A. Rolland analyse multicrite`re pour laide a` la decision 33 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    AUTRE EXEMPLE : PROMETHEE [BRANSETAL84]

    comparer les alternatives avec intensite de preferencePi(x , y) = p(gi(x) gi(y))

    P(x , y) = 0 pas de preference de x sur yP(x , y) = 1 preference forte de x sur y

    indicateur de preference pi(a,b) =

    i iPi(a,b) andpi(b,a)calcul des flux +(x) =

    y pi(x , y) and

    (x) =

    y pi(y , x)agregation des flux

    A. Rolland analyse multicrite`re pour laide a` la decision 34 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    Autres methodes

    A. Rolland analyse multicrite`re pour laide a` la decision 35 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    re`gles de decisionsAHP

    A. Rolland analyse multicrite`re pour laide a` la decision 36 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    RE`GLES DE DECISIONS [SLOWINSKYETAL01]

    problematique du triutilise la dominance et les Rough setsconvient bien aux donnees imprecises ou incomple`testre`s comprehensible par un decideur

    PRINCIPESi x domine y alors x doit etre classe dans une categorie aumoins aussi bonne que celle de y .

    A. Rolland analyse multicrite`re pour laide a` la decision 37 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    AHP [SAATY71, SAATY80]

    methode pour determiner les poids dune sommepondereeutilise les comparaisons dalternatives et de crite`respeut prendre en compte plusieurs decideurs.

    PRINCIPEDecomposer le proble`me complexe en une structurehierarchique (niveaux)Effectuer les comparaisons entre crite`res :de 1(indifference) a` 9 (extreme preference)Effectuer les comparaisons entre alternativesSynthetiser les comparaisons (moyenne) pour obtenir unclassementCoherence des jugements

    A. Rolland analyse multicrite`re pour laide a` la decision 38 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    CE QUIL FAUT RETENIRpas de methode miracle !mais des proprietes souhaitables... ou non

    LES DEFIS

    lanalyse axiomatiquele passage a` lechellelelicitation des parame`tres (preference learning)

    A. Rolland analyse multicrite`re pour laide a` la decision 39 / 39

  • Introduction Cadre Utilites Surclassements Autres methodes Conclusion

    CE QUIL FAUT RETENIRpas de methode miracle !mais des proprietes souhaitables... ou non

    LES DEFIS

    lanalyse axiomatiquele passage a` lechellelelicitation des parame`tres (preference learning)

    A. Rolland analyse multicrite`re pour laide a` la decision 39 / 39

    Introductioncoucou

    CadreUtilitsSurclassementsAutres mthodesConclusion