【摘要】 TSP问题的应用十分广泛，而传统的遗传算法在求解TSP问题时存在求解精度低和时间长等不足。针对该问题提出了一种改进的分布式并行遗传算法用来求解大规模TSP问题。改进遗传算法使父代染色体进行顺序交叉、就近变异和局部最优选择，将大规模TSP问题用k-均值聚类算法进行分组，使用分布式并行算法将子问题分配到不同的计算节点上用改进的遗传算法求解。求解得到的子问题用Delaunay三角剖分算法进行合并，从而得到整个问题的解。通过TSPlib数据库进行实验，结果显示提出的算法在求解时间和求解精度上均有所提高。更多还原

【Abstract】 TSP problem is widely used,however,the traditional genetic algorithm has some shortcomings in solving TSP problem,such as low accuracy and long time. For this problem,an improved distributed parallel genetic algorithm is proposed to solve large-scale TSP problem. The improved genetic algorithm makes the parent chromosome carry out sequential crossover,nearest mutation and local optimal selection. The large-scale TSP problems are grouped by the k-mean algorithm;the sub-problems are assigned to computing nodes and solved by the improved genetic algorithm. The optimal sub-problems are combined by the Delaunay triangulation. The results on TSPLIB database show that the proposed algorithm improves the solution time and accuracy.更多还原