of 169 /169
UNIVERSITÉ DU QUÉBEC MÉMOIRE PRÉSENTÉ À L'UNIVERSITÉ DU QUÉBEC À CHICOUTIMI COMME EXIGENCE PARTIELLE DE LA MAÎTRISE EN INFORMATIQUE Par Eunice Adjarath LEMAMOU Ordonnancement de projet sous contraintes de ressources à l'aide d'un algorithme génétique à croisement hybride de type OER 27 Août 2009

1 - Constellation - UQAC

Embed Size (px)

Text of 1 - Constellation - UQAC

  • 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.