版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
MachineLearningCHAPTER9GeneticAlgorithmsOutlineGeneticalgorithmprovideanapproachlearningthatisbasedlooselyonsimulatedevolution.HypothesesaredescribedbybitstringswhoseinterpretationdependsontheapplicationThesearchbeginswithapopulationofinitialhypotheses.ThenextgenerationofpopulationisgeneratedbymeansofoperationssuchasrandommutationandcrossoverHypothesesareevaluatedbyameasureoffitness.Application9.1MotivationGeneticalgorithmsismotivatedbyananalogytobiologicalevolutionGAsgeneratesuccessorhbyrepeatedlymutatingandrecombiningpartsofthebestcurrentlyknownhypothesesHissearchedbyagenerated-and-testbeam-searchThepopularityofGAsismotivatedby: evolutionofbiologicalsystem abilityofsearchingHcontainingcomplexinteractingparts abilityofparallelizingcomputingContentofthischapter9.2GeneticAlgorithmsHypothesisfitnessStructureofGAs: iterativelyupdatingapopulation evaluationofmembersofapopulation generatenewpopulation
AprototypicalgeneticalgorithmGA(Fitness,fitness_threshold,p,r,m)
initializepopulation:P=Generatephypothesesatrandom
Evaluate:ForeachhinP,compute
Fitness(h)
while[max
Fitness(h)]<Fitness_thresholddo createanewgeneration,PS: 1.Select:probabilisticallyselect(1-r)pmembersofPtoaddtoPS.TheprobabilityPr(hi)ofselectinghypothesishifromPisgivenby
Pr(hi)=Fitness(hi)/∑Fitness(hj) 2.Crossover:Probabilisticallyselectr*p/2pairsofhypothesesfromP,accordingtoPr(hi)givenabove.Foreachpair,<h1,h2>,producetwooffspringbyapplyingthecrossoveroperator.AddalloffspringtoPS.
3.Mutate:choosempercentofthemembersofPSwithuniformprobability.Foreach,invertonerandomlyselectedbitinitsrepresentation. 4.update:P=PS
5.Evaluate:foreachhinP,computeFitness(h)ReturnthehypothesisfromPthathasthehighestfitness9.2.1RepresentingHypothesesHypothesesareoftenberepresentedbybitstrings,sotheycanbeeasilymanipulatedbygeneticoperatorsExample:codingif-thenrulesbybitstringsFirstuseabitstringtodescribeaconstraintonthevalueofasingleattributeOutlook:Sunny、Overcast、Rain,canberepresenttedbyabitstringoflengththreeArulecaneasilyberepresentedbyconcatenatingthecorrespondingbitstrings9.2.1RepresentingHypothesesNOTEAbitstringforarulecontainsasubstringforeachattributeinahypothesisspace,evenifaattributeisnotconstrainedbytherulepreconditionsSubstringsofabitstringatspecificlocationsdescribeconstraintsonspecificattributesRepresentationofsetsofrules:concatenatingbitstringsofindividualrulesAsyntacticallylegalbitstringshouldrepresentawell-definedhypothesisHypothesescanberepresentedbysymbolicdescriptionsratherthanbitstrings,forexample,computerprogram9.2.2GeneticoperatorsThegenerationofsuccessorsinaGAisdeterminedbyasetofoperatorsthatrecombineandmutateselectedmembersofthecurrentpopulation.TypicalGAoperatorsformanipulatingbitstringhypothesesinTable9.2Themostcommonoperators:crossoverandmutationThecrossoveroperator:ProducestwonewoffspringfromtwoparentsstringsbycopyingselectedbitsfromeachparentThechoiceofwhichparentcontributesthebitpositioniisdeterminedbyanadditionalstringcalledthecrossovermask:SinglepointcrossoverTwo-pointcrossoverUniformcrossover9.2.2Geneticoperators(2)Mutationoperator:ProducesoffspringfromasingleparentandproducessmallchangestothebitstringMutationisoftenperformedaftercrossoverhasbeenappliedAdditionaloperatorsSpecializingtotheparticularhypothesisrepresentationGeneralizeandspecializerulesinavarietyofdirectedways9.2.3FitnessFunctionandSelectionThefitnessfunctiondefinesthecriterionforrankingpotentialhypothesesIfthetaskistolearnclassificationrules,thenthefitnessfunctiontypicallyhasacomponentthatscorestheclassificationaccuracy(complexityorgenerality)oftheruleoverasetofprovidedtrainingexamples.AprobabilitymethodforselectingahypothesisFitnessproportionateselection(roulette
whellselection),theprobabilityofselectingahisgibvenbytheratioofitsfitnesstothefitnessofothermemberofthecurrentpopulationTournamentselectionRankselection9.3AnIllustrativeExampleAGAcanbeviewedasageneraloptimizationmethodthatsearchesalargespaceofcandidateobjectsseekingonethatperformsbestaccordingtothefitnessfunctionAlthoughnotguaranteedtofindanoptimalobject,GAsoftensucceedinfindinganobjectwithhighfitnessApplicationofGACircuitlayoutJob-shopschedulingFunction-approximationChoosingthenetworktopologyfoeANNGabilSystemDevelopedbyDejongetal.1993.GabilusesaGAtolearnbooleanconceptsThoseconceptsrepresentedbyadisjunctivesetofpropositionrulesItsgeneralizationaccuracyisroughlycomparabletootheralgorithmssuchasC4.5andtherulelearningsystemThealgorithmusedbyGabilisthealgorithmdescribedinTable9.1.Gabilsystem(2)GabilImplementationRepresentation:eachhinGabilcorrespondstoadisjunctivesetofpropositionalrules,encodedasdescribedinsection9.2.1Geneticoperators:MutationoperatorThecrossoveroperator:anextensiontothetwo-pointcrossoveroperatorFitnessfunction:thefitnessofeachhypothesizedrulesetisbasedonitsclassificationaccuracyoverthetrainingdata,Fitness(h)=(correct(h))29.3.1ExtensionsTheadditionoftwonewgeneticoperatorsAddAlternativeDropConditionApplicationMethodTwooperatorswereapplywiththesameprobabilitytoeachhypothesisinthepopulationThebit-stringforhwasextendedtoincludetwobitsthatdeterminewhichoftheseoperatorsmaybeappliedtotheh9.4HypothesisSpaceSearchGAsemployarandomizedbeamsearchmethodtoseekamaximallyfithypothesisThegradientdescentsearchmovessmoothlyfromonehtoanewhthatisverysimilarTheGAcanmovemuchmoreabruptlyTheGAsearchisthereforelesslikelytofallintothesamekindoflocalminimaOnepracticaldifficultyinGAapplicationsistheproblemofcrowding.crowdingisaphenomenoninwhichsomeindividualthatismorehighlyfitthanothersquicklyreproduces,sothatcopiesofthisindividualandverysimilarindividualstakeoveralargefractionofthepopulationItreducesthediversityofthepopulation,therebyslowingfurtherprogressbytheGAHypothesisspacesearch(2)StrategiesforreducingcrowdingAltertheselectionfunction,usingtournamentselectionorrankselectioninplaceoffitnessproportionateroulettewheelselectionFitnesssharing,thefitnessofanindividualisreducedbythepresenceofother,similarindividualsRestrictthekindsofindividualsallowedtorecombinetoformoffspringAllowingonlythemostsimilarindividualstorecombineSpatiallydistributeindividualsandallowonlynearbyindividualstorecombine9.4.1PopulationEvolutionandtheSchemaTheoremTheschematheoremprovidesawaytomathematicallycharacterizetheevolutionovertimeofthepopulationwithinaGA(Holland1975Aschemaisanystringcomposedof0s,1sand*sTheschematheoremcharacterizestheevolutionofthepopulationwithinaGAintermsofthenumberofinstancesrepresentingeachschemaLetm(s,t)denotethenumberofinstancesofschemasinthepopulationattimetTheschematheoremdescribestheexpectedvalueofm(s,t+1)intermsofm(s,t)andotherpropertiesoftheschema,population,andGAalgorithmparametersPopulationEvolutionandtheSchemaTheorem(2)TheevolutionofthepopulationintheGAdependsontheselectionstep,therecombinationstep,andthemutationstepnotations:f(h):fitnessofhn:totalnumberofindividualstheaveragefitnessofallindividualstheaveragefitneeofinstancesofschemasattimetindicatethehisbotharepresentativeofschemaandamemberofthepopulationattimetPopulationEvolutionandtheSchemaTheorem(3)CalculatingE(m(s,t+1))usingtheprobabilitydistributionforselectionEquation9.3statesthattheexpectednumberofinstancesofschemasatt+1isproportionaltotheaveragefitness,andinverselyproportionaltoPopulationEvolutionandtheSchemaTheorem(4)Consideringthecrossoverstepandmutationsteps(consideringthenegativeinfluenceofgeneticoperatorsandonlythecaseofsingle-pointcrossover)
Schematheoremisincompleteisthatitfailstoconsiderthepositiveeffectsofcrossoverandmutation9.5GENETICPRPGRAMMINGGPisaformofevolutionarycomputationinwhichtheindividualsarecomputerprogramsratherthanbitstringsProgramsaretypicallyrepresentedbytreescorrespondingtotheparsetreeoftheprogram,eachfunctioncallisanode,theargumentstothefunctionaregivenbydescendantnodesGPmaintainsapopulationofindividuals,oneachiteration,itproduceanewgenerationofindividualsusingselection,crossover,andmutationThefitnessofanindividualisdeterminedbyexecutingtheprogramonasetoftrainingdataCrossoveroperationsareperformedbyreplacingarandomlychosensubtreeofoneparentprogrambyasuntreefromtheotherparentprogram9.5.2IllustrativeExampleLearninganalgorithmforstackingtheblocks(fig9-3)(Koza1992)DevelopageneralalgorithmforstackingtheblocksintoasinglestackthatspellsawordindependentoftheinitialconfigurationoftheblocksTheactionsavailableallowmovingonlyasingleblockatatime,thetopblockcanbemovedtothetablesurface,orablockonthetablesurfacecanbemovedtothetopofthestackTheprimitivefunctionsforthistaskinclude3terminalarguments:CS(currentstack)TB(topcorrectblock)NN(nextnecessary),9.5.2IllustrativeExample(2)OtherprimitiveintheprogramlanguageMSx:movetostackMTx:movetotableEQxy:equalNOTx:returnTifx=F,returnF,ifx=TDUxy:dountilKozaprovided166trainingsamples,thefitnessofanygivenprogramwastakentobenthenumberoftheseexamplessolvedbythealgorithmThepopulationwasasetof300randomprograms,after10generations,thesystemfindaprogramwhichsolveall166problems
(EQ(DU(MTCS)(NOTCS))(DU(MSNN)(NOTNN)))9.5.3RemarksongeneticProgrammingGPextendsGAtotheevolutionofcompletecomputerprograms.DespiteofthehugesizeofH,GPhasbeendemonstratedtoproduceintriguingresultsinanumberofapplicationsGPhasbeenusedinseveralmorecomplextasksDesigningelectronicfiltercircuitsClassifyingsegmentsofproteinmoleculesInmostcases,theperformanceofGPdependsoncruciallyonthechoiceofrepresentationandonthechoiceoffitnessfunction.9.6ModelsofEvolutionandLearningOneinterestingquestionregardingevolutionarysystem:whatistherelationshipbetweenlearningduringthelifetimeofasingleindividual,andthelongertimeframespecies-levellearningaffordedbyevolution?LamarckianEvolutionEvolutionovermanygenerationswasdirectlyinfluencedbytheexperiencesofindividualorganismsduringtheirlifetimeCurrentscientificevidenceoverwhelminglycontradictsLamarck’smodelRecentcomputerstudieshaveshownthatLamackianprocesscansometimesimprovetheeffectivenessofcomputerizedgeneticalgorithmsModelsofEvolutionandLearning(2)BaldwinEffectIndividuallearningcanalterthecourseofevolutionItisbasedonthefollowingobservationsIfaspeciesisevolvinginachangingenvironment,therewillbeevolutionarypressuretofavorindividualswiththecapabilitytolearnduringtheirlifetime.Thoseindividualswhoareabletolearnmanytraitswillrelylessstronglyontheirgeneticcodeto“hard-wire”traits.Providesanindirectmechanismforindividuallearningtopositivelyimpacttherateofevolutionaryprogress.ModelsofEvolutionAndLea
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《表面积的变化》长方体和正方体表面积的变化
- 校本研修年度研修总结5篇
- 河南教育课件教学课件
- 龙年春节联欢晚会的主持词(31篇)
- 实验室装修预定金协议
- 超市装修项目清单
- 马铃薯加工原料采购运输
- 摄影棚装修委托协议书
- 展览馆办公区装修协议
- 木材加工厂自卸车运输合同
- FDS火灾模拟技术
- 2022年中国行业云深度研究报告(上):未来五年传统行业云市场增速将超越互联网行业云-2023.03
- 洗胃术 (急诊科)
- 降本增效一体化施工方案
- 援藏干部座谈会讲话
- 二年级数学上册说课稿-用6-9的乘法口诀求商练习-北京版
- 测绘安全生产知识培训课件
- GHS化学品(含危险品)标签标志与象形符号
- 安全生产工作需要新理念现代安全生产管理新理念和新方法
- 社会主义发展史知到章节答案智慧树2023年齐鲁师范学院
- 2022年燃气管网运行工理论考试题集及答案
评论
0/150
提交评论