基于自适应层次谱聚类与遗传优化的TSP算法

A TSP Algorithm Based on Adaptive Hierarchical Spectral Clustering and Genetic Optimization

提出一种基于自适应层次谱聚类与遗传优化的算法求解大规模TSP,算法首先构建一种自适应相似矩阵,并应用到谱聚类算法中实现城市的初步聚类,当聚类城市规模超过设定阈值,用上述自适应谱聚类算法进行层次聚类,直到每类城市规模均小于阈值;其次,采用结合了最近邻与禁忌思想的改进遗传算法求解GTSP,得类间最短回路;最后,用改进遗传算法求解每类城市群的最优解,综合类间GTSP最短回路以及类内TSP最优解,即得大规模旅行商问题的最优解.实验结果表明,该算法能够取得相对较优解且求解效率显著提高.

A algorithm based on adaptive hierarchical spectral clustering and genetic optimization is proposed for large TSP.Firstly,an adaptive similarity matrix was constructed and applied to the spectral clustering algorithm to achieve the preliminary clustering of the city.When the cluster city size exceeded the set threshold,the above-mentioned adaptive spectral clustering algorithm was used for hierarchical clustering until the size of each type of city was less than the threshold;Secondly,an improved genetic algorithm combining the nearest neighbor and taboo ideas was used to solve the GTSP problem,and the shortest loop between classes was obtained.Finally,to solve the optimal solution of each type of urban agglomeration using the improved genetic algorithm,and the shortest loop of the GTSP between the classes and the TSP optimal solution within the class were obtained,which was the optimal solution for the large-scale traveling salesman problem.The results show that the algorithm can obtain better solutions and the solution efficiency is significantly improved.