文化基因算法

.,MemeticAlgorithm,Member：杨勇佳、易科、朱家骅、苏航,.,Contents,1Introduction2ThedevelopmentofMAs2.11stgeneration2.22ndgeneration2.33rdgeneration3Applications4Example,.,Introduction,Hawkins(1976)raisedmemenotion,.,Introduction,InspiredbybothDarwinianprinciplesofnaturalevolutionandDawkinsnotionofameme,theterm“MemeticAlgorithm”(MA)wasintroducedbyMoscatoin1989whereheviewedMAasbeingclosetoaformofpopulation-basedhybridgeneticalgorithm(GA)coupledwithanindividuallearningprocedurecapableofperforminglocalrefinements.,Ingeneral,usingtheideasofmemeticswithinacomputationalframeworkiscalledMemeticComputingorMemeticComputation(MC).MAisamoreconstrainednotionofMC.Morespecifically,MAcoversoneareaofMC,.,ThedevelopmentofMAs1stgeneration,amarriagebetweenapopulation-basedglobalsearch(oftenintheformofanevolutionaryalgorithm)coupledwithaculturalevolutionarystage.ThissuggestswhythetermMAstirredupcriticismsandcontroversiesamongresearcherswhenfirstintroduced.,Pseudocode:ProcedureMemeticAlgorithmInitialize:Generateaninitialpopulation;whileStoppingconditionsarenotsatisfieddoEvaluateallindividualsinthepopulation.Evolveanewpopulationusingstochasticsearchoperators.Selectthesubsetofindividuals,thatshouldundergotheindividualimprovementprocedure.foreachindividualindoPerformindividuallearningusingmeme(s)withfrequencyorprobabilityofforaperiodof.ProceedwithLamarckianorBaldwinianlearning.endforendwhile,HybridAlgorithms,.,ThedevelopmentofMAs2ndgeneration,exhibitingtheprinciplesofmemetictransmissionandselectionintheirdesign.InMulti-memeMA,thememeticmaterialisencodedaspartofthegenotype.MAconsideringmultipleindividuallearningmethodswithinanevolutionarysystem,thereaderisreferredto.,Multi-meme,Hyper-heuristicandMeta-LamarckianMA,.,ThedevelopmentofMAs3ndgeneration,Co-evolution8andself-generatingMAs9Incontrastto2ndgenerationMAwhichassumesthatthememestobeusedareknownapriori,3rdgenerationMAutilizesarule-basedlocalsearchtosupplementcandidatesolutionswithintheevolutionarysystem,thuscapturingregularlyrepeatedfeaturesorpatternsintheproblemspace.,.,ThebasicmodelofMAs,.,MAMethod,Foralltheproblemswewanttofindtheoptimalsolution.facingafundamentalquestionhowtogeneration,Pseudocode:ProcessDo-Generation(pop:individual)variablesbreeders,newpop:Individual;beginbreedersSelect-From-Population(pop);newpopGenerate-New-Population(breeders);popUpdate-Population(pop,newpop)end,.,MAMethod,ForGenerate-New-Populationprocess,themosttypicalsituationinvolvesutilizingjusttwooperators:recombinationandmutation.,Pseudocode:ProcessGenerate-New-Population(pop:Individual,op:Operator)Individualvariablesbuffer:Individual;j:1.|op|;beginbuffer0pop;forj1:|op|dobufferjApply-Operator(opj,bufferj1);Endfor;,.,Inessence,amutationoperatormustgenerateanewsolutionbypartlymodifyinganexistingsolution.Thismodificationcanberandomasitistypicallythecaseorcanbeendowedwithproblem-dependentinformationsoastobiasthesearchtoprobably-goodregionsofthesearchspace,MAMethod,.,MAMethod,Pseudocode:ProcessLocal-Improver(current:Individual,op:Operator)variablesnew:IndividualbeginrepeatnewApply-Operator(op,current);if(Fg(new)Fg(current)thencurrentnew;endifuntilLocal-Improver-Termination-Criterion();returncurrent;end,.,MAMethod,Afterhavingpresentedtheinnardsofthegenerationprocess,wecannowhaveaccesstothelargerpicture.ThefunctioningofaMAconsistsoftheiterationofthisbasicgenerationalstep,Pseudocode:ProcessMA()Individualvariablespop:Individual;beginpopGenerate-Initial-Population();repeatpopDo-Generation(pop)ifConverged(pop)thenpopRestart-Population(pop);endifuntilMA-Termination-Criterion()end,.,MAMethod,TheGenerate-Initial-Populationprocessisresponsibleforcreatingtheinitialsetof|pop|configurations,Pseudocode:ProcessGenerate-Initial-Population(:N)Individualvariablespop:Individual;ind:Individual;j:1.;beginforj1:doindGenerate-Random-Solution();popjLocal-Improver(ind);endforreturnpopend,.,MAMethod,Considerthatthepopulationmayreachastateinwhichthegenerationofnewimprovedsolutionbeveryunlikely,Pseudocode:ProcessRestart-Population(pop:Individual)Individualvariablesnewpop:Individual;j,#preserved:1.|pop|;begin#preserved|pop|%PRESERVE;forj1:#preserveddonewpopjithBest(pop,j);endforforj(#preserved+1):|pop|donewpopjGenerate-Random-Configuration();newpopjLocal-Improver(newpopj);endfor;returnnewpopend,.,MAs,Infact,MAsisageneticalgorithmframework,isaconcept,inthisframework,usingdifferentsearchstrategiescanconstitutedifferentMAs,suchasglobalsearchstrategycanbeusedgeneticalgorithms,evolutionstrategies,evolutionaryprogramming,etc.localsearchstrategycanbeusedtoclimbthesearch,simulatedannealing,greedyalgorithms,tabusearch,guidedlocalsearch.,.,Applications,manyclassicalNPproblemForexamplegraphpartitioning,multidimensionalknapsack,travellingsalesmanproblem,quadraticassignmentproblem,setcoverproblem,minimalgraphcoloring,maxindependentsetproblem,binpackingproblem.Comparisonwiththegeneticalgorithmconvergesfaster,betterresults.,.,Example,.,Example,.,Example,.,Example,.,Example,.,Example,StepusingsimulatedannealingalgorithmforlocalsearchSTEP1Givenaninitialtemperature,Individualastheinitialstateofthesimulatedannealingalgorithm;STEP2Generateanewstate,theneighborhoodfunctiondefinedasInotherstatesofthetwoitemstochoose;STEP3calculatethenumberofoldandnewstateenergy,theenergyfunctionalIsdefinedasthereciprocalofthefitnessfunction;STEP4acceptthenewstateaccordingtoguidelinesMetropolisSTEP5Samplingstabilitycriteriaaremet?truetheexecutionstep6,otherwisestep2;STEP6Returntemperaturefunction;STEP7Noterminationtemperatureswillreach?theoptimalstateasanewpopulationofanindividual;otherwisestep2.,.,Example,Algorithmicprocess,Generateinitialpopulationcalculatetheirfitnessfuncti