| 基于选路优化的改进蚁群算法 |
| |
| 引用本文： | 张毅,梁艳春.基于选路优化的改进蚁群算法[J].计算机工程与应用,2007,43(2):60-63. |
| |
| 作者姓名： | 张毅 梁艳春 |
| |
| 作者单位： | 1. 吉林大学,计算机科学与技术学院,国家教育部符号计算与知识工程重点实验室,长春,130012;吉林粮食高等专科学校,计算机系,长春,130062
2. 吉林大学,计算机科学与技术学院,国家教育部符号计算与知识工程重点实验室,长春,130012 |
| |
| 基金项目： | 国家自然科学基金
,
高等学校博士学科点专项科研项目
,
吉林省科技发展计划 |
| |
| 摘 要： | 蚁群算法在处理大规模优化问题时效率很低。为此对蚁群算法提出了基于选路优化的两点改进:(1)引入选路优化策略,减少了算法中蚁群的选路次数,显著提高了算法的执行效率。(2)在选路操作中,只根据当前城市的前C个距离最近的且未经过城市为候选城市计算选择概率,从而减少单个蚂蚁选路的计算量。尤其对于以往较难处理的大规模TSP问题,改进算法在执行效率上有明显的优势。模拟实验结果表明改进算法较之基本蚁群算法在收敛速度有明显提高。
|
| 关 键 词： | 蚁群算法 旅行商问题 选路策略 并行策略 |
| 文章编号： | 1002-8331（2007）02-0060-04 |
| 修稿时间： | 2006-06 |
Improved ant colony optimization algorithm based on route optimization |
| |
| ZHANG Yi,LIANG Yan-chun.Improved ant colony optimization algorithm based on route optimization[J].Computer Engineering and Applications,2007,43(2):60-63. |
| |
| Authors: | ZHANG Yi LIANG Yan-chun |
| |
| Affiliation: | 1.Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education,College of Computer Science and Technology,Jilin University,Changchun 130012,China; 2.Department of Computer Science,Jilin Grain College,Changchun 130062,China |
| |
| Abstract: | Two improvements on Ant Colony Optimization(ACO) algorithm is presented in this paper.The improvements are given as follows:(1)A novel optimized implementing approach is designed to reduce the processing costs involved with routing of ants in the conventional ACO.(2)In contrast to select the next city from all the cities not visited,the set of candidates is limited to the nearest c city.By this way the ant can reduce the time complexity of routing.The results of the simulated experiments show that the improved algorithm surpasses existing algorithms in performance for solving large-scale TSP problems.Simulations show that the speed of convergence of the improved ACO algorithm can be enhanced greatly compared with the traditional ACO. |
| |
| Keywords: | ant colony algorithm travelling salesman problem route strategy parallel strategy |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
