| 求解TSP问题的一种改进的遗传算法 |
| |
| 引用本文： | 谢胜利,唐敏,董金祥.求解TSP问题的一种改进的遗传算法[J].计算机工程与应用,2002,38(8):58-60,245. |
| |
| 作者姓名： | 谢胜利 唐敏 董金祥 |
| |
| 作者单位： | 1. 温州师范学院计算机科学系,温州,325003,E-mail:xieshengli@mail.wzptt.zj.cn浙江大学人工智能研究所,杭州,310027
2. 浙江大学人工智能研究所,杭州,310027 |
| |
| 基金项目： | 国家自然科学基金资助，国家863高技术推广计划CIMS主题资助项目(编号:863-511-04-0205) |
| |
| 摘 要： | TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种理想方法。文章针对解决TSP问题,提出使用改进的遗传算法,即用浓度控制选择策略以保证群体的多样性,用贪婪交叉算子和启发式倒位变异算子来提高算法的收敛速度,较好地解决了群体的多样性和收敛速度的矛盾。算法的分析和测试表明,该文算法的改进是有效的。
|
| 关 键 词： | TSP 遗传算法 浓度控制 贪婪交叉算子 |
| 文章编号： | 1002-8331-(2002)08-0058-03 |
An Improved Genetic Algorithm for TSP Problem |
| |
| Xie Shengli , Tang Min Dong Jinxiang.An Improved Genetic Algorithm for TSP Problem[J].Computer Engineering and Applications,2002,38(8):58-60,245. |
| |
| Authors: | Xie Shengli Tang Min Dong Jinxiang |
| |
| Affiliation: | Xie Shengli 1,2 Tang Min 2 Dong Jinxiang 21 |
| |
| Abstract: | TSP(Traveling Salesman Problem)is a typical NP-Complete problem,genetic algorithm(GA)is the perfect method for solving NP -Complete problem.This paper,in order to solve the contradiction between the diversity of population and the convergence speed of algorithm,puts forward an improved genetic algorithm,which use density control selection operator to protect diversity of population and use greedy crossover operator and heuristic inverse mutation operator to enhance the convergence speed.As it is proved by analysis and test,a better result is obtained by the improved genetic algorithm. |
| |
| Keywords: | Traveling Salesman Problem(TSP) Genetic Algorithm Density Control Greedy Crossover |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
