文化基因算法ppt.ppt

MemeticAlgorithm Member 杨勇佳 易科 朱家骅 苏航 Contents 1Introduction2ThedevelopmentofMAs2 11stgeneration2 22ndgeneration2 33rdgeneration3Applications4Example Introduction Hawkins 1976 raisedmemenotion Introduction InspiredbybothDarwinianprinciplesofnaturalevolutionandDawkins notionofameme theterm MemeticAlgorithm MA wasintroducedbyMoscatoin1989whereheviewedMAasbeingclosetoaformofpopulation basedhybridgeneticalgorithm GA coupledwithanindividuallearningprocedurecapableofperforminglocalrefinements Ingeneral usingtheideasofmemeticswithinacomputationalframeworkiscalled MemeticComputingorMemeticComputation MC MAisamoreconstrainednotionofMC Morespecifically MAcoversoneareaofMC ThedevelopmentofMAs 1stgeneration amarriagebetweenapopulation basedglobalsearch oftenintheformofanevolutionaryalgorithm coupledwithaculturalevolutionarystage ThissuggestswhythetermMAstirredupcriticismsandcontroversiesamongresearcherswhenfirstintroduced Pseudocode ProcedureMemeticAlgorithmInitialize Generateaninitialpopulation whileStoppingconditionsarenotsatisfieddoEvaluateallindividualsinthepopulation Evolveanewpopulationusingstochasticsearchoperators Selectthesubsetofindividuals thatshouldundergotheindividualimprovementprocedure foreachindividualindoPerformindividuallearningusingmeme s withfrequencyorprobabilityofforaperiodof ProceedwithLamarckianorBaldwinianlearning endforendwhile HybridAlgorithms ThedevelopmentofMAs 2ndgeneration exhibitingtheprinciplesofmemetictransmissionandselectionintheirdesign InMulti memeMA thememeticmaterialisencodedaspartofthegenotype MAconsideringmultipleindividuallearningmethodswithinanevolutionarysystem thereaderisreferredto Multi meme Hyper heuristicandMeta LamarckianMA ThedevelopmentofMAs 3ndgeneration Co evolution 8 andself generatingMAs 9 Incontrastto2ndgenerationMAwhichassumesthatthememestobeusedareknownapriori 3rdgenerationMAutilizesarule basedlocalsearchtosupplementcandidatesolutionswithintheevolutionarysystem thuscapturingregularlyrepeatedfeaturesorpatternsintheproblemspace ThebasicmodelofMAs MAMethod Foralltheproblemswewanttofindtheoptimalsolution facingafundamentalquestionhowtogeneration Pseudocode ProcessDo Generation pop individual variablesbreeders newpop Individual beginbreeders Select From Population pop newpop Generate New Population breeders pop Update Population pop newpop end 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 Inessence amutationoperatormustgenerateanewsolutionbypartlymodifyinganexistingsolution Thismodificationcanberandom asitistypicallythecase orcanbeendowedwithproblem dependentinformationsoastobiasthesearchtoprobably goodregionsofthesearchspace MAMethod MAMethod 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 end MAMethod Afterhavingpresentedtheinnardsofthegenerationprocess wecannowhaveaccesstothelargerpicture ThefunctioningofaMAconsistsoftheiterationofthisbasicgenerationalstep Pseudocode ProcessMA Individual variablespop Individual beginpop Generate Initial Population repeatpop Do Generation pop ifConverged pop thenpop Restart Population pop endifuntilMA Termination Criterion end MAMethod TheGenerate Initial Populationprocessisresponsibleforcreatingtheinitialsetof pop configurations Pseudocode ProcessGenerate Initial Population N Individual variablespop Individual ind Individual j 1 beginforj 1 doind Generate Random Solution pop j Local Improver ind endforreturnpopend MAMethod Considerthatthepopulationmayreachastateinwhichthegenerationofnewimprovedsolutionbeveryunlikely Pseudocode ProcessRestart Population pop Individual Individual variablesnewpop Individual j preserved 1 pop begin preserved pop PRESERVE forj 1 preserveddonewpop j ithBest pop j endforforj preserved 1 pop donewpop j Generate Random Configuration newpop j Local Improver newpop j 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 MultidimensionalKnapsackProblemsProblemDescriptionTherearenitems thevalueofeachitemis i 1 2 n existingabackpack thebackpackhasmconstraints eachconstraintmaximumProvidinganamountof j 1 2 m theiitemforthejconstraintsis i 1 2 N j 1 2 m Example Mathematicalmodel 1 max 1 2 1 0 1 i 1 2 n j 1 2 m 0representsthefirstIitemsdonotfitinabackpack 1indicatestheIitemisloadedbackpack Example Inthispaper thedegreeofconstraintviolationbysortingmethodmakesthebestsolutionAmountmaximizevaluecasesatisfiesalltheconstraints Foreachconstraintj alloftheitemsindescendingSortaccordingto and representforconstraintj anumberofthesort Calculatingforeachviolationoftheconstraints i 1 2 nj 1 2 m Example mconstraintascendingsortaccordingtoviolationoftheconstraints Wefirstprocesssmallviolationoftheconstraints ProcessingFollow if 1 L L L 1Else 0 Example InthispaperusingGreedystrategysoFitnessfunctionf 1 Generatingfunction Single pointcrossover SinglepointmutationLocalsearch SimulatedAnnealing Example StepusingsimulatedannealingalgorithmforlocalsearchSTEP1Givenaninitialtemperature Individualastheinitialstateofthesimulatedannealingalgorithm STEP2Generateanewstate theneighborhoodfunctiondefinedasInotherstatesofthetwoitemstochoose STEP3calculatethenumberofoldandnewstateenergy theenergyfunctio