[PDF] Optimisation combinatoire multi-objectif: des méthodes aux

View - Download Optimisation combinatoire multi-objectif: des méthodes aux

Previous PDF

Next PDF

>G A/, i2H@yRRy93N8 ?iiTb,ffi?2b2bX?HXb+B2M+2fi2H@yRRy93N8 am#KBii2/ QM RN CM kyR8 >GBb KmHiB@/Bb+BTHBM`v QT2M ++2bb `+?Bp2 7Q` i?2 /2TQbBi M/ /Bbb2KBMiBQM Q7 b+B@

2MiB}+ `2b2`+? /Q+mK2Mib- r?2i?2` i?2v `2 Tm#@

HBb?2/ Q` MQiX h?2 /Q+mK2Mib Kv +QK2 7`QK

i2+?BM; M/ `2b2`+? BMbiBimiBQMb BM 6`M+2 Q` #`Q/- Q` 7`QK Tm#HB+ Q` T`Bpi2 `2b2`+? +2Mi2`bX /2biBMû2 m /ûT¬i 2i ¨ H /BzmbBQM /2 /Q+mK2Mib b+B2MiB}[m2b /2 MBp2m `2+?2`+?2- Tm#HBûb Qm MQM-

Tm#HB+b Qm T`BpûbX

PTiBKBbiBQM +QK#BMiQB`2 KmHiB@Q#D2+iB7, /2b Kûi?Q/2b mt T`Q#HK2b- /2 H h2``2 ¨ UT`2b[m2V H GmM2

LB+QHb CQx27QrB2x

hQ +Bi2 i?Bb p2`bBQM, LB+QHb CQx27QrB2xX PTiBKBbiBQM +QK#BMiQB`2 KmHiB@Q#D2+iB7, /2b Kûi?Q/2b mt T`Q#HK2b- /2 H h2``2 ¨ UT`2b[m2V H GmM2X miQKiB[m2 f _Q#QiB[m2X AMbiBimi LiBQMH SQHvi2+?MB[m2 /2 hQmHQmb2

UALS hQmHQmb2V- kyRjX i2H@yRRy93N8

Institut National Polytechnique de Toulouse

NumØro d"Ordre : AnnØe : 2013

Habilitation à diriger les recherches

prØparØe au prØsentØe et soutenue publiquement, le 03/12/2013, par

Nicolas Jozefowiez

Maître de confØrences en informatique à

Institut National des Sciences AppliquØes de Toulouse

Titre :

Optimisation combinatoire multi-objectif :

des méthodes aux problèmes,de la Terre à (presque) la Lune

Jury :

Rapporteurs : M.GendreauProfesseur titulaire, Ecole Polytechnique de MontrØal P.MaheyProfesseur des universitØs, UniversitØ Blaise Pascal D.VanderpootenProfesseur des universitØs, UniversitØ Paris Dauphine Examinateurs : G.LaporteProfesseur titulaire, HEC MontrØal

P.LopezDirecteur de recherche, LAAS-CNRS

F.MessineMaître de ConfØrences-HdR, ENSEEIHT-INPT F.SemetProfesseur des universitØs, Ecole Centrale de Lille

D.VigoProfesseur, Università di Bologna

RemerciementsJe remercie les membres du Jury pour avoir acceptØ de participer à ce jury et d"avoir consacrØ

une partie de leur temps à cette tâche, notamment FrØdØric Messine qui a eu la gentillesse

d"accepter d"Œtre mon correspondant INPT. Je prØsente tous mes remerciements à FrØdØric Semet

ce jury. Je remercie aussi l"Øquipe ROC qui est plus qu"une simple Øquipe de recherche et ses membres,

Pierre, Sandra. Je remercie aussi mes doctorants passØs et prØsents : Panwadee, Boadu, Leonardo

et Leticia. Travailler à Toulouse est agrØable aussi de par la qualitØ des personnes que l"on y

côtoie : Alain, Aude, Catherine, Marcel, Pierre-Emmanuel, Sonia... Je tiens aussi à saluer ici tous

comme Clarisse ; ceux rencontrØs au loin dans le froid QuØbecquois : Fausto, Gunes, Maria, Massimo, Stefan, Tolga ... ; et ceux que j"ai eu la chance de rencontrer ici ou ailleurs : Adrien, Murat, Thierry ... Je remercie aussi les personnes qui ont su Œtre une aspiration de par leur rencontre ou la collaboration avec eux et qui sont trop nombreux pour Œtre citØs ici. Je tiens

Gilbert.

Enn, je remercie toutes ces personnes qui font que les journØes ne se rØsument pas à tenter least, il me reste à remercier ma famille. Il est probable que j"ai oubliØ de nombreuses personnes. A tous, merci. "Questions don"t have to make sense [...] but answers do." [Terry Pratchett,Thief of time] "Logic is a wonderful thing but doesn"t always beat actual thought." [Terry Pratchett,The last continent]

