| 一种改进的遗传算法求解TSP问题 |
| |
| 引用本文： | 张晓玲.一种改进的遗传算法求解TSP问题[J].大理学院学报,2009,8(4). |
| |
| 作者姓名： | 张晓玲 |
| |
| 作者单位： | 大理学院数学与计算机学院,云南大理,671003 |
| |
| 摘 要： | 提出一种基于顶点的候选表进行交配的遗传算法(Candidate Crossover Genetic Algorithm,CCGA)求解旅行商问题(TSP).遗传算法(GAs)是一种广泛使用的全局优化算法,并且已经成功地用于求解TSP.但是传统的遗传算法的交配算子缺乏指导性和启发性,交配算子随机的选择父体基因进行交配,导致GAs求解速度慢、解的精度不高等不足.通过分析TSP问题本身的特征,给出了一个使用已有的邻接边的信息和路径信息生成顶点的候选表,然后基于顶点的候选表进行交配的交配算子,使用该交配算子的遗传算法在求解TSP问题时性能上得到了很大的提高,通过TSP Lib上的测试样例将该CCGA和传统的遗传算法进行比较.比较结果表明CCGA具有更大的优势,它能使算法求解到近似最优解和最优解只存在很小的偏差.
|
| 关 键 词： | 遗传算法 旅行商问题 候选表 交配算子 邻接边 距离 |
An Improved Genetic Algorithms in Solving Traveling Salesman Problem |
| |
| Zhang Xiaoling.An Improved Genetic Algorithms in Solving Traveling Salesman Problem[J].Journal of Dali University,2009,8(4). |
| |
| Authors: | Zhang Xiaoling |
| |
| Affiliation: | College of Mathematic and Computer Science;Dali University;Dali;Yunnan 671003;China |
| |
| Abstract: | This paper proposed a candidate crossover genetic algorithm(CCGA)to solve the traveling salesman problem(TSP).GAs are widely used as optimized technology and has been applied to the TSP successfully.However,the traditional crossover methods in GAs lack heuristic guidance,and the crossover operator chooses parent gene randomly for crossing.This paper analyzed the characteristics of TSP and presented the best candidate table which can use the existing adjacent side and the information of the path and the cros... |
| |
| Keywords: | genetic algorithms traveling salesman problem candidate crossover operator adjacent side distance |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
