UNIVERSIT DU QUBEC

MMOIRE PRSENT

L'UNIVERSIT DU QUBEC CHICOUTIMI

COMME EXIGENCE PARTIELLE

DE LA MATRISE EN INFORMATIQUE

Par

Eunice Adjarath LEMAMOU

Ordonnancement de projet sous contraintes de ressources l'aide d'un algorithme gntique croisement hybride de type

OER

27 Aot 2009

bibliothquePaul-Emile-Bouletj

UIUQAC

Mise en garde/Advice

Afin de rendre accessible au plusgrand nombre le rsultat destravaux de recherche mens par sestudiants gradus et dans l'esprit desrgles qui rgissent le dpt et ladiffusion des mmoires et thsesproduits dans cette Institution,l'Universit du Qubec Chicoutimi (UQAC) est fire derendre accessible une versioncomplte et gratuite de cette uvre.

Motivated by a desire to make theresults of its graduate students'research accessible to all, and inaccordance with the rulesgoverning the acceptation anddiffusion of dissertations andtheses in this Institution, theUniversit du Qubec Chicoutimi (UQAC) is proud tomake a complete version of thiswork available at no cost to thereader.

L'auteur conserve nanmoins laproprit du droit d'auteur quiprotge ce mmoire ou cette thse.Ni le mmoire ou la thse ni desextraits substantiels de ceux-ci nepeuvent tre imprims ou autrementreproduits sans son autorisation.

The author retains ownership of thecopyright of this dissertation orthesis. Neither the dissertation orthesis, nor substantial extracts fromit, may be printed or otherwisereproduced without the author'spermission.

11

RESUME

Le problme de gestion de projet sous contraintes de ressources (ResourceConstrained Project Scheduling Problem) consiste en l'ordonnancement de tches,galement appeles activits, l'aide d'une ou plusieurs ressources renouvelables ou non,en quantit limite. Le but vis par la rsolution de ce problme est la dtermination desdates d'excution des activits en fonction de la disponibilit des ressources et de faon satisfaire des objectifs fixs. Les activits sont lies entre elles par des contraintes deprsance qui doivent tre respectes lors de l'ordonnancement.

Depuis plus de 30 ans, de nombreuses tudes ont t consacres au RCPSP qui estun problme NP-difficile au sens fort. L'aspect pratique de ce problme dans des contextesindustriels divers a conduit de nombreuses recherches et ainsi des rsolutions par desmthodes heuristiques et mtaheuristiques. Les algorithmes gntiques (AG) figurent parmiles mtaheuristiques qui perforaient le mieux pour la rsolution de ce problme.L'optimisation par essaims particulaire (OEP), quant elle, est une mthode mergente quiintresse de plus en plus de chercheurs dans le domaine de l'optimisation discrte et quidonne d'assez bons rsultats.

Ce mmoire propose une hybridation de ces.deux mthodes dans le but d'amliorerleurs performances individuelles sur des instances de taille moyenne. L'hybridation se faitau niveau du croisement en combinant deux mthodes de croisement, l'une tant lecroisement classique deux points largement rpandu au sein de la littrature. La secondemthode de croisement est nouvelle et se base sur un concept de distances entre deuxsolutions emprunt un algorithme d'OEP de la littrature traitant du problme deminimisation du retard total pondr sur une machine unique. Cet algorithme a d'abord treproduit et adapt au RCPSP. La comparaison des performances obtenues avec celles desdeux autres algorithmes d'OEP connus dans la littrature du RCPSP a t favorable cetteadaptation. Cela a donn lieu la conception d'une mthode de croisement qui s'inspire desprincipes de l'OEP et du concept de distances pour gnrer de nouvelles solutions. Lesperformances observes lors de l'hybridation des deux mthodes de croisement ci-dessusnumres montrent bien l'apport de cette technique innovatrice que constitue l'OEPdiscrte pour la rsolution du RCPSP.

Ce travail de recherche reprsente surtout une premire exploration du potentieloffert par la technique de l'OEP et sa combinaison avec deux autres champs de rechercheen volution continue : le RCPSP et les AG. L'association de ces trois domaines derecherche laisse entrevoir des possibilits intressantes pouvant mener la conception denouveaux algorithmes plus performants pour la rsolution du RCPSP. Ce mmoireconstitue une contribution non seulement vers une meilleure connaissance de l'OEP maisaussi vers l'amlioration des outils d'optimisation en gestion de projet.

Ill

DEDICACE

Je ddie ce mmoire Allah, qui m'a tout donn.

Allah, je dsire T'aimer et que mon amour jamais ne s'teigne.

IV

REMERCIEMENTS

Mes remerciements vont d'abord ma directrice de recherche Mme Caroline Gagn,

et mon codirecteur de recherche M. Marc Gravel, pour leur disponibilit, leur implication

et leur support tout au long de ce travail de recherche. Je leur suis particulirement

reconnaissante d'avoir t attentifs mes ides et mes commentaires, et aussi pour avoir

su rpondre mes nombreuses interrogations. Sans leurs conseils aviss et leur dynamisme,

ce travail de recherche n'aurait sans doute pas vu le jour.

je remercie galement M. Jean Rouette et M. Michel Gagnon pour avoir accept

d'valuer ce travail ainsi que pour leurs judicieux commentaires.

Un travail de recherche ne pourrait tre ralis sans support financier. ce titre, je

voudrais remercier l'Agence Canadienne de Dveloppement International (ACDI) qui, par

le biais du programme canadien de bourse de la francophonie (PCBF), m'a entirement

financ durant ces deux annes d'tudes.

J'adresse aussi mes remerciements aux membres du Dpartement d'Informatique et

de Mathmatique (DIM) pour le travail qu'ils effectuent afin de nous offrir un cadre

d'tudes agrable, en particulier M. Richard Bouchard qui a mis ma disposition un

laboratoire pour mes exprimentations. Je remercie galement les secrtaires de

dpartement et de programme Johanne Labrie et Suzanne Girard pour m'avoir aid voir la

vie plus belle. Vos sourires rchauffent bien des curs.

Je remercie aussi tous les membres du Groupe de Recherche en Informatique de

l'UQAC (GRI) pour la bonne ambiance qu'ils ont su mettre dans les locaux du GRI. Je

remercie tout spcialement Arnaud Zinflou, mon compagnon de bureau, pour sa prsence et

pour ses conseils aviss. Je le remercie aussi pour avoir prt une oreille attentive mes

babillages incessants et pour avoir su me rconforter lors des moments difficiles.

J'aimerais aussi remercier sincrement mes parents, mes surs, mon frre Ibrahim,

ma belle-sur Genevive, et toute ma famille pour leur soutien et leur confiance. Us ont

toujours cru en moi et m'ont toujours pouss aller de l'avant. Sans leur soutien et leur

amour, ce travail n'aurait jamais pu tre ralis. Un gros merci mon adorable neveu,

Noah, qui a ensoleill mes journes sombres. Je tiens vous dire tous, combien je vous

aime.

Je tiens aussi remercier mon conjoint Kfil Landou pour sa patience, sa

comprhension et son soutien malgr la distance qui nous a spars tout au long de

l'accomplissement de ce travail.

J'aimerais enfin remercier tous ceux qui, de prs ou de loin, ont contribu

l'aboutissement de ce mmoire.

VI

TABLE DES MATIERES

RSUM . . n

DEDICACE................................. .......................................................... ......... iii

REMERCIEMENTS v

TABLE DES MATIRES vi

LISTE DES TABLEAUX ix

JLI* 1 IL SJxJS) Jr ICjUJvtt/3 ..............................................................................., xil

CHAPITRE 1 : INTRODUCTION 1

CHAPITRE 2 ; LE PROBLEME D'ORDONNANCEMENT DE PROJET SOUS

CONTRAINTES DE RESSOURCES DANS LA LITTRATURE 10

2. Introduction

2.2 La reprsentation du RCPSP dans la littrature 12

2.3 Les mthodes de rsolution du RCPSP 15

2.3.1 Les mthodes exactes 15

2.3.2 Les mthodes approches ou heuristiques 17

2.4 Conclusion 26

CHAPITRE 3 : MTAHEURISTIQUES : LES ALGORITHMES GNTIQUES ET

L'OPTIMISATION PAR ESSAIMS PARTICULAIRES 27

3.1 Introduction 28

3.2 Les algorithmes gntiques (AG) 28

3.2.1 Analogie avec la gntique 29

3.2.2 Le principe d'un algorithme gntique 31

3.2.3 La reprsentation des individus (encodage) 33

3.2.4 La gnration de la population initiale 34

3.2.5 La slection 35

VII

3.2.6 Le croisement 46

3.2.7 La mutation 54

3.3 L'optimisation par essaims particulaires (OEP) 56

3.3.1 Fonctionnement gnral de 'OEP 57

3.3.2 L'OEP pour l'optimisation continue 58

3.3.3 L'OEP pour l'optimisation combinatoire 63

3.4 Objectifs de la recherche 65

3.5 Conclusion 67

CHAPITRE 4 : ALGORITHME D'OPTIMISATION PAR ESSAIMS

PARTICULAIRES ET ALGORITHME GNTIQUE POUR LE RCPSP. 68

4.1 Introduction 69

4.2 Conception d'un algorithme d'OEP discrte pour le RCPSP 69

4.2.1 Description de l'algorithme 70

4.2.2 Essais numriques et rsultats obtenus 80

4.2.3 Comparaison avec les algorithmes OEP proposs par Zhang et al. [2005] 93

4.3 Reproduction d'un AG avec croisement deux points (AG2P) 97

4.3.1 Description de l'algorithme 97

4.3.2 Essais numriques et rsultats obtenus 102

4.4 Conclusion 104

CHAPITRE S: HYBRIDATION DE L'ALGORITHME GNTIQUE ET DE

L'OPTIMISATION PAR ESSAIMS PARTICULAIRES 106

5.1 Introduction 107

5.2 Conception d'un croisement de type OEP pour F AG 108

5.2.1 Description du croisement de type OEP 108

5.2.2 Essais numriques et rsultats obtenus 109

5.3 Combinaison du croisement deux points avec le croisement de type OEP... 24

5.3.1 Essais numriques et rsultats obtenus 124

5.3.2 Comparaisons et analyse des rsultats 135

5.4 Conclusion 137

CHAPITRE 6 : CONCLUSION. 139

V1I1

BIBLIOGRAPHIE .... 146

IX

LISTE DES TABLEAUX

Tableau 2.1 : Dfinition des variables utilises dans le RCPSP 13

Tableau 4.1 : Rsultats obtenus avec l'alternative UPl 82

Tableau 4.2 : Rsultats obtenus avec l'alternative UP2 83

