A Generic Parallel Genetic Algorithm 通用并行遗传算法

-

PAGE

2

-

AGenericParallelGeneticAlgorithm

by

RoderickMurphy(B.E.)

AThesissubmittedto

TheUniversityofDublin

forthedegreeof

M.Sc.inHighPerformanceComputing

DepartmentofMathematics

UniversityofDublin

TrinityCollege

October2003

DECLARATION

Ideclarethat:

1. Thisworkhasnotbeensubmittedasanexerciseforadegreeatthisor anyotheruniversity.

2. Thisworkismyownexceptwherenotedinthetext.

3. Thelibraryshouldlendorcopythisworkuponrequest.

__________________________________

RoderickMurphy(October20th2003)

ABSTRACT

Geneticalgorithmshavebeenproventobebothanefficientandeffectivemeansofsolvingcertaintypesofsearchandoptimisationproblems.Thisprojectprovidesalibraryoffunctionsthatenableausertoimplementvariationsofcommonlyusedgeneticalgorithmoperators,includingfitnessfunctionscaling,selection,crossover,mutationandmigration,withwhichtheycansolvetheirspecifiedproblem.ThemainfunctionisparallelisedusingPthreads.Usingtheprisoners’dilemmaasanexampleproblem,resultsshowasignificantspeed-upcomparedwithapurelyserialimplementation.

ACKNOWLEDGEMENTS

FirstlyIwouldliketothankMrDermotFrostforhisguidanceandintroductiontothisextremelyinterestingtopic.IwouldalsoliketothankmyHPCclassfortheirpearlsofwisdomandtipsforusingthemanyusefulapplicationsthatmadethisprojectareality.InparticularIowemygratitudetoPaddyforthehourshespenthelpingmedebugmycodeandfindthenumeroustpyeosinthisthesis.AlsoDave,Rachel,MadeleineandBrianforthenumerouscupsofcoffeeandhelpfuldebateonawiderangeofbothusefulanduselesstopics.FinallyIwouldliketothankmyfamilyfortheirloveandsupportthroughouttheyear.

Contents

1.0. IntroductiontoGeneticAlgorithms

1.1. Introduction

1.2. SearchSpaces

1.3. ASimpleExample

1.4. ComparisonbetweenBiologicalandGATerminology

1.5. ApplicationsofGeneticAlgorithms

1.6. HoworwhydoGeneticAlgorithmswork?

2.0. GAOperatorsinFurtherDepth

2.1. Introduction

2.2. EncodingaProblem

2.3.0. Selection

2.3.1 FitnessProportionalSelection

2.3.2 RankSelection

2.3.3. TournamentSelection

2.4.0. FitnessScaling

2.4.1. LinearScaling

2.4.2. SigmaTruncation

2.3.3. PowerLawScaling

2.5. Elitism

2.6.0. Crossover

2.6.1. Single-pointcrossover

2.6.2. Multi-pointcrossover

2.6.3. ParameterizedUniformCrossover

2.7. Mutation

2.8. Inversion

2.9. ParameterValuesforGeneticAlgorithms

2.10. Conclusion

3.0. ParallelGeneticAlgorithmOperators

3.1. Introduction

3.2. MasterSlaveparallelGAprototype

3.3. Distributed,AsynchronousConcurrentparallelGA prototype

3.4. NetworkparallelGA

3.5. IslandModel

3.5. Conclusion

4.0. ImplementationofParallelGeneticAlgorithm

4.1. Introduction

4.2. ObjectiveValuefunction

4.3. ParallelGeneticAlgorithmFunction

4.4.0. ImplementationofMigrationOperators

4.4.1. WhatTechnologyWasUsed?

4.4.2. ThreadedImplementation

4.5. Conclusion

5.0. Results

5.1. Introduction

5.2.0. ThePrisonersDilemmausingParallelGA[MI96]

5.2.1. Encoding

5.2.2. GeneticAlgorithm

5.2.3. SerialImplementation

5.2.4. Results

5.3. Conclusion

6.0. ConclusionsandFutureDirections

6.1. Introduction

6.2. FutureDirections

