文化基因算法ppt

MemeticAlgorithm2015/01/05MemeticAlgorithmMember：杨勇佳、易科、朱家骅、苏航MemeticAlgorithm2015/01/05Contents1Introduction2ThedevelopmentofMAs2.11stgeneration2.22ndgeneration2.33rdgeneration3Applications4ExampleMemeticAlgorithm2015/01/05IntroductiongenememeCommonInthegeneticprocessofcontinuousevolutionanddevelopmentthroughcrossoverandmutationoperationsSuccessionanddevelopmentinthecommunicationprocessthroughinteraction,integration,mutation,etc.DifferentInbiologicalevolution,variationisrandom,onlyafewgoodvariationcanberetainedinnaturalselectionCulturaltransmissionprocessoftenwithfullknowledge-basedprofessionalfields,evolutionisfasterHawkins(1976)raisedmemenotionMemeticAlgorithm2015/01/05IntroductionInspiredbybothDarwinianprinciplesofnaturalevolutionandDawkins'notionofameme,theterm“MemeticAlgorithm”(MA)wasintroducedbyMoscatoin1989whereheviewedMAasbeingclosetoaformofpopulation-basedhybridgeneticalgorithm(GA)coupledwithanindividuallearningprocedurecapableofperforminglocalrefinements.Ingeneral,usingtheideasofmemeticswithinacomputationalframeworkiscalledMemeticComputingorMemeticComputation(MC).MAisamoreconstrainednotionofMC.Morespecifically,MAcoversoneareaofMCMemeticAlgorithm2015/01/05ThedevelopmentofMAs—1stgenerationamarriagebetweenapopulation-basedglobalsearch(oftenintheformofanevolutionaryalgorithm)coupledwithaculturalevolutionarystage.ThissuggestswhythetermMAstirredupcriticismsandcontroversiesamongresearcherswhenfirstintroduced.Pseudocode:ProcedureMemeticAlgorithmInitialize:Generateaninitialpopulation;whileStoppingconditionsarenotsatisfieddoEvaluateallindividualsinthepopulation.Evolveanewpopulationusingstochasticsearchoperators.Selectthesubsetofindividuals,thatshouldundergotheindividualimprovementprocedure.foreachindividualindoPerformindividuallearningusingmeme(s)withfrequencyorprobabilityofforaperiodof.ProceedwithLamarckianorBaldwinianlearning.endforendwhileilililtHybridAlgorithmsilfMemeticAlgorithm2015/01/05ThedevelopmentofMAs—2ndgenerationexhibitingtheprinciplesofmemetictransmissionandselectionintheirdesign.InMulti-memeMA,thememeticmaterialisencodedaspartofthegenotype.MAconsideringmultipleindividuallearningmethodswithinanevolutionarysystem,thereaderisreferredto.Multi-meme,Hyper-heuristicandMeta-LamarckianMAMemeticAlgorithm2015/01/05ThedevelopmentofMAs—3ndgenerationCo-evolution[8]andself-generatingMAs[9]Incontrastto2ndgenerationMAwhichassumesthatthememestobeusedareknownapriori,3rdgenerationMAutilizesarule-basedlocalsearchtosupplementcandidatesolutionswithintheevolutionarysystem,thuscapturingregularlyrepeatedfeaturesorpatternsintheproblemspace.MemeticAlgorithm2015/01/05ThebasicmodelofMAs),,,,,,,,(00LUGFlpopSizeizeoffspringSPMA𝑃0Initialpopulation𝛿0TheinitialparametersofthealgorithmpopSizePopulationsizeoffspringSizeThenumberobtainedbytheoffspringgeneratingfunctionlLengthcodingFFitnessfunctionGGeneratingfunctionUUpdatefunctionLCollectionoflocalsearchstrategyMemeticAlgorithm2015/01/05MAMethodForalltheproblemswewanttofindtheoptimalsolution.facingafundamentalquestionhowtogenerationPseudocode:ProcessDo-Generation(↓↑pop:individual[])variablesbreeders,newpop:Individual[];beginbreeders←Select-From-Population(pop);newpop←Generate-New-Population(breeders);pop←Update-Population(pop,newpop)endMemeticAlgorithm2015/01/05MAMethod•ForGenerate-New-Populationprocess,themosttypicalsituationinvolvesutilizingjusttwooperators:recombinationandmutation.Pseudocode:ProcessGenerate-New-Population(↓pop:Individual[],↓op:Operator[])→Individual[]variablesbuffer:Individual[][];j:[1..|op|];beginbuffer[0]←pop;forj←1:|op|dobuffer[j]←Apply-Operator(op[j],buffer[j−1]);Endfor;MemeticAlgorithm2015/01/05•Inessence,amutationoperatormustgenerateanewsolutionbypartlymodifyinganexistingsolution.Thismodificationcanberandom–asitistypicallythecase–orcanbeendowedwithproblem-dependentinformationsoastobiasthesearchtoprobably-goodregionsofthesearchspaceMAMethodMemeticAlgorithm2015/01/05MAMethod•Pseudocode:•ProcessLocal-Improver(↓↑current:Individual,↓op:Operator)variablesnew:Individualbeginrepeatnew←Apply-Operator(op,current);if(Fg(new)≺Fg(current))thencurrent←new;endifuntilLocal-Improver-Termination-Criterion();returncurrent;endMemeticAlgorithm2015/01/05MAMethod•Afterhavingpresentedtheinnardsofthegenerationprocess,wecannowhaveaccesstothelargerpicture.ThefunctioningofaMAconsistsoftheiterationofthisbasicgenerationalstepPseudocode:ProcessMA()→Individual[]variablespop:Individual[];beginpop←Generate-Initial-Population();repeatpop←Do-Generation(pop)ifConverged(pop)thenpop←Restart-Population(pop);endifuntilMA-Termination-Criterion()endMemeticAlgorithm2015/01/05MAMethod•TheGenerate-Initial-Populationprocessisresponsibleforcreatingtheinitialsetof|pop|configurationsPseudocode:ProcessGenerate-Initial-Population(↓µ:N)→Individual[]variablespop:Individual[];ind:Individual;j:[1..µ];beginforj←1:µdoind←Generate-Random-Solution();pop[j]←Local-Improver(ind);endforreturnpopendMemeticAlgorithm2015/01/05MAMethod•Considerthatthepopulationmayreachastateinwhichthegenerationofnewimproveds