遺傳算法英文資料

Whatisageneticalgorithm?

Methodsofrepresentation

Methodsofselection

Methodsofchange

Otherproblem-solvingtechniques

Conciselystated,ageneticalgorithm(orGAforshort)isaprogrammingtechniquethatmimicsbiologicalevolutionasaproblem-solvingstrategy.Givenaspecificproblemtosolve,theinputtotheGAisasetofpotentialsolutionstothatproblem,encodedinsomefashion,andametriccalledfitnessfunctionthatallowseachcandidatetobequantitativelyevaluated.Thesecandidatesmaybesolutionsalreadyknowntowork,withtheaimoftheGAbeingtoimprovethem,butmoreoftentheyaregeneratedatrandom.

TheGAthenevaluateseachcandidateaccordingtothefitnessfunction.Inapoolofrandomlygeneratedcandidates,ofcourse,mostwillnotworkatall,andthesewillbedeleted.However,purelybychance,afewmayholdpromise-theymayshowactivity,evenifonlyweakandimperfectactivity,towardsolvingtheproblem.

Thesepromisingcandidatesarekeptandallowedtoreproduce.Multiplecopiesaremadeofthem,butthecopiesarenotperfect;randomchangesareintroducedduringthecopyingprocess.Thesedigitaloffspringthengoontothenextgeneration,forminganewpoolofcandidatesolutions,andaresubjectedtoasecondroundoffitnessevaluation.Thosecandidatesolutionswhichwereworsened,ormadenobetter,bythechangestotheircodeareagaindeleted;butagain,purelybychance,therandomvariationsintroducedintothepopulationmayhaveimprovedsomeindividuals,makingthemintobetter,morecompleteormoreefficientsolutionstotheproblemathand.Againthesewinningindividualsareselectedandcopiedoverintothenextgenerationwithrandomchanges,andtheprocessrepeats.Theexpectationisthattheaveragefitnessofthepopulationwillincreaseeachround,andsobyrepeatingthisprocessforhundredsorthousandsofrounds,verygoodsolutionstotheproblemcanbediscovered.

Asastonishingandcounterintuitiveasitmayseemtosome,geneticalgorithmshaveproventobeanenormouslypowerfulandsuccessfulproblem-solvingstrategy,dramaticallydemonstratingthepowerofevolutionaryprinciples.Geneticalgorithmshavebeenusedinawidevarietyoffieldstoevolvesolutionstoproblemsasdifficultasormoredifficultthanthosefacedbyhumandesigners.Moreover,thesolutionstheycomeupwithareoftenmoreefficient,moreelegant,ormorecomplexthananythingcomparableahumanengineerwouldproduce.Insomecases,geneticalgorithmshavecomeupwithsolutionsthatbaffletheprogrammerswhowrotethealgorithmsinthefirstplace!

Methodsofrepresentation

Beforeageneticalgorithmcanbeputtoworkonanyproblem,amethodisneededtoencodepotentialsolutionstothatprobleminaformthatacomputeicanprocess.Onecommonapproachistoencodesolutionsasbinarystrings:sequencesof1,sand0's,wherethedigitateachpositionrepresentsthevalueofsomeaspectofthesolution.Another,similarapproachistoencodesolutionsasarraysofintegersordecimalnumbers,witheachpositionagainrepresentingsomeparticularaspectofthesolution.Thisapproachallowsforgreaterprecisionandcomplexitythanthecomparativelyrestrictedmethodofusingbinarynumbersonlyandoften"isintuitivelyclosertotheproblemspace"(FlemingandPurshouse2002,p.1228).

Thistechniquewasused,forexample,intheworkofSteffenSchulze-Kremer,whowroteageneticalgorithmtopredictthethree-dimensionalstructureofaproteinbasedonthesequenceofaminoacidsthatgointoit(Mitchell1996,p.62).Schulze-Kremer'sGAusedreal-valuednumberstorepresenttheso-called"torsionangles"betweenthepeptidebondsthatconnectaminoacids.(Aproteinismadeupofasequenceofbasicbuildingblockscalledaminoacids,whicharejoinedtogetherlikethelinksinachain.Oncealltheaminoacidsarelinked,theproteinfoldsupintoacomplexthree-dimensionalshapebasedonwhichaminoacidsattracteachotherandwhichonesrepeleachother.Theshapeofaproteindeterminesitsfunction.)Geneticalgorithmsfortrainingneuralnetworksoftenusethismethodofencodingalso.

AthirdapproachistorepresentindividualsinaGAasstringsofletters,whereeachletteragainstandsforaspecificaspectofthesolution.OneexampleofthistechniqueisHiroakiKitano's"grammaticalencoding"approach,whereaGAwasputtothetaskofevolvingasimplesetofrulescalledacontext-freegrammarthatwasinturnusedtogenerateneuralnetworksforavarietyofproblems(Mitchell1996,p.74).

