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