搜索
274Vol.27,No.420078JournalofGuilinUniversityofElectronicTechnologyAug.2007TSPX,(,541004):(GA),TSP,TSP,,,,,,,,TSP;TSPLIB,:;TSP;;:TP18:A:16732808X(2007)0420287204AnimprovedgeneticalgorithmforsolvingTSPproblemFUYi2ping,CHENGuang2xi(SchoolofMathematicsandComputingScience,GuilinUniversityofElectronicTechnology,Guilin541004,China)Abstract:TravelingSalesmanProblem(TSP)isatypicalNP2Completeproblem.GeneticAlgorithm(GA)isaglobaloptimalsearchingalgorithmbasedonthebiologicalevolutionism.GAisamethodforsolvingthisproblem,itishardforittofindglobaloptimizationquicklyandpreventprematureconvergence.Inresponsetothisproblem,anovelgeneticalgorithmisproposedinthispaper,whichisbasedonthefeatureoftheoptimumofTSPandcom2prisestheminimallineofthecity.Greedytwopointsinsertionmutationoperatorisproposedandtheheuristiccrossoveroperatorisimproved.Themutationprobabilityoftheunitsisgivenbyitssuit2functionvalue.Compar2ingwiththemeanofthegroup’ssuit2functionvalue.Inordertoimprovetheconvergencespeed,localoptimizedsearchisusedtoenhancetheabilityoftheinitialgroup.Theimprovedalgorithmcanavoidthelocaloptimumbylocaladjustment.TheexperimentalresultbasedontheimprovedGAindicatesthattheimprovedGAhasabetterconvergencepropertyandcaninducetheoptimalresults.Itstestingresultsareasgoodorevensuperiorincompar2isonwithTSPLIB.Keywords:geneticalgorithm;TSPproblem;greedmutationoperator;heuristiccrossoveroperatorTSP():n1,2n,,,,NP,,(GeneticAlgorithm,GA)MichiganJohnHolland1973,,GA,,;,X:2007206208:(10501009,10661005):(1980-),(),,,,,,(GA)[1],GATSP,GATSP:[2]TSP,,,(),;[3]:,,;[4]GA,TSP,K;[5],,,,GA:,2-opt,;;;,,22opt,,122opt[6]22opt,1.ab+cdac+bd,ab+cdac+122optbd,,22.1GA,TSP,,22opt,,2.2,Pm,Pm,;Pm,GA,:Pm=0.3,fifq0.33fq-fifq-fmin,fminfifq0.1,fi=fmin.(1)fminfqf(x)=n-1i=1d(xi,xj)+d(xn,xl).TSP(1),,,2.3:TSP,,:c,ccc1,c2,:cc1,c2,c1c,c2c;,2.4TSP:88220078[7],[3],,:,,,,,,:P1,P,X=P1,Y=P.(1)c,child(2)XYccRightX,cRightY,cLeftX,cLeftY,cRightX,cRightY,cLeftX,cLeftYd1,d2,d3,d4.cchild(3)d=min{d1,d2,d3,d4},c1,X,Yc(4)cChild.(5)c=c1,(2)(3),X,Y1,child2.5k,22opt,,3,BeginStep1,2optP={S0,S1,Sm};Step2,,,,Step4.Step3(1)Step4i=1;Step5PSi,S;Step6(0,1),,,Step7i+1;Step5Step6,i=m;Step8;;Step9Step2Step8,5,2opt,,Step2,continue;,Step10Step2Step9,:();;4Matlab7.0,2.66GPC,windowsXP.4.1[4]4.1.130TSP[8]6;7171;5869;5462;5167;3784;4194;299;764;2260;2562;1854;450;1340;1840;2442;2538;4126;4521;4435;5835;6232]3029272628252423222120181917161514131211109876543213030TSP423.741,[3],2;3,3,,5[3](14)2309824:TSP34.1.250TSP[9]:China50=[1075;369;9178;5453;851;7851;7314;2356;1540;2660;7498;9116;9275;6373;9516;2184;423;4129;3674;5615;1418;2680;4913;2494;592;6643;4826;1333;1153;4765;1570;3791;6354;4642;668;5228;6134;7013;9155;3660;2020;392;2990;8746;6287;7092;1924;3210;8184;7390]551.3980,561.851[10],[4]551.314,0.084,45011464514332637362718344304019223243241625131471082959281721414824223203538712154463913349504.2TSPLIB1TSBLIB3,100,TSPLIB,,104501Burma143330.87859Dantzig42699688.33198Berlin5275427544.485,,2-opt,,,TSP,,,:2-opt,,:[1],.[M].:,1996:10-14.[2],,.TSP[J].,2003(12):1753-1758.[3],,,.TSP[J].,2005(5):823-828.[4],.[J].,2004,40(22):67-70.[5],,.TSP[J].,2006,13:91-93.[6]WATSONJ,ROSEC,EISELEV,etal.Thetravelingsalserepproblem,edgeAssemblyCrossover,and22opt[C].ParallelProblemSolvingfromNatureV,Netherlands:Amster2dam,1998.[7],,.[M].:,1998:90-92.[8]BAECKT,FRGELDZ,MichalewiczEvolutionaryComputa2tion:AdvancedAlgorithmsandOperators[M].London:Insti2tuteofphysics,2000.[9].[J].,1999,8(3):24-30.[10],,.TSP[J].,2004(1):19-22.09220078