基于域规则预处理解决旅行商问题的遗传算法

摘要

Traveling salesman problem (TSP) is a classic combinatorial optimization problem.Based on the domain preprocessing of primary data,the paper proposes a genetic algorithm by encoding traditional path and im-proving these operators.Data preprocessing of the improved genetic algorithm makes the processing of the grid di-vision according to the regional characteristics of maps,nurtures the local excellent genetic blocks in advance,and then combines with the overall cities to finish the staged initialization.At the same time,there must be adjacent ar-eas after the processing of regional division,which gives the guidance of the position and the occurrence probabili-ty in these operators.The research results show that the genetic algorithm can improve the convergence speed and accuracy through the combination of the rules for urban data preprocessing and related strategies.%旅行商问题(TSP)是一个经典组合优化方面的问题.本文基于原始数据进行域规则的数据预处理,提出了一种对传统路径编码,以及诸算子改进的遗传算法.改进的遗传算法的数据预处理将根据地图区域化特点进行网格区域划分处理,且采用提前培育的局部优秀基因块,再与整体相结合完成分阶段初始化.同时,区域划分必然存在邻近区域,进而有了对于诸算子的发生位置的指导以及发生概率的影响.研究实现结果表明,通过对城市数据进行规则的预处理以及配套的策略相结合,可提高遗传算法的收敛速度和精确度.