英语原文共 7 页
边缘粒子群算法:一种基于重组算子的粒子群算法求解旅行商问题的算法
Vaisakh Shaj，Akhil P M，Asharaf S
喀拉拉邦印度信息技术与管理学院，特里凡得琅科学与信息技术学院，印度空间科学与技术学院数学系
摘要：我们提出了一种用粒子群算法求解旅行商问题的新方法，即智能利用边缘重组算子的边缘粒子群算法。我们观察到，最初为遗传算法提出的边缘重组算子可以用作粒子群优化的速度算子，以便在每次迭代中有效地将搜索引向对应于解空间的超立方体的更好的角，从而显著减少寻找最优解所需的迭代次数。边缘粒子群算法不仅提高了收敛速度，而且能够产生接近最优的解，即使不使用局部搜索过程，其精度也优于遗传算法
关键词：粒子群优化、旅行推销员问题、边缘重组算子
导言
在过去的20年里，许多重组算子被成功地提出，用于在遗传算法中求解旅行商问题。事实上，基于遗传算法的旅行商问题的解决方案已经影响了迭代学习算法的发展。然而，大多数关于重组算子的研究都集中在遗传算法上，考虑到它可能被用作交叉算子。
粒子群算法是一种受鱼群或鸟群行为启发的进化计算技术。粒子群算法首先由Kennedy和Eberhart提出，用于优化连续非线性函数。这种元启发式方法的基础依赖于计算机模拟社会生物运动的研究。粒子群算法的成功和流行是由于在标准粒子群算法中只使用了少量必须调整的参数，也是由于基于这种技术的算法易于实现。
粒子群算法的研究已经能够为许多关于单目标和多目标优化的应用带来最新的结果。鉴于粒子群算法在连续问题上取得了成功，处理离散优化问题的研究人员已经研究了如何使原始方案适应离散情况。在许多这样的研究中，新的方法是用旅行商问题来说明的，因为它是优化中研究最深入的问题之一。TSP作为一个一般的NP完全问题，可以发展为属于NP-complete类的任何其他问题的可行解方案。随着城市数量的增加，旅行商问题的计算复杂度呈指数级上升，使得不可能在合理的时间内解决非常大规模的实例。对于n个城市的对称问题，有(n-1)！/2中可能的路径。假设评估一条路径所需的时间为1秒，表1列出了TSP的计算复杂度。
说回到重组算子，据我们所知，还没有研究探索重组算子与粒子群算法相结合的可能性。研究表明，重组算子可以有效地用于粒子群算法中的速度运算，促进粒子群算法向局部和全局最小值移动。实验结果表明，这种重组算子的智能使用倾向于将搜索扩展到解空间的“更好”的角落。尽管从以前的文献中有许多重组算子的选择，但我们选择了边缘重组算子，因为它的计算复杂度低，并且展现了Radcliffe和Surry所提及的传递等位基因的尊重重组。在这种情况下，等位基因是在父代解中发现的边缘。一个尊重操作者确保双亲共享的所有公共边都被继承；如果后代只使用从双亲遗传的边来构建，那么操作者传递等位基因。Whitley最近提出的分区交叉也满足同样的条件。然而在本文中，我们将集中讨论边重组算子。后者可以作为未来的工作方向。
本文的其余部分安排如下：第2节简要介绍了这一领域的相关工作，包括重组算子的历史、研究人员以前使用粒子群算法求解旅行商问题的方法以及对边缘重组算子进行了简要描述。在第3节中，我们介绍了所提出的算法，并讨论了它与经典粒子群算法的区别。第4节介绍了从TSPLIB中选择数据集进行实验所获得的结果，并分析了与遗传算法相比较的收敛性。第5节对论文进行了总结。
相关著作
2.1 重组算子的历史
TSP可应用于多种情况，包括印刷电路板、微芯片和超大规模集成电路的设计，X光结晶学，规划，物流，脱氧核糖核酸测序等。为问题提供精确最优解决方案的方法称为精确方法。求解旅行商问题的一个隐含方法是简单地列出所有可行的解决方案，评估它们的目标函数值，并选出最好的。然而，如前一节所述，即使问题规模小到20个城市，也是不切实际的。由于实际应用涉及解决更大的问题，自然重点已经从启发式地在合理的时间和合理的准确度内获得好的解决方案转移到了。遗传算法是求解旅行商问题最广泛使用的启发式算法之一。
在遗传算法中，种群的解或个体通常被编码为N个城市的排列，由于交叉算子（在本文中也被广泛称为重组算子）在遗传算法中起着至关重要的作用，因此许多交叉算子被提出用于求解旅行商问题。
我们将依赖Radcliffe文章中的概念来形式化重组算子的性质，以便评估这些性质。为了得到好的重组的Radcliffe-Surry条件需要尊重传播所有基因的重组。更准确地说:
“当且仅当重组算子产生的每个子代都包含其双亲共有的所有等位基因时，重组算子才算是尊重一个代表。”
然而，尊重一词并不要求所有的边都来自父母中的任何一方，这一点在另一个叫做传输的概念中得到了体现。
“当且仅当它所产生的每个子代中的每个等位基因至少存在于它的一个亲本中时，重组算子才被称为传递与给定(正式)等位基因表达相关的等位基因。”
TSP的早期重组算子包括：1) )Grefensette的贪婪交叉，2)循环交叉[4]和3) Goldberg和Lingle的部分映射交叉（PMX）。这些方法都不是特别有效，部分原因是它们不能满足Radcliffe-Surry条件，即尊重传递等位基因的重组（本例中为边缘）。
为了寻找满足Radcliffe-Surry条件的算子，我们研究了Whitely提出的边缘重组和分区交叉算子。因此，我们的优势是减少了重组过程中的中断，这意味着相关性将会增加
2.2 边缘重组算子
Whitely于1989年提出了边缘重组算子（ERO）。重组操作符以非结构化、有意义的方式重组来自父结构的关键信息，从而产生合适的路径。这里的想法是使用尽可能多的现有边或节点连接来产生新的合法旅游。ERO基于邻接矩阵，它列出了任何父节点的邻居。例如，考虑路径[A B C D E F]和[C A B D E F]。选择每个城市配置项并形成邻接表，其中每个条目对应于来自双亲的配置项的相邻城市。在这种情况下，邻接表如下所示。
表里为双亲共有的节点加上负号，以保留孩子中双亲旅行的公共边（由此产生的ERO版本称为增强边重组算子或边缘-2算子）。现在选择任一父节点的起始节点，让它为A。从相邻节点列表中删除所有出现的A。如果A的邻接表包含一个带负号的节点，则首先选择它，否则选择在其自己的邻接表中节点数最少的节点（联系可以随机解决）。将所选节点添加到子路径，从邻接表中删除该节点的所有出现。继续该过程，直到所有节点都添加到子路径中。在这种情况下，[A B C F E D]是一个可能的有效的子路径（这可能会根据每个点选择的随机性而有所不同）。Whitely用荷兰的图式理论证明了操作者不仅产生了很少破坏边的合法路径，而且存在一种二元表示，可以用来跟踪“边重组”如何将搜索移动到对应于问题解决空间的超立方体的不同角落。
2.3 粒子群优化算法
在经典粒子群算法中，每个粒子被分配一个位置和速度。除此之外，每个粒子都知道它迄今为止到达的最佳位置和所有粒子中的全局最佳位置。
迄今为止，一个粒子达到的最佳位置称为pbest，而所有粒子中的全局最佳位置称为gbest。在每次迭代中，每个粒子分别基于公式（1）和（2）计算其速度并更新其位置。
其中v(t)表示速度，x(t)表示粒子在时间t的位置。
这里c1被称为惯性因子，它控制粒子相信自己飞行经验的程度。c2和c3分别被称为认知系数和社会系数；c2控制pbest的影响量，同时计算新速度，c3控制gbest的影响量。rand1和rand2是范围（0，1）内的随机数。
上述算法可视为传统的粒子群算法，适用于连续问题。然而，它不能直接应用于离散问题。过去曾有人尝试修改粒子群算法，使其适合离散问题实例。针对离散问题，Kennedy和Eberhart提出了粒子群算法的离散二进制版本，根据比特将处于一种或另一种状态的概率来定义粒子轨迹和速度。
Clerc提出了解决TSP问题的粒子群优化方法的一个大纲。在他的研究中，他对TSP的离散问题和相关运算的位置和速度项进行了精确的重新定义，例如：速度的反向，位置和速度的加法（移动），两个位置的减法，两个速度的加法和减法，以及速度乘以常数。这是首次在这一方向进行的研究工作之一，得出粒子群算法可以应用于TSP的结论。然而，已解决问题的规模都小于17个城市。Hendtlass试图给粒子群算法中的每个粒子增加内存，并将其应用于求解旅行商问题，提高了其性能。Wang等人引入了“交换算子”和“交换序列”的概念来重新定义粒子群算法运算，从而利用粒子群算法解决TSP问题。然而，他们解决的问题实例的大小都是14（两者都选择了Burma14的TSPLIB标准实例，有14个城市）。使用基于粒子群算法解决的旅行商问题的规模似乎是有限的。后来，通过与遗传算法、蚁群算法等混合，并结合局部搜索方法和其他高成本问题的特定操作，对上述算法进行了一些修改。
提议的算法
在本文中，我们利用重组算子的概念来研究一个离散版本的粒子群优化算法，从而解决对称TSP问题。我们打算展示已经纳入边缘重组算子的粒子群优化算法惊人的高搜索能力。 由于我们的主要目的是研究这个特定的低成本算子的搜索能力，所以我们在最初的实验中没有使用前面文章中所做的任何局部搜索启发算法。
3.1 边缘粒子群算法
粒子的位置代表了根据N个城市排列的路径。分配给每个粒子的值用旅行商目标函数计算，即路径长度。速度被定义为 (i，j)的列表，其中i和j是将被交换的置换向量的元素的索引。
在我们的算法中，我们使用了不同速度算子的概念，即在每个迭代步骤中，三个可选行为之一（惯性、朝向pbest、朝向gbest）被分配给一个粒子，并且应用相应的速度算子来修改粒子位置。对于每个粒子，每次迭代只允许一种类型的移动。这个步骤在第2节中有详细解释。因此，在我们的例子中，公式（1）被修改如下所示。
其中c1、c2、c3{ 0，1}且c1 c2 c3 = 1。v2和v3的计算公式为：
x(t) otimes; pbest代表当前粒子位置和pbest之间的边缘重组操作。类似地，x(t) otimes; gbest代表当前粒子位置和gbest之间的重组。在该步骤之后，使用反向序列变异算子（RSM）的变异步骤被应用于粒子位置x(t)，这有助于保持该算法的探索和开发之间的平衡，并且避免早熟收敛，这是基于粒子群算法的典型行为。算法1为所提出方法的伪代码。
3.2 速度上升的参数
在所提出的算法中，与认知系数和社会系数相比，惯性因子最初在控制粒子运动时被赋予较高的值。随着迭代次数的增加，惯性因子的影响逐渐减小，另外两个系数控制运动。在最后的迭代中，最大的概率与朝向gbest相关联，而最小的概率与继续其当前方向相关联。满足该标准的速度更新参数的选择有助于在探索和选择之间建立更好的平衡。它将在算法开始时促进探索，并在最终迭代中促进选择，从而快速收敛。速度系数激活的概率公式如下：
p(c1)= 0.95 - 0.95 * t/T
p(c2)=0.05 0.95 * t/T
p(c3)=0.05 0.95 * t/T
其中，t是当前迭代次数，T是给定的最大迭代次数。p(ci)表示ci获得值1的概率。基于这些概率，c1、c2、c3中的一个被激活，则其在更新粒子速度的同时控制粒子的飞行方向。这里，T被设置为5n，其中n是城市的数量，来自于实验观察到的收敛点的上界。
实验结果
七个经典的例子来自TSPLIB（gr 17, fri 26, dantzig 42, berlin 52, eil 76, rat 99, kroA 100）被用来比较所提出的方法在经典遗传算法和边缘重组交叉上求解TSP的性能。所有实验都是在英特尔电脑（酷睿i5 @ 2.2千兆赫中央处理器，4GB内存）上进行的，粒子数固定为60。表2给出了所提出的边缘粒子群算法实验的结果。为了得到平均迭代次数和平均解，所有问题实例被执行20次，结果取平均。在该表中，最好值是我们使用边缘粒子群算法获得的最佳结果，最优解是迄今为止针对该问题获得的最佳解（摘自TSPLIB）。这里的相对误差为：
通过使用遗传算法求解同一组问题，将所提出算法的性能与使用边缘重组交叉的遗传算法进行了比较。表3显示了获得的结果。表2和表3之间的比较清楚地表明，与遗传算法相比，边缘粒子群算法所需的迭代次数少得多。边缘粒子群算法的相对误差也较小。
为了更好地理解收敛性，我们绘制了路径长度相对于迭代次数的变化。图1和图2显示了问题fri 26和dantzig 42与遗传算法（使用边缘重组交叉）相比的收敛性。从图表中很容易理解，边缘粒子群算法比基于边缘建议交叉的遗传算法具有更好的收敛速度和求解质量。这清楚地表明，边缘重组算子比遗传算法更适合粒子群算法。
对于这种结果上的改进，一个可能的解释是与遗传算法不同，边缘粒子群算法有交互能力，即它总是一个健康的个体(全局最佳或局部最佳)，如图3所示。由于满足传递等位基因的尊重重组的Radcliffe-Surry条件，边缘重组算子产生的后代往往是健康的，同时也是多样的，因此能将搜索扩展到解空间的更好的角落。
在我们最初的实验研究中，我们考虑了多达100个城市的规模问题，并且没有使用任何局部搜索程序来微调最终结果，因为我们的目的是测试当与粒子群算法集成时重组算子的搜索能力。与最初引入算子的遗传算法相比，结果非常令人满意。由于该算法的复杂度低至O(n)，因此可以通过增加2-opt、3-opt或Lin Kernighan等局部搜索程序，轻松扩展到求解具有更多城市的旅行商问题。表4
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