Thevirtueofallthreeofthesemethodsisthattheymakeiteasytodefineoperatorsthatcausetherandomchangesintheselectedcandidates:flipa0toa1orviceversa,addorsubtractfromthevalueofanumberbyarandomlychosenamount,orchangeonelettertoanother.(SeethesectiononMethodsofchangeformoredetailaboutthegeneticoperators.)Anotherstrategy,developedprincipallybyJohnKozaofStanfordUniversityandcalledgeneticprogramming,representsprogramsasbranchingdatastructurescalledtreesKozaetal.2003p.35).Inthisapproach,randomchangescanbebroughtaboutbychangingtheoperatororalteringthevalueatagivennodeinthetree,orreplacingonesubtreewithanother.

Figure1:Threesimpleprogramtreesofthekindnormallyusedingeneticprogramming.Themathematicalexpressionthateachonerepresentsisgivenunderneath.

Itisimportanttonotethatevolutionaryalgorithmsdonotneedtorepresentcandidatesolutionsasdatastringsoffixedlength.Somedorepresenttheminthisway,butothersdonot;forexample,Kitano'sgrammaticalencodingdiscussedabovecanbeefficientlyscaledtocreatelargeandcomplexneuralnetworks,andKoza'sgeneticprogrammingtreescangrowarbitrarilylargeasnecessarytosolvewhateverproblemtheyareappliedto.

Methodsofselection

Therearemanydifferenttechniqueswhichageneticalgorithmcanusetoselecttheindividualstobecopiedoverintothenextgeneration,butlistedbelowaresomeofthemostcommonmethods.

Someofthesemethodsaremutuallyexclusive,butotherscanbeandoftenareusedincombination.

ElitistselectionThemostfitmembersofeachgenerationareguaranteedtobeselected.(MostGAsdonotusepureelitism,butinsteaduseamodifiedformwherethesinglebest,orafewofthebest,individualsfromeachgenerationarecopiedintothenextgenerationjustincasenothingbetterturnsup.)

Fitness-proportionateselectionMorefitindividualsaremorelikely,butnotcertain,tobeselected.

Roulette-wheelselectionAformoffitness-proportionateselectioninwhichthechanceofanindividual'sbeingselectedisproportionaltotheamountbywhichitsfitnessisgreaterorlessthanitscompetitors'fitness.(Conceptually,thiscanberepresentedasagameofroulette-eachindividualgetsasliceofthewheel,butmorefitonesgetlargerslicesthanlessfitones.Thewheelisthenspun,andwhicheverindividual"owns"thesectiononwhichitlandseachtimeischosen.)

ScalingselectionAstheaveragefitnessofthepopulationincreases,thestrengthoftheselectivepressurealsoincreasesandthefitnessfunctionbecomesmorediscriminating.Thismethodcanbehelpfulinmakingthebestselectionlateronwhenallindividualshaverelativelyhighfitnessandonlysmalldifferencesinfitnessdistinguishonefromanother.

TournamentselectionSubgroupsofindividualsarechosenfromthelargerpopulation,andmembersofeachsubgroupcompeteagainsteachother.Onlyoneindividualfromeachsubgroupischosentoreproduce.

Rankselection：Eachindividualinthepopulationisassignedanumericalrankbasedonfitness,andselectionisbasedonthisrankingratherthanabsolutedifferencesinfitness.Theadvantageofthismethodisthatitcanpreventveryfitindividualsfromgainingdominanceearlyattheexpenseoflessfitones,whichwouldreducethepopulation'sgeneticdiversityandmighthinderattemptstofindanacceptablesolution.

GenerationalselectionTheoffspringoftheindividualsselectedfromeachgenerationbecometheentirenextgeneration.Noindividualsareretainedbetweengenerations.

Steady-stateselectionTheoffspringoftheindividualsselectedfromeachgenerationgobackintothepre-existinggenepool,replacingsomeofthelessfitmembersofthepreviousgeneration.Someindividualsareretainedbetweengenerations.

HierarchicalselectionIndividualsgothroughmultipleroundsofselectioneachgeneration.Lower-levelevaluationsarefasterandlessdiscriminating,whilethosethatsurvivetohigherlevelsareevaluatedmorerigorously.Theadvantageofthismethodisthatitreducesoverallcomputationtimebyusingfaster,lessselectiveevaluationtoweedoutthemajorityofindividualsthatshowlittleornopromise,andonlysubjectingthosewhosurvivethisinitialtesttomorerigorousandmorecomputationallyexpensivefitnessevaluation.

Methodsofchange

Onceselectionhaschosenfitindividuals,theymustberandomlyalteredinhopesofimprovingtheirfitnessforthenextgeneration.Therearetwobasicstrategiestoaccomplishthis.ThefirstandsimplestiscalledmutationJustasmutationinlivingthingschangesonegenetoanother,somutationinageneticalgorithmcausessmallalterationsatsinglepointsinanindividual'scode.