Table des matières

Parcours depuis le doctorat 1

Introduction3

I Principes généraux et méthodes 7

1 Optimisation combinatoire multi-objectif 9

1.1 DØnitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2 Approches de rØsolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.3 UtilitØ et utilisation de l"optimisation multi-objectif . . . . . . . . . . . . . . . . .

13

1.4 StratØgies de prise en compte des objectifs . . . . . . . . . . . . . . . . . . . . . .

15

1.4.1 Approches non-scalaires . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1.4.2 Approches scalaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

1.4.3 Approches Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 9

1.4.4 Approches basØes sur des indicateurs . . . . . . . . . . . . . . . . . . . . .

20

1.5 MØthodes d"optimisation multi-objectif . . . . . . . . . . . . . . . . . . . . . . . .

21

1.5.1 Bornes supØrieures et infØrieures . . . . . . . . . . . . . . . . . . . . . . .

21

1.5.2 MØthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

1.5.3 MØthodes heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2 Contributions méthodologiques 27

2.1 MØthodesanytimemulti-objectif . . . . . . . . . . . . . . . . . . . . . . . . . . .2 7

2.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.1.2 ReprØsentativitØ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.1.3 UniformitØ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.1.4 EcacitØ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.2 Une Øtude en trois phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

2.2.1 Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3

2.2.2 SpØcialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.2.3 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.3 Algorithmes gØnØtiques à clefs alØatoires biaisØs multi-objectif . . . . . . . . . . .

34

2.3.1 ProblØmatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.3.2 Algorithmes gØnØtiques à clefs alØatoires . . . . . . . . . . . . . . . . . . .

35
36
i iiTABLE DES MATIÈRES 36

2.4 Algorithme de sØparations et coupes multi-objectif . . . . . . . . . . . . . . . . .

38

2.4.1 Principe de l"approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 8

2.4.2 Bornes infØrieures et supØrieures . . . . . . . . . . . . . . . . . . . . . . .

3 8

2.4.3 Calcul de la borne infØrieure . . . . . . . . . . . . . . . . . . . . . . . . . .

40

2.4.4 Elagage et Ølagage partiel . . . . . . . . . . . . . . . . . . . . . . . . . . .

40
41

2.4.6 Exemple numØrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 2

2.5 GØnØration de colonnes en optimisation combinatoire multi-objectif . . . . . . . .

43
44

2.5.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45
46

2.5.4 RØsultats de rØsolution basique . . . . . . . . . . . . . . . . . . . . . . . .

46

2.5.5 StratØgie de recherche de colonnes . . . . . . . . . . . . . . . . . . . . . .

47
II Application au transport terrestre et à la logistique 51

3 Problème du voyageur de commerce avec labels 53

3.1 DØnition et modØlisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53
56

3.3 RØsolutions mono-objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.4 RØsolution bi-objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.4.1 DØnition de la borne infØrieure . . . . . . . . . . . . . . . . . . . . . . . .

58

3.4.2 Elagage partiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58
59

3.4.4 GØnØration de coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

3.4.5 Calcul ecace de la borne infØrieure . . . . . . . . . . . . . . . . . . . . .

59

3.5 RØsultats expØrimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

4 Problèmes de tournées couvrantes 63

63

4.1.1 ModØlisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64
64
65
65

4.2 Algorithme de branch-and-price pour la version mono-objectif . . . . . . . . . . .

6 6 67
67
69

4.2.4 Application de la gØnØration de colonnes et stratØgies de branchement . .

69

4.2.5 RØsultats expØrimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

4.3 Application de la gØnØration de colonnes à la version bi-objectif . . . . . . . . . .

71
71
71

4.3.3 Heuristique pour IPPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

TABLE DES MATIÈRESiii

4.3.4 Heuristique pour SOGA . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

4.3.5 RØsultats expØrimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

III Application au spatial 77

5 Observation de la Terre par satellites agiles 79

79

5.2 Algorithme gØnØtique à clefs alØatoires biaisØ . . . . . . . . . . . . . . . . . . . .

82

5.2.1 Evaluation des solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

5.2.2 DØcodage basique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

5.2.3 DØcodage avec prioritØ idØale . . . . . . . . . . . . . . . . . . . . . . . . .

82

5.2.4 DØcodage hybride . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

5.2.5 VØrication des contraintes durant le dØcodage . . . . . . . . . . . . . . .

84

5.3 Recherche locale multi-objectif basØe sur des indicateurs . . . . . . . . . . . . . .

84
85

5.3.2 GØnØration de la population initiale - autres itØrations . . . . . . . . . . .

86

5.3.3 Etape de recherche locale . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.4 RØsultats expØrimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

Conclusions et perspectives 93

A CV détaillé111

B Bibliographie personnelle 115

C Articles119

ivTABLE DES MATIÈRES

Liste des tableaux

1.1Valeurs des objectifs pour les meilleures solutions trouvØes par Taburoute et l"AG