6.3. Conclusion

References

1.0. IntroductiontoGeneticAlgorithms

1.1. Introduction

Goldberg[GO89]describesGeneticAlgorithmsas:searchproceduresbasedonthemechanicsofnaturalselectionandnaturalgenetics.I.e.theyaregeneralsearchandoptimisationalgorithmsthatusethetheoriesofevolutionasatooltosolveproblemsinscienceandengineering.Thisinvolvesevolvingapopulationofcandidatesolutionstotheparticularproblem,usingoperationsinspiredbynaturalgeneticvariationandnaturalselection.

GeneticAlgorithmsare'weak'optimisationmethods.Thatistheydonotusedomain-specificknowledgeintheirsearchprocedure.Forthisreasontheycanbeusedtosolveawiderangeofproblems.Thedisadvantage,ofcourse,isthattheymaynotperformaswellasalgorithmsdesignedspecificallytosolveagivenproblem.

Fromtheverybeginning,computerscientistshavethoughtofsystemsthatwouldmimiconeormoreattributesoflife.However,itwasn'tuntilthe1960sthatGeneticAlgorithms(GAs)wereformallydevelopedbyJohnHolland,alongwithhisstudentsandcolleaguesfromtheUniversityofMichigan.Holland’soriginalgoal,however,wasnottodesignalgorithmstosolvespecificproblems,asinotherevolutionaryprogramming,buttostudythephenomenonofadaptationasitoccursinnatureandtodevelopwaysinwhichthemechanismsofnaturaladaptationmightbeimportedintocomputersystems.

Holland’sGAisamethodofmovingfromonepopulationofchromosomes(stringsofonesandzeros)toanewpopulationusingakindofnaturalselection,togetherwiththegenetics-inspiredoperationsofcrossover,mutationandinversion.

Atypicalalgorithmmightconsistofthefollowing:

Anumberofrandomlychosenguessesofthesolutiontotheproblem–theinitialpopulation.

Ameansofcalculatinghowgoodorbadeachguessiswithinthepopulation–apopulationfitnessfunction.

Amethodformixingfragmentsofthebettersolutionstoformnewandonaverageevenbettersolutions–crossover.

Anoperatortoavoidpermanentlossof(andtointroducenew)diversitywithinthesolutions–mutation.

WiththesebeingthebasiccomponentsofmostGAsitcanbeseenthattheyareasimplemethodtosolveaspecificproblem.Thedownside,however,isthattherearemanydifferentwaysofperformingthesesteps.InthisdissertationIhaveattemptedtoprovideapackagethatgivestheuserachoiceofusingsomeofthemorecommonmethodstosolvetheirparticularproblem.

NotethatHolland’sinversionoperationisrarelyusedinGAstodaysinceitsbenefits,ifany,arenotwellestablished.

1.2. SearchSpaces

Formanysearchoroptimisationproblemsinscience,engineeringandelsewhere,thereareahugeoreveninfinitenumberofpossiblesolutions.Thismeansthatinmostcasesitisimpossibletocheckeachandeverypossiblesolutioninordertofindtheoptimumorrequiredone.Oneapproachistolimitthenumberofpossibilitiestowithinachosenrangewithacertainstepsizeordistancebetweeneachone.Thismethodisusedinallproblemssolvedusingacomputer,sinceafterallthereisalimittothegranularityatwhichadigitalcomputercanrepresentaproblem.Thesetofpossiblesolutionsiscalleda“searchspace”.

Associatedwiththeideaofasearchspaceistheconceptofa“fitnesslandscape”(definedbythebiologistSewellWrightin1931).Thefitnesslandscapeisameasureofthesuccess,orfitness,ofeachsolutionwithinthesearchspace.ItisthisfitnessthatisusedtodeterminewhichsolutionsoftheGApopulationgoforwardtoproducethenewsolutions.

