基于基因库求解旅行商问题的遗传算法  

Novel genetic algorithm based on genes pool for traveling salesman problem

作　　者：王永[1] 吕致为 Wang Yong;Lyu Zhiwei(School of New Energy,North China Electric Power University,Beijing 102206,China)

机构地区：[1]华北电力大学新能源学院,北京102206

出　　处：《计算机应用研究》2023年第11期3262-3268,共7页Application Research of Computers

基　　金：国家重点研发计划资助项目(2022YFE0207000)。

摘　　要：针对传统遗传算法(genetic algorithm,GA)求解旅行商问题(traveling salesman problem,TSP)存在寻优效率低、实验结果缺乏一致性等问题,提出了一种基于基因库的遗传算法(genetic algorithm based on genes pool,GPGA)。GPGA从种群中搜索减小哈密顿圈长度的边,并当做优良基因构成基因库。父代哈密顿圈在基因库引导下产生更优的子代哈密顿圈,基因库也随着种群的不断进化而同步更新,引导种群个体逐步向最优解靠近。算例结果表明在同样条件下,GPGA比传统遗传算法和几种改进遗传算法的性能更优。Aiming at the problems of low efficiency and unstable solutions of traditional genetic algorithm(GA)in solving traveling salesman problem(TSP),this paper proposed a novel genetic algorithm based on genes pool(GPGA).GPGA searched for edges that decreased the fitness of Hamiltonian cycles from the population and constituted a gene pool as excellent genes.The parent generation reproduced the better offspring of Hamiltonian cycles under the guidance of the gene pool.The gene pool also synchronously updated according to the better Hamiltonian cycles and helped the current Hamiltonian cycles evolve to the optimal Hamiltonian cycle step by step.The computational results demonstrate that GPGA is better than traditio-nal genetic algorithm and several improved genetic algorithms under the same preconditions.

关 键 词：旅行商问题 遗传算法 基因库 局部优化策略 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]