Optimisation multi-objectif par colonies de fourmis : cas des problèmes de sac à dos, Multi-objective ant colony optimization : case of knapsack problems

Inès Alaya

Description

Sous la direction de Christine Solnon, Khaled Ghedira
Thèse soutenue le 05 mai 2009: Université de La Manouba, Lyon 1
Dans cette thèse, nous nous intéressons à l'étude des capacités de la méta heuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d’optimisation combinatoire multi-objectif. Dans ce cadre, nous avons proposé une taxonomie des algorithmes ACO proposés dans la littérature pour résoudre des problèmes de ce type. Nous avons mené, par la suite, une étude expérimentale de différentes stratégies phéromonales pour le cas du problème du sac à dos multidimensionnel mono-objectif. Enfin,nous avons proposé un algorithme ACO générique pour résoudre des problèmes d'optimisation multi-objectif. Cet algorithme est paramétré par le nombre de colonies de fourmis et le nombre de structures de phéromone considérées. Il permet de tester et de comparer, dans un même cadre,plusieurs approches. Nous avons proposé six variantes de cet algorithme dont trois présentent de nouvelles approches et trois autres reprennent des approches existantes. Nous avons appliqué et comparé ces variantes au problème du sac à dos multidimensionnel multi-objectif
-Optimisation par colonies de fourmis
-Optimisation combinatoire
-Problèmes multi-objectif
-Stratégies phéromonales
-Problèmes sac à dos
In this thesis, we investigate the capabilities of Ant Colony Optimization (ACO) metaheuristic to solve combinatorial and multi-objective optimization problems. First, we propose a taxonomy of ACO algorithms proposed in the literature to solve multi-objective problems. Then, we studydifferent pheromonal strategies for the case of mono-objective multidimensional knapsackproblem. We propose, finally, a generic ACO algorithm to solve multi-objective problems. Thisalgorithm is parameterised by the number of ant colonies and the number of pheromonestructures. This algorithm allows us to evaluate and compare new and existing approaches in thesame framework. We compare six variants of this generic algorithm on the multi-objectivemultidimensional knapsack problem
-Ant colony optimization
-Combinatorial optimization
-Multi-objective problems
-Pheromone strategies
-Knapsack problems
Source: http://www.theses.fr/2009LYO10060/document

Sujets

• Optimisation combinatoire
• Algorithme de colonies de fourmis

Informations

• Publié par: Thesee
• Nombre de lectures: 123
• Langue: Français

Extrait

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'ordrelal