| 旅行商问题(TSP)的伪并行遗传算法 |
| |
| 引用本文： | 刘军,王介生.旅行商问题(TSP)的伪并行遗传算法[J].控制理论与应用,2007,24(2):279-282. |
| |
| 作者姓名： | 刘军 王介生 |
| |
| 作者单位： | 鞍山科技大学,电子信息与工程学院,辽宁,鞍山,114044 |
| |
| 基金项目： | 国家自然科学基金资助项目(59977009). |
| |
| 摘 要： | 旅行商问题(TSP)是典型的NP完全组合优化问题．本文基于遗传算法求解TSP问题时的独特性,提出一种采用无性繁殖的改进伪并行遗传算法,避免了交叉算子对良好基因模式的破坏;初始种群通过贪婪算法得到并进行预处理,提高算法的收敛速度;伪并行遗传算法中子群体之间的信息交换采用孤岛模型．这些改进措施对降低算法的复杂程度、提高算法的收敛速度和全局搜索能力有重要意义．仿真研究结果表明,该算法的寻优效率较高,有效地克服了标准遗传算法的早熟收敛问题．
|
| 关 键 词： | 旅行商问题 无性繁殖 伪并行遗传算法 贪婪算法 |
| 文章编号： | 1000-8152（2007）02-0279-04 |
| 收稿时间： | 2005/6/28 0:00:00 |
| 修稿时间： | 2005-06-282006-05-18 |
Solving traveling salesman problem(TSP) with pseudo-parallel genetic algorithms |
| |
| LIU Jun,WANG Jie-sheng.Solving traveling salesman problem(TSP) with pseudo-parallel genetic algorithms[J].Control Theory & Applications,2007,24(2):279-282. |
| |
| Authors: | LIU Jun WANG Jie-sheng |
| |
| Affiliation: | School of Electronic and Information Engineering, Anshan University of Science and Technology, Anshan Liaoning 114044, China |
| |
| Abstract: | Traveling salesman problem (TSP) is a typical NP complete combinatorial optimum problem.An improved pseudo-parallel genetic algorithms (IPPGA) is proposed with an asexual reproduction for avoiding crossover operators' breach to nice gene patterns.The initial population is produced by greedy algorithm in order to enhance convergence ve- locity.Information exchange between subgroups employs island model in IPPGA.These measures are of great significance on reducing complexities and enhancing convergence velocity,as well as increasing global searching ability of the algo- rithm.Finally,simulation study of IPPGA demonstrates its capability of strong global search and superiority to SGA and high immunity against premature convergence. |
| |
| Keywords: | traveling salesman problem asexual reproduction pseudo-parallel genetic algorithms greedy algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《控制理论与应用》浏览原始摘要信息 |
|
点击此处可从《控制理论与应用》下载全文 |
