摘要
旅行商问题(TSP)是一个经典组合优化方面的问题。本文基于原始数据进行域规则的数据预处理,提出了一种对传统路径编码,以及诸算子改进的遗传算法。改进的遗传算法的数据预处理将根据地图区域化特点进行网格区域划分处理,且采用提前培育的局部优秀基因块,再与整体相结合完成分阶段初始化。同时,区域划分必然存在邻近区域,进而有了对于诸算子的发生位置的指导以及发生概率的影响。研究实现结果表明,通过对城市数据进行规则的预处理以及配套的策略相结合,可提高遗传算法的收敛速度和精确度。
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 improving these operators. Data preprocessing of the improved genetic algorithm makes the processing of the grid division 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 areas after the processing of regional division, which gives the guidance of the position and the occurrence probability 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.（Faculty of Information Engineering, Jiangxi university of Science and Technology, Jiangxi Ganzhou 341000 ）
出处
《科技广场》
2015年第9期6-15,共10页
Science Mosaic
关键词
数据预处理
邻近域
路径域混合编码
旅行商问题
Data Preprocessing
Adjacent Domain
Mixture Code of Path and Domain
Traveling Salesman Problem
