基于聚类的遗传算法解决旅行商问题

基于聚类的遗传算法解决旅行商问题摘要：遗传算法〔GA〕是解决旅行商问题〔TSPs〕的有效方法，然而，传统的遗传算法〔CGA〕对大规模旅行商问题的求解效果较差。为了克服这个问题，本文提出了两种基于聚类的改良的遗传算法，以寻找TSPs的最正确结果。它的主要过程是聚类、组内演进和组间连接操作。聚类包括两种方法来将大规模TSP划分为假设干子问题，一种方法是k-均值〔k-means〕聚类算法，另一种是近邻传播〔AP〕聚类算法。每个子问题对应于一个组。然后我们使用GA找出每个子问题的最短路径长度。最后，我们设计一个有效的连接方法将所有这些组合成为一个，以得到问题的结果。我们尝试在基准实例上运行一组实验，用来测试基于k-means聚类〔KGA〕和基于AP聚类〔APGA〕遗传算法的性能。实验结果说明了它们有效性和高效的性能。将结果与其他聚类遗传算法进行比拟，说明KGA和APGA具有更强的竞争力和有效性。关键词：大规模旅行商问题；遗传算法；聚类；k-means聚类；AP聚类一、引言旅行商问题〔TSP〕是在所有城市搜索最短哈密尔顿路线的问题。TSP是众所周知的NP-hard问题。它有许多现实世界的应用[1,2]，如规划调度、物流配送、计算机网络和VLSI路由。近年来研究人员已经研究了不同类型的TSP[3-6]。TSP问题可以用如下方式描述：有座城市，给出城市之间的距离矩阵为。TSP问题的要求是从所有路径中找到最短路径。如果被定义为在步骤中访问的城市，那么路线可以被看作城市从1到的循环排列。路线的表达式如下：〔1〕如果对于，距离满足，那么这种情况是对称TSP。TSP可以模型化为加权图。每个顶点代表一个城市，每个边缘连接两个城市。边的权重表示两个相连的城市之间的距离。现在一个TSP问题实际上是一个哈密尔顿回路，最优的TSP路径是最短的哈密顿回路。用于求解TSP的算法可以概括为两类，精确算法和启发式算法。精确的算法确保最终解决方案是最优的。分支切割算法是这一类中的典型例如[7,8]。这些算法的关键问题是它们相当复杂，并且在计算机性能方面非常苛刻[9]。自引入模拟退火[10]和禁忌搜索[11]以来，启发式算法有可能突破局限，从而找到路径的局部最优解。在过去的二十年中，提出了大量的自然启发或群体智能方法，例如蚁群算法[12,13]，粒子群算法[14]和遗传算法[15,16]来解决TSP问题。遗传算法〔GA〕是一种通过模拟自然演化过程来搜索最优解解决大规模搜索问题〔例如TSP问题〕的有效方法，GA的目的是通过几个遗传操作，如选择、交叉和突变获得大规模搜索问题的近似解。与其他精确搜索算法相比，其优点主要是通过使用群体的信息而不是仅仅一个个体来实现搜索[5]。除了上述内容之外，GA通过适应度函数的数值来评估个体的质量，减少当使用启发式算法时被浸入在局部最优解中的风险。虽然GA是解决TSPs的有效方法，但是，随着旅行城市的数量增长，经典遗传算法效果较差。为了使TSP问题变得更容易并且可以有效地解决大规模TSP，本文提出了两种改良的基于聚类的遗传算法，分别称为KGA和APGA。首先，KGA和APGA使用聚类方法将大规模TSP划分为假设干子问题，每个子问题对应于一个组。在KGA和APGA中分别采用k-means和AP聚类方法。然后，我们使用GA找到每个聚类的最短哈密顿回路。所有这些集群可以并行处理。最后，我们设计有效的连接方法将这几个组合并为一个整体，以实现缩短整个路线的目的。本文的其余内容以此方式描述：第二节提出了两种聚类方法，包括k-means和近邻传播〔AP〕。第三节描述了基于k-means聚类〔KGA〕的遗传算法和基于AP聚类〔APGA〕的遗传算法。然后在第四局部，提供实验和比拟结果。最后，我们在第五节结束本文。二、聚类方法A、K-means聚类K-means是一种普遍的无监督智能算法，由于其简单性[17]，广泛应用于各种领域，如数据挖掘。这个想法是将一组样本分成几个组〔簇〕，其中每个对象具有类似于另一个对象的特征。我们选择群集内最远的距离并标记它。该算法需要随机地产生对聚类的个初始中心点的选择。我们称之为中心。首先，计算从每个对象到其他聚类中心的距离，并将所有对象划分为距离最小的组。其次，根据上一步，重新计算每个集群中心。我们重复这两个步骤，直到中心不再改变，以实现收敛稳定。我们使用Euclidean距离来计算顶点和集群之间的距离。聚类的目的是优化以下函数：(2)其中是聚类的数量，是顶点〔或城市〕的数量，是顶点的坐标，是聚类的坐标，是属于聚类的顶点组。该算法可以通过在空间中移动聚类中心来获得最短的平方距离。聚类的新中心根据分配给它的所有顶点不断更新。计算聚类中心的公式如下：〔3〕其中是包含在簇中的顶点的数量。算法1给出了K-means聚类算法的伪代码。1随机设置K个集群中心;2repeat3for每个顶点do4计算每个聚类的距离度量;5将其分配给最近的组6end7重新计算聚类中心位置;8untilstopcriteriaaremet;算法1：K-Means的伪代码B、AP聚类基于相似性度量的聚类方法已经广泛用于工程系统和科学数据分析中。聚类的一种常见方法是将数据分成几个局部，并找到一组中心，以使数据点及其最接近的中心具有最小的平方误差和。我们从所有实际存在数据点中选择中心，并将它们命名为“样本〞。K-Means聚类方法最初使用一组随机选择的样本，然后迭代地优化那些样本，目的是降低平方误差的和。K-Means聚类方法最初很容易选择样本，所以它总是需要用不同的初始化来优化许屡次，并努力获得更好的解决方案。因此，它仅在组的数量较少并且至少一个随机初始解接近优秀解的情况下表现很好。近邻传播〔AP〕与K-Means聚类非常不同[18]，它不需要在运行算法之前人工设置聚类的数量。它将所有数据点视为同一时间的潜在样本，并将其视为每个集群的代表。在AP中的数据点之间交换的消息有两种类型。它交替地使用两种消息传递步骤来更新两个矩阵：“责任〞矩阵和“可用性〞矩阵，并且它们中的每一个考虑不同种类的竞争。可以在任何时间组合消息以从点中选择样本。“责任〞矩阵描述了点适合于点的程度，即从到的消息。“可用性〞描述点选择点作为其聚类中心的程度，将消息从发送到。点应当是考虑来自其他相邻点的支持的例如。和使用以下公式计算：〔4〕〔5〕其中，AP的详细描述可参考[19,20]。三、基于聚类的遗传算法本文提出了两种改良的聚类遗传算法，即基于K-means聚类〔KGA〕的遗传算法和基于AP聚类〔APGA〕的遗传算法，以有效地解决大规模TSP问题。首先，KGA和APGA使用聚类方法将大规模TSP转换成几个小的子问题，每个子问题对应于一个组。在KGA和APGA中分别采用K-means聚类和AP聚类方法。然后，我们使用遗传算法找到每个聚类的最短哈密顿回路。所有这些组可以并行处理。最后，以缩短整个旅行路线为目标，我们设计了有效的连接方法，将所有组合并为一个整体。A.组内演化组内演化操作的目的是为每个组中的给定结点找到最短的哈密顿回路。遗传算法是一个基于进化论的有影响力的技术，如TSP的问题[21]。在每个组中执行遗传算法，旨在通过选择、交叉和突变这几个遗传操作获得近似解。与其他精确的传统搜索算法相比，其优点主要是使用循环群体的信息而不是仅仅一个循环来执行搜索。

