文化基因算法ppt.ppt

MemeticMemeticAlgorithmAlgorithm2015/01/05 Memetic Algorithm Member：杨勇佳、易科、朱家骅、苏航MemeticMemeticAlgorithmAlgorithm2015/01/05Contents1Introduction2ThedevelopmentofMAs2.11stgeneration2.22ndgeneration2.33rdgeneration3Applications4ExampleMemeticMemeticAlgorithmAlgorithm2015/01/05IntroductiongenememeCommonInthegeneticprocessofcontinuousevolutionanddevelopmentthroughcrossoverandmutationoperationsSuccessionanddevelopmentinthecommunicationprocessthroughinteraction,integration,mutation,etc.DifferentInbiologicalevolution,variationisrandom,onlyafewgoodvariationcanberetainedinnaturalselectionCulturaltransmissionprocessoftenwithfullknowledge-basedprofessionalfields,evolutionisfasterHawkins(1976)raised meme notionMemeticMemeticAlgorithmAlgorithm2015/01/05IntroductionInspiredbybothDarwinianprinciplesofnaturalevolutionandDawkinsnotionofameme,theterm“MemeticAlgorithm”(MA)wasintroducedbyMoscatoin1989whereheviewedMAasbeingclosetoaformofpopulation-basedhybridgeneticalgorithm(GA)coupledwithanindividuallearningprocedurecapableofperforminglocalrefinements.Ingeneral,usingtheideasofmemeticswithinacomputationalframeworkiscalledMemeticComputingorMemeticComputation(MC).MAisamoreconstrainednotionofMC.Morespecifically,MAcoversoneareaofMCMemeticMemeticAlgorithmAlgorithm2015/01/05ThedevelopmentofMAs 1st generationuamarriagebetweenapopulation-basedglobalsearch(oftenintheformofanevolutionaryalgorithm)coupledwithaculturalevolutionarystage.uThissuggestswhythetermMAstirredupcriticismsandcontroversiesamongresearcherswhenfirstintroduced.uPseudocode:ProcedureMemeticAlgorithmInitialize:Generateaninitialpopulation;whileStoppingconditionsarenotsatisfieddoEvaluateallindividualsinthepopulation.Evolveanewpopulationusingstochasticsearchoperators.Selectthesubsetofindividuals,thatshouldundergotheindividualimprovementprocedure.foreachindividualindoPerformindividuallearningusingmeme(s)withfrequencyorprobabilityofforaperiodof.ProceedwithLamarckianorBaldwinianlearning.endforendwhileHybridAlgorithmsMemeticMemeticAlgorithmAlgorithm2015/01/05ThedevelopmentofMAs 2nd generationuexhibitingtheprinciplesofmemetictransmissionandselectionintheirdesign.uInMulti-memeMA,thememeticmaterialisencodedaspartofthegenotype.uMAconsideringmultipleindividuallearningmethodswithinanevolutionarysystem,thereaderisreferredto.Multi-meme,Hyper-heuristicandMeta-LamarckianMAMemeticMemeticAlgorithmAlgorithm2015/01/05ThedevelopmentofMAs 3nd generationCo-evolution8andself-generatingMAs9Incontrastto2ndgenerationMAwhichassumesthat the memes to be used are known a priori,3rdgeneration MA utilizes a rule-based local search tosupplementcandidatesolutionswithintheevolutionarysystem,thuscapturingregularlyrepeatedfeaturesorpatternsintheproblemspace.MemeticMemeticAlgorithmAlgorithm2015/01/05The basic model of MAs0Initialpopulation0The initial parameters of the algorithmpopSizePopulation sizeoffspringSizeThe number obtained by the offspring generating functionlLength codingFFitness functionGGenerating functionUUpdate functionLCollection of local search strategyMemeticMemeticAlgorithmAlgorithm2015/01/05MA MethodForalltheproblemswewanttofindtheoptimalsolution.facingafundamentalquestionhowtogenerationPseudocode:ProcessDo-Generation(pop:individual)variablesbreeders,newpop:Individual;beginbreedersSelect-From-Population(pop);newpopGenerate-New-Population(breeders);popUpdate-Population(pop,newpop)endMemeticMemeticAlgorithmAlgorithm2015/01/05MA MethodFor Generate-New-Population process,the mosttypical situation involves utilizing just two operators:recombinationandmutation.Pseudocode:ProcessGenerate-New-Population(pop:Individual,op:Operator)Individualvariablesbuffer:Individual;j:1.|op|;beginbuffer0pop;forj1:|op|dobufferjApply-Operator(opj,bufferj1);Endfor;MemeticMemeticAlgorithmAlgorithm2015/01/05In essence,a mutation operator must generate a newsolution by partly modifying an existing solution.Thismodificationcanberandomasitistypicallythecaseorcanbeendowedwithproblem-dependentinformationsoas to bias the search to probably-good regions of thesearchspaceMA MethodMemeticMemeticAlgorithmAlgorithm2015/01/05MA MethodPseudocode:ProcessLocal-Improver(current:Individual,op:Operator)variablesnew:IndividualbeginrepeatnewApply-Operator(op,current);if(Fg(new)Fg(current)thencurrentnew;endifuntilLocal-Improver-Termination-Criterion();returncurrent;endMemeticMemeticAlgorithmAlgorithm2015/01/05MA MethodAfter having presented the innards of the generationprocess,wecannowhaveaccesstothelargerpicture.ThefunctioningofaMAconsistsoftheiterationofthisbasicgenerationalstepPseudocode:Process MA()Individualvariablespop:Individual;beginpop Generate-Initial-Population();rep eatpop Do-Generation(pop)if Converged(pop)thenpop Restart-Population(pop);end ifuntil MA-Termination-Criterion()endMemeticMemeticAlgorithmAlgorithm2015/01/05MA MethodThe Generate-Initial-Population process is responsibleforcreatingtheinitialsetof|pop|configurationsPseudocode:Process Generate-Initial-Population(:N)Individualvariablespop:Individual;ind:Individual;j:1.;beginfor j 1:doind Generate-Random-Solution();popj Local-Improver(ind);endforreturn popendMemeticMemeticAlgorithmAlgorithm2015/01/05MA MethodConsider that the population may reach a state in which thegenerationofnewimprovedsolutionbeveryunlikelyPseudocode:Pro cess Restart-Population(pop:Individual)Individualvariablesnewpop:Individual;j,#preserved:1.|pop|;b egin#preserved|pop|%PRESERV E;for j 1:#preserved donewpopj ithBest(pop,j);endforfor j (#preserved+1):|pop|donewpopj Generate-Random-Configuration();newpopj Local-Improver(newpopj);endfor;return newpopendMemeticMemeticAlgorithmAlgorithm2015/01/05MAs Infact,MAsisageneticalgorithmframework,isaconcept,inthisframework,usingdifferentsearchstrategiescanconstitutedifferentMAs,suchasglobalsearchstrategycanbeusedgeneticalgorithms,evolutionstrategies,evolutionaryprogramming,etc.localsearchstrategycanbeusedtoclimbthesearch,simulatedannealing,greedyalgorithms,tabusearch,guidedlocalsearch.MemeticMemeticAlgorithmAlgorithm2015/01/05ApplicationsmanyclassicalNPproblemForexamplegraphpartitioning,multidimensionalknapsack,travellingsalesmanproblem,quadraticassignmentproblem,setcoverproblem,minimalgraphcoloring,maxindependentsetproblem,binpackingproblem.Comparisonwiththegeneticalgorithmconvergesfaster,betterresults.MemeticMemeticAlgorithmAlgorithm2015/01/05ExampleMemeticMemeticAlgorithmAlgorithm2015/01/05ExampleMemeticMemeticAlgorithmAlgorithm2015/01/05ExampleMemeticMemeticAlgorithmAlgorithm2015/01/05ExampleMemeticMemeticAlgorithmAlgorithm2015/01/05ExampleMemeticMemeticAlgorithmAlgorithm2015/01/05ExampleStepusingsimulatedannealingalgorithmforlocalsearchSTEP1Givenaninitialtemperature,Individualastheinitialstateofthesimulatedannealingalgorithm;STEP2Generateanewstate,theneighborhoodfunctiondefinedasInotherstatesofthetwoitemstochoose;STEP3calculatethenumberofoldandnewstateenergy,theenergyfunctionalIsdefinedasthereciprocalofthefitnessfunction;STEP4acceptthenewstateaccordingtoguidelinesMetropolisSTEP5Samplingstabilitycriteriaaremet?truetheexecutionstep6,otherwisestep2;STEP6Returntemperaturefunction;STEP7Noterminationtemperatureswillreach?theoptimalstateasanewpopulationofanindividual;otherwisestep2.MemeticMemeticAlgorithmAlgorithm2015/01/05ExampleAlgorithmicprocessGenerateinitialpopulationcalculatetheirfitnessfunctionVariationandcrossUsing Greedy strategy start constraintprocessing,all individuals is a viablesolutionCalculatefitnessfunctionforthenewpopulationandkeepthecurrentoptimalsolutionLocalSearchforindividualsStopuntilconditionsaresatisfiedinputOptimalresultsSettheinitialparametersYesNoMemeticMemeticAlgorithmAlgorithm2015/01/05Thank you