| 解决TSP问题的一种改进遗传算法 |
| |
| 引用本文： | 潘益民,吴龙树.解决TSP问题的一种改进遗传算法[J].宁波教育学院学报,2010,12(2):74-76. |
| |
| 作者姓名： | 潘益民 吴龙树 |
| |
| 作者单位： | 中国计量学院理学院,浙江杭州,310018 |
| |
| 摘 要： | TSP是一个典型的组合优化问题,也是一个NP难题,其可能的路径总数是随着城市数目n的增长而成几何型增长的,所以一般很难准确地求出其最优解,因而寻找出有效的近似求解算法就成了解决此问题的最佳方法。文章首先介绍了在初始化阶段经行改进的遗传方法。通过把改进方法同标准的遗传算法相比较,得出改进遗传算法在性能上有改进。最后,我们还分析了实验结果并提出了评价初始解优劣的一个指标函数——局部相似度函数,并给出了函数的具体表达式。
|
| 关 键 词： | TSP 旅行商问题 遗传算法 |
An Advanced Genetic Algorithms for TSP |
| |
| PAN Yi-min,WU Long-shu.An Advanced Genetic Algorithms for TSP[J].Journal of Ningbo Institute of Education,2010,12(2):74-76. |
| |
| Authors: | PAN Yi-min WU Long-shu |
| |
| Institution: | College of Science/a>;China Jiliang University/a>;Hangzhou 310018/a>;China |
| |
| Abstract: | TSP is a typical combinatorial optimization problems,and is an NP problem. The number of possible paths grows rapidly when the number of cities is increased slowly,so it is difficult to accurately get the optimal solution,thus to find effective approximation algorithm to get the near optimal solution has become the best way. Firstly,the article provides an advanced genetic algorithm in the initialization part. Through comparison between the advanced genetic algorithm and the standard one,we get the conclusi... |
| |
| Keywords: | TSP traveling salesman problem genetic algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