Theselandscapescanhavesurprisinglycomplextopographies.Forasimpleproblemoftwovariables(adjustableparameters),thefitnesslandscapecanbeviewedasathree-dimensionalplotshowingthevariationofthefitnessforvaryinginputparameters.Thisplotcanhaveanumberofpeaks(maxima)andtroughs(minima).Thehighestpeakisusuallyreferredtoastheglobalmaximumorglobaloptimum.Thelesserpeaksarereferredtoaslocalmaximaorlocaloptima.Formanysearchproblemsthegoalistofindtheglobaloptimum.However,therearesituationswhereforexampleanypointaboveacertainthresholdwillsuffice.Inotherproblemsforexampleinaestheticdesign,alargenumberofhighlyfityetdistant,andthereforedistinct,solutionsmightberequired.

ThereisonecaveatwiththenotionoffitnesslandscapewithrespecttoGAs.Justasinthenaturalworld,thefitnessofanyorganismdependsontheotherorganismsarounditandnotjustonitssurroundingsalone.ThismeansthatthefitnesslandscapeofmanytypesofGAsisinaconstantstateofchange.

IngeneralGAsattempttofindthehighestpeakinthefitnesslandscapeofagivenproblem.Theydothisusingacombinationofexploitationandexploration.Thatis,whenthealgorithmhasfoundanumberofgoodcandidatesolutionsitexploitsthembycombiningdifferentpartsofeachsolutiontoformnewcandidatesolutions.Thisprocessisknownascrossover.GAsalsoexplorethefitnesslandscapethroughthecreationofnewcandidatesolutionsbyrandomlychangingpartsofoldsolutions.Thisprocessisknownasmutation.

1.3. ASimpleExample

InordertoclarifyhowGAsworkIwillpresentasimpleexample[fromMI96].Firstlygivenaspecificproblemwemustchooseameansofencodingeachsolution.Themostcommonapproachistorepresenteachsolutionasabinarystringoflengthlbits.

Westartbyrandomlygeneratingnsuchstrings.Thesearethecandidatesolutionstotheproblem.

Bydecodingeachstringtosomevaluex,calculateitsfitness,f(x).Repeatthefollowingstepsuntilnoffspring(newpopulationmembers)havebeencreated.

Select,withreplacement(i.e.withthepossibilityofselectingthemagain),twoparentsfromthepopulationwithprobabilityproportionaltotheirfitness.

Withprobabilitypc(“crossoverprobability”)swapthebitsofthepairbeforesomerandomlychosenpointtoproducetwooffspring.

Withprobabilitypm(“mutationprobability”)changethevalueofindividualbitsoftheoffspringstring.

Ifthenumberofpopulationmembersisoddoneoftheoffspringcanbediscarded.

Replacetheoldpopulationwiththenoffspring.Calculatethefitnessofthenewmembersandstarttheprocessagain.

Eachiterationofthisprocessiscalledageneration.Fiftyto100generationsaretypicallycarriedouttosolveaproblemusingaGAandtheentiresetofgenerationsiscalledarun.Thefittestmemberovertheentirerunistypicallytakenastherequiredsolution.

Theareanumberofdetailstobefilledinwithregardtoeachstepofthealgorithmaswellasthevaluessuchasthenumberofmembersinthepopulationandtheprobabilitiesofcrossoverandmutation.Thesedetailswillbedealtwithinthenextchapter.

1.4. ComparisonbetweenBiologicalandGATerminology

NotsurprisinglymuchofthelanguageusedbytheGAcommunityhasitsoriginsinthatusedbybiologists.Someoftheanalogiesaresomewhatstrained,sinceGAsaregenerallygreatlysimplifiedcomparedwiththerealworldgeneticprocesses.

Alllivingorganismsconsistofcellswitheachcellcontainingthesamesetofoneormorechromosomes,orstringsofDNAthatserveas“ablueprint”forthatindividualorganism.Thebinary(orother)stringusedintheGAsdescribedabovecanbeconsideredtobeachromosome,butsinceonlyindividualswithasinglestringareconsideredinmostGAs,thechromosomeisalsothegenotype(Thegenotypeisthenamegiventothetotalnumberofchromosomesofanorganism,forexample,thehumangenotypeiscomprisedof23pairsofchromosomes).

