改进的遗传算法求解TSP问题的应用与研究

发布时间：2018-08-31 18:07

【摘要】：旅行商问题是一个经典组合优化方面的问题。随着城市集群的规模迅猛增长,旅行商问题在搜索空间里变得越来越难寻找最优解。同时,过于冗余的改进算法给程序带来更多的负面影响。因此,寻找一个高效和便捷的遗传算法计算框架成了众多学者的研究重点。对于旅行商问题这类完全问题,遗传算法具有全局搜索的优势,而它的局部搜索能力不足以及收敛速度缓慢。在传统精确算法中,它们多为局部搜索算法,一般得到局部较优解,即对小范围的城市群能够准确求出近似解。因此,近年来不断改进的遗传算法有通过和传统算法相结合成混合算法来改进,以便达到优势互补。除此之外,它也有借助相关策略的改进来提高遗传算法的性能。在改进算法中,鲜有人突出提出对于城市信息预处理来克服那些不足,有的是基于数据挖掘算法中的k均值聚类算法与遗传算法的混合算法的提出。聚类算法是以迭代时间的巨大代价来换取遗传算法处理能力的提高。本文出发点依然是围绕传统遗传算法解决旅行商问题所遇到的两大问题,采取一种直接划分地图而形成区域网格的简单方式,通过划分处理城市信息数据进而改进路径编码。改进的遗传算法是将原来城市群的坐标数据根据地图区域网格单位的划分进行数据信息预处理而达到地图压缩和提炼有用信息的目的。改进的遗传算法基于对于原始数据进行域规则的数据预处理,提出了一种对传统路径编码,以及诸算子改进的遗传算法。改进的遗传算法的数据预处理将根据地图区域化特点进行网格区域划分处理,且采用提前培育的局部优秀基因块,再与整体相结合完成分阶段初始化。同时,区域划分必然存在邻近区域,进而有了对于诸算子的发生位置的指导以及发生概率的影响。后续依托数据预处理阶段处理得到的结果信息对初始种群算子,以及选择、交叉和变异等算子进行相应的改进。正因为它运用类似聚类的算法划分,与数据挖掘算法的混合算法相比较而言,前期处理变得简单。研究实现结果表明,通过对城市数据进行域规则的预处理以及配套的策略相结合,可提高遗传算法的收敛速度和精确度。
[Abstract]:The traveling salesman problem is a classical combinatorial optimization problem. With the rapid growth of urban clusters, the traveling salesman problem becomes more and more difficult to find the optimal solution in the search space. At the same time, the redundant improved algorithm brings more negative effects to the program. Therefore, the search for an efficient and convenient genetic algorithm computing framework has become the focus of many scholars. For the complete problem such as traveling salesman problem, genetic algorithm has the advantage of global search, but its local search ability is insufficient and the convergence speed is slow. In the traditional exact algorithms, most of them are local search algorithms. Generally, the local optimal solution is obtained, that is, the approximate solution can be accurately obtained for the small urban agglomeration. Therefore, the genetic algorithm which has been improved in recent years has been improved by combining the traditional algorithm with the hybrid algorithm in order to achieve complementary advantages. In addition, it also improves the performance of genetic algorithm by the improvement of related strategies. In the improved algorithm, few people put forward to the city information preprocessing to overcome those shortcomings, some of the data mining algorithm based on the k-means clustering algorithm and genetic algorithm hybrid algorithm proposed. Clustering algorithm is a huge cost of iterative time in exchange for the improvement of genetic algorithm processing capacity. The starting point of this paper is still around the traditional genetic algorithm to solve the two major problems encountered in the traveling salesman problem, using a direct map to form a simple way to form a regional grid, by dividing the processing of urban information data and improve the path coding. The improved genetic algorithm is to preprocess the coordinate data of the original urban agglomeration according to the division of the grid units of the map area to achieve the purpose of map compression and extraction of useful information. Based on the data preprocessing of domain rules for raw data, the improved genetic algorithm (GA) is proposed to encode the traditional path and improve the operators. The data preprocessing of the improved genetic algorithm will be processed according to the characteristics of map regionalization. The improved genetic algorithm will adopt the local excellent gene blocks which are cultivated in advance and complete the initialization by stages in combination with the whole. At the same time, there must be adjacent regions in the division of regions, which will have the influence on the location of the operators and the probability of occurrence. The initial population operator, selection operator, crossover operator and mutation operator are improved based on the result information of the data preprocessing stage. Because it uses clustering-like algorithm partitioning, compared with the mixed algorithm of data mining algorithm, the preprocessing becomes simple. The results show that the convergence speed and accuracy of the genetic algorithm can be improved by preprocessing the urban data with domain rules and combining the corresponding strategies.
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】