| 旅行商问题研究及混合粒子群算法求解 |
| |
| 引用本文： | 孙聪,赵新超. 旅行商问题研究及混合粒子群算法求解[J]. 计算机工程与应用, 2009, 45(25): 38-40. DOI: 10.3778,j.issn.1002-8331.2009.25.012 |
| |
| 作者姓名： | 孙聪 赵新超 |
| |
| 作者单位： | 北京邮电大学理学院数学系,北京,100876;北京邮电大学理学院数学系,北京,100876 |
| |
| 基金项目： | 国家自然科学基金，中国科学院数学机械化重点实验室开放课题基金 |
| |
| 摘 要： | 定性地分析了基本粒子群算法，结合遗传算法思想，构造了3种杂交和4种变异运算法则，从而得到了12种混合粒子群算法，并采用14城市算例对其检验和分析。为进一步验证混合算法的性能，根据分析结果挑选了几种较优的混合算法用以解决中国34城市（CTSP）问题和kroC100问题，其中CTSP问题很快达到最优解，对kroC100问题该文提供的算法获得了一个比现有已知结果更好的结果。
|
| 关 键 词： | 旅行商问题 粒子群算法 2-opt 3-opt 遗传算法 |
| 收稿时间： | 2008-10-23 |
| 修稿时间： | 2009-1-12 |
Research on traveling salesman problem and its solving with hybrid particle swarm optimization algorithm |
| |
| SUN Cong,ZHAO Xin-chao. Research on traveling salesman problem and its solving with hybrid particle swarm optimization algorithm[J]. Computer Engineering and Applications, 2009, 45(25): 38-40. DOI: 10.3778,j.issn.1002-8331.2009.25.012 |
| |
| Authors: | SUN Cong ZHAO Xin-chao |
| |
| Affiliation: | Department of Mathematics，School of Science，Beijing University of Posts and Telecommunications，Beijing 100876，China |
| |
| Abstract: | This paper qualitatively analyzes the basic Particle Swarm Optimization(PSO) algorithm.Integrating the ideas of genetic algorithm,3 kinds of crossover and 4 mutation operators are constructed and 12 hybrid PSO algorithms are obtained.A 14-city problem is firstly used to examine and analyze the proposed algorithms.To further verify the proposed algorithms'performance, several good hybrid algorithms are selected based on the analytic results to solve the Chinese 34-city problem(CTSP) and the kroC100 problem.T... |
| |
| Keywords: | 2-opt 3-opt |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