Eachchromosomecanbesubdividedintogenes,eachofwhich,roughlyspeaking,encodeaparticulartraitintheorganism(e.g.eyecolour).Eachofthepossiblevaluesagenecantakeoniscalledanallele(e.g.blue,green,brownorhazel).Thepositionofageneinthechromosomeiscalleditslocus.

InGAterminology,ifweconsideramulti-variableproblem,agenecanbeconsideredasthebitsthatencodeaparticularparameterandanallele,anallowablevaluethatparametercanhave.

Theorganismorphenotypeistheresultproducedbytheexpressionofthegenotypewithinitsenvironment.InGAsthiswillbeaparticularsetofunknownparameters,oranindividualsolutionvector.

Organisms,suchashumans,whosechromosomesarearrangedinpairs,arecalleddiploid.Organismswhosechromosomesareunpairedarecalledhaploid.Mostsexuallyreproducingspeciesarediploid,however,forsimplicitymostGAsonlyconsiderunpairedchromosomes.

Innaturemutationoccurswhensinglenucleotides(elementarymoleculesofDNA)getchangedwhenbeingcopiedfromparenttooffspring.InGAsmutationconsistsofflippingbinarydigitsatarandomlychosenlocusinthechromosome.

1.5. ApplicationsofGeneticAlgorithms

Thelistsoffieldsandtypesofproblemstowhichgeneticalgorithmshavebeensuccessfullyappliedareevergrowing.Thefollowingarejustafewexamples:

Optimisationtasks:includingnumericaloptimisationandsuchcombinatorialoptimisationtaskssuchascircuitlayoutandjobscheduling.

AutomaticProgramming:theyhavebeenusedtoevolvecomputerprogramsforspecifictasks,andtodesignothercomputationalstructuressuchasautomataandsortingnetworks.

Machinelearning:GAshavebeenusedforoperationssuchasclassificationandpredictiontasksinweatherforecastingorproteinstructure.Theyhavealsobeenusedtoevolveaspectsofparticularmachinelearningsystemssuchasweightsforneuralnetworks,rulesforlearningclassifiersystemsorsymbolicproductionsystemsandsensorsforrobots.

Economics:theyhavebeenusedtomodelprocessesofinnovation,thedevelopmentofbiddingstrategies,andtheemergenceofeconomicmarkets.

Immunesystems:theyhavebeenusedtomodelaspectsofnaturalimmunesystems.

Ecology:GAshavebeenusedtomodelbiologicalarmsraces,host-parasiteco-evolution,symbiosisandresourceflow.

Populationgenetics:ThiswasHolland’soriginalreasonforthedevelopmentofGAs.Ithasbeenusedtostudyquestionssuchas“Underwhatconditionswillagenebeevolutionarilyviableforrecombination?”

Socialsystems:GAshavebeenusedtostudytheevolutionarybehaviourofsocialsystems,suchasthatininsectcoloniesandmoregenerallytheevolutionofco-operationandcommunicationinmulti-agentsystems.

TheabovelistgivesaflavourofthekindofproblemsGAsarebeingusedtosolve,butitdoesnotconclusivelyanswerthequestionofthetypeofproblemstheyshouldbeusedtosolve.

ItwaspreviouslystatedthattheGAisa‘search’tool,butwhatexactlydoes‘search’mean?MelanieMitchell[MI96]describesthreeconceptsforthemeaningofthewordsearch:

Searchforstoreddata.Thisisthetraditionallyadoptedmeaningofasearch.Itinvolvessearchingalargedatabaseofrecordsforsomepieceofdata,likelookingforaphonenumberandaddressinaphonebook.

Searchforpathstogoals.Theobjectivehereistoefficientlyfindasetofactionsthatmoveasystemfromsomeinitialstatetosomeendgoal.Anexampleofthistypeofsearchisthe“Travellingsalesmanproblem”wherethegoalistofindtheshortestroundtripbetweenNcities,visitingeachcityonlyonce.

Searchforsolutions.Thisisamoregeneralclassofsearchthansearchforpathstogoals.Thismethodinvolvesefficientlyfindingthesolutiontoaproblemfromaverylargesetofcandidatesolutions.ItisthistypeofsearchmethodforwhichGAsaremostcommonlyused.

