[PDF] Optimisation multi-objectif par colonies de fourmis: cas des





Previous PDF Next PDF



La proportionnalité

Les différents types de problèmes. ?La proportionnalité simple et directe ?Problèmes de proportionnalité composée et multiple. G. Martiel -2014 ...



La résolution de problèmes et la typologie Vergnaud

25 sept. 2017 proportionnalité simple composée. – proportionnalité multiple (aire



Optimisation combinatoire multi-objectif: des méthodes aux

19 janv. 2015 Je remercie aussi l'équipe ROC qui est plus qu'une simple équipe de recherche et ses ... 2.3.3 Application aux problèmes multi-objectif .



Mathématiques Résoudre des problèmes grâce à la notion de multiple

il est un multiple du plus petit commun multiple de ces trois nombres. Cette propriété n'étant pas au programme du cycle 4 il semble préférable de considérer l 



Une introduction au problème des tests multiples

10 sept. 2009 2 Formalisation du problème. Test simple. Tests multiples. 3 Méthodologie. Contrôle du FWER. Contrôle du FDR. Autres approches. 4 Conclusion.



Étude du Problème de la Patrouille Multi-Agents en Système Ouvert

20 nov. 2012 Ce problème est un bon cas d'étude pour la coordination dans les systèmes multi-agents : il est suffisamment simple pour être facilement ...



Optimisation multi-objectif par colonies de fourmis: cas des

27 juin 2011 3.4 Méthodes transformant le problème multi-objectif en un problème ... plus simple de mettre en oeuvre ce système d'interdictions consiste ...



Perceptron simple Perceptron multi-couches

Le problème de l'apprentissage dans les perceptrons multi-couches est de connaitre la contribution de chaque poids dans l'erreur globale du réseau. L'algorothme 



Chapitre 4 : Kit 3 : Proportionnalité simple composée et

Enjeux : Etablir des tableaux de correspondance pour résoudre un problème de proportionnalité multiple (dans ce cas-ci il s'agit même 



Mathématiques Résoudre des problèmes mobilisant les nombres

Justifier. • Le produit de trois nombres pairs est un multiple de 8. • La somme de deux nombres impairs est un nombre impair.

>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

vØhicules et amØliorØes via l"utilisation du parallØlisme et de la coopØration entre diØrentes

une sØrie de postdoctorats. Tout d"abord, j"ai passØ une annØe à l"UniversitØ du Colorado à Boulder,

nancØe par une bourse Fulbright. Puis, j"ai occupØ un poste d"ATER à l"UniversitØ de Valenciennes

et du Hainaut-CambrØsis et nalement j"ai ØtØ stagiaire postdoctoral au Centre Interuniversitaire

de Recherche sur les RØseaux d"Entreprise, la Logistique et le Transport (CIRRELT) à MontrØal,

Canada.

J"ai ØtØ recrutØ en fØvrier 2008 sur un poste de maître de confØrences au DØpartement de

GØnie Electrique et Informatique de l"Institut National des Sciences AppliquØes de Toulouse.

Au niveau recherche, j"ai ØtØ aectØ à l"Øquipe ModØlisation, Optimisation et Gestion IntØgrØe

(LAAS-CNRS). L"Øquipe MOGISA travaille sur l"optimisation combinatoire avec un intØrŒt initial

pour la programmation par contrainte et l"ordonnancement. Cependant avant mon arrivØe, des

recrutements et un Ølargissement des domaines d"application ont poussØ l"Øquipe à s"intØresser à

la recherche opØrationnelle plus globalement, notamment la programmation mathØmatique et son application au transport. C"est donc par rapport à ce point que mon recrutement a eu lieu. J"ai continuØ à m"intØresser à l"optimisation multi-objectif, en devenant notamment co- animateur du groupe de travail PM2O1de la ROADEF. Cependant, dans un premier temps, je

me suis moins focalisØ sur les mØta-heuristiques et plus sur les mØthodes de recherche arborescente

pour l"optimisation multi-objectif. J"ai aussi Ølargi les domaines applicatifs en menant des Øtudes

dans les Øtudiants en doctorat que j"encadre sur les sujets suivants : gØnØration de colonnes

pour l"optimisation multi-objectif, mØta-heuristiques multi-objectif pour l"observation de la

Terre par satellites, gestion de rØseau de services porte-à-porte et la proposition de nouvelles

mØta-heuristiques multi-objectif pour l"humanitaire.1. http ://www.lifl.fr/PM2O/ (Programmation Mathématique Multi-Objectif).

1

2PARCOURS DEPUIS LE DOCTORAT

trouver parmi un ensemble discret de solutions respectant des contraintes une solution qui comme "faciles", c"est-à-dire pour lesquels il existe un algorithme polynômial pour trouver la que la solution renvoyØe est bien optimale, c"est-à-dire qu"il n"existe pas d"autres solutions pour lesquelles la fonction objectif a un meilleur score. Une mØthode exacte basique serait y compris pour des instances de petites tailles. On parle d"explosion combinatoire. Il est cependant possible de dØnir des mØthodes permettant de repousser la taille des instances pouvant Œtre

rØsolue à l"optimalitØ. On peut citer notamment les ØnumØrations implicites qui exploitent des

informations fournies par des bornes infØrieures et supØrieures sur la valeur de l"objectif pour

ne pas explorer toutes les solutions. Dans ce document, on utilisera notamment des approches

utilisant la programmation linØaire en nombres entiers [141,104]. Cependant, les mØthodes dites

en temps de calcul "raisonnable", en dØpit des avancØes mØthodologiques et de l"augmentation de

la puissance de calcul des ordinateurs. Il est alors possible d"utiliser des mØthodes approchØes,

soit des heuristiques ad-hoc soit des mØthodes exploitant les stratØgies plus gØnØralistes que sont

les mØta-heuristiques. Ces approches trouvent des solutions sans garantie sur leur qualitØ en

contrepartie d"un temps de calcul moins prohibitif ou plus facilement maîtrisable qu"une mØthode

exacte [127].

sources dans les travaux de Edgeworth [42] et de Pareto [108] dans le cadre d"Øtudes d"Øconomie

milieu des annØes 1980 [125] et le domaine connaît une expansion importante depuis le milieu des2. ce qui ne signifie pas qu"il n"en existe pas.

3

4INTRODUCTIONannØes 1990 avec l"apparition de mØthodes Øvolutionnaires pour l"optimisation multi-objectif [30].

Actuellement, l"optimisation multi-objectif est appliquØe dans de nombreux domaines acadØmiques

la formeminF(x) = (f∞(x);f?(x);:::;fn(x))tel quexsoit une solution rØalisable. La solution ensemble non-dominØ. Les composantes du vecteurFsont les diØrentes fonctions à optimiser. Les solutions de cet ensemble sont nommØes solutions non-dominØes. Ces solutions sont celles

pour lesquelles l"amØlioration d"un des objectifs entraîne systØmatiquement la dØtØrioration de la

qualitØ d"au moins un autre objectif. La prØsence d"objectifs contradictoires apporte de nouveaux

dØs à relever pour les mØthodes d"optimisation. Notamment, s"il existe une littØrature foisonnante

dØdiØe aux mØthodes approchØes, l"application de mØthodes exactes est moins rØpandue.

Ce document n"est pas un reet complet de l"ensemble des travaux que j"ai eectuØs depuis mon

doctorat. Il se focalise sur mes travaux portant sur des mØthodes pour l"optimisation multi-objectif

d"ordonnancement bi-objectif [6] ne se retrouve pas non plus ici.

partie, est dØdiØe aux concepts d"optimisation combinatoire multi-objectif et aux mØthodes. La

sur l"observation de la Terre par des satellites. Les satellites d"observation volent à 700-1000 kms

d"altitude environ, on est donc un peu loin de la lune promise dans le titre du document mais on s"en approche. Le chapitre 1 pose le contexte du travail : l"optimisation combinatoire multi-objectif. Les

principales dØnitions sont prØsentØes ainsi que les problØmatiques spØciques par rapport à

l"optimisation standard. Les principales stratØgies de prise en compte de la prØsence de plusieurs

objectifs sont aussi exposØes. Un panorama des mØthodes de la littØrature est aussi fait. Les

diØrents mØcanismes, outils et mesures utiles pour le reste du document sont Øgalement introduits

dans ce chapitre.

toire multi-objectif. Dans un premier temps, les caractØristiques recherchØes dans les mØthodes

sur la gØnØration de colonnes pour l"optimisation combinatoire multi-objectif notamment pour calculer des bornes infØrieures.

5par la description de l"implØmentation de l"algorithme de sØparations et coupes prØsentØ dans le

rØsultats de la mØthode bi-objectif face à une approche basique itØrant l"algorithme mono-objectif

guidØ par une mØthode-contrainte. les sommets n"est pas obligatoire. Dans un premier temps, un algorithme de branch-and-pricequotesdbs_dbs47.pdfusesText_47
[PDF] Multiples de 7

[PDF] multiples et diviseurs 5ème

[PDF] multiples et diviseurs 5ème exercices

[PDF] multiples et diviseurs 6ème

[PDF] multiples et diviseurs cm1

[PDF] multiples et diviseurs cm2

[PDF] multiples et diviseurs de 4

[PDF] multiples et diviseurs exercices

[PDF] multiples et diviseurs exercices ? imprimer

[PDF] Multiples et pourcentages de mathematiques

[PDF] Multiples et sous multiples de l'intensité

[PDF] multiplicateur de budget équilibré

[PDF] multiplicateur fiscal calcul

[PDF] multiplication

[PDF] Multiplication