| 求解TSP的一种改进遗传算法 |
| |
| 引用本文： | 彭丹平,林志毅,王江晴.求解TSP的一种改进遗传算法[J].计算机工程与应用,2006,42(13):91-93. |
| |
| 作者姓名： | 彭丹平 林志毅 王江晴 |
| |
| 作者单位： | 1. 中南民族大学计算机学院,武汉,430074
2. 武汉理工大学计算机学院,武汉,430070 |
| |
| 基金项目： | 中国科学院资助项目;湖北省自然科学基金;上海市教委资助项目;上海市重点学科建设项目 |
| |
| 摘 要： | TSP问题是典型的NP-hard组合优化问题,GA是求解此类问题的一种方法。但它存在如何较快地找到最优解并防止“早熟”收敛的问题。文章针对上述问题并结合TSP问题的特点,提出了改进的遗传算法。它从相似性的思想出发,按适应值相似性将群体分级,在不同的级内采用不同的操作,产生数目不等的新解并利用加速算子使其更接近局部极小值。改进后的算法较好地解决了群体多样性与收敛性的矛盾。实验结果表明,该文算法的改进是有效的。
|
| 关 键 词： | TSP问题 遗传算法 分级 精英选择策略 启发式交叉算子 贪婪倒位变异算子 |
| 文章编号： | 1002-8331-（2006）13-0091-03 |
| 收稿时间： | 2005-07 |
| 修稿时间： | 2005-07 |
An Improved Genetic Algorithm for TSP Problem |
| |
| Peng Danping,Lin Zhiyi,Wang Jiangqing.An Improved Genetic Algorithm for TSP Problem[J].Computer Engineering and Applications,2006,42(13):91-93. |
| |
| Authors: | Peng Danping Lin Zhiyi Wang Jiangqing |
| |
| Affiliation: | 1 College of Computer Sciences, South-Central University for Nationalities, Wuhan 430074; 2 College of Computer Sciences, Wuhan University of Technology, Wuhan 430070 |
| |
| Abstract: | TSP is a classical NP-hard combinatorial optimization problem.GA is a method for solving this problem.But it is hard for GA to find global optimization quickly and prevent premature convergence.This paper,in order to solve the problem,considering the characteristic of TSP,puts forward an improved genetic algorithm,which based on similitude,classifying the population by similitude.Each level with its respective operations generates new solutions in different numbers and accelerates the new solutions to approach the local minimum by accelerated operator.The improved algorithm can solve the conflict between population diversity and algorithm convergence.The experimental re suit indicates that it is effective. |
| |
| Keywords: | TSP Problem Genetic Algorithm classification elitist selection strategy heuristic crossover operator greedy inverse mutation operator |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
