指针网络改进遗传算法求解旅行商问题  

Pointer Network Improved Genetic Algorithm for Solving Traveling Salesmen Problem

作　　者：陈思远 林丕源[1] 黄沛杰[1] CHEN Siyuan;LIN Piyuan;HUANG Peijie(College of Mathematics and Informatics,South China Agricultural University,Guangzhou 510642,China)

机构地区：[1]华南农业大学数学与信息学院,广州510642

出　　处：《计算机工程与应用》2020年第19期231-236,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.71472068)。

摘　　要：针对遗传算法在求解旅行商问题时,受限于初始种群质量而存在收敛速度慢、易陷入局部最优等问题,提出一种基于指针网络改进遗传算法种群模型。通过经改进指针网络生成初始种群取代原种群,并结合基于汉明距离轮盘赌策略对种群个体进行择优,形成个体质量和种群多样性高的新种群。实验在TSPLIB标准库上多组实例进行测试,并和研究进展种群改进算法和多种主流启发式算法进行多项系数对比。结果表明,经过优化后算法的收敛速度和寻优能力有显著提高,能够有效用于改善遗传算法在旅行商问题上的应用。Aimed to solve the problem that traditional genetic algorithm with poor-quality initial population easily traps into local optimum and has slow convergence speed when applied to traveling salesmen problem, this paper proposes a new algorithm model using pointer network to improve genetic algorithm for solving traveling salesmen problem. Pointer network is a effective deep learning neural network for solving combinatorial optimization problem which can provides high quality near-optimal solution. The new model uses the superior generation retention strategy and hamming distance roulette strategy on solution set from pointer network to make it become a high-quality and diversity initial population.Simulation experiment is compared new model with tradition genetic algorithm on various test instances from TSPLIB.Experimental results show that performance of new model is better than tradition genetic algorithm in both convergence speed and optimizing capacity. It is proved that pointer network hybrid genetic algorithm model is advantage on solving Traveling Salesmen Problem(TSP).

关 键 词：指针网络 遗传算法 初始种群 旅行商问题 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]