| 引用本文: | 刘军, 王介生.旅行商问题(TSP)的伪并行遗传算法[J].控制理论与应用,2007,24(2):279~282.[点击复制] |
| LIU Jun, WANG Jie-sheng.Solving traveling salesman problem(TSP) with pseudo-parallel genetic algorithms[J].Control Theory and Technology,2007,24(2):279~282.[点击复制] |
|
| 旅行商问题(TSP)的伪并行遗传算法 |
| Solving traveling salesman problem(TSP) with pseudo-parallel genetic algorithms |
| 摘要点击 3207 全文点击 822 投稿时间：2005-06-28 修订日期：2006-05-18 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/j.issn.1000-8152.2007.2.021 |
| 2007,24(2):279-282 |
| 中文关键词 旅行商问题 无性繁殖 伪并行遗传算法 贪婪算法 |
| 英文关键词 traveling salesman problem asexual reproduction pseudo-parallel genetic algorithms greedy algorithm |
| 基金项目 国家自然科学基金资助项目(59977009). |
|
| 中文摘要 |
| 行商问题(TSP)是典型的NP完全组合优化问题.本文基于遗传算法求解TSP问题时的独特性,提出一种采用无性繁殖的改进伪并行遗传算法,避免了交叉算子对良好基因模式的破坏;初始种群通过贪婪算法得到并进行预处理,提高算法的收敛速度;伪并行遗传算法中子群体之间的信息交换采用孤岛模型.这些改进措施对降低算法的复杂程度、提高算法的收敛速度和全局搜索能力有重要意义.仿真研究结果表明,该算法的寻优效率较高,有效地克服了标准遗传算法的早熟收敛问题. |
| 英文摘要 |
| 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 velocity. 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 algorithm. Finally, simulation study of IPPGA demonstrates its capability of strong global search and superiority to SGA and high immunity against premature convergence. |