Perfectionnement d'un algorithme adaptatif d'Optimisation par Essaim Particulaire : application en génie médical et en électronique

Yann Cooren

Description

Sous la direction de Patrick Siarry
Thèse soutenue le 27 novembre 2008: Paris Est
Les métaheuristiques sont une famille d'algorithmes stochastiques destinés à résoudre des problèmes d 'optimisation difficile . Utilisées dans de nombreux domaines, ces méthodes présentent l'avantage d'être généralement efficaces, sans pour autant que l'utilisateur ait à modifier la structure de base de l'algorithme qu'il utilise. Parmi celles-ci, l'Optimisation par Essaim Particulaire (OEP) est une nouvelle classe d'algorithmes proposée pour résoudre les problèmes à variables continues. Les algorithmes d'OEP s'inspirent du comportement social des animaux évoluant en essaim, tels que les oiseaux migrateurs ou les poissons. Les particules d'un même essaim communiquent de manière directe entre elles tout au long de la recherche pour construire une solution au problème posé, en s'appuyant sur leur expérience collective. Reconnues depuis de nombreuses années pour leur efficacité, les métaheuristiques présentent des défauts qui rebutent encore certains utilisateurs. Le réglage des paramètres des algorithmes est un de ceux-ci. Il est important, pour chaque problème posé, de trouver le jeu de paramètres qui conduise à des performances optimales de l'algorithme. Cependant, cette tâche est fastidieuse et coûteuse en temps, surtout pour les utilisateurs novices. Pour s'affranchir de ce type de réglage, des recherches ont été menées pour proposer des algorithmes dits adaptatifs . Avec ces algorithmes, les valeurs des paramètres ne sont plus figées, mais sont modifiées, en fonction des résultats collectés durant le processus de recherche. Dans cette optique-là, Maurice Clerc a proposé TRIBES, qui est un algorithme d'OEP mono-objectif sans aucun paramètre de contrôle. Cet algorithme fonctionne comme une boîte noire , pour laquelle l'utilisateur n'a qu'à définir le problème à traiter et le critère d'arrêt de l'algorithme. Nous proposons dans cette thèse une étude comportementale de TRIBES, qui permet d'en dégager les principales qualités et les principaux défauts. Afin de corriger certains de ces défauts, deux modules ont été ajoutés à TRIBES. Une phase d'initialisation régulière est insérée, afin d'assurer, dès le départ de l'algorithme, une bonne couverture de l'espace de recherche par les particules. Une nouvelle stratégie de déplacement, basée sur une hybridation avec un algorithme à estimation de distribution, est aussi définie, afin de maintenir la diversité au sein de l'essaim, tout au long du traitement. Le besoin croissant de méthodes de résolution de problèmes multiobjectifs a conduit les concepteurs à adapter leurs méthodes pour résoudre ce type de problème. La complexité de cette opération provient du fait que les objectifs à optimiser sont souvent contradictoires. Nous avons élaboré une version multiobjectif de TRIBES, dénommée MO-TRIBES. Nos algorithmes ont été enfin appliqués à la résolution de problèmes de seuillage d'images médicales et au problème de dimensionnement de composants de circuits analogiques
-Optimisation par essaim particulaire
-Algorithme adaptatif
-Algorithme à estimation de distribution
-Segmentation d'image
-Optimisation continue
-Optimisation multiobjectif
-Seuillage
-Métaheuristiques
Metaheuristics are a new family of stochastic algorithms which aim at solving difficult optimization problems. Used to solve various applicative problems, these methods have the advantage to be generally efficient on a large amount of problems. Among the metaheuristics, Particle Swarm Optimization (PSO) is a new class of algorithms proposed to solve continuous optimization problems. PSO algorithms are inspired from the social behavior of animals living in swarm, such as bird flocks or fish schools. The particles of the swarm use a direct way of communication in order to build a solution to the considered problem, based on their collective experience. Known for their e ciency, metaheuristics show the drawback of comprising too many parameters to be tuned. Such a drawback may rebu some users. Indeed, according to the values given to the parameters of the algorithm, its performance uctuates. So, it is important, for each problem, to nd the parameter set which gives the best performance of the algorithm. However, such a problem is complex and time consuming, especially for novice users. To avoid the user to tune the parameters, numerous researches have been done to propose adaptive algorithms. For such algorithms, the values of the parameters are changed according to the results previously found during the optimization process. TRIBES is an adaptive mono-objective parameter-free PSO algorithm, which was proposed by Maurice Clerc. TRIBES acts as a black box , for which the user has only the problem and the stopping criterion to de ne. The rst objective of this PhD is to make a global study of the behavior of TRIBES under several conditions, in order to determine the strengths and drawbacks of this adaptive algorithm. In order to improve TRIBES, two new strategies are added. First, a regular initialization process is defined in order to insure an exploration as wide as possible of the search space, since the beginning of the optimization process. A new strategy of displacement, based on an hybridation with an estimation of distribution algorithm, is also introduced to maintain the diversity in the swarm all along the process. The increasing need for multiobjective methods leads the researchers to adapt their methods to the multiobjective case. The di culty of such an operation is that, in most cases, the objectives are con icting. We designed MO-TRIBES, which is a multiobjective version of TRIBES. Finally, our algorithms are applied to thresholding segmentation of medical images and to the design of electronic components
-Continuous optimization
-Multiobjective optimization
-Metaheuristics
-Particle swarm optimization
-Adaptive algorithm
-Estimation of distribution algorithm
-Image segmentation
-Thresholding
Source: http://www.theses.fr/2008PEST0035/document

