基于选路优化的改进蚁群算法  

Improved ant colony optimization algorithm based on route optimization

作　　者：张毅[1] 梁艳春[1] 

机构地区：[1]吉林大学计算机科学与技术学院国家教育部符号计算与知识工程重点实验室

出　　处：《计算机工程与应用》2007年第2期60-63,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(60433020);高等学校博士学科点专项科研基金资助项目(20030183060);吉林省科技发展计划资助项目(20030520)。

摘　　要：蚁群算法在处理大规模优化问题时效率很低。为此对蚁群算法提出了基于选路优化的两点改进:(1)引入选路优化策略,减少了算法中蚁群的选路次数,显著提高了算法的执行效率。(2)在选路操作中,只根据当前城市的前C个距离最近的且未经过城市为候选城市计算选择概率,从而减少单个蚂蚁选路的计算量。尤其对于以往较难处理的大规模TSP问题,改进算法在执行效率上有明显的优势。模拟实验结果表明改进算法较之基本蚁群算法在收敛速度有明显提高。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 he enhanced greatly compared with the traditional ACO.

关 键 词：蚁群算法 旅行商问题 选路策略 并行策略 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]