计算机专业毕业论文外文翻译(含原文)

摘要这篇文章是描述基于旅行商问题一种粒子群算法(PSO)，一个不确定的搜索策略和交叉淘汰技术被用来加快收敛速度。相对于现有的求解TSP使用群集智能算法，有证据表明，利用粒子群算法解决问题的大小会增加。另一个基于PSO算法将其应用于采用广义的染色体解决广义旅行商问题。所提出的算法两个局部搜索技术被用来加快收敛速度。数值结果表明了该方法的有效性。1介绍粒子群算法(PSO)算法，最初,是由KennedyandEberhart提出的，是一种源于成群的鸟的或鱼社会行为的优化方法。类似的，遗传算法,该算法也是一种基于人群的优化算法。该系统在初始时首先随机生成的潜在的解决方案,然后通过迭代寻找最优解。它通过最好的粒子寻找最优解。相比算法PSO有着更好的智能背景和可执行要容易得多。根据其优势,该算法是不仅适合于科学研究,而且工程应用。目前该算法已在该领域的进化计算领域吸引了广大的注意,优化和许多其他算法问题。虽然该算法为连续优化问题了，最近，已经有一些报告工作开始关注离散的问题。旅行商问题（TSP），在组合优化中是一个基准许多新发展的著名和广泛的研究，包括在进化计算中的技术，如领域搜索（NNS），模拟退火(SA),禁忌搜索（TS），神经网络（NN），蚁群算法（ACS），遗传算法等等。更重要的是Clerc，HendtlassandWang提出不同的粒子群算法解决TSP问题。尽管PSO能够用于TSP，在TSP问题的规模，解决问题的报告都提到小于17个城市。从而看出解决TSP使用PSO算法是有限的。一个非常简单而实用的TSP的延伸是广义的TSP（GTSP），其中一组节点分为集群和目标都是为了找到一条路径经过所有节点的使成本最小。该GTSP代表了一种组合优化问题，自20世纪60年代由Henry-Labordere[18],Saskena[19]和Srivastava[20]所提出的，并通过福利机构在计算机条件下记录平衡和访问测序。它已许多广泛领域中得到应用。正如文章[21]所提到的，“在许多现实世界问题中，他们是固有的层次，GTSP提供了一个比TSP更准确的模型。”一般而言，对许多实际问题GTSP提供了更多的理想的建模工具。此外，根据我们目前的延伸在GTSP同时可以包括分组和孤立顶点。因此，GTSP包括理论上的TSP而且在GTSP在应用领域比TSP更广泛的。虽然自20世纪60年代末的GTSP已提议[18-20]，相关文献是非常有限的，对TSP问题[8-14]和现有的算法GTSP主要基于动态规划技术[18-20,22]。动态规划算法的主要方法是把GTSP转变到TSP问题，然后利用现有解决TSP算法。这些方法缺点是显著的增加了问题的维数。因此虽然在理论上GTSP用来解决相应的转变的TSP问题，其技术的局限性限制了实际的可行性。按设计广义染色体（GA），Wuetal.[23]已经研究出广义染色体的遗传算法GC能够统一GTSP和TSP问题，通过引入“超级顶点”成为一个统一的模式。因此，一般情况下，该算法不增加解决问题的大小。在文中，两个粒子之间的”减法”操作是修改和离散粒子群优化方法构建TSP问题。在该方法中也用到交叉淘汰技术。数值表明，该方法可以提高解析TSP问题的规模。基于对GTSP编码技术的在[23]，另一基于PSO算法在本文提出了求解GTSP。两个本地搜索技术还列入拟议的方法。为了测试方法的有效性，19GTSP问题测试作为研究基准。结果表明，该方法是有效解决GTSP问题的方法。将成为我们的最好知识，至今还没有试图提出一项基于PSO算法的GTSP。这个提议粒子群算法可以提供一个合适的方法解决GTSP。2粒子群优化算法首先，要介绍标准粒子群优化算法。假设搜索空间D维和m微粒形成的种群，一个粒子为一个D维的向量Xi（i=1，2....m），意思是第i个粒子在D维的搜索空间中的位置Xi=(Xi1,Xi2,….,XiD),(i=1,2….m)。每个粒子的位置都是一个潜在的解。我们通过给定的函数计算粒子的适应值fitness，当适应值比但前Xi更优，第i个粒子的飞行速度也是一个D维的向量Vi=(Vi1,Vi2,….,ViD)(i=1,2….m)。第i个粒子迄今为止搜索到的最优位置称为个体极值，记为pi=(pi1,pi2,….,piD)，相应的整个粒子群迄今为止搜索到的最优位置为全局极值，记为pg=(pg1,pg2,….,pgD)。PSO算法如下方程表示：（1）（2）式中，i=1,2,….,m,m是群体中粒子的总数。ω是[0,1]的惯性常数；c1,c2是学习因子，为非负常数，r1,r2是[0，1]的随机数。程序终止的标准是pg是否满足给定函数或给定的适应值。上文所述的算法可以被视为传统的粒子群优化，这是适用于连续的问题。然而，不能