Sujets

• Algorithme adaptatif
• Algorithme à estimation de distribution
• Segmentation d'image
• Optimisation multiobjectif
• Seuillage
• Métaheuristique

Informations

• Publié par: Thesee
• Nombre de lectures: 125
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

TH?SEDEDOCTORATYUnivUnivDEd'examenL'UNIVERSIT?hePExaminateurARIS200812GOURVM.ALRappDEIoanMARNEtparPYlaann:COORENUnivpt-FourDirecteurobtenirAmpletgradearbdedeDOCTEURCENPSCIENCESersit?sSpde?cialit?an:misSCIENCESos?eDEMicL'ING?NIEURProfesseurOptioni:deOptimisationRapp?quipterecd'accueilLab:LyLabM.oratoireProfesseurImages,ENIT,SignauxExaminateuretTRELEASyst?mesHDRInMauricetelligenng?nieurtsExaminateur(LiSSi,kE.A.des3956)ersit??cole12Dobrectoraledev:t?colecomDosionctoralecompSciencesdeetM.Ing?nieriehel:GANDMat?riauxdes-ersMot?sd?lisationersit?-ClermonEnerrandvironnemenorteurtLauren(SIMME)KR?HENB?HLSujetdedeherclaCNRSth?se:oratoireP?re,erfectionnemenontorteurdLauren'unGENESTEalgorithmedesadapersit?statifTd'OptimisationesparM.EssaimCristianPMa?trearticulConf?rencesaire.INA-GrignonApplicationsM.enCLERg?nieIm?dicalconsultanetAnnecyenM.?lectroniqueatricsoutenSIARRuProfesseureUnivleUniv27denoarisvDirecteuremth?seR?sum?Lesm?taheuristiqquileurshe.unouvesprobl?messonnoire,t?uneersit?famsouvi,llemono-obd'algorithmesd'arr?tstod?fauts.cunehastiquesundestin?sde?cetter?soudrejectifdescircuitspro-estimationbl?mesos?dCet'optimisationd?nirdicile.th?seUqtilis?esdeuxdansins?r?e,deenomrbreuxidomaines,ducesultiobm?thotdesquepr?senonstenttdel'ainvadancessustageMauriced'?treestg?n?ralemenparam?tretuecaces,l'utilisateursanstraiterppropourortemenautand?-tit?squecertainsl'utilisateurtaitphase?lemoerturedierparlad?placemenstructureybridationdedebasemaindel'essaim,l'algorithmebqu'ilr?solutionutilise.lesPouraprobl?me.rmiviencelles-ci,?l'Optradictoires.timisationvparMO-TRIBES.Ess?am?dicalesicompmOptimisation,Pmarticulairepar(OEP)algorithesttationunerecncetteoau,valgorithmeellesansclassecond'algorithmesfonctionnepropbos?eourpqu'ourprobl?mer?soudrelelesl'algorithme.probl?mesdans??tudevdeariablesermetconlestinaues.lesLesdealgorithmescesd'OEPduless'inspirenatS.dur?guli?recompd'assurer,ortemendetonnesl'espaceoherccialparticules.desstrat?gieanimauxbas?e?veoluva?nesttanenlaessaim,seintelsauquet.lescroissanoiseauxdesmigrateursprobl?mesouales?pdesoissons.dreLeseparticulescomplexit?d'un?rationm?meduessaimobcommsonuniquenttadeor?mani?remdirecteTRIBES,enalgorithmestreennellesr?solutiontoutseuillageauaulongtdetslaMots-clefsrecconhercopthejectpoptourparticulaire,construirepuneesoludistribution,tionseuillage.audeprobl?mehercpDansos?,optique-l?,enClercs'appuypropanTRIBEStquisurunleurd'OEPexpjectif?rienceaucuncollectivdee.tr?le.Reconnalgorithmeuescommedepneuiso?tedepnomlaquellebreusesn'aann?es?pleour?leuretecacit?,crit?relesdem?taheuristiquesNouspr?senosonstencettetunedescompd?fautstalequiTRIBES,rebputend'entgagerencoreprincipalescertainsuutilisateurs.lLeetr?glageprincipauxdesAnparam?trescorrigerdesdealgorithmesd?fauts,estmounonde?t?ceux-ci.jout?sIlTRIBEestUneimpd'initialisationortanestt,anpd?sourd?partcl'algorithme,haquebprobl?mecouvpdeos?,dderectrouvheerlesleUnejeuellededeparam?trest,quisuconduiseun?hdesapecerformancesalgorithmeoptimalesestimationdedistribution,l'algorithme.aussCepd?nie,endandet,tenircettedivt?cauhedeesttoutfastidieuselongettraitemenco?teuseLeenesointemps,tsum?thortoutdepdeourmlesjectifsutilisateursconduitnoconcepteursvices.adapterPm?thoourps'arancr?souhceirypdedeceLatdeypopeprodetr?glage,faitdeslesrecjectifshercoptimiserhestonentcon?t?Nousmen?esvp?labourunepropersionoserultiobdesdealgorithmesd?nomm?editsNosadaptatifs.onA?t?vappliqu?seclacesdealgorithmes,delesd'imagesvetaleursprobl?meddimensionnemenesdeparam?tresosannedesonanalogiques.t:plusoptimisationg?es,tmaisue,sonimisationtultiobmoifdim?taheuristiques,imisation?es,essaimenalgorithmefonctionadestatif,r?sultatsmcollect?s?durandetsegmenled'image,proiiiAbstractMetaheuristicsareaeralresearcalgorithm,newoptimizationfamilysegmenofcriterionstoacersithasticesalgorithmsswwhickhglobalaimalgorithm.atassolvingwithdicults.optimi-dicultzationjectivproblems.:Useding.toysolvusereofvoariousandapplicativteorderprobhlemasin,lthesemmethothdisswhicha,vdesignejectivtheofadvjectivanastageactstoforbproblemerstgenerallytoecienbtunderontoaoflargeimproamounstrategiestcessofeproblems.ossibleAmongbthenewmetaheuristics,onPdistributionarticlemainSwswarmtheOp-stimizationmetho(PSO)theirisjectivahnewcases,classWofmalgorithmsopropappliedosedimagestoonensolvuousenconadaptivtineuouseoptimizationparameter-freeproblems.hPSOosedalgorithmsClerc.areainspiredofromhtheonlysothecialdene.bjectivehaPhDvioreooffvanimalsoflivingeininswthearm,wbacsucadaptivhorderasebirdooadded.cinitializationksdenedorinsureshoscashotheols.sinceTheofparticlescess.ofofthet,swharmestimationuseisaduceddirectthewinaallynofcecommiunicationneedinjectivorderleadstotobuilddsamsolutioncase.tooftheopconsideredinpobroblem,rebaseddesignedonistheirocollectivveTRIBES.expalgorithmserithresholdeofntoce.electronicKnoKeywwnconformtheiroptimizatieciencymetaheuristics,,op-metaalgorithm,halgorithm,euristicstation,shoadaptivwmono-obtheePSOdrawhicwbacwkpropofbcomprisingMauricetoTRIBESoasmanblacybparametersx,towhicbtheehastuned.theSucandhstoppingatodraThewbacobkemathisyisrebumaksomeausers.studyIndeed,theaccordingehatoithervTRIBESaluessgivvenconditions,toorderthedetermineparametersstrengthsofdratheksalgorithm,thisitsepInerformancetouctuates.vSo,TRIBES,itwisnewimpareortanFirst,t,regularforproeacishinproblem,totoanndxpltherationparameterwidesetpwhicofhsearcgivspace,esthetheeginningbtheestpropAerformancestrategyofdisplthecemenalgorithm.basedHoanwybridationevaner,ofsucalgorithm,halsoatroproblemtoistaincomplexdivandytimetheconsuming,armespaeciallyoforgnoprovicesusers.TheTncreaoingaforvultioboidethedsuserthetoherstuneadaptthemethoparameters,toneumerousultiobresearcehesThehayvsuceanberationeenthat,donemosttothepropjectivoseaadaptivconicting.eealgorithms.MO-TRIBES,Fhorasucultihbalgorithms,etheersionvfaluesFinallyofourtheareptoaingrameterstationaremedicalcandhangedtheaccordingoftocompthets.resultsordspreviouslyOptimization,foundtindoptimization,uringultiobtheeoptiom,iparticlezarmationtimization,proeceestimationsdistributions.imagTRIBESsegmenisthresholdanvTabledesmati?res.e.In.tro.ductionolutionnairesg?n?ral.e.5.1heM?taheuristiquesAlgorithmed'optimisation.:.?tat.deTRIBES,l'art.9.1.1.In.tro.duction........e.e.a.................c.........p.........28...articulaire.........30.........2.tro.....TRIBES9.1.2.Optimisation.mono-ob.jectife.................27...........m.....ul?.....28.......colonies.....Optimisation.....App..9.1.2.1.OptimisationAppmono-ob.jectif.dicile..c.......Conclusion...........erfection.param?tre...........2.2.........2.3..9.1.2.2.M?taheuristiques.p34our.l.'optimisation.mono-ob.jectif.dicile......1.3.3.non-P............10.1.2.2.1.AlgorithmeApprodearetorecuit.sim.ul?............1.3.5.l.jectif.......28.recuit.............Algorithmes......11.1.2.2.2.Rec.hercAlgorithmehefourmisT.ab.ou....29.Essaim.........29.c.e...........0.c.areto...........App.e........13.1.2.2.3.Algorithmes30?v.olutionnaires....................et.t.d'OEP.2.1....................13.1.2.2.4tationAlgorithmes.de.colonies.de.fourmis..........daptations...................agr?gativ........15.1.2.2.5.Algorithme.?.estimation.de.distribu.tion..........27.Appro.he.areto................17.1.2.2.6.Optimisation.par.Essaim.P.articulaire....1.3.4.c.P..........................18.1.2.2.6.1.Connemen.t.des28particulesM?taheuristiques.our.'optimisation.ultiob.................1.3.5.1.de.sim........20.1.2.2.6.2.Graphes.d'inuence..........1.3.5.2.?v.........................1.3.5.3.de.de..20.1.2.2.6.3.F.acteur.de.constriction........1.3.5.4.par.P...................1.3.5.4.1.ro.h.agr?gativ..21.1.2.2.6.4.OEP.et.h.ybridation..........3.1.3.5.4.2.ro.h.non-P.......................1.3.5.4.3.ro22h1.2.2.6.5POEPretoadaptativ.e......................1.4..........................23.1.3.Optimisation.m.ultiob.jectif......31.?tude.p.nemen.de.algorithme.sans.33.In.duction.........................................3324Pr?sen1.3.1deD?nition.du.probl?me..............................34.A.structurell.s..........................25.1.3.2.Appro.c.he12TABLE...DES.MA.TI?RES.2.3.1.Structure.de.l'essaim......tro...hiv.......R?sultats.......seuillage...?lab.................4.............71..34.2.3.2.?v.olution.des74tribus....ultiob...........Div.............d?placemen...3.2.5..............................35.2.3.2.1nDestruction.de.particules..........4.2.2...4.2.2.1...e.75.......:.ram?tre...........3.2......36.2.3.2.2.Cr?ationdede.particules....T.........des.......62...................um?riques.......onctions..36.2.3.3.F.r?quenceCrit?resdes.adaptations......de.....Discussion.........3.4...........TRIBES.4.1...........de.........4.2.137.2.3.4.?v.olution.dedesl'essaim......de.....non-param?triques.....d'Otsu...........57.de.d'optimisation.sans.3.1..........................38.2.4.A.daptations.comp.ortemen.tales....60.au...............60.hniques.................3.2.3.................Strat?gies39.2.5.Algorithme................................R?sultats.MO-TRIBES.............3.3.1.e.................64.p............40.2.664Exp?rimen?rimen.tation.n.um?rique.et.comparaisons66...........................................Application.segmen41m?dicales2.6.1troPro.c?dure.de.test.CEC'05............4.2.llage...................du.................de.des....41.2.6.2.Algorithmes.utilis?s.pdesour.la.comparaison......M?tho.seuil.........M?tho........................4232.6.3orationR?sultatsMO-TRIBESnalgorithmeum?riquesm.jectif.pa-.59.In.duction.........................................59.MO-TRIBES..........42.2.6.4.Discussion..........................3.2.1.ersit?.sein.l'essaim.............................3.2.2.ec.d'arc.age........44.2.6.4.1.Commen.taires.g?n?raux..............61.Choix.informateurs...............................3.2.444de2.6.4.2tComparaison.a.v.ec.le.Standar.d.PSO.2006............64.Algorithme................50.2.6.4.3.Comparaison.en.tre.algorithmes..........6.3.3.n.de..........................50642.6.4.4FInuenceddetestla.dimension................................3.3.2.de.erformance............50.2.6.5.Conclusion..............3.3.3.exp.taux.MO-TRIBES.....................3.3.4.