应用聚类算法求解TSP问题

龙源期刊网问题作者：朱美玲来源：《商情》2015年第42期【摘要】首先通过对大规模TSP问题进行聚类处理，将其分解成许多小规模TSP问题，然后分别对每个小规模TSP问题利用贪婪算法并行求解，最后将所有小规模TSP问题的解按一定规则合并成大规模TSP问题的解，从而提高算法的效率。【关键词】旅行商问题，聚类处理，贪婪算法1引言：TSP（TravelingSalesmanProblem）问题是一个著名的NP-Hard问题。即找不到一种算法能在多项式时间内求得问题的最优解。它可以简单描述为：给出一条遍历给定的若干个城市中所有城市的最短路径。TSP是一个经典的组合优化问题。所有的路线组合数为，需要问题规模的指数阶时间。所以，针对TSP问题，首先通过对大规模问题进行聚类处理，将其分解成许多小规模问题，再利用现有优化算法对小规模问题进行求解。最后将每类中的路径按一定策略组合成问题的解。当问题的聚类数越多，且每类中的城市数较接近时，算法的性能越好。2问题定义及聚类处理2.1问题定义2.2聚类处理确定适当的分类方法的原则：⑴各类重心之间的距离必须很大。⑵确定的类中，各类所包含的元素都不要太多。⑶类的个数必须符合实用目的。针对这一原则，本文从常用聚类方法出发，并作出了一些有效的改进。本文采用下面方法产生一批凝聚点。以每个城市为球心，落在这个球内的城市数（不包括作为球心的城市）就叫做这个城市的密度。计算所有城市点的密度后，首先选择密度最大城市作为第一凝聚点，并且人为地规定一个正数D（一般Dd，常取D=2d）。然后选出次大密度城市点，若它与第一个凝聚点距离大于D，则将其作为第二个凝聚点，否则舍去此点，再选密度次于它的城市。或者在确定d值后，首先以所有城市的均值作为第一凝聚点，然后依次考察每个城市，若某城市与已选定的凝聚点的距离均大于d，该城市作为新的凝聚点，否则考察下一个城市。聚类步骤：步骤1，规定城市间的距离（欧氏距离）。人为地规定出三个数：K（分类数），C（类间距离的最小值）和R（类内距离的最大值）；取出K个城市作为凝聚点。ⅰ）由前面问题定义知，城市数为N，城市间距离为龙源期刊网ⅱ）作为凝聚点的K个城市的选取：计算出所有城市间的距离，并对之升序排序，平均分K/2-1段，取出K/2个距离点，对应的K个城市即为凝聚点。步骤2，计算这K个凝聚点两两之间的距离，如最小距离C，则将相应的两个凝聚点合并，用这两个点的重心作为新凝聚点，再重复步骤2，直至所有凝聚点之间的距离均≥C为止。步骤3，将剩下的N-K个城市逐个归类，对每一个城市，计算该城市与所有凝聚点的距离，如最小距离R，则该城市作为新凝聚点，如最小距离≤R，则将该城市归入与它距离最近的凝聚点所在的类，随即重新计算这一类的重心，以重心作为新的凝聚点，如凝聚点之间的距离都≥C，则考虑下一个城市，否则用步骤2，进行合并后再考虑下一个城市，直至所有城市都归了类。步骤4，将所有城市从头至尾再逐个按步骤3进行归类，不同之处是某个城市归类后，如分类与原来一致，则重心不必计算；如分类与原来不同，则涉及到的两类重心要重新计算。如果新的分类与上次相同，则聚类过程结束，否则重复步骤4。3最优路径的生成3.1类之间的连接顺序下面要做的工作就是怎样把各个类的“局部”最优路径（由于规模均不大，可用贪婪算法）合并成“全局”最优路径。算法步骤：设可将所有城市聚类成类U1，U2，……Uc类（c为类的个数），Ki（i=1，2，……，c）为每一类的中心（Ki可以不是Ui中的城市）。对以Ki（i=1，2，……，c）构成的TSP问题，用贪婪算法求解为Ki1，Ki2，……，Kic（i1，……ic为1，2，…c的一个排列），则i1，i2，……，ic，i1即为各类的排列顺序。算法描述如下：步骤1，对TSP问题中的城市进行聚类处理，设可将城市聚成U1，U2，……Uc类（其中c为类的个数）。设Ki（i=1，2，……，c）为每类的中心（其中Ki可以不是Ui中的城市）；步骤2，对于中心城市Ki（i=1，2，……，c）构成的TSP问题，用贪婪算法求解，设所得的解为Ki1，Ki2，……，Kic，其中i1，……ic为1，2，…，c的一个排列。步骤3，将每类Ui（i=1，2，…，c）中的城市看成（小规模）TSP问题，并用贪婪算法并行求解。设所得的解分别为R1，R2，……，Rc，在解Ri（i=1，2，……，c）中断开最长龙源期刊网的边，生成一条类Ui中从边界城市1到边界城市2的最短路径，记所求得的路径为P1，P2，……，Pc。步骤4，将路径Pi（i=1，2，……，c）按i1，i2，……ic顺序进行连接，从而求得大规模TSP问题的一个最优解，其中i1，i2，……ic为步骤2求得的连接顺序。至此，便得到一条“全局”最优路径。4结论应该指出，关于类个数如何确定问题，至今还没有一个合适的标准，也就是说，对任意大规模TSP问题，都没有一个唯一正确的分类数。本文对K-均值法的改进在分类效果上取得了较满意的解。论文提出的聚类算法，首先通过对大规模TSP问题进行聚类处理，将其分解成许多小规模TSP问题，利用贪婪算法对小规模TSP具有较高的求解性能，并行求解所有小规模TSP问题，生成类内的最短路径，最后将每类中的路径按一定顺序组合成问题的解，当问题的聚类数越多，且每类中的城市数较接近时，算法的性能越好；但当问题的聚类特征不明显，该算法将退化成一般的贪婪算法。龙源期刊网