适用于离散问题直接。针对离散问题，肯尼迪和埃伯哈特提出了离散二进制版本的PSO算法的确定粒子的运动轨迹和速度的变化概率这一点将会在一国或其他[5]。因此，在每一代中粒子的移动将被限制成0和1，Vid代表Xid的取1时的概率。公式（2）中除了pid，xig在整数{0，1}内，粒子群公式保持不变。公式（1）更新为：其中S(•)是物流转变，能够保持vid在整数{0，1}，且S(vid)可被视为是一个概率。3离散的粒子群算法解决TSP3.1离散PSO算法求解TSP问题的详解Clerc提出了一个简单的粒子群算法求解TSP问题的概述。通过在PSO算法中对每个粒子的添加内存的能力，Hendtlass[16]采用PSO算法解决小规模TSP的问题，并改善其性能，wang等[17]通过引入“交换操作”和“交换序列”的概念重新确定PSO的的操作者。在[16]和[17]的城市大小中都是14（双方都选择Burma14，基准问题TSPLIB与14个城市），而[15]是17个城市（它选定br17，一个基准问题TSPLIB与17个城市）。这就是说，在算法中城市的大小受到限制。为了扩大规模，解决问题，受到[17]中“交换操作”的启发，我们介绍置换的概念纳入我们提议的离散PSO算法解决TSP问题。并且增加一个不确定性搜索

战略以加快收敛速度。对以m的tsp问题，定义Xi={xi1，xi2,...xim}为第i个粒子在PSO的种群中，代表xi1→xi2。。。。→xim→xi1。传统的PSO算法被定义为方程（1）（2）。为了能解决TSP问题，方程（1）保持不变，而第二项方程右边的意思即Vi(k+1)改变了。因此方程（2）可以被重新定义。首先两个粒子的减法应该被重新定义。为了表示这个问题，一些概念置换将介绍。定义1置换可以用相关符号表示。一个可以安排元素“自然”排列，然后在此基础再重新排列：[12345]→[25431]用s(1)=2,s(2)=5,s(3)=4,s(4)=3,s(5)=1代表[12345]置换定义2.让X为一集合，一个循环为一个置换,如存在X的不同元素a1,a2,…ak定义3.一个循环命令是一些元素和他平凡的轨道。一个周期k阶也所谓的K-循环。一个1-循环是一个身份置换，因此任何置换可以分解一组不连续的循环（包括1-循环）。定义4.给定一有限数组X={a1,a2,…,an}，一个换位是一个置换f，如存在指数i，j，f(ai)=aj,f(aj)=ai,且f(ak)=ak,。一个换位是2-循环。任何循环能够分解为一组换位。所以任何置换可以分解为一组换位。给定两个n组有序序列A={a1,a2,…,an}和B={b1,b2,…,bn},定义以下置换为集合k为PAB最小换位的数目，即PAB=T1,T2…TK。然后我定义减法B-A=T1,T2…TK粒子的位置可被视为一个m-有序序列，所以两个粒子位置的减法可以按上定义。定义5.对一个m-有序序列X=(x1,x2,…,xm),移动的粒子表现在X是SL(X，k)={x(1+k)%m,x(2+k)%m,…x(m+k)%m}。定义6.对于一个m-有序序列X=(x1,x2,…,xm),对X的跌倒顺序的操作是RE(X)=(xM,xM-1,…,x1)。对一个粒子X，我们定义SL(X,k)=X和RE(X)=X定义7.给定两个粒子位置Xi={xi1，xi2,...xim}和Xj={xji1，xj2,...xjm}，定义他们的减法如下：集合r是一个实值T是一个换位，定义为其中PI是一个恒等排列。重新定义方程2中r1,r2为一个实向量，它的维数相应的换位的数目。因此方程2能够被改写为：惯性系数ω是一个常数小于1，项目排列的高ω可能被忽略。在本文对项目的ω-有序超过2都省略。因此我们有：图1伪代码删除交叉进程图2删除交叉进程示意图总之，提出的离散粒子群优化算法在TSP问题可以概括如下(1)初始化粒子群：包括初始化每个粒子的位置和评价每个粒子的适应值fitness。在这一阶段，Pg还被搜查和每个颗粒子初始位置Pi。(2)应用每个粒子的PSO优化流程：(a)根据方程(1)-(8)对每个粒子执行搜索过程(b)对Pg执行删除交叉进程；(3)判断终止的标准，即是否迭代达到一定数量或最好适应值fitness是否到达指定的值。如果满足标准停止该执行，否则请转到步骤2。3.2.数值结果为了验证所提出的离散PSO算法，从TSPLIB图书馆[24]某些情况下被选中的模拟。实验执行环境在个人电脑上有2GHz处理器和128M内存。每个实例运行100次。表1介绍了数值结果。第二栏代表每个问题(Opt)的最优游览距离长度，和第七的相对错误（Err），相对误差的计算方法如下：Err=(Ave−Opt)/Opt×100%(9)表1显示，拟出的离散粒子群优化方法可用于解决TSP问题有效性。从表1可以看出，在5次测试问题，最大的相对误差为4.1673％，平均相对误差3.5496％。可以看出，当问题的规模介于50至80，我们的结果是公平的良好的，[15-17]表明，已解决TSP问题规模均小于17个城市。很明显该算法解决同样规模的问题与现有的算法比具有优势。4离散粒子群优化方法解决GTSP问题4.1.声明广义的TSP(GTSP)广义旅行商问题（GTSP）

