粒子群优化算法求解旅行商问题

黄　岚,王康平,周春光,庞　巍,董龙江,彭　利(,130012):首先介绍粒子群优化的搜索策略与基本算法,然后通过引入交换子和交换序的概念,构造一种特殊的粒子群优化算法,并用于求解旅行商问题.实验表明了在求解组合优化问题中的有效性.:粒子群优化算法;旅行商问题;组合优化:TP31:A:1671-5489(2003)04-0477-04:2003-07-10.:(1974),,,,,E-mail:[e-mail].:(1947),,,,,E-mail:[e-mail].:(:60175024).(Particleswarmoptimization,PSO)KennedyEberhart[1],,,.[24].(Travelingsalesmanproblem,TSP):n,.TSP,NP,[5,6].,PSO,,PSOTSP.1PSO,n,.X.,Pid,,,Pgd.,V,Vid=XVid+G1rand()(Pid-Xid)+G2rand()(Pgd-Xid),(1.1)Vidid,X,G1,G2PidPgd,rand().,:Xid=Xid+Vid.(1.2)(1.1)(1.2),,Vid(Pid-Xid)(Pgd-Xid),X,G1G2.PSO:(1),XV;(2);(3),Pid,,Pid;(4),Pgd,,Pgd;(5)(1.1)(1.2);(6)(),;(2).Vol.41　　　　　吉林大学学报(理学版)No.4200310JOURNALOFJILINUNIVERSITY(SCIENCEEDITION)477480PSO,:,,;;.2TSPNP,..:n,.:G=(V,A),V,A,,Hamilton,.dijij,(i,j).:xij=1,ij;0,,(2.1)TSPminZ=ni,j=1xijdij.(2.2)TSP,,,,,,,.,TSP,.PSO,.,PSO,TSP.33.1nTSPS=(ai),i=1,,n.SO(i1,i2)Sai1ai2,S=S+SO(i1,i2)SSO(i1,i2),+.3.15TSP,S=(13524),SO(1,2),S=S+SO(1,2)=(13524)+SO(1,2)=(31524).3.2,SS.SS=(SO1,SO2,,SOn),(3.1)SO1,SO2,,SOn,.TSP,S=S+SS=S+(SO1,SO2,,SOn)=[(S+SO1)+SO2]++SOn.(3.2)3.3,.3.4,Ý.3.2SS1SS2,S,S.SSS,S,SS=SS1ÝSS2,(3.3)SSSS1ÝSS2.,SS.3.5,..AB,SS,B+SS=A.A:(12345);B:(23154).478　　　　　吉林大学学报(理学版)Vol.41　,A(1)=B(3)=1,SO(1,3),B1=B+SO(1,3),B1:(13254),A(2)=B1(3)=1,SO(2,3),B2=B1+SO(2,3),B2:(12354).,SO(4,5),B3=B2+SO(4,5)=A.,:SS=A-B=(SO(1,3),SO(2,3),SO(4,5)).4TSPPSOPSO(1.1)TSP,:Vid=VidÝA(Pid-Xid)ÝB(Pgd-Xid),(4.1)A,B(A,B[0,1]).A(Pid-Xid)(Pid-Xid)A;,B(Pgd-Xid)(Pgd-Xid)B.,A,(Pid-Xid),Pid;,B,(Pgd-Xid),Pgd.TSPPSO:(1),;(2),(5);(3)Xid,Xid,;1)PidXidA,A=Pid-Xid,A,AXidPid;2)B=Pgd-Xid,B;3)(4.1)Vid,Vid;4)Xid=Xid+Vid;(4.2)5),Pid;(4),Pgd.(2).(5).514TSP().PC(PentiumIV-2GHzCPU,256MRAM,Win2000OS,VC++6.0).14TSP1,1,2.Table1TSPwith14nodesNode1234567891011121314CoordinateX16.4716.4720.0922.3925.2322.0020.4717.2016.3014.0516.5321.5219.4120.09CoordinateY96.1094.4492.5493.3797.2496.0597.0296.2997.3898.1297.3895.5997.1394.55Table2AnalysesofthealgorithmperformanceSizeofsolutionspace(14-1)!/2=3113510400Numberofparticlesintheswarm100Averagenumberofiterations20000Averagesizeofsearchspace20000*100=2000000Searchspace/solutionspace2000000/3113510400=0.064%Bestsolutionofthealgorithm1109118137126543142Length30.8785(Equaltothebestknownresultintheworld),,,.14TSP,TSP479　No.4　黄　岚等:粒子群优化算法求解旅行商问题　　　(Lin-Kernighan[7]),PSOTSP.Fig.1ThesolutionpathsofTSPwith14nodes[1]EberhartR,KennedyJ.ANewOptimizerUsingParticlesSwarmTheory[C].ProcSixthInternationalSympo-siumonMicroMachineandHumanScience.Nagoya,Japan:IEEEServiceCenter,Piscataway,1995.3943.[2]XieX,ZhangW,YangZ.AdaptiveParticleSwarmOptimizationonIndividualLevel[C].InternationalConfer-enceonSignalProcessing(ICSP2002).Beijing:2002.12151218.[3]ParsopoulosKE,VrahatisMN.RecentApproachestoGlobalOptimizationProblemsThroughParticleSwarmOptimization[J].NaturalComputing,2002,1(23):235306.[4]RayT,LiewKM.ASwarmMetaphorforMultiobjectiveDesignOptimization[J].EngineeringOptimization,2002,34(2):141153.[5]ZhouChun-guang(),LiangYan-chun().ComputationalIntelligence()[M].Changchun():JinlinUniversityPress(),2001.269277.[6]HuangLan(),WangKang-ping(),ZhouChun-guang(),etal.HybridAntColonyAlgo-rithmforTravelingSalesmanProblem()[J].JournalofJilinUniversity(ScienceEdition)[()],2002,40(4):369373.[7]LinS,KernighanBW.AnEffectiveHeuristicAlgorithmfortheTravelingSalesmanProblem[J].OperationsRes,1973,21:498516.ParticleSwarmOptimizationforTravelingSalesmanProblemsHUANGLan,WANGKang-ping,ZHOUChun-guang,PANGWei,DONGLong-jiang,PENGLi(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China)Abstract:Thispaperintroducesthebasicalgorithmandsearchstrategiesofparticleswarmoptimiza-tion(PSO),viapresentingtheconceptsofswapoperatorandswapsequenceanalgorithmofakindofspecialparticleswarmoptimizationisconstructedandthenproposesitsapplicationtotravelingsales-manproblems(TSP).TheexperimentsshowthenewPSOcanachievegoodresults.Keywords:particleswarmoptimization;travelingsalesmanproblem;combinatorialoptimization(责任编辑:赵立芹)480　　　　　吉林大学学报(理学版)Vol.41