分区协作遗传算法及其在大规模TSP问题中的应用

Subpartition Cooperation Genetic Algorithm and Its Application in Large Scale TSP Problem

针对传统遗传算法(Genetic Algorthm,GA)在求解大规模路径优化问题时容易陷入局部最优问题,提出一种分区协作优化模型,以提升种群多样性及局部搜索能力。首先,根据拟分区的规模基本相同,以代价函数为依据提出一种自适应聚类分区方法,将大规模路径优化划分为若干分区,采用传统GA算法获得局部的最短路径排列;然后,按照就近原则将分区最短路径进行拼接,获得大规模路径优化问题的最优解,并利用4个TSPLIB标准集进行试验验证。最后,利用Rat195TSP实例探究分区数目对优化结果的影响。结果表明,分区数目相同时,路径规模与优化结果具有明显正相关关系。Rat195TSP实例拟合表明,分区数与最优解满足凹函数特性,当分区数目在8~12时,获得的最优解效果最好。

Traditional genetic algorithm(GA) is easy to fall into the local optimal problem when solving large-scale path optimization problems. This paper proposes a subpartition cooperation optimization model to improve the population diversity and local search ability. According to the size of quasi partition is basically the same, an adaptive clustering partition method is proposed based on the cost function. The large-scale path optimization is divided into several partitions, and the traditional GA algorithm is used to obtain the local shortest path arrangement. According to the principle of proximity, the shortest paths are spliced to obtain the optimal solution of large-scale path optimization problem, and four TSPLIB standard sets are used for experimental verification. Rat195 tsp is used as an example to explore the impact of the number of partitions on the optimization results. The results show that when the number of partitions is the same, the path size has a significant positive correlation with the optimization results. Rat195 tsp example fitting shows that the number of partitions and the optimal solution meet the concave function characteristics. When the number of partitions is 8~12, the optimal solution is the best.