英语原文共 11 页
基于交换序的人工蜂群算法求解旅行商问题
作者：Indadul Khan，Manas Kumar Maiti
摘要
在本研究论文中，使用多个更新规则和K-opt操作改进的人工蜂群算法解决旅行商问题。 设计中使用具有交换序列和交换操作特性的城市序列(解决方案/路径)用于创建不同解决方案(路径)的更新规则算法。随后，提出了八种不同的规则来更新算法中的解决方案。 通过更新解决方案，雇佣蜂或观察蜜蜂是通过使用轮盘赌规则随机选择来完成的选择过程。 在算法的侦察蜂阶段，应用扰动技术K-opt操作对任何停滞不前的解决方案进行固定次数的可能性的改进。 K-opt操作是在搜索过程结束时再次使用，以提高最终解决方案的质量(如果可能)。 提出的方法是用TSPLIB的一组基准测试问题进行测试的，并观察到效率算法在解决标准TSP的准确性和一致性方面是足够有效的。
关键词：旅行推销员问题;人工蜂群算法;交换顺序;交换操作;K-opt
1.简介
旅行推销员问题(TSP)是标准的离散优化问题。 问题包括一组N个顶点(节点/城市)，任意两个顶点之间的距离已知，要求：推销员从顶点开始，准确地访问所有顶点，每个节点只访问一次，并以这样的方式返回到起始顶点行进的距离是最小的。 所以问题的目标是找到一个通过顶点集合进行最短的游览，使每个顶点除起始顶点外，只访问一次。 TSP问题是众所周知的NP难问题，无法使用任何多项式时间精确求解算法。 在TSP中，当任意两个顶点之间的距离x i和x j等于x j和x i之间的距离，则问题是称为对称TSP(STSP)。 另一方面，如果存在一对顶点 x i和x j之间的距离不等于x j之间的距离和 x i，问题属于不对称TSP(ATSP)。 一般来说，有两种方法解决TSP：精确方法和启发式方法。 确切的方法对于较大的 N 需要大量时间，因此启发式方法是典型的用于解决TSP问题。 确切的方法包括切割平面LP放松，分支和界限，分支和削减等。只有小尺寸的TSP才能在合适时间内，通过精确的方法合理地解决。另一方面，已经提出的求解TSP问题启发式或基于软计算的技术，如Ant Colony Opti-mization(ACO)，本地搜索，混合算法，遗传算法(GA)，粒子群优化(PSO)，人工蜜蜂算法(ABC)等等。有几个完善的求解STSP的启发式算法，王等人使用了交换运算符和交换的概念序列，并在此基础上重新定义了PSO的一些运算符解决TSP。 结合PSO，ACO和3-opt混合算法的特点，Mahi等人提出了 PSO-ACO-3-opt算法解决标准TSP问题。 Akhand等人，提出了部分搜索算法的PSO解决TSP问题。 Akhand等人改进了这个算法来查找TSP的解决方案并命名为速度暂定PSO。 耿等人提出了一种基于Simulated的有效局部搜索算法退火(SA)和贪婪的搜索技术来解决TSP。 Jolai和Ghanbari提出了一种改进的人工神经网络(ANN)解决TSP的方法。 Dorigo等人提出了一个解决TSP的蚁群系统， Dorigo和Gambardella描述了一个能够解决TSP问题的ACO算法。 Bontoux和Feillet提出一种解决TSP的混合算法—— Beam-ACO算法，即结合ACO和光束搜索的混合方法用于求解TSP。 Gunduz等人提出了一种新的等级方法并基于群体智能算法来求解TSP。 汗等人提出了一种基于ACO-PSO-K-otp的混合算法求解TSP。 黄等人提出了一种基于PSO的算法求解TSP。 此外，他们建立了不同的启发式方法，提高求解其他NP难组合优化问题的能力，像车辆路由问题、流水车间计划问题。最近，Rajasekhar等人制作了迄今为止针对不同类别的优化问题关于不同的蜂群算法进行了开发的调查。 取决于生物学观点，他们提到了不同的算法的前景和动机在各类问题中进行比较并比较算法。
从上面的讨论可以得出结论，启发式方法对于在可行的时间内解决TSP更有效——道琼斯指数。 自2005年以来，ABC已被证明在连续优化方面取得的成功，在这个领域，已经可以有效地开展了很多工作。 已经引入了一些离散版本的ABC在文献中。 Karaboga和Gorkemli提出了一个用于TSP的新ABC算法称为Combinatorial ABC。 应用交换序列和交换操作的特征，Pan等为批量流流水车间调度问题提出了一个离散的ABCLEM算法。 伊克巴尔等人提出了一种新的蜜蜂算法来求解多个具有软时间窗的客观车辆路径问题。 使用时对于TSP，任何启发式算法有时会收敛到本地可选择路径(游览)。 K-opt是一种扰动技术应用于旅游(路径)以克服这种趋同的问题。 事实上，K-opt是用于搜索更好邻居的最广泛使用的启发式方法任何可能的TSP解决方案。 它就像一个突变功能GA。 K-opt是一种旅行改进算法，其中每个步骤K。当前旅游的链接被K链接取代，以这种方式实现了更短的旅行。
本文提出了一种新的ABC算法变种来解决STSP和ATSP。 在该算法中，有八种不同的规则建议改善受雇蜂或观察蜂的解决方案蜜蜂。 设计使用了交换序列和交换操作来定义规则推销员的潜在路径(解决方案)，改善解决方案雇佣蜂或观察蜜蜂从规则集中选择规则随机使用轮盘赌轮(RW)选择过程。对于一个解决方案分配给侦察蜂的，在第一次K-opt操作时应用于固定的可能改进的迭代次数。 如果它没有能力在改进解时，解随机再生。 K-选择在算法结束时再次使用操作来改善质量最终解决方案(如果可能的话)。 上述提出的方法，用a测试来测试TSPLIB的一组基准测试问题，并且观察到了就准确性而言，算法的效率是充分的以及与文献中的现有算法比较解决标准TSP(ATSP和STSP)的一致性。
本文的其余部分安排如下：第 2 节，提出了问题的数学表述。在第 3 节，交换讨论了序列和交换操作。在第 4 节，讨论ABC特点。K-opt操作见第 5 节。建议算法在第 6 节中介绍。实验结果在第 7 节讨论。第8节得出了一个简短的结论 。
2.问题提出
TSP可以用图表 G =(V，E)表示，其中V = {1，2，... N}是一组顶点或节点和E是边的集合。这里，每个节点代表一个城市，每个边代表路径。两个城市之间，每个边缘都与一个距离相关联，与之对应的是城市之间的距离。 推销员旅行距离周期性地访问 N个城市(或节点)。 在一个他完全访问每个城市一次并完成他开始的地方最短的旅行距离。 设 d jk为j -th之间的距离城市和第k个城市。 然后，该模型可以表示为：
其中 x jk = 1，如果推销员从city- j旅行到city- k，否则x jk = 0。设 ( x 1， x 2 ...， x N， x 1 )是推销员的完整之旅，在那里XĴisin;V，forall;Ĵisin;V和所有的x j字是不同的，即，(X 1，X 2 ...，X N，X 1)是推销员在城市中旅行的城市序列。 那么以上问题减少到，
3.交换TSP的序列和交换运算符
由Wang等人提出的交换运算符和交换序列的概念，并在2003年使用PSO解决了TSP问题。 潘等人在DABC中使用这些操作来解决流水车间调度问题。
下面给出这些操作的简要描述。
交换运算符：考虑正常的节点解决方案序列，具有N个节点的TSP的X =( x 1， x 2， ... x N， x 1 )，具有节点集V = {1，2，... N}，其中X Iisin;V和X Ine;XĴ，forall; I ne;j时。 在这里，交换operator——SO ( i， j )被定义为节点x i和节点x j的交换在序列 X中。 然后X #39; = X ♢SO ( i， j )被定义为新的在X上操作运符SO(i，j )之后的解序列 。 符号♢表示二进制操作交换操作。它可以给出一个具体的例子：假设有一个TSP同六节点，和X =(X 1，X 2，X 3，X 4，X 5，X 6)=(1，3，5，2，4，6)是一个解决方案序列。 让SO(2，4)，是一个交换操作者，然后X#39;= X♢SO(2,4)=(1，3，5，2，4，6)SO♢(2,4)=(1，2,5，3，4，6)，即交换X 的位置2和位置4的节点以创建新的解决方案序列 X #39; 。
交换顺序：一个特定的不同交换运算符的集合order被称为交换序列SS 。 设SS =(SO 1，SO2，...，SO N )，其中SO 1，SO 2， ...，SO N是交换运算符。 交换序列作用于解决方案意味着交换序列的所有交换运算符都作用于按顺序解决。 这可以通过以下公式来描述：
X #39; = X ♢SS = X ♢(SO 1，SO 2，...，SO N )=(......(( X ♢SO 1 ) ♢SO 2 )... ♢SO N )
作用于相同解决方案的不同交换序列可能产生相同的新解决方案 所有这些交换序列都被命名为等价物交换序列集。 在等价集中，具有的序列最少数量的交换运算符称为集合的基本交换序列或简称基本交换序列(BSS)。可以将几个交换序列合并到新的交换序列中。这里，运算符 oplus;被定义为两个交换序列的合并进入一个新的交换序列。 假设有两个交换序列，SS 1并且SS 2按顺序作用于一个解X，即SS 1首先，SS 2秒并获得新的解 X #39; 。 让另一个交换序列SS #39;作用于相同的解决方案X并获得解决方案X #39;，然后SS #39;称为SS 1和SS 2的合并，它表示为：
SS#39;=SS 1oplus;SS 2
这里，SS#39;和SS 1oplus;SS 2在相同的等效集。
基本交换序列的构建：假设有两个解决方案， A和B，我们的任务是构建一个可以的SSS，SS在 B上采取行动以获得解决方案A. 这里，SS定义为SS = A⊖B 。 所以运算符 ⊖表示两个城市序列之间的差异
显然这种差异由一些连续交换表示操作，即根据A从左到右交换 B中 的节点得到SS 。 所以必须有一个等式A = B ♢SS 。 例如，考虑一下两个解决方案。
A =(1，2，3，4，5)，B =(2，3，1，5，4)
在这里，A(1)= B(3)= 1，因此，第一个交换操作符是SO(1，3)。 然后SO 操作 (1，3)1 = B♢SO(1，3)获得关于B，新序列B如下：
乙 1 = B♢SO(1，3)=(1，3，2，5，4)，再次 A(2)= B 1(3)= 2，所以第二个操作者是SO(2，3)和operater-SO (2，3)上B 1，新的序列B 2作为获得
B 2 = B 1♢SO(2，3)=(1，2，3，5，4)类似地，第三操作者是SO(4，5)，和
乙 3 = B 2♢SO(4，5)=(1，2，3，4，5)= A，因此，BSS，SS = A⊖B =(SO(1，3)，SO(2，3)，SO(4，5))。
4.用于TSP的人工蜂群
ABC是由Karabog在2005年通过
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