Tableau 4.3 : Rsultats obtenus par l'algorithme avec le facteur de constriction/ 85

Tableau 4.4 : tude compare des algorithmes OEP par rapport l'utilisation du facteur de

constriction / , sur l'ensemble d'instances J30 87

Tableau 4.5 ; Rsultats obtenus par l'algorithme OEP utilisant une liste LIFO 89

Tableau 4.6 : Rsultats obtenus par l'algorithme OEP utilisant une liste mixte 91

Tableau 4.7 : Rsultats obtenus par l'algorithme OEP(UPl,Ang,LIF0r) sur l'ensemble

d'instances J30 par rapport au nombre de solutions values 95

Tableau 4.8 : Tableau comparatif de l'algorithme OEP(UPl,Ang,LIF0,-) avec ceux de

Thmgetal. [2005] 96

Tableau 4.9 : Rsultats obtenus par l'algorithme AG2P 103

Tableau 5.1 : Rsultats obtenus par l'algorithme AGOEP(Ang,FIFO,-) 111

Tableau 5.2 : Rsultats obtenus par l'algorithme AGOEPC&FIFO,-) 113

Tableau 5.3 : Rsultats obtenus par l'algorithme AGOEP(#,L/F0,-) 115

Tableau 5.4 : Rsultats obtenues par l'algorithme KGom(x,Mixte,-) i 17

Tableau 5.5 : Rsultats obtenus en variant la taille de population sur l'ensemble J30 avec

l'algorithme AGOB%FIFO,~) 120

X

Tableau 5.6 : Rsultats obtenus en variant la taille de population sur l'ensemble 330 avec

l'algorithme AGOEPCf,L/Fa-) 120

Tableau 5.7 : Rsultats obtenus en variant la taille de population sur l'ensemble 360 avec

l'algorithme AGOEPnp(x,FIFO,-,25%) 133

XI

Tableau 5.17 : Rsultats obtenus en variant la taille de la population sur l'ensemble J60

avec l'algorithme AGOEmp(x>Mixte,-,15%) 133

Tableau 5.18 : Rsultats obtenus en variant la taille de la population sur l'ensemble J120

avec l'algorithme AGOEmp(x,Mixte,-,5%) 134

Tableau 5.19 : Comparaison des rsultats obtenus par les algorithmes AG2P,

AGOE%FIFO,-) et AGOEm\,FIFO,-,25%) 136

Xl

LISTE DES FIGURES

Figure 2.1 : Exemple de projet avec ordonnancement minimal [Baptiste et al. 2005] 14

Figur 2.2 : Exemple d'ordonnancement avec l'algorithme srie et l'algorithme parallle 19

Figure3.1 : Structure gnrale d'un algorithme gntique [Dro tal. 2003] 32

Figure 3.2 : Exemple de slection par la mthode du tirage roulette [Davis 1991] 39

Figure 3.3 : Algorithme de la slection universelle stochastique [Gen et Cheng 1997] 40

Figure 3.4 : Exemple de la slection universelle stochastique 41

Figure 3.5 : Exemple de slection par la slection stochastique avec remplacement 42

Figure 3.6 : Exemple de slection par la slection stochastique sans remplacement 44

Figure 3.7 : Illustration du croisement deux points 48

Figure 3.8 : Illustration du croisement partiellement trac (PMX) 49

Figure 3.9 : Illustration du croisement par ordre (OX) 50

Figure 3.10 ; Illustration du croisement par cycle (CX) 51

Figure 3.11 : Carte d'artes initiale 52

Figure 3.12 : Illustration du croisement par recombinaison d'artes (EKX) 53

Figure 3.13 : Illustration de la mutation par insertion 55

Figure 3.14 : Illustration de la mutation par change 55

Figure 3.15 : Illustration de la technique de l'inversion [Sait et Youssef 1999] 55

Figure 3.16 : Principe de l'algorithme d'optimisation par essaims particulaires 58

X l l l

Figure 4.1 : Pseudo-code de l'algorithme d'OEP pour rsoudre le RCPSP 71

Figure 4.2 : Calcul de la liste de dplacements d'une particule ni une particule ni 72

Figure 4.3 : Exemple de pseudo-insertion sur une particule itj 75

Figure 4.4 : Exemple de procdure de correction d'une pseudo-squence 76

Figure 4.5 : Pseudo-code de la procdure de rparation des prsances d'une particule. ...76

Figure 4.6 : Exemple d'application des mthodes de mise jour UP1 et UP2 79

Figure 4.7 ; Graphes de comparaison des rsultats obtenus par les alternatives de mise

jour UP1 et UP2 84

Figure 4.8 : Graphes de comparaison des rsultats des algorithmes OEP par rapport

l'utilisation du facteur de constriction x 86

Figure 4.9 : Graphe de comparaison des rsultats des algorithmes OEP par rapport

l'utilisation du facteur de constriction %> s u r l'ensemble J30 en fonction du nombre de

solutions values 88

Figure 4.10 : Graphes de comparaison des rsultats des algorithmes OEP par rapport au

type de liste utilis 90

Figure 4.11 : Graphes de comparaison des rsultats des algorithmes OEP utilisant les listes

FIFO, LIFO et Mixte 93

Figure 4.12 : Graphe de comparaison de l'algorithme OEP(UPl,Ang,LIFO,-) avec ceux de

Zhang et al. [2005] 96

Figure 4.13 : Pseudo code de l'algorithme AG2P 98

Figure 4.14 : Illustration du croisement tendu deux points 101

XIV

Figure 5.1 : Graphes de comparaison des rsultats des algorithmes AGOEF(Ang,FIFO,-) et

AG2P 112

Figmre 5.2 : Graphes de comparaison des rsultats des algorithmes AGOEP par rapport

l'utilisation du facteur de constriction 114

Figure 5.3 : Graphes de comparaison des rsultats des algorithmes AGOEP utilisant les

listes FIFO et LIFO 116

Figure 5.4 : Graphes de comparaison des rsultats des algorithmes AGOEP par rapport au

type de liste utilis 118

Figure 5.5 : Graphes de comparaison des algorithmes AGOEP/2P 10% et 25% de

croisement de type OEP sur l'ensemble d'instances J30 129

Figure 5.6 : Graphes de comparaison des algorithmes AGOEP/2P 10% et 15% de

croisement de type OEP sur l'ensemble d'instances J60 131

CHAPITRE 1

INTRODUCTION

Un projet est un ensemble fini d'activits entreprises dans le but de rpondre un

besoin prcis, dans des dlais fixs et dans la limite de l'enveloppe budgtaire alloue.

C'est donc une action temporaire avec un dbut et une fin, qui mobilise des ressources

identifies (humaines, matrielles, informationnelles et financires) durant sa ralisation,

qui possde un cot et fait donc l'objet d'une budgtisation de moyens et d'un bilan

indpendant de celui de l'entreprise qui le ralise. La gestion de projet est une dmarche

visant structurer, assurer et optimiser le bon droulement d'un projet suffisamment

complexe pour devoir tre planifi dans le temps et tre budgtis. Elle permet de matriser

les risques afin d'atteindre le niveau de qualit souhait au cours du projet.

L'un des problmes les plus souvent rencontrs en gestion de projet consiste en la

planification des diffrentes activits accomplir. Celle-ci peut tre effectue plus ou

moins facilement avec les outils familiers tels que les mthodes CPM (Critical Path

Method), PERT (Programm Evaluation and Review Technic) et le diagramme de GANTT

pour des projets de petite taille. Toutefois, ces mthodes ne prennent pas en compte la

gestion des ressources qui, dans un projet rel, sont de capacit limite. Il est donc utile de

faire appel des outils plus sophistiqus lorsque le nombre d'activits excuter au sein du

projet est important ou qu'il existe des contraintes sur les ressources. C'est dans ce cadre

que se situe le problme d'ordonnancement de projet sous contraintes de ressources, encore

appel RCPSP (Ressource Constrained Project Scheduling Problem).

Le RCPSP consiste en l'ordonnancement d'un ensemble donn de tches ou

activits, l'aide d'une ou de plusieurs ressources renouvelables ou non, en quantit

limite. La rsolution du RCPSP a pour but la dtermination des dates d'excution des

activits en fonction de la disponibilit des ressources et de faon satisfaire les objectifs

fixs. Ces objectifs peuvent consister, par exemple, en l'optimisation de la dure totale du

projet, de la date d'achvement ou de l'utilisation des ressources. Le RCPSP a plusieurs

applications dans le domaine industriel comme, par exemple, l'ordonnancement des

processus en informatique distribue, les problmes de dcoupe, les problmes courants

d'ordonnancement d'ateliers. On l'utilise aussi dans le domaine organisationnel pour

modliser certains problmes savoir, les problmes d'emploi du temps et les problmes de

planification de personnel.

Depuis plus de 30 ans, de nombreuses tudes ont t faites sur le RCPSP. Celui-ci

est en quelque sorte une gnralisation des problmes classiques d'ordonnancement comme

le flow-shop, le flow-shop hybride et le job-shop. Le RCPSP est un problme

d'optimisation NP-diffcile en raison de sa nature fortement combinatoire [Baptiste et al.

2005]. Plusieurs mthodes ont t utilises dans la littrature pour adresser ce problme.

Ces mthodes regroupent aussi bien les mthodes exactes que les mthodes approches.

Les mthodes exactes comprennent la programmation par contraintes [Baptiste et al. 2001],

les mthodes par sparation et valuation [Damay et Sanlaville 2006], les schmas de

branchement [Demeulemeester et Herroelen 2002], les bornes infrieures [Carlier et

Latapie 1991] et la programmation linaire [Mingozzi et al. 1998; Pritsker et al. 1969].

Quant aux mthodes approches, elles sont constitues des heuristiques telles que les

algorithmes srie et parallle [Kolisch 1996b], les rgies de priorit [Kolisch 1996a] et les

mtaheuristiques. Ces dernires incluent aussi bien des mthodes de recherche locale telles

que la recherche avec tabous [Pinson et al. 1994] et le recuit simul [Bouleimen et Lecocq

2003], que des mthodes volutives comme les algorithmes gntiques [Hartmann 2002],

l'optimisation par essaims particulaires [Zhang et al. 2005], les algorithmes de colonies de

fourmis [Merkle et al. 2002] et la recherche par dispersion (Scatter Search) [Debels et al.

2006]. Les algorithmes gntiques demeurent l'une des meilleures mthodes de rsolution

du RCPSP selon les mesures de performance effectues par Koiisch et Hartmann [2000;

2006].

Par sa nature fortement combinatoire, le RCPSP a fait l'objet de nombreux travaux

