一种求解TSP的生物信息启发式遗传算法  

Bioinformation Heuristic Genetic Algorithm for Solving TSP

作　　者：徐佳[1] 韩逢庆[1] 刘奇鑫 薛晓霞 Xu Jia;Han Fengqing;Liu Qixin;Xue Xiaoxia(Chongqing Jiaotong University,Chongqing 400046,China)

机构地区：[1]重庆交通大学,重庆400046

出　　处：《系统仿真学报》2022年第8期1811-1819,共9页Journal of System Simulation

基　　金：重庆市研究生导师团队建设项目(JDDSTD201802)。

摘　　要：遗传算法是解决旅行商问题(traveling salesman problem,TSP)的通用路径优化算法之一。为解决传统遗传算法收敛速度慢且解不稳定的问题,提出一种生物信息启发式遗传算法(bioinformation heuristic genetic algorithm,BHGA)。通过优化适应度函数和初始种群,引入生物信息学中的基因序列对比手法进行交叉重组排序,采用基因逆转操作进行变异,对遗传算法进行改进,使算法能够加快收敛速度,得到更优路径解。利用BHGA对TSPLIB数据库中算例进行求解,实验仿真结果表明:该算法在中小型规模的TSP中求解效果好且结果稳定。Genetic algorithm(GA)is one of the universal path optimization algorithms for traveling salesman problem(TSP).Aiming at the slow convergence and unstable solution of the traditional GA,a bioinformation heuristic genetic algorithm(BHGA)is proposed.By optimizing the fitness function and initial population,the gene sequence comparison technique in bioinformatics is introduced to carry out the cross recombination sorting.The gene reversal operation is used to implement mutation,to accelerate the convergence speed and get a better path solution.The numerical examples in TSPLIB database are solved by BHGA and the experimental simulation results show that the algorithm is effective and the solution of the medium and small scale TSP data are stable.

关 键 词：旅行商问题 改进遗传算法 基因序列对比 适应度函数 等价矩阵 

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