However,evenifaparticularproblemfallsintothethirdcategory,thisdoesn'tguaranteethataGAwillbeanefficientsearchalgorithm.UnfortunatelythereisnorigorousanswerastoexactlywhatkindofproblemsGAscansolveefficiently.Thereare,however,afewguidelinesthatresearchershavefoundtoholdtrue.TheefficiencyofaGAisrelatedtothesearchspaceoftheparticularproblem.Generally,aGAwillperformwellinproblemsthathavelargesearchspaceswhoselandscapesarenotsmoothorunimodal(i.e.,consistingofasinglesmoothhill).Thatisthatthesearchspacesarenotwellunderstoodorarenoisy.GAsalsoperformwellincaseswhereitismoreimportanttofindagoodsolutionratherthantheabsoluteoptimalsolution.

Obviouslyifthesearchspaceisnotlargeallsolutionscanbesearchedexhaustivelyandthebestonecanbefound,whereasaGAmightconvergeonalocaloptimumratherthantheglobaloptimum.Ifthesearchspaceissmoothorunimodalthenagradientascentalgorithm,suchassteepestascenthillclimbingwill,bemoreefficientthanaGA.Iftheproblemiswellunderstoodthensearchmethodsthatusedomain-specificinformationcanbedesignedtooutperformanygeneral-purposemethodsuchasaGA.Somesearchmethodsasinsimplehillclimbingmightbeleadastrayinthepresenceofnoise,butbecauseGAsworkbyaccumulatingfitnessstatisticsovermanygenerationstheywillperformwellinthepresenceofasmallamountofnoise.

However,takingtheaboveintoaccountthemethodwithwhichthecandidatesolutionsareencodedcanpredominantlydictatetheperformanceoftheGA.

1.6. HoworwhydoGeneticAlgorithmswork?

ThereisnoabsolutelyconclusiveexplanationastowhyGAsdoorevenshouldworksoeffectivelyassearchalgorithms.Thereare,however,anumberoftheories,themostwidelyaccepted(atleastuntilrecently)istheschematatheoryintroducedbyHolland[HO75]andpopularisedbyGoldberg[GO89].

Thetheoryofschemas(orschemata)isbasedontheideathatGAsworkbydiscovering,emphasising,andrecombininggood“buildingblocks”ofsolutions.Thatisthatgoodsolutionstendtobecomprisedofgoodcombinationsofbitvaluesthatconferhigherfitnessonthestringsinwhichtheyarepresent.

Soaschemaisasetofbitstringsthatcanbedescribedasatemplatemadeupofones,zerosandasterisks,whereasterisksrepresent“don’tcare”values.E.g.theschema:

H=1****1

representsthesetofall6-bitstringsthatbeginandendwith1.Thestrings100101and101011arecalledinstancesoftheschemaH.

Wecanestimatethefitnessofacertainschemaastheaveragefitnessofallinstancesofthatschemapresentinthepopulationatanytime,t(averagefitness=û(H,t)).Thuswecancalculatetheapproximateincreaseordecreaseofanygivenschemaoversuccessivegenerations.Aschemawhosefitnessisaboveaveragewillproduceanexponentiallyincreasingnumberofsamples.See[MI96]pp27-30foramoreindepthanalysis.

2.0. GAOperatorsinFurtherDepth

2.1. Introduction

Havingexplainedthebasicmechanismsofgeneticalgorithmsinthepreviouschapter,inthischapterIwillattempttoexplainsomeofthesubtlerdetailsofsomeGAoperatorsandalsodelveintotheimplementationofthesefunctions.

2.2. EncodingaProblem

PerhapsthemostimportantaspectforanyGAtobesuccessfulisthemannerinwhichthecandidatesolutionsareencoded.Althoughunnatural,HollandandhisstudentsconcentratedonbinaryencodingandmuchoftheGAworldhasfollowedsuit.Thusmostofthetheoryhasbeendevelopedaroundthistypeofencoding(althoughmuchofitcanbeextendedtonon-binaryapproaches),alsotheheuristicparametersettings,suchascrossoverandmutationrates,havebeendevelopedforGAsusingbinaryencoding.

