边缘粒子群算法：一种基于重组算子的求解TSP的粒子群算法

Edge-PSO : A Recombination Operator Based PSO Algorithm for Solving TSP

摘要

我们提出了一种利用粒子群算法求解TSP的新方法，即通过智能使用边缘复合算子的边缘粒子群算法。我们观察到，最初为遗传算法提出的边缘重组算子可以用作粒子群优化的速度算子，以便在每次迭代中有效地将搜索指向超立方体中与解空间相对应的更好的角点，从而显著减少找到最优解所需的迭代次数。边缘PSO算法不仅提高了收敛速度，而且可以产生接近最优的解，即使不使用TSPLIB标准实例的局部搜索过程，其精度也优于GA算法。

一、 简介

在过去的20年中，许多重组算子已经成功地开发出来，用于求解旅行商问题（TSP）。事实上，基于GA的TSP解决方案影响了迭代L-K算法的发展[17]。然而，大多数关于重组算子的研究都集中在遗传算法上，并考虑到其作为交叉算子的可能性。

PSO是Kennedy和Eberhart提出的一种计算方法，它模拟鱼群或鸟群的行为，以优化连续非线性函数[1][2]。这种元启发式方法的基本原理依赖于计算机模拟社会生物运动的研究[18][19][20]。事实上，在标准PSO算法中，只需调整少量参数，而且易于实现，这导致了PSO的成功和普及。

PSO算法的研究已经能够为单目标和多目标优化的许多应用程序产生最先进的结果[1][2]。受连续问题PSO算法成功的激励，处理离散优化问题的研究人员已经研究了将原始方案适应离散情况的方法。在许多研究中，新方法都以旅行推销员问题为例进行了说明，因为它是优化中研究最深入的问题之一。TSP作为一个一般的NP完全问题，可以发展为任何其他属于NP完全类的问题的容许解。TSP的计算复杂性随着城市数量的增加呈指数级增加（)，因此不可能在合理的时间内解决非常大的实例。对于n个城市的对称问题，有（n-1)!/2次可能的旅行。假设评估路径所需的时间为1s，表I显示了TSP的计算复杂性。

回到重组算子，据我们所知，在探索重组算子与粒子群优化算法结合的可能性方面，还没有进行过研究。我们表明，重组算子可以有效地用于粒子群优化中的速度运算，从而促进向局部和全局最小值移动。经验结果表明，这种对重组算子的智能使用倾向于将搜索扩展到解空间的更好角落。虽然在以前的文献[3]到[8]中有许多重组算子可供选择，但我们选择了边缘重组算子[7]，因为它的O(n)计算复杂度低，并且显示了Radcliffe和Surry[23]所称的传递等位基因的尊重重组。在这种情况下，等位基因是在母体溶液中发现的边缘。通过尊重操作符，一种方法是继承两个父项共享的所有公共边；据说，如果后代仅由两个父母遗传的边缘组成，则操作员会传递等位基因。另一个选择是whitley最近提出的分区交叉[8]，它也满足相同的条件。然而，在本文中，我们将集中讨论边缘复合算子。后者可以作为未来的工作。

 本文的其余部分组织如下：第二节简要介绍了该领域的相关工作，包括重组算子的历史、边缘重组算子的简要概述以及文献中使用粒子群优化算法求解TSP的先前尝试。在第三节中，我们介绍了所提出的算法，并讨论了它与TSPLIB[10]所选问题的不同之处，边缘粒子群优化算法的收敛性分析与基于边缘重组算子的遗传算法的比较，最后我们报告了所提算法与其他进化算法在较大城市问题上的性能比较。第五节对论文进行了总结。

二、相关工作A。

重组操作的历史

TSP在各种情况下都有应用，包括印刷电路板、微芯片和VLSI电路的设计[21]、X射线结晶学[22]、规划、物流、DNA测序等。能够为这个问题提供精确解决方案的算法称为精确TSP算法。最直接的解决方案是尝试所有排列（有序组合），看看哪一个最便宜（使用暴力搜索）。然而，如前一节所述，即使问题规模小至20个城市，这也是不切实际的。由于实际应用涉及解决更大的问题，自然重点已经从以启发式的方式在合理的时间和合理的精度内获得好的解决方案转移到了。遗传算法（GA）是用于求解TSP实例的最广泛的启发式算法之一。

