文化基因算法ppt

MemeticAlgorithmMember：楊勇佳、易科、朱家驊、蘇航Contents1Introduction2ThedevelopmentofMAs2.11stgeneration2.22ndgeneration2.33rdgeneration3

Applications4ExampleIntroductiongenememeCommonInthegeneticprocessofcontinuousevolutionanddevelopmentthroughcrossoverandmutationoperationsSuccessionanddevelopmentinthecommunicationprocessthroughinteraction,integration,mutation,etc.DifferentInbiologicalevolution,variationisrandom,onlyafewgoodvariationcanberetainedinnaturalselectionCulturaltransmissionprocessoftenwithfullknowledge-basedprofessionalfields,evolutionisfasterHawkins(1976)raisedmemenotionIntroductionInspiredbybothDarwinianprinciplesofnaturalevolutionandDawkins'notionofameme,theterm“MemeticAlgorithm”(MA)wasintroducedbyMoscatoin1989whereheviewedMAasbeingclosetoaformofpopulation-basedhybrid

geneticalgorithm(GA)coupledwithanindividuallearningprocedurecapableofperforminglocalrefinements.Ingeneral,usingtheideasofmemeticswithinacomputationalframeworkiscalled"MemeticComputingorMemeticComputation"(MC).MAisamoreconstrainednotionofMC.Morespecifically,MAcoversoneareaofMCThedevelopmentofMAs—1st

generationamarriagebetweenapopulation-basedglobalsearch(oftenintheformofanevolutionaryalgorithm)coupledwithaculturalevolutionarystage.ThissuggestswhythetermMAstirredupcriticismsandcontroversiesamongresearcherswhenfirstintroduced.Pseudocode:Procedure

MemeticAlgorithm

Initialize:Generateaninitialpopulation;

while

StoppingconditionsarenotsatisfieddoEvaluateallindividualsinthepopulation.Evolveanewpopulationusingstochasticsearchoperators.Selectthesubsetofindividuals,thatshouldundergotheindividualimprovementprocedure.

for

eachindividualindoPerformindividuallearningusingmeme(s)withfrequencyorprobabilityofforaperiodof.ProceedwithLamarckianorBaldwinianlearning.

endforendwhileHybrid

AlgorithmsThedevelopmentofMAs—2nd

generationexhibitingtheprinciplesofmemetictransmissionandselectionintheirdesign.InMulti-memeMA,thememeticmaterialisencodedaspartofthe

genotype.MAconsideringmultipleindividuallearningmethodswithinanevolutionarysystem,thereaderisreferredto.Multi-meme,Hyper-heuristicandMeta-LamarckianMAThedevelopmentofMAs—3nd

generationCo-evolution[8]

andself-generatingMAs[9]

Incontrastto2ndgenerationMAwhichassumesthatthememestobeusedareknownapriori,3rdgenerationMAutilizesarule-basedlocalsearchtosupplementcandidatesolutionswithintheevolutionarysystem,thuscapturingregularlyrepeatedfeaturesorpatternsintheproblemspace.Thebasicmodel

of

MAsInitialpopulationTheinitialparametersofthealgorithmpopSizePopulationsizeoffspringSizeThenumberobtainedbytheoffspringgeneratingfunctionlLengthcodingFFitnessfunctionGGeneratingfunctionUUpdatefunctionLCollectionoflocalsearchstrategyMAMethodForalltheproblemswewanttofindtheoptimalsolution.facingafundamentalquestionhowtogenerationPseudocode:ProcessDo-Generation(↓↑pop:individual[])variablesbreeders,newpop:Individual[];beginbreeders←Select-From-Population(pop);newpop←Generate-New-Population(breeders);pop←Update-Population(pop,newpop)endMAMethod

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;Inessence,amutationoperatormustgenerateanewsolutionbypartly

modifyinganexistingsolution.Thismodificationcanberandom–asitistypicallythecase–orcanbeendowedwithproblem-dependentinformationsoastobiasthesearchtoprobably-goodregionsofthesearchspaceMAMethodMAMethodPseudocode:ProcessLocal-Improver(↓↑current:Individual,↓op:Operator)

variables

new:Individual

begin

repeat

new←Apply-Operator(op,current);

if(Fg(new)?Fg(current))then

current←new;

endif

untilLocal-Improver-Termination-Criterion();

returncurrent;

endMAMethodAfterhavingpresentedtheinnardsofthegenerationprocess,wecannowhaveaccesstothelargerpicture.ThefunctioningofaMAconsistsoftheiterationofthisbasicgenerationalstepPseudocode:ProcessMA()→Individual[]

variables

pop:Individual[];

begin

pop←Generate-Initial-Population();

repeat

pop←Do-Generation(pop)

ifConverged(pop)then

pop←Restart-Population(pop);

endif

untilMA-Termination-Criterion()

endMAMethodTheGenerate-Initial-Populationprocessisresponsibleforcreatingtheinitialsetof|pop|configurationsPseudocode:ProcessGenerate-Initial-Population(↓μ:N)→Individual[]

variables

pop:Individual[];

ind:Individual;

j:[1..μ];

begin

forj←1:μdo

ind←Generate-Random-Solution();

pop[j]←Local-Improver(ind);

endfor

returnpop

endMAMethodConsiderthatthepopulationmayreachastateinwhichthegenerationofnewimprovedsolutionbeveryunlikelyPseudocode:ProcessRestart-Population(↓pop:Individual[])→Individual[]

variables

newpop:Individual[];

j,#preserved:[1..|pop|];

begin

#preserved←|pop|·%PRESERVE;

forj←1:#preserveddo

newpop[j]←ithBest(pop,j);

endfor

forj←(#preserved+1):|pop|do

newpop[j]←Generate-Random-Configuration();

newpop[j]←Local-Improver(newpop[j]);

endfor;

returnnewpop

endMAsInfact,MAsisageneticalgorithmframework,isaconcept,inthisframework,usingdifferentsearchstrategiescanconstitutedifferentMAs,suchasglobalsearchstrategycanbeusedgeneticalgorithms,evolutionstrategies,evolutionaryprogramming,etc.localsearchstrategycanbeusedtoclimbthesearch,simulatedannealing,greedyalgorithms,tabusearch,guidedlocalsearch.Applicationsmanyclassical

NP

problemForexamplegraphpartitioning,

multidimensionalknapsack,

travellingsalesmanproblem,

quadraticassignmentproblem,

setcoverproblem,

minimalgraphcoloring,

maxindependentsetproblem,

binpackingproblem.Comparisonwiththegeneticalgorithmconvergesfaster,betterresults.Example

Example

Example

Example

Example

ExampleStepusingsimulatedannealingalgorithmforlocalsearchSTEP1Givenaninitialtemperature,Individualastheinitialstateofthesimulatedannealingalgorithm;STEP2Generateanewstate,theneighborhoodfunctiondefinedasInotherstatesofthetwoitemstochoose;STEP3

calculatethenumberofoldandnewstateenergy,theenergyfunctionalIs