Abstract: A Four Vertices and Three Lines Genetic Algorithm （4V3LGA） is proposed to resolve the traveling salesman problem, which is proven to be NP-complete. The special part of the proposed algorithm is two-phase strategies. The first local optimization strategy is the mutation operator, which is executed to reverse every Local Hamiltonian Path （LHP）. Every LHP contains more than 2 vertices and generates the shorter Hamiltonian Cycles （HC）. The second local optimization is HC segmentation, which is executed to divide HC to n four vertices and three lines LHPs to generate the shorter HC. The sum of the LHPs is divided by 1/3. After crossover, if the positions in offspring HCs are the same, the duplicated positions of un-exchanged part are exchanged with the same positions of the father HCs of exchanged part. To prove the efficiency of the 4V3LGA 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 better approximate solutions than other two algorithms. It can be used to find shorter TSP HC.

Key words: genetic algorithm, traveling salesman problem, two-phase strategies, four vertices and three lines

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

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