由Henry-Labordere，Saskena，Srivastava提出，在并通过福利机构在计算机条件下记录平衡和访问测序。20世纪60年代。GTSP有许多广泛的应用领域，如涉及旅游的问题，物流系统设计，后箱收集，随机车辆路径与arc路由，和许多其他[21,25]。在GTSP问题，候选城市划分成若干组。一些城市可能属于不止一个组，而其他一些城市可能只是在一个组。GTSP的目的是寻求最小的长度行周期。根据风格，存在着两种不同类型的GTSP周期：通行路线经过组里每个顶点。每个通行线路至少进过每个组一个顶点。为简洁，只有第一种情况是在本文件。4.2.离散粒子群优化方法算法的GTSP为了方便起见，Wu等提出了广义染色体（GC）在[22]介绍了。假设有N个候选城市分为m组（包括单个城市）。即，任意给定城市ci（i=1,2,…n）,一定存在至少一组弧Vj(j=1,2,…m)满足ci∈Vj。然后遍历由图中m个顶点和m顶点连成m条连线。如果属于Vj的城市数大于1和如果属于Vj的城市成为元素，那么一组弧Vj(j=1,2,…m)被认为是一个超级顶点。如果Vj={ci}（j=1,2,…m）城市ci（i=1,2,…n）被认为是一组分散的顶点。然后顶点可以根据他们的类型分为两类，即,超级顶点或分散的一个，定义超级定带你的数目为，分散顶点数目为，所有的超级顶点，所有分散顶点为，相关的所有广义的顶点被定义为，图3.广义染色体（10）基于wu等编码技术等开发，在[23]第2节的正文中的一部分，仍然是“置换”的概念说明，我们考虑增加两个本地搜索的进程和发展的离散算法方法GTSP。方程(1)仍然是工作中的方法。但是通过对粒子的位置Xi和速度Vi不同于存在超顶点在GTSP问题的TSP问题。Xi代码可命名为：正文部分如第二部分为计算粒子的速度，即：不同粒子的位置相减如方程（6）。XH不是一个不重复的序列，所以我们给于更新XH的速度如下：为了加快收敛，算法中使用了两个局部搜索技术。首先一个地方搜索添加到头部。对于每一个相同的头部，最好的指数在相应超顶点是要首先搜查，然后原来的指数改为最好。上述本地搜索进程名本地搜索I，这可以被视为作为一个贪婪搜寻。第二个本地搜索行为自身搜索，这是用来交换在每个迭代中两个广义顶点的位置随机。如果然后适应值fitness增加则交换保持不变，否则其他原始粒子保持不变。相应地，这是本地搜索二的命名，可以被看作是一个随机搜索。总之，离散粒子群优化方法解决GTSP可描述为：(1)初始化粒子群：包括初始化每个粒子的头部和身体，和计算每个粒子适应值fitness。然后搜索Pg和每个粒子Pi，设为初始位置。(2)适应每个粒子的算法流程(a)根据方程(17)-(18)执行对每个粒子的搜索进程；(b)执行局部搜索Ⅰ(c)执行局部搜索Ⅱ（3）判断终止条件，即是否达到给定迭代数目或是否达到给定适应值fitness。如果满足停止执行，否则转到（2）。4.3.数值结果从TSPLIB图书馆[24]19实例已选定审查的有效性，提出的算法为解决GTSP问题。这些事例都最初生成的测试标准的TSP算法来测试GTSP算法。Fischetti等在[22]对“广义subtour消除制约”提出提一个准确的分离算法。这样我们就可以在不同的运行提供数据秩序得到相同的分割结果。同样的（详情可参考在第3节[22]）。因此，准确分离算法可用来生成测试数据的不同的算法。在下面的实验中，规模为80。表2列出了计算结果。第二列表明每个问题的最佳游览的确切长度[22]。表2显示，提出的离散粒子群优化方法可用于解决GTSP有效性。从表2可以看出，在19测试的问题，最大相对误差为9.69％和所有测试的平均相对误差是4.25％。因此，计算结果是相当好的。表25.结论关于TSP的问题，通过增加了一个不确定的战略加入方法中提出一种新型的离散算法。此外，通过引入广义染色体技术，该算法延伸解决广义的TSP问题。尽我们所知，这是第一次以该算法为基础的算法用于解决GTSP问题。数值结果表明，该算法有效的。它也表明，这种算法比现有的算法可以解决更大规模问题。参考文献 [1]J.Kennedy,R.C.Eberhart,Particleswarmoptimization,in:ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks,Perth,Australia,vol.4,IEEEServiceCenter,Piscataway,NJ,1995,pp.1942–1948.[2]P.J.Angeline,Evolutionaryoptimizationversusparticleswarmoptimization:philosophyandperformancedifferences,EvolutionaryProgramming7(1998)601–610.[3]M.Clerc,J.Kennedy,Theparticleswarm-explosion,stability,andconvergenceinamultidimensionalcomplexspace,IEEETransactionsonEvolutionaryComputation6(2002)58–73.[4]I.C.Trelea,Theparticleswarmoptimizationalgorithm:convergenceanalysisandparameterselection,InformationProcessingLetters85(2003)317–325.[5]J.F.Chang,S.C.Chu,J.F.Roddick,J.S.Pan,Aparallelparticleswarmoptimizationalgorithmwithcommunicationstrategies,JournalofInformationScienceandEngineering4(21)(2005)809–818.[6]J.Kennedy,R.C.Eberhart,Discretebinaryversionoftheparticleswarmalgorithm,in:ProceedingsoftheIEEEInternationalConferenceonSystems,ManandCybernetics,vol.5,Orlando,Florida,USA,1997,pp.4104–4108.[7]M.Clerc,in:DiscreteParticleSwarmOptimization,illustratedbytheTravelingSalesmanProblemNewOptimizationTechniquesinEngineering,Springer,2004,pp.219–239.[8]R.E.Bellman,Dynamicprogrammingtreatmentofthetravelingsalesmanproblem,JournaloftheACM9(1962)61–63.[9]M.Bellmore,G.L.Nemhauser,Thetravelingsalesmanproblem:asurvey,OperationsResearch16(1968)538–558.[10]D.E.Goldberg,Messygeneticalgorithms:motivation,analysis,andfirstresults,ComplexSystems3(1989)493–530[11]G.Ausiello,M.Demange,L.Laura,V.Paschos,Algorithmsfortheon-linequotatravelingsalesmanproblem,InformationProcessLetters92(2004)89–94.[12]T.Munakata,Y.Nakamura,Temperaturecontrolforsimulatedannealing,PhysicalReviewE64(2001)046127.[13]F.V.Fomin,A.Lingas,Approximationalgorithmsfortimedependentorienteering,InformationProcessLetters83(2002)57–62.[14]L.Huang,C.G.Zhou,K.P.Wang,Hybridantcolonyalgorithmfortravelingsalesmanproblem,ProgressinNaturalScience4(13)(2003)295–299.[15]M.Clerc,Discreteparticleswarmoptimizationillustratedbythetravelingsalesmanproblem,,2000.[16]T.Hendtlass,PreservingDiversityinParticleSwarmOptimization,in:LectureNotesinComputerScience,vol.2718,Springer,2003,pp.4104–4108.[17]K.P.Wang,L.Huang,C.G.Zhou,W.Pang,Particleswarmoptimizationfortravelingsalesmanproblem,InternationalConferenceonMachineLearningandCybernetics3(2003)1583–1585.[18]A.L.Henry-Labordere,Therecordbalancingproblem:adynamicprogrammingsolutionofageneralizedtravelingsalesmanproblem,RIROB2(1969)43–49.[19]J.P.Saskena,Mathematicalmodelforschedulingclientsthroughwelfareagencies,CORSJ.8(