在遗传算法的情况下，种群的解或个体通常被编码为N个城市的排列，由于交叉算子（在本文中也称为重组算子）在遗传算法中起着重要作用，许多交叉算子已被开发用于TSP的离散问题。

我们将依赖于Radcliffe的工作[23]中的概念来形式化重组算子的属性，以便对其进行评估。Radcliffe和Surry条件[23]对于良好重组涉及传递所有基因的相应重组。更准确地说：

“当且仅当重组算子所产生的每个子代都包含其双亲共有的所有等位基因时，据说重组算子尊重一种表示。”

然而，尊重这个术语并不要求所有的边缘都来自父母中的任何一方，这在另一个称为传播的概念中得到了体现。

“当且仅当重组算子所产生的每个子代中的每个等位基因至少存在于其父母中的一个时，称重组算子就给定的（正式的）等位基因表示传递等位基因。”

TSP的早期重组算子包括1）Grefensette的贪婪交叉[3]，2）循环交叉[4]和3）Goldberg和Lingle的部分映射交叉[5]。这些都不是特别有效的，部分原因是它们不能满足Radcliff Surry条件[23]，即传递等位基因的尊重性重组（本例中为边缘）。

在寻找满足Radcliff Surry标准的运算符时，我们遇到了由Whitely提出的Edge Recombination[7]和Partition Crossover[8]运算符。因此，我们具有在重组过程中减少破坏的优势，这意味着父母和后代的适应度之间的相关性将增加，因为后代仅由父母的边组成，并且具有相同的公共边。此外，这些算子的计算复杂度仅为O（n），这使得它们适用于大型城市问题。

B、 边缘重组算子

边缘复合算子（ERO）由Whitley于1989年提出[9]。重组操作符以非破坏性、有意义的方式重新组合来自父结构的关键信息，从而产生合法巡视。这里的想法是使用尽可能多的现有边或节点连接来生成新的合法路线。ERO基于邻接矩阵，该矩阵列出了任何父节点中每个节点的邻居。例如，考虑旅游[A B C D E F]和[C A B D E F]。选择每个城市Ci并形成邻接列表，其中每个条目都对应于父级Ci的邻接城市。在这种情况下，相邻列表如下所示

 这里，为父节点和父节点的公共节点加一个减号，以保留父节点在子节点中的公共边（ERO的最终版本称为增强边复合算子或边2算子[7]）。现在选择任一父节点的起始节点，使其为A。从相邻列表中删除A的所有匹配项。如果A的邻接列表包含一个带负号的节点，则首先选择该节点，否则选择其邻接列表中节点数最少的节点（可以随机解析关系）。将所选节点添加到子巡更中，从相邻列表中删除该节点的所有匹配项。继续该过程，直到所有节点都添加到子巡更中。在这种情况下，[A B C F E D]可能是有效的儿童巡演（这可能会因每个点的随机选择而有所不同）。惠特利利用霍兰德的图式理论[7]证明，操作员不仅可以生成对边几乎没有破坏的合法巡游，而且存在一个二进制表示，可以用来跟踪“边重组”如何将搜索移动到对应于问题解决空间的超立方体的不同角点。

C.粒子群优化

在经典的粒子群优化算法中，每个粒子都被指定了位置和速度。除此之外，每个粒子都知道

•迄今为止达到的最佳位置。

•所有粒子中的全局最佳位置。

到目前为止，粒子达到的最佳位置称为pbest，而所有粒子中全局最佳的位置称为gbest。在每次迭代期间，每个粒子都会计算其速度，并分别基于方程（1）和（2）更新其位置。

 式中，v（t）表示速度，x（t）代表粒子在时间t处的位置。

这里，c1被称为惯性因子，它控制着粒子对自身飞行经验的信任程度。c2和c3分别称为认知系数和社会系数；c2在计算新速度时控制来自pbest的影响量，c3控制来自gbest的影响的量。rand1和rand2是范围（0,1）内的随机数。

