摘要
遗传算法容易产生早熟现象以及局部寻优能力较差的缺陷。针对遗传算法的这一缺点,就遗传算法的交叉算子进行改进,并应用于求解旅行商问题。传统的交叉算子操作方法寻优效率低,并易陷入局部最优,就顺序交叉方法进行改进。改进后的交叉算子是在随机选择交叉区域和交叉片断长度后,对重复节点和前后节点的路径长度进行比较后,再删除路径长的重复节点,有效地提高了算法的寻优效率,优化了解的质量。为了验证算法的有效性,对TSPLIB库中的两个公共实际事例eil51和gr202以及安徽省17个城市的数据进行了仿真实验,结果表明改进后的算法是有效的。
Genetic Algorithm is prone to be pre mature optimization, and less capable in local optimization. In terms of the shortcomings of Genetic Algorithm, this paper aims at making some improvements with the crossover operator of Genetic Algorithm and applying the improved algorithm in the solution to TSP. The traditional crossover operator optimization methods are of low efficiency, and easy to fall into local optimum. The improved crossover operator first makes random selection in the cross-region and cross-fragment length, and later compares the length of the path, and then deletes the duplicate node path length, which improves the algorithm efficiency and improves the solution quality. The proposed Algorithm was evaluated on the two public data gr202 and ei151 in TSPLIB library and the TSP data from 17 cities in Anhui Province. The results show the effectiveness of the improved genetic algorithm.
出处
《淮南师范学院学报》
2009年第5期114-119,共6页
Journal of Huainan Normal University
关键词
TSP
遗传算法
交叉算子
TSP
Genetic Algorithm
crossover operator
