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

摘要：

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

关键词：路径优化;遗传算法;聚类分区;大规模TSP

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;云南省教育厅科学研究基金项目

在线出版日期：2022-02-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：27-29,32