求解旅行商问题的改进k-opt遗传算法  

An Improved Kopt Genetic Algorithm for Travelling Salesman Problem

作　　者：赵涛 叶志伟[1] 宗欣露[1] 潘虎 ZHAO Tao;YE Zhiwei;ZONG Xinlu;PAN Hu(School of Computer Science,Hubei Univ.of Tech.,Wuhan 430068,China)

机构地区：[1]湖北工业大学计算机学院,湖北武汉430068

出　　处：《湖北工业大学学报》2023年第5期75-81,共7页Journal of Hubei University of Technology

摘　　要：为了增强遗传算法的局部搜索能力,加速算法运行效率,尽量避免算法陷入早熟问题,提出一种改进k-opt遗传算法求解旅行商问题。该算法利用改进的k-opt方法初始化获得较优种群,引入改进的交叉变异机制增强算法全局搜索能力,结合改进的k-opt方法强化算法局部搜索能力。实验结果表明,改进的k-opt遗传算法能有效平衡算法探索和开发能力,其求解的质量优且运行效率高。The traveling salesman problem is a classical combinatorial optimization problem,and the genetic algorithm has a good global search ability to obtain the shortest path with better quality when dealing with this problem.However,the local search ability of the genetic algorithm is weak.In order to enhance the local search ability of the genetic algorithm,accelerate the operation efficiency of the algorithm,and slow down the phenomenon of the algorithm falling into premature maturity,an improved kopt genetic algorithm for solving the traveling salesman problem is proposed in this paper.The algorithm uses the improved kopt method to initialize to obtain a better population,introduces an improved crossover mutation mechanism to enhance the global search ability of the algorithm,and combines the improved kopt method to strengthen the local search ability.The experimental results show that the improved kopt genetic algorithm can effectively balance the algorithm's exploration and exploitation abilities,and its solution has good quality and high operation efficiency.

关 键 词：旅行商问题 k-opt 遗传算法 局部搜索 组合优化问题 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]