四点三线遗传算法求解旅行商问题  

Solution for traveling salesman problem with four vertices and three lines genetic algorithm

作　　者：郑明[1,2,3] 卓慕瑰 ZHENG Ming;ZHUO Mugui(Guangxi Colleges and Universities Key Laboratory of Professional Software Technology, Wuzhou University, Wuzhou,Guangxi 543002, China;College of Information and Electronic Engineering, Wuzhou University, Wuzhou, Guangxi 543002, China;College of Computer Science and Technology, Jilin University, Changchun 130012, China)

机构地区：[1]梧州学院广西高校行业软件技术重点实验室,广西梧州543002 [2]梧州学院信息与电子工程学院,广西梧州543002 [3]吉林大学计算机科学与技术学院,长春130012

出　　处：《计算机工程与应用》2017年第14期148-154,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61502343;No.61373051);中国博士后科学基金第59批面上资助一等资助(No.2016M590260);广西自然科学基金(No.2015GXNSFBA139262);广西高校科研项目(No.KY2015ZD122);梧州学院院级项目(No.2014A002)

摘　　要：为解决NP完全的旅行商问题,提出一种四点三线遗传算法。该算法特色在两阶段策略,第一阶段是变异算子优化,将汉密尔顿环中所有大于两点的内部路径倒置,并用新极值代替原极值。第二阶段是四点三线优化,将汉密尔顿环分为n个四点三线局部路径并将每个局部路径转化为最优局部路径,将所有局部路径长度求和除以1/3。交叉算子结束后,如子代含有重复位点,将未交叉部分重复位点与交叉部分重复位点对应的父代等位点交换。通过将该算法与传统遗传算法及只进行第一步优化的遗传算法进行比较,采用TSPLIB数据库实例数据,证明该算法有更高的执行效率,有更强的收敛性,适合寻找最短TSP路径。A Four Vertices and Three Lines Genetic Algorithm(4V3LGA)is proposed to resolve the traveling salesmanproblem,which is proven to be NP-complete.The special part of the proposed algorithm is two-phase strategies.The firstlocal optimization strategy is the mutation operator,which is executed to reverse every Local Hamiltonian Path(LHP).Every LHP contains more than2vertices and generates the shorter Hamiltonian Cycles(HC).The second local optimizationis HC segmentation,which is executed to divide HC to n four vertices and three lines LHPs to generate the shorterHC.The sum of the LHPs is divided by1/3.After crossover,if the positions in offspring HCs are the same,the duplicatedpositions of un-exchanged part are exchanged with the same positions of the father HCs of exchanged part.To prove theefficiency of the4V3LGA proposed,traditional GA and first-phase GA are used to compare with the proposed algorithm.TSPLIB instances are used in the experiments.The computation results show that the proposed algorithm can find the betterapproximate solutions than other two algorithms.It can be used to find shorter TSP HC.

关 键 词：遗传算法 旅行商问题 两阶段策略 四点三线 

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