Theproblemwithbinary-valuedencodingariseswhentherangeofrealworld(phenotype)valuesarenotapowerof2,somesortofclippingorscalingisrequiredsothatallbinarygeneorchromosomecombinationsrepresentsomerealworldvalue.

Themostfrequentlyusedmethodofbinaryencodingisstandardbinarycoding(000=0,001=1,101=5etc).Analternativemethod,however,isGraycoding.Thisissimilartobinaryencodingexceptthateachsuccessivenumberonlydiffersbyonebit.Thishastheadvantagethatsinglebitchangesduringmutationhavelessofaneffectonthefitnessofthestring.Itsdisadvantageisthatitslowsexploration,theprocessofcreatingnewsolutionsthatarenotmadefrompartsofothersolutions.

Amorenaturalformofencodingistousemulti-characterorrealvaluedalphabetstoformthechromosomes.UnderHolland'sschematheory,however,multicharacterencodedstringsshouldperformworsethanthoseencodedinbinary.However,thishasbeenshownnottobetrue.ItseemstheperformancedependsontheproblemandthedetailsoftheGA–thisposesadilemmasince,ingeneral,GAsareusedtosolveproblemsaboutwhichnotenoughisknowntosolvetheminotherwaysthus,thetypeofencodingthatwillworkbestcannotbeknown.Onewayaroundthisistousethesameencodingthatwasusedforasimilarproblem.

Anothermethodistreeencoding[MI96pp35-44].Thisallowssearchspacestobeopen-endedsincethereisnolimittothesizeofthetree.However,thiscanalsoleadtopitfalls–thetreescangrowtoolargeandbecomeuncontrolled,preventingtheformationofmorestructuredcandidatesolutions.

[MI96]proposeshavingtheencodingadaptitselfsothattheGAfindstheoptimummethod.Thisalsosolvestheproblemoffixed-lengthencodinglimitingthecomplexityofthecandidatesolutions.

2.3.0. Selection

Selectionistheoperationwherebycandidatesolutions(chromosomes)areselectedforreproduction.Ingeneraltheprobabilityofselectionshouldbeproportionaltothefitnessofthechromosomeinquestion.Tomakethispossiblewemustmakethefollowingassumptions:firstly,theremustbesomemeasurablequalityinordertosolvetheproblem-thefitness,secondly,thatthesolutioncanbefoundbymaximisingthefitness,andlastly,thatallfitnessvalues,bothgoodandbad,shouldbepositive.Withtheseconditionssatisfiedthereareanumberofdifferentwaysinwhichwecanselectmembersfromthepopulationforcrossover.Themostcommonoftheseisfitnessproportionateselection.

2.3.1. FitnessProportionateSelection

Iffiisthefitnessofindividualiandistheaveragepopulationfitness,whereNisthepopulationsize,thentheprobabilityofanindividualibeingselectedforcrossoveris:

Thiscanbeimplementedusingtheroulettewheelalgorithm.Asthenamesuggestsawheelisconstructedwithamarkerforeachmemberinthepopulation,thesizeofeachmarkerbeingproportionaltothatindividual'sfitness.Thusasthewheelisspuntheprobabilityoftheroulettelandingonthemarkerforindividualiispi.

Thisalgorithmcanbesimulatedusingthecumulativedistributionrepresentation-Arandomnumber,r,isgeneratedbetweenzeroandthesumofeachindividual'sfitnessvalue.Thefirstpopulationmemberwhosefitness,addedtothefitnessoftheprecedingmembers,isgreaterthanorequaltorisreturned.

Thereare,however,problemswiththismethodofselectionundercertainconditions.Considerthecasewhenacertainindividual'sfitnessisverymuchgreaterthattheaveragepopulationfitness.Underfitnessproportionateselectionthismemberwillbechosenmuchmorefrequentlythanothermembersinthepopulation.Thus,overafewgenerationsthegenepoolwillbecomesaturatedwithitsgenes.Ifthismember'sphenotyperesidesclosetoalocalmaximum,andnottheglobalmaximum,inthefitnesslandscapethentheGA,withoutthehelpofmutationorevenhyper-mutation(mutationwithaveryhighmutationrate-discussedlater),canbecomestuckatthislocalmaximum.Thisisknownasprematureconvergence.

