英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
摘要
本文通过多种更新规则和K-opt操作对人工蜂群算法进行了改进以解决旅行商问题。这里面向城市顺序（解序列/路径）的交换序列和交换算子用于创建不同的解序列（路径）更新规则算法。提出了八个不同的规则来更新算法中的解序列。雇佣蜂或观察蜂影响的解的更新是通过轮盘赌从规则集中随机选择完成的。在算法的侦察蜂阶段应用了扰动技术和K-opt操作，对任何停滞解进行一定次数的改进。K-opt操作是在搜索过程结束时再次使用以提高最终解的质量（如果可能）。用TSPLIB的一组基准测试问题对所提出的方法进行了测试，结果表明，与文献中已有的算法相比，该算法在求解标准TSP（对称和非对称）的精度和一致性方面是有效的。
关键词： 旅行商问题；人工蜂群算法；交换序列；交换算子；K-opt
1 综述
旅行商问题（TSP）是一个标准的离散组合优化问题。这个问题由一组其中任意两个顶点之间的距离已知的N个顶点（节点/城市）构成。推销员从一个顶点开始，精确地访问所有顶点一次并返回到起始顶点，使得总行驶距离最小。因此，问题的目标是找到一个尽可能短地遍历这组顶点，每个顶点除起始顶点外仅被访问一次的路径。这是众所周知的NP难题[1,2]，无法使用任意多项式时间算法精确解决。在TSP中，当任意两个顶点之间的距离xi和xj等于xj和xi之间的距离，则问题被称为对称TSP（STSP）[3,4]。另一方面，对于至少一对顶点来说，如果顶点xi和xj之间的距离不等于xj和xi之间的距离，则问题属于非对称TSP（ATSP）[5]。通常有两种方法可以解决TSP：精确方法和启发式方法。精确方法因为庞大的可组合方案N需要大量计算时间，因此通常用启发式方法解决TSP。确切的方法包括切割平面[6]，LP松弛[7]，分支和约束[8]，分支和剪切[9]等。只有小型带时间窗口TSP才能通过精确的方法以合理的方式解决。另一方面，一些TSP已使用启发式或基于软计算的技术，例如蚁群优化（ACO）[3]，本地搜索[10]，混合算法[11]，遗传算法（GA）[12]，粒子群优化（PSO）[4]，人工蜂群（ABC）[13]等。有几种完善的启发式方法用于STSP。 Wang等[4]使用交换运算符和交换顺序的概念，根据它们重新定义一些PSO运算符，以解决TSP。 结合PSO，ACO和3-opt混合算法的特征，Mahi等人提出了PSO-ACO-3-opt[14]以解决标准TSP。Akhand等[15]提出了带有局部搜索算法的PSO用于解决TSP。Akhand等[16]改进了该算法以查找TSP的解，并将其命名为速度暂定PSO。Geng等[17]提出了一种基于模拟退火（SA）和贪婪搜索技术的局部有效搜索算法来解决TSP。Jolai和Ghanbari [18]提出了一种应用改进的人工神经网络（ANN）解决TSP的方法。Dorigo等[3]提出了一种蚁群算法解决TSP。Dorigo和Gambardella[19]描述了一个能够解决TSP的ACO。Beam-ACO算法是结合了ACO和波束搜索的混合方法，也被用来求解TSP。Gunduz等[22]提出了一种新的基于群智能算法的分层方法解决TSP。Khan等[23]提出了一种基于ACO-PSO-K-otp的混合算法求解TSP。
Huang等[24]提出了一种基于PSO的求解算法。此外，建立了不同的方法解决其他NP难组合优化问题，例如车辆路线问题[25]，流水作业时间表问题[26]等等。最近，Rajasekhar等人[27]针对不同的蜂群算法进行了详细的调查，到目前为止已经针对不同类别的优化问题进行了开发。基于生物学观点和动机，他们提到了不同算法在各自类别问题中的前景，并与其他人算法比较。
从上面的讨论可以得出结论，启发式在可行时间窗内求解TSP问题的方法更为有效。自2005年以来，ABC已被证明可以成功实现持续优化问题，并这方面已经有效地完成了许多工作
[28-30]。ABC的一些离散版本已经被引入文献[26,31,32]。Karaboga和Gorkemli[13]提出了TSP的组合ABC算法。应用交换序列和交换算子的特点，Pan等人[26]提议了一个离散ABC方法求解批量流车间调度问题。Iqbal等人[33]提出了一种新的求解多目标问题的蜂群算法用于解决具有软时间窗的车辆路径问题。用于TSP时，任何启发式算法有时都会有收敛到局部最优解的问题。K-opt是一种微扰技术，它可以应用于行程解（路径）以克服这种收敛。实际上，K-opt是寻找TSP任意潜在解更好的邻域解使用最广泛的启发式方法。它的工作原理就像一个GA。K-opt是一种行程解改善算法，在每个步骤K中以K链接替换当前行程链接的方式实现了更短的行程[34]。
本文提出了一种新的ABC算法变体来解决STSP和ATSP。在这个算法中，八个不同的规则是用来指导雇佣蜂或观察蜂改进行程的。规则使用旅行商问题的一个潜在路径（解）和交换序 [16,35]。改进解规则是雇佣蜂或观察蜂从规则集使用轮盘赌（RW）随机选择[36]。
为了得到一个解而分配任务给侦察蜂，第一次K-opt操作应用于可能改进的迭代次数。如果不能改进现有解，解将随机再生。K-opt在算法的末尾再次被使用来提高最终解的质量（如果可能）。通行的方法是通过来自TSPLIB [37]的一组基准数据测试问题和评判解决标准TSP（ATSP和STSP）时的一致性，据观察，就准确性而言，算法的效率是足够与文献中现有算法相提并论的。
论文的其余部分安排如下：在第2节，给出了数学问题的表达式。在第3节中，讨论了交换序列和交换算子。在第4节中讨论了ABC。第5节介绍了K-opt操作。第6节提出算法。第7节讨论了实验结果。第8节是一个简短的结论。
2 问题描述
TSP可以用图来表示G = (V, E), V={1，2，hellip;.N}是顶点或节点的集合，E是边的集合。在这里，每个节点代表一个城市，每个边代表在两个城市之间的路径。每条边都表示与之相关的城市之间的距离。推销员旅行一定距离，经过N个城市（或节点）。在一次旅行中，他每个城市只游览一次，并以最短的旅行距离为目的结束他开始的旅程。设djk为第j城城和第k城之间的距离。那么这个模型可以用数学公式表示为[7]：
如果推销员从城市j到城市k，则Xjk=1，否则为0。
令（x1，x2 ...，xN，x1）代表推销员完整的路径，其中xjisin;V，forall;jisin;V并且所有xj都是不同的，即（x1，x2 ...，xN，x1）是推销员在城市中旅行的城市顺序。然后上述问题简化为[38]，
3 交换序列和交换算子
2003年Wang等人[35] 用粒子群算法求解tsp引入交换算子和交换序列的概念。潘等人[26]在DABC中使用这些操作来解决flow-shop调度问题。这些操作的简要说明如下。
交换算子：考虑具有N个节点的TSP，其具有节点集V={1，2，N}，其中xi isin; V且xi ne; xj, forall;i ne; j，它的自然解序列为X =（x1，x2，hellip;X N，x1）。这里，交换算子SO(i, j) 定义为节点Xi和节点Xj在解序列X中的交换。然后X′= X♢SO(i, j)被定义为一个新的，在原解X上操作算子SO(i, j)后得到的解序列。符号♢表示二进制交换操作运算符。给出一个具体的例子：假设有一个6节点的TSP问题，X = (x1, x2, x3, x4, x5, x6) = (1, 3, 5, 2, 4, 6)是其一个解序列。让 SO(2, 4)作为一个交换算子， X′ = X♢SO(2, 4) = (1, 3, 5, 2, 4, 6)♢SO(2, 4) = (1, 2, 5, 3, 4, 6)。原解序列X中的节点2和节点4交换位置得到新的解序列X′。
交换序列：不同交换算子按照一定顺序排列构成的集合称为交换序列SS。让SS=(SO1, SO2,hellip;, SON)，其中SO1,SO2,hellip;,SON是交换算子。交换序列作用于解意味着这个交换序列的所有交换算子按照一定的顺序作用于解。可以用下面的公式来描述：
X′ = X♢SS = X♢(SO1, SO2,hellip;, SON) = (hellip;((X♢SO1)♢SO2)hellip;♢SON)
作用于相同解的不同交换序列可能会产生相同的新解。所有这些交换序列的集合都被命名为等价交换序列集。在等价交换序列集中，具有最少数量的交换算子的交换序列被称为此等价交换序列集的基本交换序列或简称基本交换序列（BSS）。
几个交换序列可以合并为一个新的交换序列。此处，运算符oplus;定义为将两个交换序列合并为一个新的交换序列。假设有两个交换序列，SS1和SS2依次作用于一个解X，即SS1首先，SS2其次，得到一个新的解X。让另一个交换序列SS作用于相同的解X并得到解X，则SS 称为SS1和SS2的合并，它表示为：
SS′ = SS1oplus;SS2
这里，SS和SS1oplus;SS2在一个等价交换序列集中。
基本交换序列的构建：假设有两个解A和B，我们的任务是构建BSS，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)作用于解B得到新解B1：
B1 = B♢SO(1, 3) = (1, 3, 2, 5, 4)
又有A(2) = B1(3) = 2，第二个交换算子是SO(2, 3)，进而得到新解B2：
B2 = B1♢SO(2, 3) = (1, 2, 3, 5, 4)
同理，第三个交换算子是SO(4, 5)，得新解B3：
B3 = B2♢SO(4, 5) = (1, 2, 3, 4, 5) = A
要构建的基本交换序列BSS即为SS, SS = A⊖B = (SO(1, 3), SO(2, 3), SO(4, 5))。
4 人工蜂群算法
模仿蜜蜂在它们属地的觅食和摇摆舞行为，启发式的ABC由Karaboga在2005年为解决数值优化问题而提出[39]。ABC算法通常在一组随机生成于搜索空间的潜在解的基础上开始寻找优化问题的最优解。在算法中潜在解类似于不同食物源的位置。蜜蜂的目标是寻找最佳食物源，类似于问题的最优解。根据不同的行为，蜜蜂可以分为三类：雇佣蜂，观察蜂和侦察蜂。因此，算法的每次迭代都包含三个阶段，即雇佣蜂阶段，观察蜂阶段和侦察蜂阶段。第一阶段是雇佣蜂阶段。随机生成的一组解全部与雇佣蜂相关联。在雇佣蜂阶段每个雇佣蜂都会按照指定的规则改善自己的位置（即相应的解）以寻找更好的食物源（即改进后的解）。算法由一组观察蜂组成。完成雇佣蜂阶段后，观察蜂阶段开始。在这个阶段每个观察蜂根据解自身的适应度在这一组解中选择一个解并尝试改进它。每个解与一个计数器相关联，其值在首次迭代时设为0。如果一个解没有被它的雇佣蜂或者任何观察蜂所改进，它的计数器就会增加一个。在最后一个阶段，即侦察蜂阶段，所有的解都被检查一遍。如果发现一个解在预定义的迭代次数中没有被雇佣蜂或者观察蜂改进，那么它将被视为停滞解并被分配给侦察蜂。侦察蜂随机再生它并使其计数器归零。在期望的ABC变体中考虑在侦察蜂阶段对侦察蜂使用K-opt操作改进一轮迭代得到的解。如果有找到任何改进，那么解进入下一轮迭代，并返回其计数器值，否则侦察蜂会随机再生它并把计数值设置为零。K-opt操作在第5节中讨论。此外，类似于Kiran等人[28]，这里提出了一组更新解的规则（适用于tsp），用于雇佣蜂或观察蜂更新解。在它们工作的时候，雇佣蜂或者观察蜂通过合适的选择过程从这组规则集中选择一种规则，并利用此规则尝试改进它的解。经过以上讨论，要使用拟定的ABC解决TSP，在此简要讨论其不同的步骤和过程。如果在ABC算法中，每个食物源都代表该问题的潜在解，那么在这里，将一系列节点作为解（食物源），就可以被认为是TSP。所以初始解集里的每一个解Xi是在解空间中随机生成的（3）。
Xi = (xi1, xi2,hellip;xiN, xi1), i = 1, 2,hellip;fs (3)
其中，xijisin;V，j = 1，2，...，N，V = {1，2，... N}是节点集，对于jne;k，xijne;xik，fs是解集。在通过等式（3）初始化所有解之后，每个解都分配给一个雇佣蜂，即解的数量等于雇佣蜂的数量
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236775]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
