




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 用智慧譜寫幼兒園發(fā)展新篇章計劃
- 重大建設(shè)項目的安全檢查計劃
- 2025年貓爬架項目發(fā)展計劃
- 2025年板臥式電除塵器項目合作計劃書
- 2025年密封用填料及類似品項目建議書
- 實施均衡發(fā)展的人口政策
- 醫(yī)療健康管理服務(wù)協(xié)議
- 藝術(shù)品交易與展示項目投資合同
- 擔保期權(quán)合同
- 西游記中的人物形象賞析與解讀
- 人教版(2024新版)七年級上冊英語各單元重點語法知識點講義
- 安全閥校驗標準
- 耳穴壓豆課件
- 建筑制圖與識圖教學(xué)課件:第八章 結(jié)構(gòu)施工圖
- 湘教版三年級美術(shù)下冊教案全冊
- (高清版)DB15∕T 3585-2024 高標準農(nóng)田施工質(zhì)量評定規(guī)程
- 試油(氣)HSE作業(yè)指導(dǎo)書
- 重癥監(jiān)護-ICU的設(shè)置、管理與常用監(jiān)測技術(shù)
- 法律顧問服務(wù)投標方案(完整技術(shù)標)
- 中醫(yī)藥三方合作協(xié)議書范本
- 2024年《動漫藝術(shù)概論》自考復(fù)習(xí)題庫(附答案)
評論
0/150
提交評論