基于组合变异和分组优化的单亲遗传算法求解旅行商问题
Partheno-Genetic Algorithm based on Combined Mutation and Grouped Optimization for Solving Traveling Salesman Problem
周琴 1谭代伦1
作者信息
- 1. 西华师范大学数学与信息学院,四川 南充 637009
- 折叠
摘要
针对遗传算法求解旅行商问题存在收敛速度慢、容易陷入局部最优等问题,提出了基于组合变异和分组优化的单亲遗传算法.算法设计了由双侧倒序、近邻交换、跳跃基因构成的组合变异算子,用于扩大搜索范围,增强种群的多样性;经过精英优选后,将种群按适应度优劣分为两组作局部优化,对优质互异组依次采用插入和2opt算子,加快进化收敛速度;对普通组用倒序算子,增强其跳出局部最优的能力.仿真实验表明,对于中小型规模的旅行商问题,该算法在收敛速度和求解能力上得到明显改善和增强.
Abstract
Aiming at the problems of slow convergence speed and falling easily into local optimum in solving Traveling Sales-man Problem,Partheno-Genetic Algorithm based on Combined Mutation and Grouped Optimization is proposed.Combined muta-tion is designed to be composed of two-sided reverse order,nearest neighbor exchange and jumping gene,which is used to expand the search range and enhance the diversity of population.After elite selection,the populations are divided into two groups accord-ing to their fitness for local optimization,and insertion and 2opt are used successively for the high-quality and different group to accelerate the evolutionary convergence speed.The reverse order operator is used for the ordinary group to enhance its ability to jump out of the local optimum.Experiments show that the proposed algorithm has significantly improved in convergence speed and solving ability for small and medium-sized traveling salesman problem.
关键词
旅行商问题/单亲遗传算法/组合变异策略/精英优选/分组局部优化策略Key words
Traveling Salesman Problem/Partheno-Genetic Algorithm/Combined Mutation Strategy/Elite Selection/Grouped Optimization Strategy引用本文复制引用
基金项目
四川省科技计划项目资助(2019YFG0299)
教育部产学合作协同育人项目(202102454008)
四川省教育厅重点教改项目(JG2021-959)
出版年
2024
国家科技期刊平台
NSTL
万方数据