Upload
erwin
View
62
Download
11
Embed Size (px)
DESCRIPTION
Aide multicritère à la décision spatio-temporelle. Salem Chakhar LAMSADE Université Paris Dauphine www.lamsade.dauphine.fr 09-11-2004. Plan de l'exposé. Introduction. Cadre conceptuel proposé. Concept de la carte décisionnelle. Problème de génération des corridors. - PowerPoint PPT Presentation
Citation preview
Aide multicritère à la décision spatio-temporelle.
Salem ChakharLAMSADE
Université Paris Dauphinewww.lamsade.dauphine.fr
09-11-2004
2
Plan de l'exposé.
1. Introduction.
2. Cadre conceptuel proposé.
3. Concept de la carte décisionnelle.
4. Problème de génération des corridors.
5. Modélisation des préférences temporelles.
6. Conclusion.
3
Introduction.
• Un problème spatial réfère à tout problème de décision dont l'espace géographique constitue un élément prépondérant en tant que milieu de vie, d'activité et d'intervention humaine, et en tant que support d'évaluation et d’implémentation de toute décision.
• Un problème spatial peut être appréhendé selon :
- une perception statique, ou
- une perception dynamique.
4
Introduction.
• Pour modéliser un problème spatial, on peut faire recourt à :
- des données stables, ou/et- des données évolutives.
• Selon la nature du problème et la finalité décisionnelle, on est amené à prendre :
- une décision unique de type "une fois pour toutes", ou- une série de décisions dispersées dans le temps.
5
Introduction.
Vision Statique Temporelle Temps-réel Séquentielle
Env. de décision
Statique Dynamique Dynamique Stable/
Dynamique
Nature de l’inf.
Stable Dispersée Instantanée Stable/
Dispersée
Type de décision
Décision unique
Décision unique
Série de décisions
Série de décisions
Objectif Prise de décision à court terme
Prise de décision à long terme
Contrôle de systèmes dynamiques
Recherche séquentielle de l’information
6
Introduction.
• Vision temporelle : une vision qui cherche à penser long terme
Pratique décisionnelle dominée par la pensée
‘court-termiste’
Pratique décisionnelle à vocation
‘long-termiste’
• Cette vision nécessite :
1. Des changements comportementaux et intellectuels
2. Mais aussi de nouveaux outils et de nouvelles approches méthodologiques
7
Introduction.
Définition.
L'aide à la décision spatio-temporelle est une activité d'aide à la décision (au sens de la définition de Bernard Roy) dont l'objectif est de dégagé des éléments de réponses à des questions qui ont trait à des problèmes spatiaux approchés selon une vision temporelle à vocation long-termiste.
8
Introduction.
• Les spécificités d'une activité d'aide à la décision spatio-temporelle :
- Elle vise la prise en compte explicite du long terme
- Elle a comme point d'application une action localisée dont la mise à exécution action doit tenir compte des impacts futurs.
- Elle permet d'appréhender, définir et modéliser des préférences qui évoluent dans le temps.
9
Plan de l'exposé.
1. Introduction.
2. Cadre conceptuel proposé.
3. Concept de la carte décisionnelle.
4. Problème de génération des corridors.
5. Modélisation des préférences temporelles.
6. Conclusion.
10
Cadre conceptuel.
• Processus de prise de décision spatiale adopté :
1. Identification et formulation du problème
2. Analyse
3. Négociation
4. Concertation
5. Evaluation
6. Choix
11
Cadre conceptuel.Processus Objectifs Outils
1. Identification et formulation du problème
Définition des enjeux et des objectifs, Production des données
Outils de gestion des données spatiales : SIG
2. Analyse Définition des critères, des alternatives, évaluer les conséquences et impacts
Outils de modélisation du problème, de génération des alternatives : SIG + Carte décisionnelle + modèles de prévision et de simulation
3. Négociation
4. Concertation
Faire surgir les alternatives d’action supportées par les différents intervenants
Outils de communication :
Carte décisionnelle
5. Evaluation Evaluation et comparaison des
alternatives
Outils d’analyse multicritère
(AMC)
6. Choix Recommandation d’une ou plusieurs alternatives d’action
Outils de diffusion : SIG
12
Cadre conceptuel.
• Idée du cadre : Il se base sur une intégration entre :
SIG AMC
Carte décisionnelle
Décideur 1 Autres acteurs
Décideur n
- Système d’information géographique
- Analyse multicritère
- Carte décisionnelle
13
Données descriptives et spatiales
Résultat d’analyse
Paramètres de la méthode multicritère
Logiciel SIG
Gestion des données
descriptives et spatiales
Interface SIG
BD spatiale
Modélisation et analyse
du problème
Interface MCA
Paramètres MCA
Système intermédiaire
Reformulation des données et des résultats
(c) Stratégie compète(b) Stratégie built-in
Interface SIG
BD spatiale
Modélisation et analysedu problème
Paramètres MCA
Model MCA autonomeGestion des données descriptives et spatiales
Interface SIG
BD spatiale
Gestion des données descriptives et spatiales+
Modélisation et analyse du problème
Fonctions de base du SIG
(a) Stratégie indirecteLogiciel MCA
Données descriptives et spatiales
Paramètres de la méthode multicritère
Données descriptives et spatiales
Résultat d’analyse
Résultat d’analyse Résultat
d’analyse
Cadre conceptuel.
Fonctions d’évaluation multicritère
Paramètres de la méthode multicritère
• Approches d’intégration SIG-AMC :
14
• Idée de la stratégie d’intégration SIG-AMC :
Intégré dans le SIG :
1. Les différentes fonctions d’évaluation multicritère
2. Un module pour le choix de la procédure d’agrégation
Cadre conceptuel.
15
Cadre conceptuel.
Alternatives Critères
Performances
Tableau des performances
Préférences
Agrégation
Analyse de sensitivité
Recommandation
Schéma général d’un modèle multicritère
Fonction
F1 Définition/Génération des actions
F2 Définition/Génération des critères
F3 Définition/Génération du tableau des performances
F4 Définition/Inférence des préférences
F5 Agrégation
F6 Analyse de sensitivité
F7 Recommandation
Fonctions d’évaluation multicritère
16
Cadre conceptuel.
Identification des caractéristiques du problème de décision à référence
spatiale (PDRS)
Identification des caractéristiques du problème de décision à référence
spatiale (PDRS)
Sélection d’un sous ensemble de PAMC
Sélection d’un sous ensemble de PAMC
Arbre de classificationArbre de classification
Module de sélection de la procédure d’agrégation
Identification des caractéristiques des procédures d’agrégation
multicritère (PAMC) adaptées au problème
Identification des caractéristiques des procédures d’agrégation
multicritère (PAMC) adaptées au problème
Tableau de correspondance PDRS - PAMC
Tableau de correspondance PDRS - PAMC
Sélection d’une PAMCSélection d’une PAMC
Condition d’utilisation de la procédure d’agrégation
Condition d’utilisation de la procédure d’agrégation
17
Type of decision problem Nature of the set of alternatives Required information Nature of evaluation result
Characteristics of the Spatially-Referenced Decision Problem (SRDP)
Choice Discrete (vector) Measuring scale Spatial extent of the impact
. a single solution
. a set of solutions
. Nominal
. Ordinal
. punctual, local
. regional, national. Interval
. RatioAffectation Continuous (raster) Available Information reliabilityOrdering . deterministic
. non-deterministic
. excellent
. averageCharacteristics of the
Multi-Criterion Aggregation
Procedure (MCAP)
Choice Discrete Criteria-related information Type of result
. Ordinal
. Cardinal
. locational
. distributionalCriteria-related
InformationSorting . value
. discrimination potential of factors
ContinuousInter-criteria
information
Accurarcy
considered:Ordering . explicitly known
. partly known
. unknown
. yes
. no
Cadre conceptuel.Tableau de correspondance PDRS-PAMC
18
AHP (αγ, ae, k )ELECTRE II (γ, re, k)ELECTRE IV (γ, re, u)
UTA (αγ, ae, k)PROMETHEE (γ, re, k)
SMART (αγ, ae, k)VOLVOX (γ, re, k)
...
AHP (αγ, ae, k )ELECTRE II (γ, re, k)ELECTRE IV (γ, re, u)
UTA (αγ, ae, k)PROMETHEE (γ, re, k)
SMART (αγ, ae, k)VOLVOX (γ, re, k)
...
Argus (γ, re, k)Bernardo (γ, re, k)
ELECTRE I (α, re, k)ZAPROS (γ, re, k)
QUALIFLEX (γ, re, pk)REGIME (γ, re, k)VOLVOX (γ, re, k)
...
Argus (γ, re, k)Bernardo (γ, re, k)
ELECTRE I (α, re, k)ZAPROS (γ, re, k)
QUALIFLEX (γ, re, pk)REGIME (γ, re, k)VOLVOX (γ, re, k)
...
FLIP (f)Leung (f)
Tanaka (p)...
FLIP (f)Leung (f)
Tanaka (p)...
ELECTRE III (γ, re, k)ELECTRE IS (γ, re, k)ELECTRE Tri (ß, ae, k)Martel & Zaras (γ, re, k)
Martel, Azondékon & Zaras (γ, re, k)MAUT (αγ, ae, k)VOLVOX (γ, re, k)
...
ELECTRE III (γ, re, k)ELECTRE IS (γ, re, k)ELECTRE Tri (ß, ae, k)Martel & Zaras (γ, re, k)
Martel, Azondékon & Zaras (γ, re, k)MAUT (αγ, ae, k)VOLVOX (γ, re, k)
...
Rebaϊ (αγ, ae, pk)Rietveld & Ouwersloot
(γ, re, k)Decision Grid
(γ, re, k)...
Rebaϊ (αγ, ae, pk)Rietveld & Ouwersloot
(γ, re, k)Decision Grid
(γ, re, k)...
Geoffrion, Dyer & Feinberg (e)
Point de mire (u)Stuer & Choo (u)
STEM (u)Zionts & Wallenius (e)
...
Geoffrion, Dyer & Feinberg (e)
Point de mire (u)Stuer & Choo (u)
STEM (u)Zionts & Wallenius (e)
...
Goal programming (np)
Compromize programming (np)
Mutli-Objective Simplex of Zeleny
(aps)Utility function (apr)
...
Goal programming (np)
Compromize programming (np)
Mutli-Objective Simplex of Zeleny
(aps)Utility function (apr)
...
PROTRADE (y, ia)Stancu Minian
(y, nin)STRANGE (y, ia)PROMISE (n, ia)
...
PROTRADE (y, ia)Stancu Minian
(y, nin)STRANGE (y, ia)PROMISE (n, ia)
...
others(PD, TE, II)
others(PD, TE, II)
others(PD, TE, II)
others(PD, TE, II)
others(PD, TE, II)
others(PD, TE, II)
Others(PD, TE, II)
Others(PD, TE, II)
Other(TI)
Other(TI)
Other(IP)
Other(IP)
others(CI, A)others(CI, A)
Other(N)
Other(N)
level of information
level of information
level of information
level of information approachapproach type of non
determinismtype of nondeterminism
nature of informationnature of
informationnature of
informationnature of
information
set of alternatives
set of alternatives
discrete continuous
deterministic non-deterministic deterministic non-deterministic
cardinal non-cardinal cardinal non-cardinal interactive non-interactive stochastic non-stochastic
PD: Type of problem α : choice ß : sorting γ : ranking
TE: Type of evaluation ae : absolute evaluation re : relative evaluation
II: Inter-criteria information k : known pk : partialy known u : unknown
TI: Type of information e : explicit i : implicit
IP: Preference incorporation np : no preference apr : a priori aps : a posterioriCI: Complete information? y : yes n : no
A: Approach ia : interactive nin : non-interactive
N: Nature of non-stochastic f : fuzzy p : possibility
Cadre conceptuel.
Arbre de classification
19
Plan de l'exposé.
1. Introduction.
2. Cadre conceptuel proposé.
3. Concept de la carte décisionnelle.
4. Problème de génération des corridors.
5. Modélisation des préférences temporelles.
6. Conclusion.
20
Carte décisionnelle.
Définition :
Une carte décisionnelle est une version avancée de la carte géographique qui est enrichie avec de l’information préférentielle et destinée à éclairer une décision. Elle se présente comme un ensemble d’unités homogènes. Chaque unité est caractérisée par une évaluation globale unique provenant de l’agrégation de plusieurs évaluations relatives aux différents critères.
21
Carte décisionnelle.
• Procédure pour la construction et utilisation d’une carte décisionnelle :
1. Définition du problème (génération des cartes critères)
2. Génération d’une carte intermédiaire (par intersection des cartes critères)
3. Inférence des paramètres préférentiels et élaboration de la carte finale
4. Utilisation de la carte décisionnelle
22
Carte décisionnelle.
• Exemple : Problème de valorisation d’une zone donnée
• Quatre thèmes en relation avec l’eau et l’environnement sont à évaluer :
Critère Description Max/Min Poids
g1 Aptitude à l’urbanisation Max 0.25
g2 Vulnérabilité des ressources en eau Min 0.25
g3 Sensibilité à l’érosion Min 0.25
g4 Aptitude au géoassainissement Max 0.25
23
Carte décisionnelle.
• Définition d’une carte critère :
Pente Lithologie
Débordements
Carte critère Aptitudeà l’urbanisation
Opérations
spatiales
Données
originales
Zones humides
Zones instables(glissements)
Modèle Numérique du Terrain
Géologie
24
Carte décisionnelle.
1 2 16 18
4 3 15 17
5 7 23
6 9 24 21 20
8 14 19
13 25 22 26
10 11 12 27
• Carte critère Aptitude à l’urbanisation :
5 Très Bonne
4 Bonne
3 Moyenne
2 Mauvaise
1 Très Mauvaise
Echelle :
25
Carte décisionnelle.
1 2 3 4 28 25 24
6 5 27
8 7 26
9 14 20 21 22 23
11 13 15 19
17 18
10 12 16
• Carte critère Sensibilité à l’érosion :
1 Très faible
2 Faible
3 Moyenne
4 Forte
5 Très forte
Echelle :
26
Carte décisionnelle.
1 2 3 21
20 23 24
7 4 22
8 6 5 19 25
10 16 26 27
9 13 14 17 28
11 12 15 18 29
Echelle :
• Carte critère Vulnérabilité des ressources en eau :
1 Très faible
2 Faible
3 Moyenne
4 Forte
5 Très forte
27
Carte décisionnelle.
1 2 3 14 28 27
6 5 4 15 16 29
7 17 26
9 13 25 24
8 18 21
12 20 22
10 11 19 23
Echelle :
• Carte critère Aptitude au géoassainissement :
5 Très Bonne
4 Bonne
3 Moyenne
2 Mauvaise
1 Très Mauvaise
28
1 2 3 21
20 23 24
7 4 22
8 6 5 19 25
10 16 26 27
9 13 14 17 28
11 12 15 18 29
1 2 3 4 28 25 24
6 5 27
8 7 26
9 14 20 21 22 23
11 13 15 19
17 18
10 12 16
1 2 3 14 28 27
6 5 4 15 16 29
7 17 26
9 13 25 24
8 18 21
12 20 22
10 11 19 23
1 2 16 18
4 3 15 17
5 7 23
6 9 24 21 20
8 14 19
13 25 22 26 10 11 12 27
Intersection
Carte intermédiaire
Carte décisionnelle.
g1: aptitude à l’urbanisation
g2: sensibilité à l’érosion
g3 : vulnérabilité des ressources en eau
g4 : aptitude au géoassainissement
Chaque unité ui est caractérisée par un vecteur des performances :
[g1(ui),g2(ui),g3(ui),g4(ui)]
u1 u2 u3 u4 u5 u6 u7 u8 u9 u10
u11 u12 u13 u1 4 u15 u16 u17 u18 u19 u20
u21 u22 u23 u24 u26 u27 u28 u29 u30
u31 u32 u33 u25 u34 u35 u36 u37
u39 u40 u41 u42 u43 u44 u45
u38 u46 u47 u48 u49 u50 u51 u52
u53 u54 u55 u56 u57 u58 u59 u60 u61
[3,4,4,3]
[2,5,2,5]
29
Carte décisionnelle.
[2,4,4,2]
u1
[3,4,4,3]
u2
[3,3,4,1]
u3
[5,1,1,1]
u4
[1,5,5,1]
u5
[1,5,1,4]
u6
[3,1,3,4]
u7
[3,1,3,5]
u8
[3,4,2,3]
u9
[5,3,2,1]
u10
[2,4,4,5]
u11
[5,5,4,5]
u12
[3,3,4,3]
u13
[5,1,1,1]
u1 4
[3,3,5,3]
u15
[1,4,11]
u16
[3,3,5,3]
u17
[3,1,2,5]
u18
[3,1,2,3]
u19
[5,3,1,1]
U20
[3,5,3,5]
u21
[1,5,3,1]
u22
[3,4,4,3]
u23
[5,4,3,2] [4,2,5,4][4,4,2,4]
u26
[4,3,2,4]
u27
[3,2,3,5]
u28
[4,3,3,2]
u29
[3,4,4,4]
[2,5,4,5]
u31
[1,5,1,1]
u32
[3,2,2,4]u24
u25
[1,3,5,1]
u34
[4,2,2,2]
u35
[2,4,4,2]
u36
[4,2,4,3]
u37
u30
[2,5,2,5][5,5,1,5]
u39
u33 [3,3,3,2] u40
[1,5,4,1]
u41
[4,2,2,4]
u42
[1,5,5,2][4,2,1,3]
u44
[3,4,3,4]
u38
[3,1,1,2]
u46
[3,1,3,5]
u47
[2,3,4,5]
u48
[4,2,2,5]
u49
[1,1,5,1]
u50
[2,4,5,1]
u51
u43
[5,5,2,5]
u52
u45
[1,2,2,5]
u53
[3,1,3,2]
u54
[3,1,1,2]
u55
[4,2,1,4]
u56
[2,2,2,4]
u57
[2,2,4,2]
u58
[2,2,4,1] u59
[1,5,2,3]
u60
[1,5,1,3]
u61
?
Carte finale
c-à-d, pour chaque ui de la carte intermédiaire,
définir une évaluation globale g(ui) = [gj(ui)]jF
Carte intermédiaire
30
Carte décisionnelle.
• Modèle de tri :
: Em E [g1(u),g2(u),…,gm(u)] g(u) • On suppose que tous les critères sont évalués sur une même échelle ordinale E :
Très faible Faible Moyenne Forte Très forte
c1 < c2 < c3 < c4 < c5
31
Carte décisionnelle.
= Electre Tri
• Cinq catégories :
g1 g2 g3 g4
g(b4) 4.5 1 1 4.5
q4 0.2 0.2 0.2 0.2
p4 0.3 0.3 0.3 0.3
g(b3) 3.5 2 2 3.5
q3 0.2 0.2 0.2 0.2
p3 0.3 0.3 0.3 0.3
g(b2) 2.5 3.5 3.5 2.5
q2 0.2 0.2 0.2 0.2
p2 0.3 0.3 0.3 0.3
g(b1) 0.25 4 4 0.25
q1 0.2 0.2 0.2 0.2
p1 0.3 0.3 0.3 0.3
32
Carte décisionnelle.
• Résultat sans informations supplémentaires (en utilisant Iris v. 2.0) :(c2)
u1
(c2,c3)
u2
(c2,c3)
u3
(c2,c5)
u4
(c1,c2)
u5
(c1,c2, ,c3)
u6
(c3,c4 ,c5)
u7
(c3,c4)
u8
(c2, c3)
u9
(c2,c3, c4)
u10
(c2)
u11
(c1,c2,c3)
u12
(c2,c3)
u13
(c2,c5)
u1 4
(c1,c3)
u15
(c2)
u16
(c1,c3)
u17
(c3,c4,c5)
u18
(c3,c4)
u19
(c2,c3,c4)
u20
(c1,c3)
u21
(c1,c2)
u22
(c2,c3)
u23
(c2,c3) (c1,c4)(c2,c4)
u26
(c3,c4)
u27
(c3,c4)
u28
(c2,c3)
u29
(c2,c3)
(c1,c2)
u31
(c1,c2)
u32
(c3,c4) u24 u25
(c1,c2)
u34
(c2,c4)
u35
(c2) u36
(c2,c3,c4)
u37
u30
(c1,c2,c3) (c1,c5)
u39
u33(c2,c3) u40
(c1,c2)
u41
(c4)
u42
(c1,c2)(c3,c4)
u44
(c2,c3)
u38
(c2,c3,c4)
u46
(c3,c4)
u47
(c2,c3)
u48
(c4)
u49
(c1,c2)
u50
(c1)
u51
u43
(c1,c4,c5)
u52
u45
(c2,c4)
u53
(c2,c3)
u54
(c2,c3,c4)
u55
(c4)
u56
(c2,c4)
u57
(c2)
u58
(c2) u59
(c1,c2, ,c3)
u60
(c1,c2, ,c3) u61
Très faible Faible Moyenne Forte Très forte
• Informations supplémentaires : u33c4 ; u40 c1-c3 ; u61 c1-c2
33
Carte décisionnelle.
• Résultat avec informations supplémentaires :
(c2)
u1
(c2)
u2
(c2)
u3
(c5)
u4
(c1)
u5
(c2)
u6
(c4)
u7
(c3)
u8
(c3)
u9
(c3)
u10
(c2)
u11
(c2)
u12
(c3)
u13
(c5)
u1 4
(c3)
u15
(c2)
u16
(c3)
u17
(c4)
u18
(c3)
u19
(c4)
u20
(c3)
u21
(c1)
u22
(c2)
u23
(c2) (c4)(c4)
u26
(c4)
u27
(c3)
u28
(c4)
u29
(c2)
(c2)
u31
(c2)
u32
(c4) u24 u25
(c2)
u34
(c4)
u35
(c2) u36
(c3)
u37
u30
(c2) (c5)
u39
u33(c3) u40
(c1)
u41
(c4)
u42
(c1)(c4)
u44
(c4)
u38
(c3)
u46
(c3)
u47
(c2)
u48
(c4)
u49
(c2)
u50
(c2)
u51
u43
(c4)
u52
u45
(c4)
u53
(c3)
u54
(c3)
u55
(c4)
u56
(c4)
u57
(c2)
u58
(c2) u59
(c1)
u60
(c2) u61
Très faible Faible Moyenne Forte Très forte
34
Carte décisionnelle.
• Résultat après regroupement :
u4
u5 u13 u14
u29u30
u6 u12 u28 u31 u35
u3
u7 u11
u15u27 u32
u2 u19 u26 u33
u34
u8
u10u16 u20 u25
u9 u17
u21 u24
u1 u18 u22 u23
Très faible Faible Moyenne Forte Très forte
35
Carte décisionnelle.
• A quoi sert une carte décisionnelle ?
Elle sert :
1. A l’elicitation des préférences/expertises
2. Comme support de communication et de participation
3. A la génération des alternatives d’action
36
Plan de l'exposé.
1. Introduction.
2. Cadre conceptuel proposé.
3. Concept de la carte décisionnelle.
4. Problème de génération des corridors.
5. Modélisation des préférences temporelles.
6. Conclusion.
37
Génération des corridors.
• Le problème : trouver un couloir entre un point o origine et un point d destination :
o ? d
L’idée :
• Générer une carte décisionnelle contenant o et d
• Définir un graphe de connexité ayant comme sommets les unités
homogènes de la carte décisionnelle
• Trouver les chemins entre les sommets représentant les unités
contenant o et d
38
Génération des corridors.
• Procédure de génération des corridors :
* Phase 1. Elaboration d'une carte décisionnelle - Etape 1.1. Définition et élaboration des critères - Etape 1.2. Elaboration d'une carte décisionnelle initiale - Etape 1.3. Inférence des paramètres préférentiels et génération d'une carte décisionnelle
* Phase 2. Génération des corridors - Etape 2.1 Construire le graphe de connexité G(X,U) X = {unités territoriales élémentaires} U = {(x,y) : x,y X et possède une frontière avec y} - Etape 2.2 Appliquer un algorithme pour la génération des corridors
39
Génération des corridors.
Carte décisionnelle
G(X,U) où X = {u1, u2,…, u35} U = {(x,y) : x,y X et x et y sont adjacents} u1 : origine ; u35 : destination
origine
destination
• Un exemple :
u4
u5 u13 u14
u29u30
u6 u12 u28 u31 u35
u3
u7 u11
u15u27 u32
u2 u19 u26 u33
u34
u8
u10u16 u20 u25
u9 u17
u21 u24
u1 u18 u22 u23
40
Génération des corridors.
Graphe de connexité
u1
u2
u3
u4
u28
u26
u25
u24
u5
u6
u7
u8
u9
u10
u11
u12
u14
u13
u15
u16
u17
u18
u19
u20
u21u22
u23
u35
u34
u29
u30
u31
u32
u33
u27
41
Génération des corridors.
• Un tronçon est une chaîne sans cycle entre deux sommets distincts x et y de G.
• Un corridor est une suite de tronçons adjacents reliant les sommets origine o et destination d.
Le problème : comment générer, à partir du graphe de connexité, un nombre restreint de corridors potentiellement intéressants ?
42
Génération des corridors.• Piste : Résolution d’un problème de plus court chemin multicritère :
xi
avec vE(x) : évaluation du sommet x X sur une échelle E tq e1<e2<…<ek
• Pour l’évaluation d’un corridor :
[vE(xo),…, vE(xn)] [r1,r2,…,rk]
où ri peut être :
- Le nombre de sommets xj (i.e. unité uj) tel que vE(xj)=ei
- La surface des unités uj d’évaluation ei traversées par le corridor
- La distance minimale totale parcourue dans les unités uj de niveau ei
vE(xj)vE(xi)
x1xo xnXn-1
vE(xo) vE(x1) vE(xn)vE(xn-1)
xj
Corridor c
43
Génération des corridors.
* ri : nombre de sommets (on suppose que les unités ont la même taille) :
[e2,e5,e2,e5,e4,e5] [0,2,0,1,3]
* ri : surface traversée (s : surface d’une unité) :
[e2,e5,e2,e5,e4,e5] [0, 2s, 0, s, 3s]
* ri : distance totale parcourue:
[e2,e5,e2,e5,e4,e5] [0, h+ l2+(h/2)2, 0, l, 2 l+ (l/2)2+h2 ]
e4 e2 e5 e4 e5
e5
e3
e4 e5 e2
e2
e4 e3 e1 e1
E: e1<e2<e3<e4<e5
• Exemple : l
h
44
Génération des corridors.
• L’évaluation globale d’un corridor v(c) est :
[r1,r2,…,rk] v(c) = [r1,r2,…,rk] IR
: est un mécanisme d’agrégation :
* Lexicographique :
Si ri est le nombre de sommets : [r1,r2,…,rk] = ei avec ri = maxj rj
* Par règle :
- Si [nombre de rk]>3/4 n Alors v(c)=ek
- Si [nombre de rk]<1/3 Alors v(c)<ek
45
Plan de l'exposé.
1. Introduction.
2. Cadre conceptuel proposé.
3. Concept de la carte décisionnelle.
4. Problème de génération des corridors.
5. Modélisation des préférences temporelles.
6. Conclusion.
46
Préférence temporelles.
• Cadre : problème du choix multicritère où : - A : ensemble d'actions. - F : famille cohérente de critères.
• On suppose que : - les conséquences des actions sont dispersées dans le temps. - l'axe du temps est discret. - l'horizon temporel T est divisé en n périodes : T={t0,t1,…,tn}.
• On désignera par t la période ]t-1,t].
• T doit aussi vérifier les deux conditions suivantes : - i ≠ j, ti tj=
- i ti =T
47
Préférences temporelles.
Définition.
Nous appellerons préférences temporelles les préférences faisant référence à l'ensemble de l'horizon temporel T.
• La modélisation des préférences temporelles nécessite la définition : - d’un mécanisme d’agrégation multicritère M - d’un mécanisme d’agrégation temporelle
48
Préférences temporelles.
Où :• j : Indice de critères.• t : Période.•T : Horizon temporel.• F : Famille de critères• g(x) : Performance de l’action x. = (P,I,R) et =(P,I,R) : Structures de préférence.
Agrégation par rapport au temps puis par rapport aux critères
Agrégation par rapport aux critères puis par rapport au temps
Approche par fonction de valeurs
gjT(x) = [gj
t(x)]tT
gT(x) = M[gjT(x)]jF
gt(x) = M[gjt(x)]jF
gT(x) = [gt(x)]tT
Approche par relations binaires
jT = [j
t]tT
T = M[jT]jF
t = [jt]jF
T = M[t]tT
•Possibilités de modélisation :
49
Préférences temporelles.
• Objectif : Supporter les sémantiques induites par la dimension temporelle et qui affectent les préférences :
1. Une évolution positive est préférée à une évolution négative.2. Une stabilité est préférée à une évolution négative.3. Une évolution positive est préférée à une stabilité.4. Une faible variabilité est équivalente à une stabilité.5. Une faible variabilité est préférée à une grande variabilité.
• Question : Quelle approche choisir ?
50
Préférences temporelles.• Le modèle basé sur une relation binaire S où aSb signifie que "l'action a est au moins aussi bonne que l'action b, permet de représenter trois situations :
- aPb aSb et (bSa) : a est préférée à b.- aIba aSb et bSa : a et b sont équivalentes.
- aRb (aSb) et (bSa) : a et b sont incomparables.
• Ces relations doivent généralement vérifier les propriétés suivantes :
- P est asymétrique.- I est réflexive et symétrique.- R est irréflexive et symétrique.
Définition. (P,I,R) constitue une structure de préférence ssi si les relations binaires P, I et R sont mutuellement exclusives et vérifient les propriétés précédentes.
51
Préférences temporelles.• Pour chaque période t, on définira la relation St où la proposition aStb signifie que "l'action a est au moins aussi bonne que l'action b durant la période t". St permet de représenter les situations suivantes :
- aPtb aStb et (bSta) : a est préférée à b durant t.- aItba aStb et bSta : a et b sont équivalentes durant t.
- aRtb (aStb) et (bSta) : a et b sont incomparables durant t.
• Ces relations doivent vérifier les propriétés suivantes :
- Pt est asymétrique.- It est réflexive et symétrique.- Rt est irréflexive et symétrique.
Définition. t=(Pt,It,Rt) constitue une structure de préférence pour la période t ssi durant t les relations binaires Pt,It et Rt sont mutuellement exclusives et vérifient les propriétés précédentes.
52
Préférences temporelles.• Pour la modélisation des préférences pour la totalité de l’horizon temporel T, on introduira la relation binaire ST où la proposition aSTb signifie que "l'action a est au moins aussi bonne que l'action b durant l’horizon T".
• ST synthétise les informations préférentielles exprimées par les relations binaires St :
1 2 k T-1 T
t
agrégation
T = [t]tT
53
Préférences temporelles.• ST permet également de représenter les situations suivantes :
- aPTb aSTb et (bSTa) : a est préférée à b durant T.- aITba aSTb et bSTa : a et b sont équivalentes durant T.
- aRTb (aSTb) et (bSTa) : a et b sont incomparables durant T.
• Ces relations doivent vérifier les propriétés suivantes :
- PT est asymétrique.- IT est réflexive et symétrique.- RT est irréflexive et symétrique.
Définition. T=(PT,IT,RT) constitue une structure de préférence temporelle ssi durant T les relations binaires PT,IT et RT sont mutuellement exclusives et vérifient les propriétés précédentes.
54
Préférences temporelles.
• P1. Dominance temporelle :
gt(a) gt(b)
gt-1(a) gt(a)
gt-1(b) gt(b)
gt(a) gt(b)
gt-1(a) gt(a)
gt-1(b) gt(b)
t T,
t T,
aTb
aTb
ou
t 0 1 2 3 4 5 6 7
gt(x) 12.5 12 12 11.5 11 10.5 10.5 10
gt(y) 7 7.5 8.5 9 9.5 9.75 10 10
gt(z) 7 7 8 8 8 9.5 10 10
Un exemple
D’après P1, on a :
• x T y
• x T z
• y T z
55
Préférences temporelles.
• P2. Cohérence temporelle : t T, aStb sSTb
t0 t1 t2 t3 t4 t5 t6 t7
xIy xPy xPy xQy xQy xIy xIy xIy
xIz xPz xPz xQz zPx xIz xIz xQz
Un exemple
• P3. Décisivité de chaque période :
rT, aPrb t r, aItb aSTb
Un exemple
P2 xSTy
t0 t1 t2 t3 t4 t5 t6 t7
zIy zIy zIy zIy zIy zPy zIy zIyP3 zSTy
56
Préférences temporelles.
• P4. Monotonicité : TH(a,b) : ensemble des périodes t pour lesquelles aH tb
t0 t1 t2 t3 t4 t5 t6 t7
xPy xPy xIy xIy xPy yPx xRy xPy
xPz xPz xIz xIz zPx zPx xRz zPx
Si [aPTb aPTc].
TP(a,c) TP(a,b)
TP(c,a) TP(b,a)
TI(a,c) = TI(a,b)
TR(a,c) = TR(a,b)
Un exemple
On a : TP(x,y)={t0,t1,t4,t7} ; TI(x,y)={t2,t3}
TP(x,z)={t0,t1,t4} ; TI(x,z)={t2,t3}
TP(y,x)={t5} ; TR(x,y)={t6}
TP(z,x)={t5,t7} ; TR(x,z)={t6}
D’après P4, Pour que ST soit monotone, il faut que : xPTz xPTy
57
Préférences temporelles.
• On introduit la fonction suivante :
: AxT [0,1] (x,t) gt(x) – gt-1(x)
• Pour calculer l'indice de concordance temporelle, il est nécessaire de déterminer les deux coalitions suivantes :
C(aStb)={t : t T, (a,t) + qt (b,t)}
C(bQta)={t : t T, (a,t) + qt < (b,t) (a, t)+ pt} qt et pt représentent les seuils d'indifférence et de préférence pour la
période t
58
Préférences temporelles.
t 1 2 3 4 5 6 7 Variabilité
g1t(a) 0.5 1 1 1.5 2 3 4.5 Evolution positive
g2t(a) 5 5 5 5 5 5 5 Stabilité
g3t(a) 4.5 4 4 3.5 3 2 0.5 Evolution négative
g1t(b) 9 2 7 1 6 0.5 6 Grande variabilité
g2t(b) 1 2 1.5 3 0.5 1 2 Faible variabilité
g3t(b) 1 6 0.5 6 4.5 8.5 1 Grande variabilité
g1t(c) 13 7 2.5 4.5 10.
55.75 0.25 Grande variabilité
g2t(c) 1 1.5 2 3.5 3.5 3.75 4 Evolution positive
g3t(c) 1 1.5 0.5 2 1 0.5 0.75 Faible variabilité
g1t(d) 0.5 0.5 0.5 2 3 3 3 Evolution en
escalier
g2t(d) 1 1 1 1 1 1 1 Stabilité
g3t(d) 14 14 14 5.5 1 1 1 Stabilité suivie par
une ‘chute libre’
g1t(e) 8 6 5.5 5 3 2 0.4 Evolution négative
g2t(e) 6 5.5 3.5 3 3 1.7 0.3 Evolution négative
g3t(e) 5 4.5 4 2 1 0.3 0.3 Evolution négative
g1t(f) 0.4 2 3 5 5.5 6 8 Evolution positive
g2t(f) 0.3 1.7 3 3 3.5 5.5 6 Evolution positive
g3t(f) 0.3 0.3 1 2 4 4.5 5 Evolution positive
• Exemple :
t 2 3 4 5 6 7
t 1 2 4 6 8 10
w1 1 3 4 5 6 7
w2 1 1 1 1 1 1
w3 7 6 5 3 2 1
qt 1 1 1 1 1 1
pt 2 2 2 2 2 2
vt 3 3 3 3 3 3
Tableau des performances
Paramètres préférentiels
59
Préférences temporelles.• Résultas :
a b c d e f
a 1 0.32 0.65 1 0.98 0
b 0.68 1 0.35 0.68 0.68 0.55
c 0.35 0.65 1 0.42 0.35 0.35
d 0.26 0.32 0.65 1 0.58 0
e 0.065 0.32 0.65 0.42 1 0
f 1 0.65 0.68 1 1 1
Matrice de concordance temporelle
f
a b c
de
Graphe final
60
Plan de l'exposé.
1. Introduction.
2. Cadre conceptuel proposé.
3. Concept de la carte décisionnelle.
4. Problème de génération des corridors.
5. Modélisation des préférences temporelles.
6. Conclusion.
61
Conclusion.
En cours :
• Définition d’un cadre plus général pour la modélisation des préférences
temporelles.
Reste à faire :
• Ajout de la dimension temporelle dans la définition de la carte décisionnelle.
• Identification/élaboration des algorithmes pour la génération de corridors.
• Modélisation des critères issus des conséquences dispersées dans l’espace et
dans le temps.
• Implémentation informatique.
• Application à un problème réel.