上述算法可视为传统的粒子群优化算法，适用于连续问题。然而，它不能直接应用于离散问题。过去曾尝试修改PSO算法，以便将其应用于离散问题实例。针对离散问题，Kennedy和Eberhart[1][2]提出了离散二进制PSO算法，通过根据比特处于一种状态或另一种状态的概率定义粒子轨迹和速度。

Clerc[11]提出了求解TSP问题的PSO方法的简要概述。在他的工作中，他精确地重新定义了TSP离散问题的位置和速度项以及相关操作，例如：速度的反义词、位置和速度的加法（移动）、两个位置的减法、两个速度的加减法以及速度乘以常数。这是在这个方向上所做的首批研究工作之一，得出了PSO方法可以应用于TSP的结论。然而，解决问题的规模都小于17个城市。Hendtlass[15]尝试在PSO算法中为每个粒子添加内存，并将其用于求解TSP，从而提高了其性能。Wang等人[16]引入了“交换算子”和“交换序列”的概念，以重新定义PSO操作，从而使用PSO解决TSP问题。然而，[15]和[16]中解决的问题实例的规模都是14个（它们都选择了缅甸的TSPLIB基准实例14个城市）。使用基于粒子群优化算法解决的TSP问题的规模似乎是有限的。后来，通过与GA、ACO等混合，并结合本地搜索方法和其他高成本的问题特定操作，对上述算法进行了一些修改。[12] [13] [14] [24].

三、 提出算法

在本文中，我们利用重组算子的概念开发了一种离散版本的粒子群优化算法，用于解决对称TSP问题。我们打算展示边缘重组算子在融入粒子群优化算法时所具有的难以置信的高搜索能力。由于我们的主要目标是研究这个特定的低成本算子的搜索能力，因此我们没有像之前的论文[12][13][14]在我们的初始实验中那样使用任何局部搜索启发式。

A、 边缘PSO

粒子的位置表示N个城市的排列。分配给每个粒子的值是使用TSP目标函数计算的，因此与巡更长度相对应。速度定义为成对列表（i，j），其中i和j是将要交换的置换向量元素的指数。

在我们的算法中，我们使用了不同速度操作符的概念[12]，即在每个迭代步骤中，将三个可选移动（惯性、朝向pbest、朝向gbest）中的一个指定给粒子，并应用相应的速度操作符来修改粒子的位置。对于每个粒子，每次迭代只允许一种类型的移动。B小节详细解释了这一步骤。因此，在我们的例子中，方程式（1）修改如下。

 x（t）⊗ pbest表示当前粒子位置和pbest之间的边缘复合操作。同样，x（t）⊗gbest表示当前粒子位置和gbest之间的复合。在此步骤之后，使用反向序列变异（RSM）算子[27]将变异步骤应用于粒子位置x（t），这有助于在探索和利用此算法之间保持平衡，并避免早熟收敛，这是基于粒子群优化算法的典型行为。算法1显示了所提方法的伪代码。

B、 速度更新参数

在所提出的算法中，与认知系数和社会系数相比，惯性系数在控制粒子运动时具有较高的概率。随着迭代次数的增加，惯性因子的影响逐渐减小，其他两个系数在控制运动中起主导作用。在最后的迭代中，最高的概率与走向gbest有关，而最低的概率与继续沿着当前方向前进有关。选择满足此标准的速度更新参数有助于在勘探与开发之间建立更好的平衡。这将促进算法开始时的探索，并促进在最终迭代中的利用，从而实现快速收敛。方程式[12]中速度系数的激活概率公式如下。

其中t是当前迭代，t是给定的最大迭代次数。p（c i）表示c i得到值1的概率。基于这些概率，c 1、c 2、c 3中的一个被激活，它在更新粒子速度的同时控制粒子的飞行方向。这里T设为5n，其中n是城市的数量，我们根据观测到的收敛点上界计算得出。

四、 实验结果