Thesecondmethodiscalledcrossoverandentailschoosingtwoindividualstoswapsegmentsoftheircode,producingartificial"offspring"thatarecombinationsoftheirparents.Thisprocessisintendedtosimulatetheanalogousprocessofrecombinationthatoccurstochromosomesduringsexualreproduction.Commonformsofcrossoverincludesingle-pointcrossoverinwhichapointofexchangeissetatarandomlocationinthetwoindividuals'genomes,ancbneindividualcontributesallitscodefrombeforethatpointandtheothercontributesallitscodefromafterthatpointtoproduceanoffspring,anduniformcrossoverinwhichthevalueatanygivenlocationintheoffspring'sgenomeiseitherthevalueofoneparent'sgenomeatthatlocationorthevalueoftheotherparent'sgenomeatthatlocation,chosenwith50/50probability.

Figure2:Crossoverandmutation.Theabovediagramsillustratetheeffectofeachofthesegeneticoperatorsonindividualsinapopulationof8-bitstrings.Theupperdiagramshowstwoindividualsundergoingsingle-pointcrossover;thepointofexchangeissetbetweenthefifthandsixthpositionsinthegenome,producinganewindividualthatisahybridofitsprogenitors.Theseconddiagramshowsanindividualundergoingmutationatposition4,changingthe0atthatpositioninitsgenometoa1.

Otherproblem-solvingtechniques

Withtheriseofartificiallifecomputingandthedevelopmentofheuristicmethods,othercomputerizedproblem-solvingtechniqueshaveemergedthatareinsomewayssimilartogeneticalgorithms.Thissectionexplainssomeofthesetechniques,inwhatwaystheyresembleGAsandinwhatwaystheydiffer.

NeuralnetworksAneuralnetwork,orneuralnetforshort,isaproblem-solvingmethodbasedonacomputermodelofhowneuronsareconnectedinthebrain.Aneuralnetworkconsistsoflayersofprocessingunitscallednodesjoinedbydirectionallinks:oneinputlayer,oneoutputlayer,andzeroormorehiddenlayersinbetween.Aninitialpatternofinputispresentedtotheinputlayeroftheneuralnetwork,andnodesthatarestimulatedthentransmitasignaltothenodesofthenextlayertowhichtheyareconnected.Ifthesumofalltheinputsenteringoneofthesevirtualneuronsishigherthanthatneuron'sso-calledactivationthreshold,thatneuronitselfactivates,andpassesonitsownsignaltoneuronsinthenextlayer.Thepatternofactivationthereforespreadsforwarduntilitreachestheoutputlayerandistherereturnedasasolutiontothepresentedinput.Justasinthenervoussystemofbiologicalorganisms,neuralnetworkslearnandfine-tunetheirperformanceovertimeviarepeatedroundsofadjustingtheirthresholdsuntiltheactualoutputmatchesthedesiredoutputforanygiveninput.Thisprocesscanbesupervisedbyahumanexperimenterormayrunautomaticallyusingalearningalgorithm(Mitchell1996,p.52).Geneticalgorithmshavebeenusedbothtobuildandtotrainneuralnetworks.

Inputlayer

Hiddenlayer

Outputlayer

Figure3:Asimplefeedforwardneuralnetwork,withoneinputlayerconsistingoffourneurons,onehiddenlayerconsistingofthreeneurons,andoneoutputlayerconsistingoffourneurons.Thenumberoneachneuronrepresentsitsactivationthreshold:itwillonlyfireifitreceivesatleastthatmanyinputs.Thediagramshowstheneuralnetworkbeingpresentedwithaninputstringandshowshowactivationspreadsforwardthroughthenetworktoproduceanoutput.

Hill-climbingSimilartogeneticalgorithms,thoughmoresystematicandlessrandom,ahill-climbingalgorithmbeginswithoneinitialsolutiontotheproblemathand,usuallychosenatrandom.Thestringisthenmutated,andifthemutationresultsinhigherfitnessforthenewsolutionthanforthepreviousone,thenewsolutioniskept;otherwise,thecurrentsolutionisretained.Thealgorithmisthenrepeateduntilnomutationcanbefoundthatcausesanincreaseinthecurrentsolution'sfitness,andthissolutionisreturnedastheresult(Kozaetal.2003,p.59).(Tounderstandwherethenameofthistechniquecomesfrom,imaginethatthespaceofallpossiblesolutionstoagivenproblemisrepresentedasathree-dimensionalcontourlandscape.Agivensetofcoordinatesonthatlandscaperepresentsoneparticularsolution.Thosesolutionsthatarebetterarehigherinaltitude,forminghillsandpeaks;thosethatareworsearelowerinaltitude,formingvalleys.A"hill-climber"isthenanalgorithmthatstartsoutatagivenpointonthelandscapeandmovesinexorablyuphill.)Hill-climbingiswhatisknownasagreedyalgorithm,meaningitalwaysmakesthebestchoiceavailableateachstepinthehopethattheoverallbestresultcanbeachievedthisway.Bycontrast,methodssuchasgeneticalgorithmsandsimulatedannealing,discussedbelow,arenotgreedy;thesemethodssometimesmakesuboptimalchoicesinthehopesthattheywillleadtobettersolutionslateron.

SimulatedannealingAnotheroptimizationtechniquesimilartoevolutionaryalgorithmsis