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

遗传算法是解决旅行商问题（traveling salesman problem，TSP）的通用路径优化算法之一。为解决传统遗传算法收敛速度慢且解不稳定的问题，提出一种生物信息启发式遗传算法（bioinformation heuristic genetic algorithm，BHGA）。通过优化适应度函数和初始种群，引入生物信息学中的基因序列对比手法进行交叉重组排序，采用基因逆转操作进行变异，对遗传算法进行改进，使算法能够加快收敛速度，得到更优路径解。利用BHGA对TSPLIB数据库中算例进行求解，实验仿真结果表明：该算法在中小型规模的TSP中求解效果好且结果稳定。

Bioinformation Heuristic Genetic Algorithm for Solving 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.