使用TSPLIB[10]中的七个经典示例（gr 17，fri 26，dantzig 42，berlin 52，eil 76，rat 99，kroA 100），将所提出的方法与经典遗传算法的性能进行比较，使用边缘重组交叉求解TSP。所有实验都是在Intel PC（内核i5@2.2GHz CPU，4GB RAM）上进行的，粒子大小固定为60。表II给出了建议的边缘PSO的结果。为了获得平均迭代次数和平均解决方案，所有问题实例执行20次，并对结果进行平均。在表中，最佳解是我们使用边缘PSO算法获得的最佳结果，而最佳结果是迄今为止针对该问题获得的最佳解（摘自TSPLIB[10]）。此处相对误差估计为

通过使用GA解决同一组问题，将所提算法的性能与GA（使用边缘重组交叉）进行了比较。表III显示了所得结果。表II和表III之间的比较清楚地表明，边缘粒子群优化算法相对于遗传算法所需的生成/迭代次数要少得多。而且边缘粒子群算法的相对误差要小得多。

为了更好地理解收敛，我们绘制了旅游成本与迭代次数的变化。图1和图2显示了与GA（使用边缘复合交叉）相比，问题fri 26和dantzig 42的收敛性。从图中可以很容易地看出，边缘粒子群优化算法比基于边缘复合交叉的遗传算法具有更好的收敛速度和解的质量。这清楚地表明边缘复合算子比遗传算法更适合于粒子群优化。

结果改善的一个可能解释是，与GA不同，边缘PSO始终是健康个体（全球最佳或本地最佳），如图3所示。边缘重组算子，因为满足了传递等位基因的相互尊重重组的Radcliffe和Surry条件，结果产生的后代往往同时健康多样，因此将搜索范围扩展到解决方案空间的更好角落。

在我们最初的实证研究中，我们考虑了规模高达100个城市的问题，并且没有使用任何本地搜索程序来微调最终结果，因为我们的目标是测试重组算子与粒子群优化算法结合时的搜索能力。与最初引入算子的GA相比，结果非常令人满意。由于算法的复杂性小到O（n），因此可以很容易地扩展到求解具有更多城市的TSP，并添加2-opt、3-opt或Lin Kernighan等本地搜索程序。表IV显示了与简单的2-opt局部搜索混合时算法的性能，每个粒子在第一次迭代时停止，种群大小与以前一样固定为60。

结果表明，局部搜索程序的加入进一步减少了迭代次数，使收敛结果如预期的那样，对于较大的城市问题，得到了高质量的解决方案。

最后，我们尝试将edgePSO算法与其他流行的基于群体智能的优化技术进行性能比较。由于粒子群算法求解TSP的结果很少，这给了更难的基准问题的结果，所以我们参考了[24]，这是用粒子群算法解TSP的最流行的论文之一。从表五可以明显看出，从文献[24]可以看出，边缘粒子群优化算法优于这种流行的离散粒子群优化（DPSO）算法。与其他流行的算法（如ACO[25][26]）相比，边缘粒子群优化算法似乎能给出有竞争力的解，这些算法通常用于通过图形找到好的路径，即使问题实例多达442个城市。我们相信，将边缘粒子群算法与其他进化算法和更好的局部搜索程序（如3-opt或Lin Kernighan）相结合，可以进一步改善结果。

五、结论

本文利用重组算子的概念开发了用于求解对称TSP问题的粒子群优化算法的离散版本。我们提出了一个称为边缘PSO的新框架，其中我们使用边缘复合算子重新定义PSO中的相关移动。在TSPLIB基准问题的收敛速度和解的质量方面，新算法明显优于基于边缘重组交叉的GA。我们表明，PSO算法（通常被视为针对TSP等离散问题实例的弱算法）可以以合理的精度和较低的计算成本解决更大的城市问题。作为未来的工作，可以探索使用改进版本的边缘重组算子和其他最先进的重组算子（包括分区交叉）的可能性。此外，我们希望这项工作将鼓励研究人员开发更多的重组算子，同时牢记PSO所鼓励的正常与健康相互作用的肥厚本质。