et il possde un large champ d'applications industrielles [Demassey 2003]. En informatique

distribue, l'ordonnancement des processus consiste excuter des processus (les activits)

sur des machines parallles ou multiprocesseurs (les ressources) en grant les exclusions

mutuelles et la synchronisation. Dans le domaine des textiles ou de la mtallurgie, les

problmes de dcoupe consistent dbiter de larges rouleaux de taille standard R en

rouleaux de moindres largeurs de faon minimiser le nombre de rouleaux initiaux. Ce

problme se modlise en un RCPSP avec une seule ressource de capacit R et o, chaque

rouleau dcouper correspond une activit de dure unitaire et de consommation gale

la largeur du rouleau. On peut citer aussi les problmes courants d'ordonnancement

d'ateliers (job-shop, flow-shop et open-shop) [Allahverdi et al. 2008] o des travaux,

dcomposs en squences d'opration, doivent tre excutes par des machines disjonctives

n'excutant qu'une opration la fois, chaque opration ayant sa machine ddie. Tous les

problmes d'ateliers sont des cas particuliers du RCPSP, o les activits sont les oprations

et la ressource est unitaire et correspond une machine. La consommation d'une activit est

de / sur la ressource ddie correspondante et de 0 sur toutes les autres ressources. Vignier

et al. [1999] proposent une version hybride du problme d'atelier cheminement unique

(flow-shop) qui sert modliser de nombreux cas industriels. La version classique est

constitue d'un ensemble de travaux possdant tous le mme nombre d'oprations traites

dans le mme ordre. La version hybride tend le problme d'atelier cheminement unique

en permettant, qu' chaque tape, les oprations soient excutes sur l'une des machines

identiques disponibles. C'est tout point de vue assimilable un problme

d'ordonnancement de projet o, chaque tape correspond une ressource d'une capacit

donne, et o les activits sont les oprations. Ces activits sont de consommation unitaire

sur la ressource requise, nulle sur les autres, et lies par les contraintes de prsance en

chanes. Une dfinition quivalente existe pour le problme d'atelier cheminements

multiples (joh-shop).

Le RCPSP a aussi des applications dans le domaine organisationnel comme, par

exemple, les problmes d'emploi du temps (planification d'horaires) [Baptiste et al. 2005].

Un exemple simple d'emploi du temps est celui de l'universit, o il est question de rpartir

les cours par enseignants, par salies et par crneaux horaires. Le problme se modlise en

un RCPSP, pratiquement de la mme manire qu'un problme d'atelier, mais o les

ressources (salles et enseignants) ont des capacits dpendantes du temps, les enseignants

n'tant disponibles qu' certaines priodes.

Le RCPSP possde plusieurs variantes bases sur le modle classique

(SMRCPSP ou Single-mode RCPSP). On distingue entre autres, le GRCPSP {Generalized

RCPSP), le PRCPSP (Preemptive RCPSP), le MMRCPSP (Multi-Mode RCPSP) et le

RCPSPR (RCPSP with Rework).

Le GRCPSP permet une meilleure modlisation du problme tudi. En effet, les

contraintes de prsance incluses dans le modle du GRCPSP sont plus prcises. Le modle

classique contient uniquement des relations de prsance du type finish-to-start (FS). Quant

au GRCPSP, il intgre galement des contraintes de prsance dites gnralises (GPR,

Generalized Precedence Relationships) : start-to-start (SS), finish-to-finish (FF) et start-to-

finish (SF). Dans ce modle, une activit peut partiellement s'excuter en mme temps que

l'un de ces prdcesseurs. Ce modle inclut galement des contraintes de ressources

gnralises : ressources partiellement renouvelables, ressources continuellement

divisibles, ressources ddies, ressources dont la disponibilit est variable. Pour rsoudre le

GRCPSP, Sampson et Weiss [1993] ont utilis des techniques de recherche locale ainsi que

Klein [2000] qui a utilis la recherche avec tabous, avec des rgles de priorit.

Demeulemeester et Herroelen [1997], quant eux, ont prfr utiliser les schmas de

branchement.

Le PRCPSP autorise la premption des activits. Le temps d'excution d'une

