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

简介

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