改进遗传算法求解TSP问题

doi:10.16039/j.cnki.cn22-1249.2025.02.003

下载:

PDF (1494KB)
输出: BibTeX | EndNote (RIS)

摘要针对传统遗传算法求解旅行商问题时初始解质量差、容易陷入局部最优、求解精度低等问题,提出了一种改进遗传算法。首先,将贪婪算法与精英选择结合,提高种群中初始解的质量;其次,设计自适应交叉和变异概率的步骤,结合Metropolis准则来防止遗传算法陷入局部最优;最后,加入贪婪双向三交叉和2-opt搜索算法,提高求解精度。实验结果表明,改进遗传算法最优解的偏差率均小于1.88%,均值的偏差率均小于2.27%。

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	（）
	作者相关文章
	朱建军
	王志宾

关键词: 旅行商问题遗传算法贪婪双向三交叉自适应 2-opt算子

Abstract: An improved Genetic Algorithm (GA) is proposed to solve the problems of poor initial solution,local optima and low aceuracy of the traditional GA for solving the Travelling Salesman Problem(TSP).Firstly,the greedy algorithm is combined with elite selection to improve the quality of the initial solutions in the population. Secondly , the steps of adaptive crossover and mutation probability are designed, and the Metropolis criterion is combined to prevent the genetic algorithm from falling into local optima.Finally, Bidirectional Three- Cross of Greedy Algorithm and 2-opt search algorithm are added to improve the accuracy The results show that the deviation rate of the optimal solution of the improved genetic algorithm is less than 1.88%, and the deviation rate of the mean is less than 2.27%.

Key words: travel salesman problem(TSP) genetic algorithm Bidirectional Three-Cross of Greedy Algorithm self-adaptation 2-opt operator

出版日期: 2025-02-25 发布日期: 2025-07-05 整期出版日期: 2025-02-25

ZTFLH:

TP301.6

引用本文:

朱建军, 王志宾. 改进遗传算法求解TSP问题[J]. 吉林化工学院学报, 2025, 42(2): 11-17.
ZHU Jianjun, WANG Zhibin. Improving Genetic Algorithm for Solving Travel Salesman Problem. Journal of Jilin Institute of Chemical Technology, 2025, 42(2): 11-17.

链接本文:

https://xuebao.jlict.edu.cn/CN/10.16039/j.cnki.cn22-1249.2025.02.003 或 https://xuebao.jlict.edu.cn/CN/Y2025/V42/I2/11