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

来源：计算机工程与应用杂志2017年第14期北京时间：

作者：郑 明1，2，3，卓慕瑰1，2

单位：1.梧州学院 广西高校行业软件技术重点实验室，广西 梧州 543002；2.梧州学院 信息与电子工程学院，广西 梧州 543002；3.吉林大学 计算机科学与技术学院，长春 130012

摘要：为解决NP完全的旅行商问题，提出一种四点三线遗传算法。该算法特色在两阶段策略，第一阶段是变异算子优化，将汉密尔顿环中所有大于两点的内部路径倒置，并用新极值代替原极值。第二阶段是四点三线优化，将汉密尔顿环分为n个四点三线局部路径并将每个局部路径转化为最优局部路径，将所有局部路径长度求和除以1/3。交叉算子结束后，如子代含有重复位点，将未交叉部分重复位点与交叉部分重复位点对应的父代等位点交换。通过将该算法与传统遗传算法及只进行第一步优化的遗传算法进行比较，采用TSPLIB数据库实例数据，证明该算法有更高的执行效率，有更强的收敛性，适合寻找最短TSP路径。

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