de Prins. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1 Analyse de la sensibilitØ pour le nombre de labels et d"itØrations. . . . . . . . . .

37

3.1 RØsumØ des rØsultats pour l"algorithme de sØparations et coupes. . . . . . . . . .

62

3.2 RØsumØ des rØsultats pour l"algorithme de sØparations et coupes tronquØ. . . . . .

62

4.1 Temps de calcul (secondes cpu). . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73
74

4.3 Nombre de colonnes gØnØrØes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74
v viLISTE DES TABLEAUX

Table des figures

1.1Les deux buts de l"optimisation multi-objectif dans la recherche d"une approximation.11

1.2 ReprØsentation de la surface dominØe par un ensemble par rapport à un point de rØfØrence calculØ par l"hypervolume. . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3 Un ensemble potentiellement non-dominØ pour le CCVRP. . . . . . . . . . . . . .

14

1.4 La mØthode lexicographique dans le cas bi-objectif. . . . . . . . . . . . . . . . . .

1 6

1.5 La mØthode d"agrØgation pour∞=?= 0:5. . . . . . . . . . . . . . . . . . . . .1 7

1.6 La mØthode-contrainte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18

1.7 Exemple de ranking. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

1.8 Illustration de l"indicateurIHD(issue de [145]). . . . . . . . . . . . . . . . . . . .21

1.9 Point idØal et relaxation, point nadir, borne infØrieure. . . . . . . . . . . . . . . .

22

1.10 Illustration de la mØthode en deux phases. . . . . . . . . . . . . . . . . . . . . . .

23

1.11 Illustration de l"utilisation de la mØthode-contrainte. . . . . . . . . . . . . . . .25

1.12 DiØrences entre les approches classiques et l"optimisation basØe sur des ensembles.

26

2.1 Illustration de la reprØsentativitØ. . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.2 UniformitØ de la convergence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.3 EcacitØ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

2.4 Une Øtude en trois phases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3

2.5 Gestion de la population dans BRKGA. . . . . . . . . . . . . . . . . . . . . . . .

3 5 2.6 Relations de dominance possibles entre la borne infØrieure (cercle) et la borne supØrieure (carrØ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.7 ligne) donne la valeur des deux objectifs et dex∞etx?pours?(resp.s∞ets?). .42 2.8 ets?). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43 2.9 etx?pours?(resp.s∞ets?). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44

2.10 Bornes infØrieures pour une instance du UBPP. . . . . . . . . . . . . . . . . . . .

47

3.1 Une solution pour le MLTSPM. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.2 Une contrainte (3.9) est violØe pouriet le label reprØsentØ par des tirets. . . . . .55

3.3 Une contrainte (3.11) est violØe pourSet le label reprØsentØ par des tirets. . . . .56

vii viiiTABLE DES FIGURES

4.1 Borne infØrieure et borne supØrieure pourjVj= 50;jWj= 150;p= 5;q= +1. . .7 5

5.1 Prise de vue par le satellite [97]. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

5.2 Exemple de dØcoupage en strips et de spot [92]. . . . . . . . . . . . . . . . . . . .

81

5.3 DØcoupage d"un polygone en strips et direction d"acquisition [92]. . . . . . . . . .

81

5.4 Exemple de calcul de prioritØ idØale. . . . . . . . . . . . . . . . . . . . . . . . . .

83

5.5 Gestion de l"ensemble de solutions Ølites lors du dØcodage hybride. . . . . . . . .

84

5.6 VØrication des contraintes et aectation des acquisitions. . . . . . . . . . . . . .

85

5.7 Exemple de solutions pour l"instance modiØe. . . . . . . . . . . . . . . . . . . . .

86

5.8 GØnØration alØatoire de la population initiale. . . . . . . . . . . . . . . . . . . . .

88

5.9Comparaisons des valeurs d"hypervolume et des temps de calcul entre BRKGA et

IBMOLS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.10 d"arrŒt dynamique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

5.11 Meilleure approximation pour chaque instance. . . . . . . . . . . . . . . . . . . .

91
quotesdbs_dbs47.pdfusesText_47

[PDF] mathématiques tout en un 2e année mp mp * pdf

[PDF] mathématiques tout en un pour la licence 3 pdf

[PDF] mathématiques tout en un pour la licence niveau l1 pdf

[PDF] mathématiques tout-en-un pour la licence 1 pdf gratuit

[PDF] Mathématiques Transmaths 3éme

[PDF] Mathematiques triangle, pyramide

[PDF] Mathématiques Une énigmes

[PDF] Mathematiques Une histoire

[PDF] Mathématiques Urgennt !!!!

[PDF] Mathématiques variations maths ,

[PDF] Mathematiques vrai ou faux

[PDF] Mathematiques!

[PDF] Mathématiques(PGCD) quatrième (4))

[PDF] Mathématiques, Conjecture , Effectuer

[PDF] Mathématiques, développement et factorisation Merci de m'aider