文化基因算法

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

Applications4Example第2頁IntroductiongenememeCommonInthegeneticprocessofcontinuousevolutionanddevelopmentthroughcrossoverandmutationoperationsSuccessionanddevelopmentinthecommunicationprocessthroughinteraction,integration,mutation,etc.DifferentInbiologicalevolution,variationisrandom,onlyafewgoodvariationcanberetainedinnaturalselectionCulturaltransmissionprocessoftenwithfullknowledge-basedprofessionalfields,evolutionisfasterHawkins(1976)raisedmemenotion第3頁IntroductionInspiredbybothDarwinianprinciplesofnaturalevolutionandDawkins'notionofameme,theterm“MemeticAlgorithm”(MA)wasintroducedbyMoscatoin1989whereheviewedMAasbeingclosetoaformofpopulation-basedhybrid

geneticalgorithm(GA)coupledwithanindividuallearningprocedurecapableofperforminglocalrefinements.Ingeneral,usingtheideasofmemeticswithinacomputationalframeworkiscalled"MemeticComputingorMemeticComputation"(MC).MAisamoreconstrainednotionofMC.Morespecifically,MAcoversoneareaofMC第4頁ThedevelopmentofMAs—1st

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

MemeticAlgorithm

Initialize:Generateaninitialpopulation;

while

StoppingconditionsarenotsatisfieddoEvaluateallindividualsinthepopulation.Evolveanewpopulationusingstochasticsearchoperators.Selectthesubsetofindividuals,thatshouldundergotheindividualimprovementprocedure.

for

eachindividualindoPerformindividuallearningusingmeme(s)withfrequencyorprobabilityofforaperiodof.ProceedwithLamarckianorBaldwinianlearning.

endforendwhileHybrid

Algorithms第5頁ThedevelopmentofMAs—2nd

generationexhibitingtheprinciplesofmemetictransmissionandselectionintheirdesign.InMulti-memeMA,thememeticmaterialisencodedaspartofthe

genotype.MAconsideringmultipleindividuallearningmethodswithinanevolutionarysystem,thereaderisreferredto.Multi-meme,Hyper-heuristicandMeta-LamarckianMA第6頁ThedevelopmentofMAs—3nd

generationCo-evolution[8]

andself-generatingMAs[9]

Incontrastto2ndgenerationMAwhichassumesthatthememestobeusedareknownapriori,3rdgenerationMAutilizesarule-basedlocalsearchtosupplementcandidatesolutionswithintheevolutionarysystem,thuscapturingregularlyrepeatedfeaturesorpatternsintheproblemspace.第7頁Thebasicmodel

of

MAsInitialpopulationTheinitialparametersofthealgorithmpopSizePopulationsizeoffspringSizeThenumberobtainedbytheoffspringgeneratingfunctionlLengthcodingFFitnessfunctionGGeneratingfunctionUUpdatefunctionLCollectionoflocalsearchstrategy第8頁MAMethodForalltheproblemswewanttofindtheoptimalsolution.facingafundamentalquestionhowtogenerationPseudocode:ProcessDo-Generation(↓↑pop:individual[])variablesbreeders,newpop:Individual[];beginbreeders←Select-From-Population(pop);newpop←Generate-New-Population(breeders);pop←Update-Population(pop,newpop)end第9頁MAMethod

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

modifyinganexistingsolution.Thismodificationcanberandom–asitistypicallythecase–orcanbeendowedwithproblem-dependentinformationsoastobiasthesearchtoprobably-goodregionsofthesearchspaceMAMethod第11頁MAMethodPseudocode: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;

end第12頁MAMethodAfterhavingpresentedtheinnardsofthegenerationprocess,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()

end第13頁MAMethodTheGenerate-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

end第14頁MAMethodConsiderthatthepopulationmayreachastateinwhichthegenerationofnewimprovedsolutionbeveryunlikelyPseudocode: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

end第15頁MAsInfact,MAsisageneticalgorithmframework,isaconcept,inthisframework,usingdifferentsearchstrategiescanconstitutedifferentMAs,suchasglobalsearchstrategycanbeusedgeneticalgorithms,evolutionstrategies,evolutionaryprogramming,etc.localsearchstrategycanbeusedtoclimbthesearch,simulatedannealing,greedyalgorithms,tabusearch,guidedlocalsearch.第16頁Applicationsmanyclassical

NP

problemForexamplegraphpartitioning,

multidimensionalknapsack,

travellingsalesmanproblem,

quadraticassignmentproblem,

setcoverproblem,

minimalgraphcoloring,

maxindependentsetproblem,

binpackingproblem.Comparisonwiththegeneticalgorithmconvergesfaster,betterresults.第17頁Example

第18頁Example

第19頁Example

第20頁Example

第21頁Example

第22頁ExampleStepusingsimulatedannealingalgorithmforlocalsearchSTEP1Givenaninitialtemperature,Individualastheinitialstateofthesimulatedannealingalgorithm;STEP2Generateanewstate,theneighborhoodfunctiondefinedasInotherstatesofthetwoitemstochoose;STEP3

calculatethenumberofoldandnewstateenergy,theenergyfunctionalIsde