一种求解旅行商问题的演化算法研究  

A new evolutionary algorithm for the traveling salesman problem

作　　者：许冲 钟玮 刘欣欣 XU Chong;ZHONG Wei;LIU Xinxin(School of Computer Science,Minnan Normal University,Zhangzhou,Fujian 363000,China)

机构地区：[1]闽南师范大学计算机学院,福建漳州363000

出　　处：《闽南师范大学学报（自然科学版）》2020年第2期44-48,共5页Journal of Minnan Normal University：Natural Science

基　　金：福建省中青年项目(JAT170351,JAT170361)。

摘　　要：旅行商(TSP)问题是一个被证明具有NP计算复杂性的组合优化问题.郭涛算法在求解TSP问题的高效率是得到广泛认可的,其算法的核心在于Inver-over算子的设计.当节点数量较多时,该算法在寻找近似最优解仍然有很好的表现,但其寻找全局最优解的能力却会下降.提出的基于基因片段插入的演化算法,它能以较高的概率找到TSP问题的最优解.文中提出一种新的演化算法,将基于基因片段插入与Inver-over算子进行融合.实验证明:新算法可有效防止解的早熟,增强了算法的全局搜索能力,使算法获得全局最优解的概率大大提高,同时仍然具备高效率的特性.The traveling salesman problem(TSP)is a combinatorial optimization problem which is proved to have NP computational complexity.High efficiency of Guo Tao’s algorithm in solving the TSP is widely recognized,the core of this algorithm is the design of Inver-over operator.When the number of nodes is large,the algorithm still has a good performance in finding the approximate optimal solution,but its ability to find the global optimal solution will decrease.It propose an evolutionary algorithm based on gene fragment insertion,which can find the optimal solution of the TSP with a higher probability.A new evolution algorithm which is based on the combination of gene fragment insertion and inver-over operator is proposed.Experiments show that:the new algorithm can effectively prevent premature convergence solutions,and enhance its global search ability,which enables the algorithm to obtain the global optimal solution with a higher probability,while still have high efficiency.

关 键 词：旅行商问题 郭涛算法 基因片段插入 演化算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]