activit est divis en plusieurs priodes (l'activit est divise en plusieurs sous-activits) au

sein desquelles il n'y a pas de premption. L'objectif est alors de minimiser la date de dbut

au plus tt de la dernire opration de la dernire activit. Des contraintes de prsance

doivent tre rajoutes entre chaque sous-activit, contraintes de type FS. Les problmes

d'ateliers, dans lesquels une opration peut tre divise en plusieurs sous-activits

effectues sur la mme machine, sont des exemples de PRCPSP. Vanhoucke et Debels

[2008] prsentent l'tat de l'art des procdures utilises pour la rsolution du PRCPSP.

Demeulemeester et Herroeen [1996] ont aussi rsolu le problme en utilisant les schmas

de branchement.

Le MMRCPSP intgre la possibilit d'avoir plusieurs modes opratoires par

activit, l'oppos du SMRCPSP qui oblige chaque activit s'excuter dans un unique

mode opratoire. La notion de mode d'excution permet de spcifier les diverses faons

avec lesquelles une activit utilise une ou plusieurs ressources. Par exemple, une activit

qui ncessite une seule unit de ressource pour tre complte en 8 jours (mode 1), peut

tre excute en 4 jours avec deux units de ressource (mode 2). On peut y retrouver la

fois le GRCPSP et le PRCPSP. Kolisch et Sprecher [1997] prsentent une synthse des

mthodes utilises aussi bien pour le SMRCPSP que pour le MMRCPSP. Selon les auteurs,

les mthodes les plus utilises sont la programmation linaire et les mthodes par

sparation et valuation (Bmnch-and-Bound) pour les instances de petite taille. Pour des

instances de plus grande taille, les mthodes privilgies sont les heuristiques et les

algorithmes stochastiques.

Le RCPSPR consiste tenir compte des incertitudes dans l'ordonnancement de

projet sous contraintes de ressources. La plupart des mthodes de rsolution du RCPSP,

partent du principe que le travail faire est fait correctement sans qu'il ne soit ncessaire de

revenir l-dessus. B est suppos aussi que les conditions de travail sont idales et que les

dlais sont respects. Malheureusement, tel n'est pas souvent le cas en gestion de projet o

la gestion de la qualit prend une part importante [Tukel et Rom 1998]. H est souvent

ncessaire pour une raison ou une autre, de reprendre une ou plusieurs activits au cours

d'un projet, ou bien d'en prolonger la dure. Des retards de livraison ou l'indisponibilit de

g

certaines ressources peuvent aussi tre la base d'un non-respect de l'ordonnancement

initial. Cette variante du problme se retrouve trs peu dans la littrature. Tukel et Rom

[1997] dmontrent qu'il est plus intressant de tenir compte au cours de l'ordonnancement,

de la possibilit de reprendre une ou plusieurs activits au cours du projet. Ds utilisent la

routine d'optimisation OSL (Optimization Subroutine Library) d'IBM [Wilson et Rudin

1992J pour rsoudre le problme. Toutefois, selon Bean et Hadj-Alouane [1993], cette

mthode n'est pas efficace pour rsoudre les problmes d'optimisation lorsque le nombre

de variables est important (plus de 50 variables). Le terme 'robuste' est utilis pour

qualifier un algorithme qui prend en compte les incertitudes au cours de l'ordonnancement.

Ce mmoire traite plus particulirement du RCPSP classique avec minimisation de

la dure totale du projet. Un algorithme d'optimisation par essaims particulaires est propos

pour le rsoudre. Une nouvelle mthode de croisement pour les algorithmes gntiques est

aussi conue en se basant sur la mthode d'optimisation par essaims particulaires. Le

contenu du mmoire est organis en cinq chapitres.

Dans le Chapitre 2, le RCPSP est prsent de faon plus dtaille. Un tat de l'art

est aussi effectu quant aux mthodes utilises dans la littrature pour le solutionner.

Le Chapitre 3 est consacr aux mthodes utilises dans ce mmoire pour rsoudre le

RCPSP, en l'occurrence les algorithmes gntiques et l'optimisation par essaims

particulaires. La structure et les diffrents oprateurs qui composent ces deux mthodes

sont dcrits. Diverses mthodes de slection, de croisement et de mutation sont prsentes

pour les algorithmes gntiques.

Dans le Chapitre 4, un algorithme d'optimisation par essaims particulaires est

propos. Cet algorithme se base sur des concepts emprunts un autre algorithme

d'optimisation par essaims particulaires conu pour le problme de minimisation du retard

total pondr sur une machine unique. La gestion des contraintes de prsance a t

intgre l'algorithme et certains paramtres ont t modifis. Une reproduction d'un

algorithme gntique de la littrature est aussi effectue dans ce chapitre.

Dans le Chapitre 5, les algorithmes gntiques sont hybrides avec la mthode

d'optimisation par essaims particulaires. Une forme particulire d'hybridation est utilise.

Dans un premier temps, le concept de l'optimisation par essaims particulaires sert la

conception d'une mthode de croisement pour l'algorithme gntique. Ensuite, cette

mthode de croisement est utilise en association avec une autre mthode de croisement au

sein de l'algorithme afin d'amliorer les rsultats obtenus.

Ce travail de recherch permet de mettre en vidence l'intrt que pourrait

constituer la mthode mergente que constitue l'optimisation par essaims particulaires,

initialement conue pour l'optimisation continue, pour les problmes variables discrtes

et plus particulirement pour e RCPSP. Dans la conclusion de ce mmoire, le bilan du

travail accompli est effectu et de futures avenues de recherche sont aussi identifies.

CHAPITRE 2

LE PROBLEME D'ORDONNANCEMENT DE PROJET SOUSCONTRAINTES DE RESSOURCES DANS LA

LITTRATURE

11

2.1 Introduction

Le RCPSP classique, encore appel SMRCPSP (Single-mode RCPSP), consiste en

l'ordonnancement d'un ensemble donn d'activits, sur une ou plusieurs ressources

renouvelables ou non, en quantit limite, dans le but d'optimiser un objectif donn. Les

objectifs les plus souvent rencontrs sont la minimisation de la dure du projet ou de sa

date de fin (makespari), la minimisation du cot total du projet et la maximisation de la

NPV (Net Present Value).

Les activits d'un projet sont non-interruptibles, i.e. qu'une activit commence ne

doit pas tre interrompue tant qu'on ne l'a pas termine. Chaque activit ncessite une

quantit donne de chacune des ressources tout au long de son excution. Les activits sont

lies entre elles par deux sortes de contraintes : les contraintes de prsance et les

contraintes de ressources. Au niveau des contraintes de prsance, une activit j ne peut pas

commencer tant que l'activit i n'est pas finie; on dit que l'activit i prcde l'activit j .

Quant aux contraintes de ressources, tout instant et pour chacune des ressources, la

somme des besoins des activits en cours ne doit pas dpasser la capacit de la ressource.

Les ressources d'un projet sont dites cumulatives, c'est--dire qu'il est possible d'excuter

plusieurs activits de faon simultane. De mme, il est possible d'utiliser plusieurs

ressources simultanment pour l'excution d'une activit. Les ressources peuvent tre

soumises d'autres contraintes telles que la disponibilit des ressources non stockabies

seulement sur une priode bien dtermine (heures de travail du personnel ou

d'quipement); ces ressources seront perdues si elles ne sont pas utilises au cours de la

priode concerne. Il existe aussi des contraintes de localisation temporelle qui peuvent

12

indiquer qu'une activit ne peut dbuter avant une date prcise, en raison d'une

indisponibilit de la ressource correspondante.

2.2 La reprsentation du RCPSP dans la littrature

Plusieurs notations sont utilises dans le RCPSP. Celles que nous utilisons dans ce

document ne proviennent pas d'un auteur en particulier, mais constituent une synthse des

notations que nous avons rencontres.

Soient / le nombre de activits, K le nombre de ressources, dt la dure de l'activit i.

ri,k la quantit de la ressource k ncessaire l'excution de l'activit i, Rk la quantit de la

ressource k disponible et H l'horizon de planification, i.e. la dure maximale de

l'ordonnancement. On ajoute au projet deux activits fictives 0 et I+l, 0 tant la premire

activit et 1+1 la dernire activit du projet. Ces deux activits sont de dures nulles. Soit V

la relation d'ordre partiel sur l'ensemble des activits, i.e. l'ensemble des couples (i, j) tels

que l'activit i prcde l'activit j . En dsignant par S, la date de dbut de l'excution de

l'activit i, le problme d'ordonnancement de projet sous contraintes de ressources consiste

dterminer un ordonnancement de dure minimale, soit le vecteur S = (So, S/,.... Si+j) tel

que Sr+i soit minimise et que les contraintes de prsance et de ressources soient

respectes. Xiit est une variable binaire qui sert dterminer la date de fin ordonnance t de

la activit i.

Ces notations sont dfinies dans le Tableau 2.1 o l'on retrouve dans la premire

colonne les variables utilises et, dans la seconde, leur description.

13

Tableau 2.1 : Dfinition des variables utilises dans le RCPSP

Variables

/

K

dt

ri.k

Rk

V

H

t

Xu

Si

Description

Nombre d'activits au sein du projet.

Nombre de ressources, k = 1,... K.

Dure de l'activit i.

Quantit de la ressource k ncessaire l'excution de l'activit i.

Quantit de la ressource k disponible pour le projet.

Ensemble des couples (i, j), tels que l'activit i prcde l'activit j .

Dure maximale de l'ordonnancement.

Instant de dcision t= 1,... H.

Variable binaire : gale 1 si l'activit i se termine la date t et 0 dans le cascontraire.

Date de dbut de l'excution de l'activit i.

L'objectif principal du RCPSP est de minimiser la dure totale du projet

{makespari). La modlisation mathmatique du RCPSP est donne ci-dessous. L'quation

2.1 reprsente la fonction 'objectif qui minimise la date de fin de la dernire activit du

projet. Les quations 2.2 2.5 traduisent les contraintes sur les activits et les ressources.

L'quation 2.2 traduit le fait qu'il existe une date de fin unique par activit au sein du

projet. L'quation 2.3 reprsente la contrainte selon laquelle la date de fin de toute activit

est infrieure l'horizon. L'quation 2.4 montre la relation de prsance entre deux

activits i et j . Enfin, l'quation 2.5 traduit le respect des limites de ressources par les

activits s'excutant de faon simultane.

/ = Min (?=o t * X!+lit) o /est la fonction 'objectif (quation 2.1)

(quation 2.2)

14

Ef=o t * Xlit

15

Plusieurs mthodes ont t utilises dans la littrature pour rsoudre le RCPSP. Sans

prtendre que la liste des travaux prsents la prochaine section soit exhaustive, nous

avons dvelopp les principales approches de rsolution pour le RCPSP.

23 Les mthodes de rsolution du RCPSP

De nombreux auteurs ([Herroelen et al. 1998; 2001], [Hartmann et Kolisch 2000;

2006], [Demeulemeester et Herroelen 2002], [Artigues et al. 2008]) ont publi des tudes

dtailles sur les diverses mthodes employes pour rsoudre le RCPSP. Ces mthodes se

subdivisent en deux groupes : les mthodes exactes et les mthodes approches. Nous

parlons ici des mthodes les plus usuelles.

2.3.1 Les mthodes exactes

Les mthodes exactes comprennent la programmation par contraintes [Baptiste et al.

2001], ies mthodes par sparation et valuation [Damay et Sanlaville 2006], les schmas

de branchement [Demeulemeester et Herroelen 2002], les bornes infrieures [Carlier et

Latapie 1991] et la programmation linaire [Mingozzi et al. 1998; Pritsker et al. 1969].

Les techniques de programmation par contraintes se basent, d'une part, sur une

relaxation successive du problme de RCPSP chacune de ses ressources et, d'autre part,

sur la relaxation des contraintes de prsance des fentres temporelles afin d'tablir des

conditions ncessaires d'existence d'une solution de dure infrieure H. Ces techniques

ont t prsentes dans la littrature par Bracker et al. [1998] pour Y edge-finding disjonctif,

par Dorndorf et al. [2000] pour Y edge-finding disjonctif et le raisonnement nergtique,

16

Baptiste et Le Pape [1996] pour Y edge-finding cumulatif. Baptiste et al. [2001] ont mis

jour des dominances entre diffrentes rgles d'ajustement applicables au RCPSP. Ils

proposent aussi une tude exprimentale des rgles plus complexes de Yedge-finding

cumulatif et du raisonnement nergtique. La mthode de programmation par contraintes

est prsente de faon dtaille par Baptiste et al. [2005]. Les auteurs prsentent les

modles, les mthodes de rsolution et les applications industrielles des divers problmes

de planification et d'ordonnancement.

La programmation linaire et les autres mthodes exactes sont utilises le plus

souvent, conjointement avec les techniques de programmation par contraintes dans le but

d'amliorer l'efficacit de ces algorithmes. Ces mthodes regroupent diverses notions telles

que les bornes infrieures, la relaxation lagrangienne, les ressources redondantes, la

gnration des coupes, qui sont prsentes par divers auteurs. Carlier et Nron [2003; 2007]

ont largement parl des bornes infrieures et des fonctions redondantes travers leurs

diverses publications. Dans sa thse de doctorat, Demassey [2003] prsente une revue de la

littrature sur les mthodes hybrides de la programmation par contraintes et de la

programmation linaire pour la rsolution exacte de problmes combinatoires. L'auteure

prsente aussi deux nouvelles mthodes d'valuation par dfaut pour le RCPSP bases sur

l'hybridation de la programmation par contraintes et de la programmation linaire. La

premire est base sur l'utilisation conjointe de techniques de propagation de contraintes et

d'une relaxation lagrangienne originale du problme. La seconde repose sur la linarisation

des rgles ou bien des inferences de la programmation par contraintes pour la gnration de

coupes ajoutes des relaxations continues du RCPSP. Une mthode de rsolution

17

optimale du RCPSP appele resolution search a aussi t dveloppe dans ce

document.

2.3.2 Les mthodes approches ou heuristiques

Les heuristiques sont des algorithmes de rsolution d'un problme mathmatique

bien dfini, par une approche intuitive qui se base sur l'interprtation et l'exploitation de la

structure du problme afin d'en dterminer une solution raisonnable [Silver et al. 1980].

Elles comprennent, par exemple, les mthodes de construction progressive et les

mtaheuristiques.

Les mthodes de construction progressive d'une squence d'activits en RCPSP

sont constitues des algorithmes srie et parallle et des rgles de priorit. Ces mthodes

suivent le mme principe et comprennent / tapes au cours desquelles une activit est

ordonnance chaque tape. L'ordre de slection des activits est dtermin par une rgle

de priorit. Les algorithmes srie et parallle prennent en entre une squence d'activits

classes dans un ordre compatible avec les contraintes de prsance et leur assignent une

date de dbut ou de fin. La diffrence fondamentale entre l'algorithme srie et l'algorithme

parallle est que l'algorithme srie slectionne les activits dans l'ordre de la squence et

ordonnance l'activit le plus tt possible en tenant compte des contraintes de prsance, de

ressources, et des activits ordonnances aux tapes prcdentes. Quant l'algorithme

parallle, il ordonnance les activits en incrmentant un instant de dcision t initialise 0;

chaque tape, l'algorithme parcourt la squence des activits non encore ordonnances et

place successivement au temps t les activits possibles sans violer les contraintes de

18

prsance ou de ressources. Les deux algorithmes gnrent des ordonnancements actifs, i.e.

qu'on ne pourrait programmer aucune des activits plus tt sans dplacer les autres

activits. De plus, l'algorithme parallle gnre des ordonnancements sans dlai, ce qui

veut dire qu' aucun moment une ressource n'est laisse inactive alors qu'elle pourrait

dmarrer l'excution d'une activit. D existe obligatoirement un ordonnancement actif

optimal, et l'algorithme srie est capable de le trouver si la "bonne" rgle de priorit est

utilise pour tablir la squence en entre. Par contre, rien n'indique qu'il peut exister un

ordonnancement sans dlai optimal; l'algorithme parallle peut donc ne jamais trouver la

meilleure solution quelque soit la squence d'activits fournie en entre [Hartmann et

Kolisch 2000], L'illustration de la Figure 2.2 montre le rsultat obtenu par chacun des deux

algorithmes pour l'exemple prsent la Figure 2.1 avec la squence d'activits (1, 2, 3,4,

5, 6, 7).

L'algorithme srie ordonnance les activits dans l'ordre de la squence. Ainsi, aprs

l'activit 3, l'activit 4 est ordonnance la date 6, le plus tt possible sans violer les

contraintes de prsance et de ressources et l'activit 5 suit la date 7. Quant l'algorithme

parallle, il ordonnance chaque instant t, dans l'ordre de la squence, toutes les activits

possibles sans violer les contraintes de prsance et de ressources. la fin de l'activit 3,

l'activit 4 ne peut tre ordonnance car l'activit 2, qui la prcde, est encore en cours.

Toutefois, les contraintes de prsance de l'activit 5 sont respectes et les ressources

ncessaires pour son excution sont disponibles. L'activit 5 est donc ordonnance la

date 4 et l'activit 4 la date 7.

19

Ressource kj, Rl-3 Ressource fc/?Rl=3

tmi avec l'algeriSsase srie

S=(,2,2,6,7J,1C)

parallle

Figure 2.2 : Exemple d'ordonnancement avec l'algorithme srie et l'algorithme parallle

Concernant les heuristiques bases sur les rgles de priorit, il existe des

heuristiques simples, dites passe unique, et des heuristiques passes multiples. Une

heuristique simple permet de dterminer l'ordre de slection des activits par une rgle de

priorit unique. Par exemple, l'ordre croissant de la marge totale (dlai entre le dbut au

plus tt et le dbut au plus tard de l'activit) permet d'ordonnancer les activits les plus

urgentes d'abord. Les heuristiques passes multiples consistent lancer successivement

l'algorithme srie ou parallle avec diffrentes squences d'activits, en conservant tout

moment la meilleure solution obtenue. Diffrentes rgles de priorit peuvent, par exemple,

tres utilises pour construire les squences. Il est aussi possible de modifier alatoirement

la squence d'activits obtenue par une rgle de priorit donne. Avec cette dernire

mthode, Kolisch et Hartmann [2000] montrent, par exprimentation sur des ensembles

d'instances de test classiques du RCPSP, que les meilleurs rsultats sont obtenus par la

rgle LFT (plus petite date de fin au plus tard) avec l'algorithme srie pour les instances de

20

petite taille (30 activits), et les rgles LFT et WCS (plus petite marge restante si l'activit

n'est pas slectionne) avec l'algorithme parallle pour les plus grandes instances (60 et 120

activits). Une autre mthode passes multiples appele ordonnancement avant/arrire

(forward-backward improvement), consiste excuter alternativement l'algorithme srie ou

l'algorithme parallle dans l'ordre normal puis, l'envers en inversant la liste des activits

et les arcs du graphe de prsance, et en ordonnanant les activits partir de ia fin du

projet.

Une mtaheuristique est un processus de gnration itrative qui permet de guider

une heuristique subordonne par la combinaison de divers concepts tels que l'exploitation

et l'exploration de l'espace de recherche, ainsi que des stratgies d'apprentissage qui sont

utilises pour structurer efficacement l'information afin de dterminer des solutions

d'excellente qualit [Osman et Laporte 1996]. Les mtaheuristiques sont en gnrai non-

dterministes et ne donnent aucune garantie d'optimalit mais ils peuvent faire usage de

l'exprience accumule durant la recherche de l'optimum, pour mieux guider Sa suite de la

procdure de recherche. On distingue les mtaheuristiques solution unique parmi

lesquelles on retrouve de nombreux algorithmes de recherche locale, et les mtaheuristiques

base de population.

Les techniques de recherche locale associent itrativement un voisinage chaque

solution si de l'ensemble des solutions du problme d'ordonnancement, ia premire

solution tant gnralement gnre par un algorithme constructif simple. Divers critres

d'arrt peuvent tre considrs, tel qu'un temps limite impos ou un cart acceptable par

21

rapport une borne infrieure. La mthode de recherche locale la plus simple est la

mthode de descente qui gnre, chaque itration, la solution voisine si+i qui minimise la

fonction 'objectif dans le voisinage de la solution s,-. L'algorithme s'arrte ds qu'il n'y a

pas d'amlioration de la fonction 'objectif entre deux itrations successives. Le principal

dfaut de la mthode de descente est son arrt au premier minimum local rencontr. Divers

algorithmes ont t proposs pour remdier cette situation.

La technique du recuit simul (Simulated Annealing) [Kirkpatrick et al. 1983], par

exemple, choisit au hasard la solution Sj+i dans le voisinage de s,. Cette solution voisine Si+i

est automatiquement accepte comme nouvelle solution courante si elle est meilleure que s,.

Dans le cas contraire, si+j n'est accepte comme nouvelle solution courante qu'avec une

certaine probabilit. Si sl+/ est refuse, une nouvelle solution est choisie au hasard dans le

voisinage de s,, et ainsi de suite. La procdure peut s'arrter, par exemple, lorsque la

solution Si n'a plus t modifie depuis un certain temps. Jeffcoat et Bulfin [1993] utilisent

cette mthode pour rsoudre le RCPSP. Bouleimen et Lecocq [2003] utilisent la mme

mthode pour rsoudre le RCPSP multi-mode. Vails et al. [2005] utilisent la mthode

d'ordonnancement avant/arrire pour amliorer l'efficacit du recuit simul et prouvent que

cette technique permet d'obtenir de meilleurs rsultats.

La recherche avec tabous (Tabu Search) [Glover 1986] est similaire la mthode de

descente, en ce sens que la solution SM choisie dans le voisinage de s,- est la meilleure

possible. Cependant, l'algorithme ne s'arrte pas lorsque le premier minimum local est

atteint, le principe sous-jacent tant qu'il se peut que l'on doive dtriorer la solution

22

courante pour pouvoir atteindre un optimum global. B n'est pas impossible que Si aussi soit

la meilleure solution dans le voisinage de Si+j, et l'algorithme pourrait alors boucler autour

des solutions Si et Si+i. Pour contourner cette difficult, la recherche avec tabous considre

une liste de critres dits tabous, i.e. qu'il est interdit de choisir une solution rpondant aux

critres de cette liste pendant un certain nombre d'itrations. De ce fait, lorsque la

recherche avec tabous se dplace d'une solution Si vers une solution voisine $,+/, le critre

introduisant la diffrence entre $i et $,+; est plac dans la liste taboue, empchant ainsi la

boucle de se former. Ceci ne bloque pas seulement la solution s, mais toutes les solutions

prsentant ce critre, ce qui constitue un lger handicap pour la recherche avec tabous.

Cependant, une condition prioritaire appele condition d'aspiration oblige l'algorithme

slectionner une solution si elle est meilleure que toutes les solutions parcourues jusque-l,

mme si cette solution prsente des critres de la liste taboue. Plusieurs auteurs ont utilis

la recherche avec tabous pour rsoudre le RCPSP [Baar et al. 1998; Nonobe et Ibaraki

2OO23. Thomas et Salhi [1998] introduisent une mthode o ils oprent directement sur les

ordonnancements au lieu de manipuler des listes d'activits. Klein [2000] dveloppe une

mthode ractive de recherche avec tabous pour le RCPSP avec des contraintes de

ressources variables dans le temps. Gagnon [2002] propose une nouvelle rgle de priorit

ainsi qu'une adaptation de la recherche avec tabous pour rsoudre le RCPSP sous

contraintes de disponibilits variables de ressources. L'auteur propose galement

diffrentes stratgies de recherche avec tabous pour rsoudre la variante multi-mode du

RCPSP [Gagnon et al 2005]. Pan et al. [2008] combinent d'autres mthodes d'intelligence

23

artificielle avec la recherche avec tabous et trouvent que cette technique donnent de

meilleurs rsultats que la mthode traditionnelle.

Contrairement la recherche locale qui tente d'amliorer itrativement une solution

courante, les mthodes base de population, quant elles, travaillent sur une population de

solutions en appliquant un processus cyclique compos d'une phase de coopration et

d'une phase d'adaptation individuelle qui se succdent tour de rle. Dans la phase de

coopration, les solutions de la population courante sont compares entre elles, puis

combines, dans le but de produire de nouvelles solutions qui hritent des bons aspects de

chaque membre de la population. Dans la phase d'adaptation individuelle, chaque solution

dans la population peut voluer de manire indpendante. On peut utiliser les mmes types

de critre d'arrt que dans la recherche locale, ou alors on peut dcider d'arrter une

mtaheuristique base de population ds que les solutions dans la population sont juges

trop similaires [Baptiste et al. 2005].

L'algorithme de colonies de fourmis {Ant Colony Optimization) a t propos par

Dorigo [1992] dans sa thse de doctorat pour la recherche de chemins dans le problme du

voyageur de commerce. L'auteur s'inspire de l'observation de l'exploitation des ressources

alimentaires chez les fourmis. Une fourmi (l'claireuse) parcourt au hasard

T environnement autour de la colonie. Si celle-ci dcouvre une source de nourriture, elle

rentre directement au nid, en laissant sur son chemin une piste de phromones. Ces

phromones sont attractives et les fourmis passant proximit ont tendance suivre cette

piste de faon systmatique. En revenant au nid, ces mmes fourmis vont renforcer la

24

piste en y dposant d'autres phromones. Si deux pistes sont possibles pour atteindre la

mme source de nourriture, celle tant la plus courte sera parcourue par plus de fourmis que

la longue piste. La piste courte est donc de plus en plus renforce, et donc de plus en plus

attractive. Les phromones tant volatiles, la piste la plus longue finit par disparatre. Cette

mthode a t utilise dans la littrature pour la recherche de l'ordonnancement de moindre

dure pour le problme du RCPSP [Merkle et al. 2002] ainsi que pour le GRCPSP

[Shipeng et al. 2003]. Les auteurs concluent que l'algorithme de colonies de fourmis est

parmi ceux qui performent le mieux pour la rsolution des problmes d'optimisation.

L'algorithme gntique (Genetic Algorithm) [Holland 1975], dnomm AG dans la

suite de ce document, est un exemple particulier de mthode volutive pour lequel

l'adaptation individuelle est ralise l'aide d'un oprateur dit de mutation, alors que

S'change d'information est gouvern par un oprateur de reproduction et un oprateur de

combinaison (crossover). Les AG ont attir beaucoup de chercheurs du monde du RCPSP.

Hartmann [1998] dveloppe un AG qui utilise l'algorithme srie avec la rgle de priorit

LFT pour l'ordonnancement des activits. L'auteur amliore ses rsultats en ralisant un

algorithme qui adapte l'algorithme srie ou parallle selon le problme trait [Hartmann

2002]. Alcaraz et Maroto [2001] combinent l'ordonnancement avant-arrire l'algorithme

srie et obtiennent de meilleurs rsultats avec les AG. Les auteurs associent plus tard

l'algorithme parallle et obtiennent de bien meilleurs rsultats qu'ils amliorent un peu plus

avec la recherche locale [Alcaraz et Maroto 2006]. Valls et al. [2008] combinent aussi la

recherche locale aux AG pour en amliorer l'efficacit. Les travaux dans le domaine

25

continuent, les auteurs ne tarissent pas d'ides nouvelles sur le sujet [Chen et Weng 2009;

Lova et al. 2009; Mendes et al. 2009].

L'optimisation par essaims particulaires {Particle Swann Optimization) [Kennedy et

Eberhart 1995], dsign par OEP dans la suite de ce document, s'inspire des

comportements collectifs de dplacement chez certains groupes d'animaux tels que les

oiseaux et les poissons. Que ce soit la recherche de nourriture ou pour viter leurs

prdateurs, ces animaux se dplacent de faon relativement complexe mais cohrente alors

que chaque individu n'a accs qu' des informations limites telles que la position et la

vitesse de ses plus proches voisins [Dro et al. 2003]. Chaque individu utilise donc

l'information dont il dispose par rapport sa propre histoire et celle de ses plus proches

voisins, afin de dterminer la direction qu'il doit prendre ainsi que sa vitesse de

dplacement. L'OEP est similaire aux mtaheuristiques prcdentes dans le sens o elle

part d'une population d'individus appels particules, qu'elle essaie d'amliorer chaque

itration. La particule fait donc le choix chacune des itrations de demeurer sa position

actuelle, d'aller vers sa meilleure position jamais connue ou vers celle de ses voisines

appeles informatrices. L'OEP a t conue initialement pour les problmes d'optimisation

continue. Cependant, plusieurs auteurs l'ont rcemment adapt pour rsoudre des

problmes discrets comme le RCPSP [Zhang et al. 2005]. Shan et al [2007] hybrident cette

mthode avec la technique d'optimisation par colonie de fourmis pour rsoudre la version

multi-mode du RCPSP. Les auteurs concluent, en gnral, que cette approche obtient de

bonnes performances et qu'elle semble avoir un bel avenir dans le domaine de

1 ' ordonnancement.

26

2.4 Conclusion

Dans ce chapitre, nous avons dcrit le RCPSP ainsi que les mthodes les plus

utilises dans la littrature pour le rsoudre. Ces mthodes sont nombreuses et comprennent

aussi bien des mthodes exactes, pour la rsolution des problmes de petite taille, que des

mthodes approches. Parmi les mthodes approches, les mtaheuristiques se distinguent

au sein des techniques qui perforaient le mieux pour la rsolution du RCPSP.

Le chapitre qui suit prsente un peu plus en dtails les mtaheuristiques utilises

dans le cadre de ce mmoire, notamment les AG et l'OEP.

CHAPITRE 3

METAHEURISTIQUES : LES ALGORITHMESGNTIQUES ET L'OPTIMISATION PAR ESSAIMS

PARTICULAIRES

28

3.1 Introduction

Les mtaheuristiques ont pour but de dterminer en un temps raisonnable, une

solution approche un problme d'optimisation lorsqu'il n'existe pas de mthode exacte

pour le rsoudre efficacement. Ces mthodes sont des techniques gnrales adaptables

chaque problme particulier et ont dmontr leur efficacit dans plusieurs domaines

[Baptiste et al. 2005]. Elles comprennent deux groupes d'approches qui sont les mthodes

solution unique et les mthodes base de population. Ces dernires se basent sur une

population d'individus qui interagissent entre eux afin de s'amliorer ou de produire de

nouveaux individus plus performants. Il existe plusieurs mtaheuristiques base de

population. Les mtaheuristiques prsentes dans ce chapitre sont celles qui ont fait l'objet

de notre tude : les algorithmes gntiques et l'optimisation par essaims particulaires.

3.2 Les algorithmes gntiques (AG)

Les AG appartiennent la famille des algorithmes volutionnaires. Ces algorithmes

ont la particularit de s'inspirer de l'volution des espces dans leur cadre naturel, d'aprs la

notion de slection naturelle dveloppe par Charles Darwin au XDCe sicle et les mthodes

de combinaison de gnes introduites par Gregor Mende au XXe sicle. Ces mthodes

consistent faire voluer une population dans le but d'en amliorer les individus. chaque

itration, un ensemble d'individus est mis en avant, gnrant ainsi un ensemble de solutions

pour un problme donn.

Les AG sont issus des travaux de John Holland et de ses collgues et tudiants de

l'universit de Michigan qui ont commenc s'y intresser depuis 1960. Ces travaux ont

29

vu leur aboutissement en 1975 avec la publication par John Holland d'un livre intitul

Adaptation in natural and artificial systems [Holland 1975]. Quelque temps aprs,

Goldberg sortait un livre dans lequel il rsumait les divers domaines d'applications des AG

tels que la recherche, l'optimisation et l'apprentissage-machine [Goldberg 1989]. Cette

publication marque le dbut d'un intrt scientifique croissant pour cette nouvelle

technique d'optimisation. Gen et Cheng [1997] dveloppent alors un peu plus l'application

de ces algorithmes aux problmes d'optimisation. Dans la mme priode, une librairie C++

appele GAlib a t labore pour servir de support la programmation base d'AG. Cette

librairie contient une panoplie d'outils conus pour rsoudre des problmes d'optimisation

l'aide des AG.

3.2.1 Analogie avec la gntique

La gntique est une branche de la biologie qui tudie la transmission des caractres

hrditaires chez les tres vivants. Les AG tant inspirs de cette science, il importe de

replacer les divers termes utiliss dans ce document, dans leur contexte originel afin de

mieux en saisir le sens.

Les tres vivants sont constitus de cellules. Chaque cellule contient des

chromosomes. Le nombre de chromosomes contenu dans une cellule est spcifique

chaque espce. l'intrieur de chaque chromosome, se trouve l'information gntique de

chaque tre, conserve sous forme d'une molcule d'acide dsoxyribonuclique

communment appele ADN. L'lment de base de ces chromosomes est un gne, qui est

une squence d'ADN. Sur chaque chromosome, il existe une suite de gnes constituant une

30

chane qui code les diverses caractristiques de l'organisme (par exemple, la couleur des

cheveux, la forme du nez). Chez une espce donne chaque gne possde, sur un

chromosome, un emplacement fixe appele le locus. Les diffrentes formes qui peuvent

tre prises par un mme gne sont appeles des allles. L'ensemble des gnes d'un individu

est son gnotype et son apparence physique constitue son phnotype.

Par analogie la gntique, les AG travaillent sur une population d'individus et non

sur un individu isol. Ici, un individu est une solution potentielle au problme pos. Une

population est donc un ensemble de solutions, plus ou moins performantes, pour ce

problme. Chaque individu est reprsent par un chromosome unique constituant son

gnotype. Une population constitue donc un ensemble de chromosomes. Un chromosome

est compos d'une chane de symboles qui sont les gnes. Le phnotype est la

reprsentation naturelle d'une solution au problme trait, obtenue aprs le dcodage du

gnotype. La population volue durant une succession d'itrations, appeles gnrations,

jusqu' ce qu'un critre d'arrt, spcifi l'avance, soit vrifi.

Selon Darwin [1859], l'volution des tres vivants dans un milieu donn repose sur

la comptition. Les individus les mieux adapts survivent, se reproduisent et transmettent

leurs descendants les caractres qui ont favoris leur survie. Quant aux autres, ils finissent

par disparatre. On finit donc au fil des gnrations par obtenir des individus de plus en plus

forts et mieux adapts. D est rare, mais cependant possible, qu'il y ait au cours de la

reproduction ou par un effet de la nature, une modification de la structure gntique d'un

individu. Ce phnomne appel drive gntique ou mutation, se produit alatoirement au

31

sein d'une population. Les AG traduisent ces trois caractristiques par des oprateurs de

slection, de croisement et de mutation qu'ils utilisent pour gnrer des populations

'enfants' et former de nouvelles gnrations.

3.2.2 Le principe d'un algorithme gntique

Le schma de la Figure 3.1 illustre la structure gnrale d'un AG. L'algorithme

commence par gnrer une population initiale qui se compose d'un nombre dtermin

d'individus. La meilleure solution peut ne pas se trouver dans cette population initiale.

chaque gnration, une succession d'oprations de slection, de croisement, de mutation,

d'valuation et de remplacement est applique aux individus de la population, afin de

produire la gnration suivante. Lorsque le critre d'arrt est atteint, la meilleure solution

trouve est slectionne et 'algorithme s'arrte.

Gnration de

la population

initiale

valuation des

enfants

obtenus

Slection pour

le

remplacement

valuation des

individus

Mutation si

approprie

Remplacement

del

population

Slection pourle croisement

Croisement des

individus

slectionns

Oui

Meilleure

solution

32

Non

Figure 3.1 : Structure gnrale d'un algorithme gntique [Dro et al. 2003]

L'objectif des AG est de faire voluer une population afin de trouver le meilleur

individu. En termes mathmatiques, le but des AG est de dterminer l'extrmum d'une

fonction /d'un espace de recherche E vers l'ensemble des rels :

Chaque lment de E est not xn. Une population P est donc un ensemble de N

individus de l'espace E telle que P~ (xi, x2, .... xn> .... xN). La fonction/appele fonction

d'adaptation, fonction d'valuation ou encore fonction fitness, sert comme son nom

33

l'indique, mesurer l'adaptation des individus ieur environnement. Elle associe donc une

valeur chaque individu de la population, permettant ainsi aux solutions de pouvoir tre

compares entre elles. Dans la suite du document, le terme 'fonction d'adaptation' est

utilis pour dsigner la fonction/.

La fonction d'adaptation est propre chaque type de problme. Elle devrait tenir

compte de la reprsentation choisie et de la nature des oprateurs afin de pouvoir donner

des indications non trompeuses sur la progression vers l'optimum. Cependant, dans le cas

des problmes industriels, l'valuation de la fonction d'adaptation consomme de loin la

plus grande part de la puissance de calcul durant une optimisation volutionnaire [Dro et

al. 2003]. D faudrait donc veiller la simplifier autant que possible afin de rduire la

puissance de calcul ncessaire.

3.2.3 La reprsentation des individus (encodage)

Gnralement, les chromosomes sont reprsents sous forme d'une chane de bits.

Ce type de codage a pour intrt de permettre de crer des oprateurs simples de croisement

et de mutation. Cependant, ce type de codage ne convient pas pour modliser tous les

problmes. C'est le cas, par exemple, du problme du voyageur de commerce (PVC). Ce

problme concerne un commerant qui doit parcourir n villes afin de livrer ses produits.

Son objectif est de trouver l'ordre dans lequel il doit parcourir ces villes et retourner son

point de dpart, afin d'avoir le trajet le plus court possible, sachant qu'il ne peut passer par

une ville qu'une et une seule fois. Gen et Cheng [1997] proposent deux formes de

reprsentation pour ce type de problme : la reprsentation par cls alatoires et la

34

reprsentation par permutation. Ces deux reprsentations sont aussi celles qui sont

retrouves le plus souvent dans la littrature du RCPSP.

La reprsentation par cls alatoires consiste encoder la solution avec des nombres

alatoires gnrs dans l'intervalle [0, 1[. Chaque emplacement reprsente un numro de

ville et les nombres (ou cls) alatoires reprsentent l'ordre de passage des villes. En

ordonnant les cls de faon croissante, on retrouve l'ordre de passage de chaque ville. Pour

un problme cinq villes, on a, par exemple, le chromosome [0,24 0,14 0,78 0,18 0,32] qui

reprsente l'ordre de passage suivant : [2 - 4 - 1 - 5 - 3]. Le voyageur part donc de la ville

2 et se rend la ville 4 suivie respectivement des villes 1, 5 et 3. B retourne ensuite la

ville 2.

La reprsentation par permutation est, selon les auteurs, la reprsentation la plus

naturelle du PVC [Gen et Cheng 1997]. Elle consiste numrer les villes sous forme

d'une liste, dans l'ordre dans lequel elles sont visites. Un chromosome constitue donc une

permutation des N villes parcourues. Dans le cas d'un problme 5 villes, on peut avoir,

par exemple, le chromosome [32514] qui consiste parcourir dans cet ordre, les villes 3,

2, 5,1, 4 et retourner la ville 3.

3.2.4 La gnration de la population initiale

La population initiale est trs importante car elle affecte non seulement la qualit de

la solution, mais galement le nombre de gnrations au bout duquel on obtient de bonnes

solutions [Sait et Youssef 1999]. Le niveau de diversit prsente au sein de la population

35

initiale reprsente galement une caractristique importante de l'algorithme. La gnration

de la population initiale concerne aussi bien la taille de la population que la manire dont

elle est gnre.

Habituellement, la population initiale est gnre de manire alatoire ou l'aide

d'une mthode de construction progressive. Cependant, on peut parfois partir de quelques

solutions trouves l'aide de certaines heuristiques. Cette mthode connue sous le nom de

seeding est, selon Davis [1991], plus efficace.

En ce qui concerne la taille de la population, elle agit non seulement sur le taux de

convergence et la qualit des solutions obtenues, mais aussi sur la performance de

l'algorithme. Une taille trop petite ne permet pas une bonne exploration de l'espace de

recherche et peut conduire une convergence prmature de la population vers un optimum

local. Par ailleurs, une taille trop grande peut abaisser exagrment le taux de convergence

et altrer les performances de l'algorithme. Se basant sur ses propres expriences, Alander

[1992] propose une valeur comprise entre / et 21 (l tant la longueur d'un chromosome)

pour la taille de la population.

3.2.5 La slection

chaque gnration de TAG, deux slections sont effectues : la premire pour la

reproduction, et la seconde pour le remplacement. La slection pour la reproduction

consiste choisir et apparier les individus qui sont ensuite croiss pour donner de

nouvelles solutions; il est possible de slectionner plusieurs fois le mme individu. Quant

36

la slection pour le remplacement, elle consiste choisir les chromosomes qui vont

constituer la gnration suivante; chaque chromosome ne peut tre slectionn qu'au plus

une fois. La capacit d'un chromosome tre slectionn dpend la fois de sa

performance pour la fonction d'adaptation et de ia mthode de slection utilise. Les

chromosomes ayant les meilleures valeurs de fonction d'adaptation ont souvent plus de

chance d'tre reproduits que les autres et sont frquemment choisis pour remplacer les

moins bons. Il se pose cependant un problme lors de la slection : le dilemme 'exploration

vs exploitation'. 1 s'agit alors de choisir entre utiliser les mthodes stochastiques afin de

favoriser une diversification des solutions dans le systme (exploration), versus effectuer

une slection davantage litiste afin d'obtenir les meilleurs individus et amliorer la

population (exploitation).

3.2.S. la slection pour la reproduction

La slection pour la reproduction peut s'effectuer de diffrentes faons. On

distingue, par exemple, ia slection dterministe, la slection proportionnelle et la slection

par tournoi [Dro et al. 2003].

3.2.5.1.1 La slection dterministe

La slection dterministe consiste ranger les individus dans l'ordre croissant

(dcroissant pour un problme de maximisation) de leur fonction d'adaptation et

slectionner les meilleurs. Cette mthode est aussi appele mthode d'litisme car elle

favorise les meilleurs individus. La slection dterministe a une variance trs faible et se

base uniquement sur la valeur retourne par la fonction d'adaptation. Le fait de slectionner

37

uniquement les meilleurs individus favorise une convergence prmature de la population,

ce qui est viter car l'algorithme est susceptible de s'arrter sur un optimum local [Dro et

al. 2003].

3.2.5.1.2 La slection proportionnelle

Deux techniques principales se sont imposes pour ce type de slection : le tirage

roulette (Roulette Wheel Selection) introduite par Holland [1975] et la slection universelle

stochastique (Stochastic Universal Sampling) propose par Baker [1985].

Le tirage roulette

Le tirage roulette est une mthode stochastique qui exploite la mtaphore d'une

roulette de casino. Elle consiste associer chaque individu un segment (ou case de la

roue) dont la longueur est proportionnelle sa performance. La roue tant lance, l'individu

slectionn est celui sur lequel la roue s'est arrte. Cette mthode favorise les meilleurs

individus, mais tous les individus conservent nanmoins des chances d'tre slectionns.

Soit F la somme totale des fonctions d'adaptation des individus de la population. Le

tirage roulette consiste slectionner alatoirement un nombre entre 0 et F. Pour chaque

individu de la population, on fait la somme cumule de sa fonction d'adaptation avec ceux

des individus qui le prcdent. L'individu choisi est le premier pour lequel cette somme

cumule est suprieure ou gale au nombre alatoire gnr. La Figure 3.2 illustre un

exemple de slection par la mthode de la roulette tir du livre de Davis [1991]. Cette

figure est constitue en trois parties. La premire partie est un tableau de trois lignes : dans

la premire se trouvent dix numros de chromosomes; la deuxime contient leur fonction

38

d'adaptation individuelle et la troisime, les fonctions d'adaptation cumules. La deuxime

partie montre une roue divise en dix tranches proportionnelles la fonction d'adaptation

de chaque individu : c'est la roue de la slection. Dans la troisime partie se trouve un

tableau constitu de deux lignes : la premire contient des nombres gnrs alatoirement et

la seconde, le numro des chromosomes correspondants. Le problme ci-dessous est un

problme de maximisation. Plus la fonction d'adaptation d'un chromosome est grande, plus

ce chromosome a donc de chance d'tre slectionn. On remarque que le meilleur individu

(numro 3) a t slectionn trois reprises dans ce cas prcis.

La mthode du tirage roulette a une forte variance. Toutefois, il peut arriver que

sur n slections successives destines dsigner les parents de la gnration suivante, la

majorit des chromosomes slectionns soient de mauvaise qualit selon leurs valeurs de la

fonction d'adaptation. Cette occurrence peut rduire la performance de l'algorithme

gntique, mais la probabilit que cela advienne reste trs faible [Davis 1991].

Rciproquement, on peut aussi se retrouver face une domination crasante par un

chromosome localement suprieur. Ceci entraine une perte importante de la diversit de

la population conduisant parfois une convergence prmature vers cet optimum local.

ChromosomeFonction d'adaptationFonction d'adaptationcumule

Nombre alatoireChromosomeslectionn

18

8

22

10

317

27

47

34

52

36

612

48

Fonction d'adaptation

m

1

mm

PwSlection des chromosomes

23

3

49

7

76

10

13

3

1

1

i

{11ff

27

3

711

59

57

7

87

66

48

6

93

69

107

76

i

2

3

4

5

6

7

S

9

29

4

1Q

6

1

Figure 3.2 : Exemple de slection par la mthode du tirage roulette [Davis 1991]

La slection universelle stochastique

La slection universelle stochastique consiste choisir les individus qui participent

au croisement en se basant sur la valeur attendue en d'un individu xn. Cette valeur est

calcule comme indiqu par l'quation 3.1, o N est le nombre d'individus au sein de la

population e t^ est la fonction d'adaptation de l'individu xn.

/n *N (quation 3.1)

40

Cette mthode consiste faire la slection de faon proportionnelle la fonction

d'adaptation, mais avec une petite portion de gnration alatoire qui permet chaque

individu d'avoir une chance d'tre slectionn. Le principe est simple et est illustr par

l'algorithme de la Figure 3.3. Au dpart, un nombre est gnr alatoirement dans

l'intervalle [0, 1[ et conserv dans Variable. Pour chaque individu xn de la population,

Cumul est calcul en faisant la somme des valeurs attendues en des individus qui le

prcdent et de la sienne. Tant que Cumul est suprieur la valeur contenue dans Variable,

l'individu courant xn est slectionn et Variable est incrment de 1.

DbutInitialiser Cumul 0

Pour allant de l W Faire | N tant la taille de la population

Cumul = Cumul + esTant que Cumul > Variable,Faire

Slectionner le chromosome xxVariable * Variable+1

Fin Tant que

Fin Pour

Fin

Figure 3.3 : Algorithme de la slection universelle stochastique [Gen et Cheng 1997]

La Figure 3.4 illustre un exemple de slection universelle stochastique, se basant sur

l'exemple de la Figure 3.2. La premire partie de la figure est constitue d'un tableau de

trois lignes contenant les chromosomes, leur fonction d'adaptation et leur valeur attendue

en. La seconde partie est aussi un tableau de trois lignes qui montre le choix des

chromosomes d'aprs le cumul des en et la valeur courante de Variable mentionne plus

41

haut. La valeur alatoire gnre au dpart est 0,5. H faut noter que seules les tapes

auxquelles un chromosome est slectionn sont explicites dans cette figure.

Chromosome xnFonction d'adaptation/Valeur attendue en

18

1,05

22

0,26

317

2,24

47

0,92

52

0,26

612

1,58

711

1,45

87

0,92

93

0,39

107

0,92Slection des individus

Cumul des en (Cumul)VariableChromosome slectionn

1,050,51

3,551,53

3,552,53

3,553,53

4,734,55

6,315,56

7,766,57

7,767,57

8,688,58

9,999,510

Figure 3.4 : Exemple de la slection universelle stochastique

L'exemple prsent montre que plus forte est la fonction d'adaptation d'un

chromosome, plus ce chromosome a de chances d'tre slectionn. Nanmoins, le

chromosome 5 qui a une trs faible fonction d'adaptation, a pu obtenir une chance d'tre

choisi de faire partie des individus croiss pour produire la nouvelle gnration. Cette

mthode, l'instar du tirage roulette, maintient davantage la diversit au sein de la

population.

Deux autres mthodes de slection stochastique bases sur la valeur attendue ont t

prsentes par Sait et Youssef [1999]. Il s'agit des mthodes de slection stochastique avec

et sans remplacement.

La slection stochastique avec remplacement consiste ranger les individus par

ordre dcroissant de leur valeur attendue en. Les meilleurs individus sont ensuite

slectionns et une probabilit de slection leur est attribue en fonction de en. La Figure

3.5 illustre le principe de cette mthode en utilisant trois tableaux. Le premier tableau

contient, dans sa premire ligne les numros des chromosomes, et leur fonction

42

d'adaptation dans la seconde. Dans le deuxime tableau, les chromosomes sont ordonns

suivant l'ordre dcroissant de leur valeur attendue en. Enfin, dans le troisime tableau, les

chromosomes sont slectionns chaque tape et leur probabilit de slection est spcifie.

Ainsi le chromosome 3 ayant une valeur attendue en de 2,24 est slectionn deux fois avec

une probabilit de 7,00 et une troisime fois avec une probabilit de 0,24. Il en est de mme

pour les chromosomes suivants.

Les individus sont donc choisis proportionnellement leur valeur attendue, et par

consquent, leur fonction d'adaptation. Cette mthode est peu utilise du fait de sa faible

variance : seuls les individus ayant les meilleures fonctions d'adaptation ont la chance

d'tre slectionns, ce qui entraine une convergence trs prmature de la population.

ChromosomeFonction d'adaptation

18

22

317

47

52

612

711

87

93

107

RangementValeur attendueOrdre

2,243

1,586

1,457

1,051

0,924

0,928

0,9210

0,399

0,262

0,265

Slection des chromosomesRangChromosome choisiProbabilit

13

1,00

23

1,00

33

0,24

46

1,00

56

0,58

67

1,00

77

0,45

81

1,00

91

0,05

104

0,92

Figure 3.5 : Exemple de slection par la slection stochastique avec remplacement

La slection stochastique sans remplacement part du mme principe. La

diffrence ici est que chaque chromosome peut avoir la chance d'tre slectionn. Certains

chromosomes sont d'abord slectionns par la mthode prcdente en utilisant uniquement

la partie entire de leur valeur attendue. Les chromosomes restants sont ensuite slectionns

par la mthode du tirage roulette dans laquelle'la probabilit de slection de chaque

43

individu est proportionnelle la partie dcimale de sa valeur attendue. Cette mthode est

illustre la Figure 3.6. Cette dernire est constitue de cinq parties. La premire partie

contient les numros des chromosomes et leur fonction d'adaptation. Dans la deuxime

partie, les chromosomes sont ordonns suivant l'ordre dcroissant de leurs valeurs

attendues. Dans la troisime partie, les premiers individus sont slectionns, ceux dont la

valeur attendue est suprieure ou gale 1. La quatrime partie de la figure montre le

cumul des parties dcimales des valeurs attendues de chaque chromosome. Enfin, dans la

dernire partie, les individus restants sont slectionns en utilisant la mthode du tirage

roulette. Ainsi le chromosome 2 qui a une trs faible valeur attendue, a pu tre slectionn

pour aller au croisement.

Cette mthode associe le tirage roulette la slection stochastique, permettant de

ce fait des individus plus faibles d'tres slectionns tout en privilgiant les plus

performants.

3.2.5.1.3 La slection par tournoi

La slection par tournoi [Brindle 1981] a pour principe la comparaison des

individus d'un sous-groupe de q chromosomes (g > 2) de la population. Il s'agit de la

slection q-tournoi. Le chromosome ayant la plus forte valeur de fonction d'adaptation est

slectionn. Le tournoi est refait chaque fois, avec ou sans remise, jusqu' ce que le

nombre d'individus ncessaires pour le croisement soit atteint. Le tournoi peut tre

dterministe ou stochastique. Dans le cas d'un tournoi stochastique, le meilleur individu du

sous-groupe considr est slectionn avec une probabilit comprise entre 0,5 et 1. La

44

variance de cette mthode est forte, mais le choix de la taille q du sous-groupe permet de

faire varier la pression slective, i.e. les chances de slectionner les individus ayant les

meilleures valeurs de la fonction d'adaptation. Plus q est lev, plus forte est la pression

slective et inversement. La mthode de slection par tournoi est trs utilise du fait de sa

simplicit de mise en uvre.

ChromosomesFonction d'adaptation/

18

22

317

47

52

612

711

87

93

107

RangementValeur attendue enOrdre

2,243

1,586

1,457

1,051

0,924

0,928

0,9210

0,399

0,262

0,265

Slection des chromosomesRangChromosomesslectionns

1

3

2

3

3

6

4

7

5

1

6 7 8 9 10

Calcul des cumuls des parties dcimalesChromosomesParties dcimalesValeurs cumules

155

22631

32455

492147

526173

658231

745276

892368

939

407

1092499

Slection des chromosomes restantsRangNombre alatoireChromosomesslectionns

1 2 3 4 5 6305

8

724

2

8240

7

9133

4

1049

3

Figure 3.6 : Exemple de slection par la slection stochastique sans remplacement

3.2.5.2 La slection pour le remplacement

II existe aussi plusieurs mthodes de slection pour le remplacement en vue de

former la gnration suivante. Dro et al. [2003] prsentent quelques-unes de ces mthodes

savoir le remplacement gnrationnel, le remplacement stationnaire, les stratgies

d'volution et la mthode d'litisme.

45

3.2.5.2.1 Le remplacementgnrationnel

Ce type de remplacement est le plus simple. Considrant une population de taille N,

les N enfants gnrs par le croisement et la mutation remplacent purement et simplement

les parents de la gnration courante afin de constituer la prochaine gnration.

3.2.5.2.2 Le remplacement stationnaire (Steady-State)

Dans ce schma, un petit nombre de descendants (un ou deux) sont engendrs

chaque gnration. Ceux-ci sont rinsrs dans la population en remplacement d'un nombre

infrieur ou gal de parents. Ces derniers peuvent tre slectionns par un tournoi invers

(le gagnant tant le moins performant), de manire stochastique (uniforme ou non) ou

dterministe (les parents les moins performants sont remplacs).

3.2.5.2.3 La mthode d'litisme

Cette mthode consiste conserver dans la gnration suivante, au moins le

meilleur individu de la gnration courante. Le mme individu peut donc se retrouver dans

plusieurs gnrations conscutives. Ceci favorise l'exploitation des meilleures solutions au

dtriment de l'exploration de l'espace de recherche. Il pourrait en rsulter une convergence

prmature de l'algorithme vers cette solution.

3.2.5.2.4 Les stratgies d'volution

Deux schmas sont regroups sous ces appellations : les schmas (pi, X)-ES et

(H+X)-ES. partir d'une population de taille ju, X enfants sont gnrs par application des

oprateurs gntiques, X tant suprieur p. L'tape de remplacement est totalement

dterministe. Dans le schma (/i, X)-ES, les // meilleurs enfants deviennent les parents de la

46

gnration suivante. Dans le schma (n + k)-ES, les meilleurs des Qi + X) parents et enfants

deviennent les parents de la gnration suivante. Ce deuxime schma est aussi considr

comme une mthode litiste.

3.2.6 Le croisement

Le croisement permet, par la manipulation de la structure des chromosomes,

l'enrichissement de la population. Il consiste en un change de gnes entre deux ou

plusieurs chromosomes afin d'en former de nouveaux. Classiquement, les croisements

impliquent deux parents qui gnrent un ou deux enfants. Selon Davis [1991], c'est le

croisement (encore appel recombinaison ou crossover) qui fait la force des AG. Il s'agit

de slectionner deux individus parmi les parents potentiels, alatoirement ou l'aide d'une

des mthodes de slection pour la reproduction. Ces derniers sont croiss suivant une

probabilit pcroiS appele probabilit de croisement afin d'obtenir de nouveaux individus

appels 'enfants'. Parfois, les 'bons' gnes d'un parent se substituent aux 'mauvais' gnes

de l'autre pour former un meilleur descendant. La probabilit de croisement est plus ou

moins leve dans les AG. Elle varie souvent entre 0,7 et 1 [Yang 2008].

D existe plusieurs mthodes de croisement en fonction de la mthode de

reprsentation des solutions. Pour la reprsentation par permutation, les mthodes suivantes

peuvent tre cites : le croisement un ou plusieurs points, le croisement partiellement

trac (PMX), le croisement par ordre (OX), le croisement par cycle (CX) et le croisement

par recombinaison d'artes (ERX).

47

Le croisement un point [Holland 1962] consiste choisir alatoirement, sur les

chromosomes parents, un point de croisement partir duquel ceux-ci changent leurs

gnes. Il faut noter que le croisement s'effectue au niveau des gnes, ce qui permet de

couper les chromosomes n'importe quel niveau. Il existe aussi des croisements

multipoints. Le plus courant, le croisement deux points, consiste choisir alatoirement

deux points sur les chromosomes 'Parents' et changer les gnes compris entre ces deux

points. Dans le cas de la reprsentation de solutions par permutation des gnes, ces

mthodes de croisement entranent coup sr la formation de solutions non viables

(rptition de certains gnes et suppression d'autres).

Reeves [1995] dfinit une technique gnrale de croisement ( un ou plusieurs

points) pour la reprsentation des solutions par permutation. La Figure 3.7 prsente un

exemple pour le croisement deux points o les chromosomes sont coups entre le

troisime et le sixime emplacement. Les gnes du premier chromosome sont recopis dans

le chromosome 'enfant' jusqu'au premier point de croisement. Ensuite, les gnes du second

chromosome qui ne font pas encore partie du chromosome 'enfant' sont recopis dans

l'ordre partir du dbut jusqu'au second point de croisement. Les gnes restants sont enfin

recopis dans le chromosome 'enfant' selon leur ordre dans le premier parent. La procdure

est la mme pour les autres types de croisement points bass sur la reprsentation par

permutation. Dans le cas du RCPSP, cette technique conserve aussi les relations de

prsance au sein du chromosome [Hartmann 1998]. Dans l'exemple de la Figure 3.7,

toutes les relations de prsance communes aux deux chromosomes 'parents' sont en effet

maintenues dans les chromosomes 'enfants'.

48

Figure 3.7 : Illustration du croisement deux points

La premire tape du PMX (Partially Mapped Crossover) [Goldberg et Lingle

1985] est la slection de deux points de coupure sur chaque chromosome 'parent'. Les

gnes compris entre ces deux points de coupure sont ensuite changs. Les gnes dupliqus

dans les chromosomes 'enfants' obtenus sont ensuite remplacs par leurs correspondants

qui ont t supprims par le croisement. La Figure 3.8 montre un exemple illustrant le PMX

avec les deux parents prcdents. l'tape 1, les gnes situs entre les points de coupure

sont changs.