Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication


THÈSE
en cotutelle entre
UNIVERSITE DE LA MANOUBA
ECOLE NATIONALE DES SCIENCES DE L’INFORMATIQUE

Et

L’UNIVERSITE CLAUDE BERNARD LYON1

Présentée en vue de l’obtention du diplôme de

DOCTEUR EN INFORMATIQUE

par
Inès Alaya


Optimisation multi-objectif par colonies de fourmis
Cas des problèmes de sac à dos


Sous la direction de
Khaled GHEDIRA et Christine SOLNON
Réalisée au sein de
et
Soutenu le : 5 mai 2009

Devant le jury composé de :
Président : Jean-Michel JOLION, Professeur, Université de Lyon
Rapporteur : Yves DEVILLE, Professeur, Université catholique de Louvain
Rapporteur : Béchir AYEB, Professeur, Faculté des sciences de Monastir
Examinateur : Patrick ALBERT, Directeur Scientifique, ILog
Directeurs de thèse : Khaled GHEDIRA, Professeur, Institut Supérieur de Gestion
Christine SOLNON, Maître de Conférences, Université Lyon1
tel-00603780, version 1 - 27 Jun 2011Tabledes.hes.mati?res.Inbtro.duction.g?n?ralec7.I.Optimisation.c.o23m1.5.3binatoire.13d'optimisation1.In.tro.duction.15.1.1heuristiquesIn.troparduction..es...sac.....la.1.7.......1.7.1.......Progra.....Les.......p.......pro.......probl?me.dos..15.1.2.D?nition1.6.p.de.binatoire.appro...............h.............21.dynamique.........22.c.............1.8.115c1.3oisinageComplexit?.th?orique.d'un.probl?me....A.hes...........29.Le.du.?.quadratique..........16.1.420MoApprod?lisationhes.our.r?solution.probl?mes.com.21.Les.c.compl?tes.........................21.Branc.and.ound................18.1.5.Exemples.de.probl?mes1.7.2d'optimisationmmationcom.binatoire..................1.8.appro18hes1.5.1.Le.probl?me.du.v.o.y.ageur.de.commerce......22.A.pro.hes.v............18.1.5.2.Le.probl?me.du.sac1.8.2?pdoscmconstructivultidimensionnel.....................19
tel-00603780, version 1 - 27 Jun 20111.9Conclusion...........Conclusion.......................3.2.3.v.3.2.5.m.la...2.6.......49............30.2.Optimisationtpar.colonies.d.e.fourmis.33.2.12.5Inhetro.duction....l'in.............Optimisation.duction.................orm.......N.......id?al..........33.2.2.Analogiedebiologique....53.de.....CO.c.cale.............tr?le.ersication.......44................34462.3ulti-obOInptim.isation.par.colonie.de.fourmis.et.probl?me.de3.2v.o.y.ageur.de.commerce......3.2.1...............50.de.............oin.P.Nadir.........3.2.4..............36.2.3.1eAerformancen.t.System......Classication.tho.........55.A.et.re.herc.lo.........................44.Con36de2.3.2tensication/divExtensions.de.An.t.System........2.7................................38.2.43Lammjectifs?3.1taheuristiquetrod'optimisation.par.colonie.de.fourmis.............39.2.4.1.Repr?sen.tation.du.probl?me49.D?nitions.................................50.F40ulation2.4.2.Com.p.ortemen.t.des.fourmis................3.2.2.otion.dominance....................40.2.4.350LaPm?taheuristiquetAetCOoin.de...................52.Con.exit?................41.2.4.4.A.p.pl.ications..53.M.sures.p.......................3.3.des.?.des.r?solution................42
tel-00603780, version 1 - 27 Jun 2011−
destransformantA..le.probl?me.m.ulti-ultipleob.jectif.en.unAprobl?me.uni-ob.jectif....t.probl?me.ultiple...w.t...78...................An.ec.............Cro..........57.3.4.169A.gr?.ga.t.iAnon.p.ond?r?eL'.....4.2.3.....4.2.4.....72.System.v.......y.....an.......ulti-Ob..57.3.4.2.Mt?.thoaxonomiede.M?tho..763.4.con.train.te............Algorithmes...............4.2.1.jectiv...........70.BicriterionAn58.3.4.3.M.?.tho.dealgorithmeprogrammation.par.but......areto.y.........M.Colon.our.tourn?es.a.de....58.3.5.Appro4.2.6cthes.non-agr?g?es........4.2.7...............4.2.8.e.A.........75.P.on-based.y...4.3.algorithmes59.3.5.1.L.e.s.algorithmesDiscussiong?n?tiques....................................4.2.MO.CO59.3.5.2.Recuit.sim.ul?..................69.M.Ob.e.t-Q.....................4.2.2.algorithme.t..64.3.5.3.Rec.herc.he.tab.ou....70.L'.BicriterionMC...................71.P.An.Colon.Optimization..............65.3.5.44.2.5Aultipleptproycpheslehdeybridede?hiculessv.fen?tres.temps.................72.M.An.Colon.System..................66733.6COMPETConclusionts...........................74.M.jectiv.Net.ork.CO...................4.2.9.wding.opula.i.An67Colon4OptimisationOptimisation.par.colonies75deTfourmisdespMOourCOla.r?solution.de.pr.o.-.bl?mes.m.ulti-ob.jectifs4.469.4.1.In.tro.duction..........................
tel-00603780, version 1 - 27 Jun 2011α ρ
....Com...CO.110.hm.........tation.d'autres.......6.2.........Ensem.9.Edge-AK...hes.5.6.....robl?mes......78.I.I?Etude.de.st?rimenra.t?gies.ph?romonale.set81.5paraisonStrat?giesertex-AK,ph?romonalesparaisonp.our.leecprobl?me.du.sac.?.dos.m.ult6idi-lamensionnel107mono-ob.jectif.83.5.1.In-Atro.duction..6.2.1.....109...........5.5.et...........95.de.d'exp.....5.5.2.algori.s.ath-AK.5.5.3.v.A.....100.a83appro5.2.Algorithme.A.CO.p.our.le.MKP............algorithme.p.de.ulti-ob.In.................g?n?rique....84.5.2.1.L'.algorithme.Andet-Knapsac.k........M.de...................92.Exp.tations.r?sultats..85.5.2.2.D?finiti.on.des.comp.osan.ts.ph?romonaux....5.5.1.ble.tests.conditions.?rimen.........6.Com87des5.2.3tD?finitieonVduPfacteuretph?romonal96.Com.a.ec.algorithmes.CO...........5.5.4.paraison.v.d'autres.c..88.5.2.4.M.ise.?.jour.de102laConclusionph?romone................................104.Un.A.g?n?rique89our5.3r?solutionInfluencepdesmparam?tresjectifsConclusion6.1ductiontroet.4.5.sur.la.r?solution........................10790L'algorithme5.4mInfluenceCOdes.traces.de.ph?romone.sur.la.similarit?.des.solutions.cal-.cul?es108.Construction.solutions.....................6.2.2.ise.jour.ph?romone.....................
tel-00603780, version 1 - 27 Jun 20111
2
3
4
5
6
6
dem-ACO..la.sures.5.....CO...m.......tation...(1,m).....119....1117.46.3.1.V.arian.te.1122:.m-A.COdestes124(m+1,m)7.5.6...137.......du.ulti-ob.120.......heuristique...........ble111.6.3.2.V.arianite.2123:consid?r?esm-A.CO124arianarian(m+1,m)..de.les.lyse...............141.....Le.?.dimensionnel..113.6.3.3ChoixVph?romonalearian.t.3.:.m-A.COduv.(m,m)........r?sultats...........7.5.1.tests.............Condi.d'exp.param?trage113.6.3.4.VMarianpt.4.:.m-A.COCom6tes(1,1)de.....Com.CO.v.g?n?tiques.n...............Conclusion............114.6.3.5.Vg?n?ralearian.te.5.:.m-A7.2COprobl?medesac(1,m)dos.ulti.m.jectif.......7.3.de.strat?gie.....................120115D?nition6.3.6facteurV.arian.te.6.:.m-A.CO.Description.121.Exp.tations.(1,m)7.5.?rimen.et.......................122.Ensem.de........115.6.4.Conclusion..............7.5.2.t.ons.?rimen.et...........7.5.3.e.de.erformance.................7.5.4.paraison.di?ren.v.tes116m-A7.Application.de.m.-7.5.5AparaisonCOm-A6.3auprobl?meadecualgorithmessac132?Adosamglobaleultidimensionnel.m.ulti-ob.jectif.119.7.1.In.tro.duction..........7.6...................................Conclusion.143.
tel-00603780, version 1 - 27 Jun 20116
tel-00603780, version 1 - 27 Jun 2011Introductiondeenl'optimG?n?raledeLesyprobl?mes?se,d'optimisationMoNP-diciles[Do-ner?alis?.pdeoss?de'optimisationncapacit?st-pas,St?zle,?eceDepuisjour,unaut?uncoma19lgo-?rithmedeg?n?ralfourmis.pt?ressonsermettanristiquettde&lesk,r?soudre?en?t?unotempsetpCOolynomial.deCeleprobl?meappliqu?edeprobl?mel'explosion[Dorigoc[Gamomlesbinatoiredelimiteparl'utilisationetdecoloniem?thocettedesnousexactesl'?tudeplaourparlaisr?solutiony?CO)desCaro,probl?mes&deDorigopLesetitesdetailles.onDanseletcassde1992,probl?mes,deapparition,grandedetl'attenaaille,tiquecommequ'ellecelaaestplusieurssouvcommeenvtdeleGamcasaectationdans7lesneurones,applicationsalgorithmesr?elles,estimationlesdistribution,m?thoisationdesessaimiparticulesnclomparpl?tdees,Dansquithsacriennoustinla?compl?tudedespdeourm?taheu-gad'optimisationgnecolonierfourml'ecacit?,('AndeviennenColontOptimization'uneAalternativ[DorigoeDiin1999,t?res-ysonsanMandericte.1988,Ces&derni?res2004].ann?es,algorithmeslabaseplupartcoloniesdesfourmism?taheuristiquestpr?seninitialt?esmdansnlaproplitt?ra-s?turedansprigo,ourDorigor?soudreal.d1996].essonprobl?mesl'Acomrequiertbinatoiresplussonplusttiond'inspirationlbiologique.commPscienarmivucessucc?sm?taheuristiques,anousEllep?t?ouv?onsprobl?mesciterbinatoiresleslealgorithmesdug?n?tiques,oleageurrecuitcommercesim&ulbardella,?97],,quadratiquelesbardellar?seaux
tel-00603780, version 1 - 27 Jun 2011etal.,1plusieurstlargemen999a],cliqueroutageimpde?livdans?chipuisquecmulesprobl?mes[Bullnheimerpaset?al.exemple,t19t,99],probl?messacts?tdoss?lectionmcetteultidi-hoixmensionneldes[Alacyconictuels.aLaetprobl?mesal.sac,satisfaction2004a]pas,...ph?romonaleNousnenousg?n?ralemensommesheinlt?ress?ts,nousdanspro-cetteunth?se,et?lal'?tudesuitedesjectif,capacit?ests.der?el,cettemenm?taheuristique,d'optimiseretsonnousjeaultan?menvoptimaleonsdisparaittenbt?probl?mesdedos,d?gageroudesconpistesilconcetrnanunetEnlepro-ceuvhoix?tred'une?strat?gierecph?romonale.cCdansettecompstrat?giesolutionsconsisten'est?t.unplusm?canismet?ress?sd'apprendutissagequiuti-classiquelis?sous-ensemparales?tudi?algorithmesNousAparCOcaspmourlepstructureermettreplus?alalacoloniduenedeoptimiserconunvmaisergerultan?menvetersg?n?ralemenlesmsolutionsconsistequiserestplusieursbas?desurnileuni-obd?pour?tmde8traceslesdedeph?romone.?Cesdetracesmaximalesondetdeen-trainsuitees,utilis?esn'estp?videnourdebiaiserhoisirlesstrat?gied?cisionsappropri?e.lorseedeceslabl?mesconstructionpdeensolutions.pasLeramen?s,ct,hoixdesd'unedetellehercstrat?giedeesthemins,?l'ordrelalequefoislesd?tosanermidensonas?lectionn?snpastortanetNousd?sommeslparticuli?remenicatinenaufonctionbl?medessac-?-dosprobl?mes.ultidimensionnelInitialemenestt,probl?meladem?taheuristiquedeAble,COquia?t??t?tindanstrolitt?rature.duite?tendonsp?tudeourlar?soudreauxundesprobl?med'optimisationdeulti-obreco?hercched'unedeph?romonalecencorehemindhamiltoniencdanstunDansgraphe,pluparti.e.probl?mesvmondeoilys'agitageurd'deseule-commerce.tDseulansrit?receplut?tcas,simlatstrat?giecrit?resph?romonalequiconsistet?td?pL'optimisationoserulti-oblactifph?romonedoncsuroptimi-lessimctheminsfonctions.construits.notionPsolutionourulesqueprobl?mesl'optimisationdejectifs?lectionpdelessous-ensemd'optimisationbleulti-ocommejectifpar
tel-00603780, version 1 - 27 Jun 2011auprotdecsolutions.heuristiqueslailnotionm?thod'leensembleen-deauxsolutionsestParhapitreetonousoptimalesles.laL'utilisationjecdeslesm?taheuristiqueseplaourprobl?mesr?soudreindesapproprobl?mesleml'optimisationulti-obulti-objectifsos?esahesfaitulti-obl'obonjetoptimiserd'untintt?r?tnidedeplusth?seente.pluspr?sencroissanbinatoiret.existanAdanspr?sencomt,r?solutiolescasm?taheuristiquesmconstituenplustfourmis.unlesdesnouscheshamNouspsdescriptiondeorer?soudrecosonsherct,heplusieurslessplusultan?menactifsplusdanstl'optimisationph?romonales,massoulti-obobtjectifs.oiterLaconstructionplupartm?moiredesorganis?trasuivvpremi?reaux?existanontsonconcel'?tudernendets.l'optimroisationpremierbi-obprobl?mesjectif.etLehescascompl?tesmourulti-objectif.jectifuxirestecdicilefo?tr?soudre,coloniesnond?nissonsseulemenctd'optimisation?tifcausesendeapprolar?solutioncomplexit?ladeleces?probl?mes,appromaisCOaussies?pcauseprobl?mesduNousnom9bredan?levlorsqu'?adesobsolutionstifP?aretosimoptimalest,?n'estun?videnprobl?mecommend'optimisationd?nirmstructuresulti-obcommenjectif.lesNouscierpropfonctionsosons,jectifs,danscommencettelesth?se,xpld'?tudierlorsleslacapacit?sdedeCeladem?taheuristiqueestAdeCOfa?onpanourLalapartier?solutionconsacr?edeslaprobl?mestatid'optimisationdesmd'optimisatiulti-obcomjectif.etPdesourdescer?solutionfaire,teilNousesttindispduisonsensableledeccleshoisird'optimisationlabinatoirestrat?gielesph?romonalecappropri?e.deDenplus,etppourlecemono-obgenreDansdedeprobl?mes,?leechapitre,hoixnousdescalisonsstructuresparticuli?remenph?romonalessurestparundeautreNouspdansointroisi?methapitrecl?probl?mesdansmljecaetr?solution.pr?Entonseet,principalespcourdelespropprobl?mesdansmono-oblit?rature.jectif,consacronsg?n?ralemenquatri?methapitreunelaseuledesstructurecdeAph?romonepropests?utilis?edanscorresplitt?ratureondanourtdes?ml'uniquejectifs.l'obpropjectif.dansCep
tel-00603780, version 1 - 27 Jun 2011