Lecture 36 GENETIC ALGORITHM (1)

Intro.ANN&FuzzySystemsLecture36GENETICALGORITHM(1)Intro.ANN&FuzzySystems(C)2001byYuHenHu2Outline•WhatisaGeneticAlgorithm?–AnExample•ComponentsofaGeneticAlgorithm–Representationofgene–SelectionCriteria–ReproductionRules•Cross-over•Mutation•PotentialApplicationsofGA.Intro.ANN&FuzzySystems(C)2001byYuHenHu3WhatisaGeneticAlgorithm?•Geneticalgorithmsaresearchalgorithmsbasedonthemechanicsofnaturalselectionandnaturalgenetics.•Theycombinesurvivalofthefittestamongstringstructureswithastructuredyetrandomizedinformationexchangetoformasearchalgorithmwithsomeoftheinnovativeflairofhumansearch.•Ineverygeneration,anewsetofartificialcreatures(strings)iscreatedusingbitsandpiecesofthefittestoftheold;anoccasionalnewpartistriedforgoodmeasure.•Whilerandomized,geneticalgorithmsarenosimplerandomwalk.Theyefficientlyexploithistoricalinformationtospeculateonnewsearchpointswithexpectedimprovedperformance.-GeneticAlgorithmsinSearch,Optimization&MachineLearningbyDavidE.GoldbergIntro.ANN&FuzzySystems(C)2001byYuHenHu4WhatisaGeneticAlgorithm?RepeatEvaluatecurrentcandidatesDevelopnewcandidatesviareproductionwithmodificationwhichreplaceleast-fitformercandidatesUntilsatisfiedThreeComponents:•Representationofcandidatesolutions(states)-Genes•SelectioncriteriatoevaluatetheFITNESSofeachgene•Reproductionrulestogeneratenewcandidatesolutions(genes)basedonderivationfromcurrentsolutions(cross-overbreeding)anddirectedrandomsearch(mutation).Intro.ANN&FuzzySystems(C)2001byYuHenHu5AGAEXAMPLEObjective-tofindabinarystringoflength5with41’s.Representation:binarystringoflength5Solutionspace:5feasiblesolutionsamong25solutions.Firststep:randomlygenerate5candidates,andevaluatetheirfitnessusingthenumberof1ísinthestringasacriterion.00010(eval:1)10001(eval:2)10000(eval:1)01011(eval:3)10010(eval:2)Populationevaluationaverage:1.8Intro.ANN&FuzzySystems(C)2001byYuHenHu6GAEXAMPLE(2)SecondStep:generatenewchromosomesModificationmethods:(a)crossoverduringwhichtwogenesinterchangetheirchromosomes;(b)inversionbyflippingsub-stringofthesamegene;and(c)mutationbyrandomlyperturbation.Selectionistdistribution:Geneswithhigherfitnessvaluehashigherprobabilitytoproduceoff-springs!100010(eval:1)210001(eval:2)310001(repeat)410000(eval:1)501011(eval:3)601011(repeat)701011(repeat)810010(eval:2)910010(repeat)Selectpairs(indicesfromselectionistdistribution):1&4@1,4&5@4,9&7@3,8&6@1,7&[e-mail]&FuzzySystems(C)2001byYuHenHu7GENERATENEWGENESForexample,crossover1(00010)and4(10000)atposition1yields00000whichevaluates0!Otherresultsare:4+5@4=10001(eval:2)9+7@3=10011(eval:3)8+6@1=11011(eval:4)7+5@1=01011(eval:3)Newpopulationevaluationaverage:2.4Since8+6producesafeasiblesolution,theiterationterminates,andtheGAalgorithmsuccessfullyfoundasolution.Intro.ANN&FuzzySystems(C)2001byYuHenHu8GAAlgorithmOverview•GAisarandomsearchalgorithmwhichkeepsapoolofcandidatesolutions(genepool).•Eachsolutionisencodedinabinarystringcalledachromosomewitheachbitbeingagene.•Evaluatethefitnessofasolutionusingaselectioncriteria.•Generatenewchromosomesbyreproductionrules,includingcross-over(mating),inversion,andmutation.•Annihilateinferior(accordingtotheresultofevaluationusingtheselectioncriteria)genes,tomakeroomfornewgenes.•Addingnewgeneswithhighfitnessvaluesintogenepool.•Evaluateterminationcriteria.Ifnotyetsatisfied,continuethesearchprocess.Intro.ANN&FuzzySystems(C)2001byYuHenHu9GENETICALGORITHMCYCLEReplacementGenePool(Chromosomes)MatingPool(Parents)Subpopulation(Off-springs)ObjectiveFunctionfitnessSelectionReproductionfitnessphenotypephenotypeIntro.ANN&FuzzySystems(C)2001byYuHenHu10GENEREPRESENTATIONEncodingisakeytotheGA:Feature(knowledge)representationEachchromosomeisavectorofgenesrepresentingatrialsolution.Eachgenecanbeabinarynumber,arealnumberorothersymbols.Bit-stringencodingwhereeachgeneisabinarynumberisthemostpopularapproach.Otherapproaches:realnumberrepresentation,order-basedrepresentation(goodforgraphcoloringproblem),embeddedlist(forfactoryscheduling),variableelementlists(IClayout),andevenLISPS-expressions.Intro.ANN&FuzzySystems(C)2001byYuHenHu11SELECTION(FITNESS)CRITERIA1.Windowing:Letv(i)=objectivevalueofchromosomei,andc:aconstant,thenthefitnessofchromosomeicanbefoundas:f(i)=c[v(i)v(w)]wherev(w)v(i)foralliw.2.LinearNormalization:Rankobjectivevaluesofchromosomes.Assignthebestperformedchromosomewithfitnessvaluef(best).Assignremainingi-thchromosomewithfitnessvaluef(i)=f(best)(i1)dIntro.ANN&FuzzySystems(C)2001byYuHenHu12PARENTSELECTION•Emulatethesurvival-of-the-fittestmechanisminnature!•InaProportionateschemewherethegrowthrateofachromosomewithfitnessvaluef(x,t)isdefinedasf(x,t)/F(t)whereF(t)istheaveragefitnessofthepopulation.Animplementationisasfollows:RouletteWheelParentSelectionAlgorithm1.Sumthefitnessofallpopulationmembers;namedastotalfitness,n.2.Generatearandomnumberbetween0andn.ReturnthefirstpopulationmemberwhosefitnessaddedtothefitnessoftheprecedingpopulationmembersisgreaterthanorequaltonIntro.ANN&FuzzySystems(C)2001byYuHenHu13CROSS-OVERSinglepointcrossover:Multi-pointcrossover:parentsOffspringparentsOffsprin