首页|基于组合变异和分组优化的单亲遗传算法求解旅行商问题

基于组合变异和分组优化的单亲遗传算法求解旅行商问题

扫码查看
原文链接
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 万方数据
针对遗传算法求解旅行商问题存在收敛速度慢、容易陷入局部最优等问题,提出了基于组合变异和分组优化的单亲遗传算法.算法设计了由双侧倒序、近邻交换、跳跃基因构成的组合变异算子,用于扩大搜索范围,增强种群的多样性;经过精英优选后,将种群按适应度优劣分为两组作局部优化,对优质互异组依次采用插入和2opt算子,加快进化收敛速度;对普通组用倒序算子,增强其跳出局部最优的能力.仿真实验表明,对于中小型规模的旅行商问题,该算法在收敛速度和求解能力上得到明显改善和增强.
Partheno-Genetic Algorithm based on Combined Mutation and Grouped Optimization for Solving Traveling Salesman Problem
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.

Traveling Salesman ProblemPartheno-Genetic AlgorithmCombined Mutation StrategyElite SelectionGrouped Optimization Strategy

周琴、谭代伦

展开 >

西华师范大学数学与信息学院,四川 南充 637009

旅行商问题 单亲遗传算法 组合变异策略 精英优选 分组局部优化策略

四川省科技计划项目资助教育部产学合作协同育人项目四川省教育厅重点教改项目

2019YFG0299202102454008JG2021-959

2024

10.16595/j.1671-055X.2024.03.006

六盘水师范学院学报
六盘水师范学院

六盘水师范学院学报

影响因子：0.271
ISSN：1671-055X
年,卷(期)：2024.36(3)
  • 10