| 求解旅行商问题的一个改进的遗传算法 |
| |
| 引用本文： | 刘烨,倪志伟,刘慧婷.求解旅行商问题的一个改进的遗传算法[J].计算机工程与应用,2007,43(6):65-68. |
| |
| 作者姓名： | 刘烨 倪志伟 刘慧婷 |
| |
| 作者单位： | 合肥工业大学,计算机网络系统研究所,合肥,230009 |
| |
| 基金项目： | 安徽省自然科学基金
,
安徽省高校青年教师科研项目 |
| |
| 摘 要： | 利用遗传算法求解TSP问题,通常需要使用PCX,CX和OX等特殊的交叉算子以提高算法的运行效率。针对自然数编码的方式,提出一种改进的遗传算法,即改进传统的顺序交叉算子,进行不相同子排列顺序交叉,使子代继承父代中优秀的子排列,加快算法的收敛速度。另外,采用没有重复的稳态繁殖避免早熟。实验结果表明,此改进算法对于TSP和DHC问题均具有较好的性能。
|
| 关 键 词： | 旅行商问题 遗传算法 交叉算子 顺序交叉 |
| 文章编号： | 1002-8331（2007）06-0065-04 |
| 修稿时间： | 2006-06 |
Improved genetic algorithm to traveling salesman problem |
| |
| LIU Ye,NI Zhi-wei,LIU Hui-ting.Improved genetic algorithm to traveling salesman problem[J].Computer Engineering and Applications,2007,43(6):65-68. |
| |
| Authors: | LIU Ye NI Zhi-wei LIU Hui-ting |
| |
| Affiliation: | Institute of Computer Network Systems,Hefei University of Technology,Hefei 230009,China |
| |
| Abstract: | Genetic algorithm is an important method for solving traveling salesman problem.In order to improve the algorithm's rate,some special crossover operators are needed,such as partially matched crossover,cycle crossover and ordered crossover.In this paper,an improved GA is proposed for natural number encoding scheme.It will guarantee the rapid convergence of GA to use an improved ordered crossover_dissimilar ordered crossover,which makes the offspring inherits the best arrange of its parents.Otherwise,steady state reproduction without duplicates is used to avoid precocity.The results show that the proposed algorithm is effective for both TSP and DHC. |
| |
| Keywords: | traveling salesman problem genetic algorithm crossover operator ordered crossover |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