在组内使用有序编码方案。使用此方案，每个结点都被编号为从1到该群体结点总数量中的唯一整数。染色体是以整数排列，表示交通路径。我们将组中结点的编号排列在基因片段上，染色体可以被认为是所有基因片段的排列，并且每个基因片段代表组。每个聚类中使用的遗传算法的过程如下：1随机生成初始群体;2计算适宜度值并保存最小值;3repeat4选择下一代的父母;5执行交叉算子操作6执行变异算子操作8untilstopcriteriaaremet;9输出最正确途径;所有这些集群可以并行处理。这一步的结果是将结点聚类为组。B.组间连接有效地解决TSP问题的目的是找到最短的旅行路线。在上一步中，我们获得的是每个组中给定结点的最短哈密顿回路，然后在这一步我们需要考虑如何连接所有的组，并实现所有结点的连接。连接两个组就是确定哪些路径将从每个组中的最短哈密顿回路中删除，以及哪些路径将被连接以将两个相邻组组合成一个。假设，是与两组最接近的结点，对于，与是与相邻的两个结点，同样对于，和是与相邻的两个结点。给出和，为了连接两个组为一个，我们需要选择两个结点、来删除及连接边缘。如何选择它们，我们参考公式(1):(1)其中，。重复此过程，直到所有组被合并为一个整体，实现所有结点的连接。以上方案如图1所示：图1.组合集群的过程不同的组合中的组合序列将导致不同的交通布线路径，寻找最短的路径是我们的目的。因此，当群体数量较大时，我们考虑设计一个修改的遗传算法进行整体优化，以缩短整个交通路线。有序编码方案也用于整体优化。然而，不同于代表交通路径的染色体，在这个过程中，我们在组之间梳理编码序列。换句话说，我们需要优化聚类的序列并找到最好的组合序列。在该序列之后，前两个组被组合成一个，然后新生成的组与第三组组合……逐步完成。最后，所有这些组被合并成一个整体，并且得出最优路径。以上算法的整个过程如下：1Input一个轨道交通布线问题;2采用K-means或AP将轨道交通布线问题聚类为k个子问题；3For每个子问题,do:4repeat5选择下一代的父母;6执行交叉算子;7执行变异算子;8untilstopcriteriaaremet;9Output子问题的哈密尔顿回路;10End11利用GA寻求最正确组合序列;12将所有这些哈密尔顿回路结合到最正确序列之后的一个整体路径中;13Output最短路径.四、实验在本节中，我们进行广泛的实验来评估KGA和APGA的有效性，其中KGA表示K-means聚类与遗传算法的组合，APGA表示亲和力增殖聚类与遗传算法的组合。我们将它们应用于来自TSPLIB[22]的标准测试实例，并比拟它们的性能。此外，在相同条件下，我们还将结果与通过经典遗传算法〔CGA〕和其他相关聚类遗传算法获得的结果进行比拟。所提出的KGA和APGA对于每个测试实例独立运行20次。表I给出了20个独立运行的每个基准问题和统计的实验结果，包括路线长度值的最正确值、平均值和标准偏差〔std〕。如表I所述，通过KGA获得的平均值分别小于通过APGA获得的对于att532，d657，rat783，u2319和pcb3038获得的平均值，这说明KGA在这些测试问题上表现优于APGA。同时，APGA在其他测试实例〔包括pcb442，u2152和rl5915〕上的性能优于KGA。一般来说，KGA在优化旅行路线方面表现与APGA类似或稍好一点。然而，K-means聚类对中心的初始选择相当敏感，并且聚类的数量需要预先设置。然后我们喜欢APGA来解决这种类型的TSP。表IKGA和APGA的比照问题最正确KGAAPGA平均值最小值标准偏差时间花费(s)平均值最小值标准时间花费(s)pcb4425077862129.161461.5279.35.061955.661946.2257.87.3rat57567737647.097820.56263.25.27814.357925.44156.24.6d6574891256785.356738.243.55.156801.556784.147.98.4rat78388069882.99822.044.66.69997.19934.739.610.7u21526425375689.375184.4297.419.575571.873825.21807.349.6u2319234256243336.3242605.5412.725.0245704.4249980.11066.568.9pcb3038137694159777.9159182.2906.795.2161086.5160284.71116.5133.6rl5915565530786908.3780619.97590.980.5656647.9619020.95895.5188.6此外，我们将所提出的KGA，APGA与其他相关工作，包括经典遗传算法〔CGA〕和两级遗传算法〔TLGA〕进行比拟[3]。这四种算法的比拟示于表II中。通过CGA和TLGA获得的实验结果从[3]中引用。除了进化迭代的次数，其他参数是相同的。表II中的结果说明，在小的进化迭代中，尤其是对于APGA，KGA和APGA的效果都比CGA和TLGA好得多。换句话说，在相同的其他参数下导出最正确游历，KGA和APGA比CGA和TLGA需要更少的计算本钱。KGA和APGA是高效的。此外，APGA可以产生比其他三种算法更少迭代的更短的路线。图2显示了巡回长度与测试问题迭代次数的演变。在CGA方面，KGA和APGA显示出比普通算法明显的优势。APGA可以获得更好的初始解决方案。这些结果说明，基于聚类的算法在迭代方面收敛比CGA快得多。换句话说，KGA和APGA需要比CGA更少的迭代来解决TSP。从图2和表II中，我们可以得出结论，KGA和APGA比CGA更加有效，并且它们在有限时间内对于大TSP获得更合理的行程中表现良好。图3绘制了KGA与不同的收敛。是组的数量。从图中可以看出，随着的增加，KGA的收敛速