A study of five parallel approaches to a genetic a

IntelligentAutomationandSoftComputing,Vol.11,No.4,pp.217-234,2005Copyright©2005,TSI®PressPrintedintheUSA.Allrightsreserved217ASTUDYOFFIVEPARALLELAPPROACHESTOAGENETICALGORITHMFORTHETRAVELINGSALESMANPROBLEML.WANG1,A.A.MACIEJEWSKI2,H.J.SIEGEL2,3,V.P.ROYCHOWDHURY4,ANDB.D.ELDRIDGE21MicrosoftCorporationRedmond,WA98052-63992ElectricalandComputerEngineeringDepartment3ComputerScienceDepartmentColoradoStateUniversityFortCollins,CO80526-1373email:[e-mail](CORRESPONDINGAUTHOR)4ElectricalEngineeringDepartmentUCLALosAngeles,CA90095-1594ABSTRACT—Thispaperpresentsacomparativestudyoffivedifferentcoarse-grainedparallelgeneticalgorithms(PGAs)usingthetravelingsalesmanproblemasthecaseapplication.AllofthesePGAsarebasedonthesamebaselineserialgeneticalgorithm,implementedonthesameparallelmachine(IBMSP2),testedonthesameprobleminstances,andstartedfromthesamesetofinitialpopulations.Basedontheseexperiments,aPGAthatcombinesanewsubtourtechniquewithaknownmigrationapproachisidentifiedtobethebestforthetravelingsalesmanproblemamongthefivePGAsbeingcompared.KeyWords:ParallelGeneticAlgorithms;TravelingSalesmanProblem;MemeticAlgorithms1.INTRODUCTIONSerialgeneticalgorithms(SGAs)areapromisingsearchheuristicforfindingnear-optimalsolutionsinlargesearchspaces(e.g.,[1]).ToreducethelargeamountofcomputationtimeassociatedwithSGAs,parallelGAs(PGAs)havebeenproposed.PGAshavealsobeenusedtosolvelargerproblemsandtofindbettersolutions.Thereexistsalargebodyofliteraturethatdiscussestheparallelizationofgeneticalgorithmsformanydifferentapplications,e.g.,[2-16].PreviouscomparativestudieshavecontrastedtheperformanceofPGAswithandwithoutmigration,demonstratingthatmigration,ingeneral,resultsinsuperiorperformance,e.g.,[11,13].Oneofthefeaturesthatdistinguishesthispaperfrompreviousworkisthatitcomparesfourconceptuallydifferentcoarse-grainparallelizationtechniques,includingtwonewapproachesalongwiththestandardindependentandmigrationPGAs.Inaddition,itcomparesaPGAthatisahybridofanewandastandardapproach.Allofthesecomparisonsaredoneusingacommonframework.Thetravelingsalesmanproblem(TSP),describedinSection2,isusedasthebasisofthiscasestudy.Tomakefaircomparisons,allofthesePGAsaretestedonthesamesetofTSPinstances(listedinSection2),implementedonthesameparallelmachine(theIBMSP2describedinSection3),basedonthesamebaselineSGA(presentedinSection4),andstartedfromthesamesetofinitialpopulations.218IntelligentAutomationandSoftComputingThePGAsstudiedaretwoexistingapproaches(theindependentPGAandthemigrationPGA),twonewapproaches(thepartitionedPGAandthesegmentationPGA),andahybridapproach(thesegmentation-migrationPGA).TheindependentPGAexecutesanindependentSGAoneachprocessor.ThemigrationPGAextendstheindependentPGAbyperformingperiodicmigrationofchromosomesamongprocessors.ThepartitionedPGApartitionstheproblemspaceandhaseachprocessorsearchadisjointpartition.InthesegmentationPGA,processorsiterativelyoperateonTSPsubtours(chromosomesegments)andthenrecombinesubtoursintolargersubtoursuntilfulltours(fullchromosomes)areformed,atwhichpointtheindependentapproachisfollowed.Thesegmentation-migrationPGAcombinesthesegmentationandmigrationapproaches.ThesePGAapproachesaredescribedinmoredetailinSection5.ExtensiveexperimentswereconductedtoquantifyeachPGA’sabilitytofindqualitysolutionsandtotesthowquicklythePGAscanfindsolutionsofsimilarquality.Experimentalresultsshowedthatthefournon-partitionedPGAsstudiedfoundhighqualitysolutions(within1%ofthebestknownsolutions).Inter-processorcommunicationsthatmigratethelocallybestchromosomesamongtheprocessorsshortenedthetotalexecutiontime.Usingmigrationtogetherwithchromosomesegmentationandrecombination(thesegmentation-migrationapproach)furtherreducedthistime.TheseexperimentsarepresentedandanalyzedinSection6.2.THETRAVELLINGSALESMANPROBLEMThetravelingsalesmanproblem(TSP)isawell-knownNP-hardcombinatorialoptimizationproblem[17].Itcanbestatedasfollows.ThereareCcities,whicharenumberedfrom0toC−1.Thedistancefromcityitocityjisknowntobedij,where0≤i,jCanddij=0ifi=j.Atourisapaththatstartsfromacity,visitseachcityexactlyonce,andgoesbacktothestartingcity.Mathematically,atourcanbeexpressedbyavectortofCelements.Eachoftheelementsintrepresentsacity,i.e.,0≤t(i)Candt(i)≠t(j)ifi≠j.Thetourstartsfromt(0),visitscitiesintheordertheyappearint,andthengoesbacktot(0)aftervisitingt(C−1).ThegoaloftheTSPistofindatourtwiththeminimumtourlength,i.e.,tominimize∑−=−++20)0()1()1()(CitCtititdd(1)Becausethetoursareclosed(circular),thesametourcanberepresentedbymultiplet-vectorsthatarerotationsofoneanother.Thus,thevectorst1andt2representthesametourift1(i)=t2((i+j)moduloC)foranyfixedintegerj,foralli,0≤iC.Ifthedistancebetweenanytwocitiesisindependentofthetraveldirection,i.e.,dij=djiforalliandj,theTSPisasymmetricTSP.Otherwise,theTSPisasymmetric.ForsymmetricTSPs,thetourt1mustbethesamelengthast2ift1isjustareversaloft2,i.e.,t1(i)=t2(C−1−i),foralli,0≤iC.Furthermore,theserotationandsymmetricpropertiescanbecombinedtoformequivalenttours.AsubsetofthesymmetricTSPiscalledtheEuclideanTSP,whereeachcityisrepresentedbyasetofcoordinat