基于改进自适应遗传算法的旅行商问题研究  

Research on Travelling Salesman Problem Based on Improved Adaptive Genetic Algorithm

作　　者：陈璐 魏文红 CHEN Lu;WEI Wenhong(School of Computer Science and Technology,Dongguan University of Technology,Dongguan 523808,China)

机构地区：[1]东莞理工学院,计算机科学与技术学院,广东东莞523808

出　　处：《东莞理工学院学报》2024年第5期1-8,共8页Journal of Dongguan University of Technology

基　　金：广东省自然科学基金项目(2024A1515011838);广东省高校新一代电子信息(半导体)重点领域专项(2023ZDX1028);东莞市社会发展科技项目(20211800904722);东莞市科技特派员项目(20221800500052)。

摘　　要：传统遗传算法因其强大的全局搜索能力成为了解决旅行商问题的优选之一,但它较差的局部搜索能力限制了该算法在寻求最优解时的效能。为解决此问题,笔者通过改良圈算法优化初始解,在进化过程中自适应调整进行各遗传操作的概率,结合模拟退火算法的关键步骤metropolis准则和加入逆转操作,基于随机模拟的策略对遗传算法进行改进并将其应用于求解旅行商问题。仿真结果表明,改进的遗传算法在算法收敛速度、收敛效果和解质量方面均优于传统遗传算法。Traditional genetic algorithm has become one of the preferred choices to solve the travelling salesman problem because of its powerful global search ability,but its poor local search ability limits the effectiveness of the algorithm in seeking the optimal solution.To solve this problem,this paper optimizes the initial solution through a modified circle algorithm and the probability of an adaptive adjustment to perform each genetic operation during evolution;by combining the key step of the simulated annealing algorithm with the metropolis criterion and incorporating the reversal operation,the genetic algorithm based on the random simulation strategy is improved and applied to solve the traveling traveler problem.The simulation results show that the improved genetic algorithm is superior to the traditional genetic algorithm in convergence speed,convergence effect and quality.

关 键 词：遗传算法 旅行商问题 自适应调节 组合优化问题 局部搜索算法 

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