Anotherproblemwithfitnessproportionateselectionisthatofstagnation.Thisgenerallyoccurstowardstheendofarun,althoughitcanhappenatanytime.Ifallindividualshavesimilarfitnesses,thenfitnessproportionateselectionwillimposelessselectionpressureandsowillbealmostaslikelytopickthefittestmembersastheleastfitmembers.

Boththeseproblemscanbesolvedusingfitnessscalingtechniques,whichwillbediscussedin§2.4.However,therearedifferentselectionmethodsavailablethatdonotsufferfromtheaboveproblems.

2.3.2. RankSelection

Inthisselectionoperationallindividualsaresortedbyincreasingvaluesoffitness.Eachindividualisthenassignedaprobability,pi,ofbeingselectedfromsomepriorprobabilitydistribution.Typicaldistributionsinclude:

Linear: pi=ai+b, (a<0)

and

Negativeexponential: pi=ae(bi+c)

Fig2.1 Plotoflinearandnegativeexponentialdistributionsusedforrankselection.

Thevaluesofaandbarecalculatedbysatisfyingthefollowingconditions:

Thesumoverallmembersofeachindividual'sselectionprobabilitymustbeone.

Theratioofthehighesttolowestprobabilitiesisc.

Theseresultinthefollowingequations:

whereNisthepopulationsize.Bychoosinganappropriatevalueforcwecandictatehowselectioniscarriedout.Generallycistakenas~2.

Rankselectionsolvestheproblemofprematureconvergenceandstagnationandthesizeofthegapsbetweenfitnessesbecomeirrelevant.However,thereislittleevidenceofthisselectionmethodoccurringinnature,makingitsusedifficulttojustify.Thereorderingprocessalsointroducesacomputationaloverheadmakingitlessengaging.

2.3.3. TournamentSelection

Thiscanbeviewedasanoisyversionofrankselection.Theselectionprocessisthus:selectagroupofN(N2)members,thenselectthefittestmemberofthisgroupanddiscardtherest.

Tournamentselectioninheritstheadvantagesofrankselectionbutdoesnotrequiretheglobalreorderingofthepopulationandismoreinspiredbynature.

2.4.0. FitnessScaling

Thetwoundesirablecharacteristicsoffitnessproportionateselection,prematureconvergenceandstagnation,cancauseproblemswiththeselectionprocedure.Ratherthanchoosinganalternativeselectionmethod,onecanchoosetoscalethefitnessvaluessoastoreducetheseunwantedeffects,whilestillusingfitnessproportionateselectionmethodssuchasroulettewheelselection.TherearethreemaintypesofscalingusedbytheGAcommunity.

2.4.1. LinearScaling

Thefitnessofeachindividual,f,isreplacedbyf'=a.f+b

whereaandbarechosensothat:

1. Thescaledaveragefitnessisequaltotherawaveragefitness().

2. Themaximumvalueofthescaledfitnessissomeconstanttimesthe averagefitness.Thisconstant,c,isthenumberofexpectedcopies desiredforthebestindividual(usuallyc=2).

Theseconditionsresultinthefollowingequationsforaandb:

Oneproblemwithlinearscaling,particularlyifisclosetofmaxorifagivenfitnessisverymuchlessthan,isthatfitnessvaluescanbecomenegative.Tosolvethiswecansetanynegativefitnessvaluestozero.This,however,isobviouslyundesirablesincethismeansthattheseindividualswillneverbeselected.Anotherwaytosolvethisproblemistouseanalternativescalingmethodsuchassigmatruncation.

2.4.2. SigmaTruncation

Withsigmatruncation,fisreplacedbyf'=f-(-c.).Whereisthepopulationstandarddeviation,c,isareasonablemultipleof(Usually1c3).Sigmatruncationremovestheproblemofscalingtonegativevalues.Truncatedfitness