多优解更新信息素的混合行为蚁群算法  

Hybrid-behavior ant-colony optimization algorithm with pheromone updated by multiple good solutions

作　　者：任志刚[1] 冯祖仁[1] 张兆军[1] 

机构地区：[1]西安交通大学系统工程研究所制造系统工程国家重点实验室,陕西西安710049

出　　处：《控制理论与应用》2010年第9期1201-1206,共6页Control Theory & Applications

基　　金：国家自然科学基金资助项目(60875043);国家重点基础研究发展计划("973"计划)资助项目(2007CB311006)

摘　　要：蚁群算法在优化领域,尤其在组合优化问题中获得了较为成功的应用,然而它存在易于早熟收敛、搜索时间长等不足.针对该问题,提出了一种改进算法.该算法一方面在典型的状态转移规则中融合了一种随机选择策略,保证算法始终具有一定的探索能力;另一方面在搜索过程中保持一个优解池,通过交替使用池中最优解和其它次优解更新信息素,达到平衡算法强化搜索和分散搜索的目的.文中讨论了相关参数的选取方法,分析了所提算法的计算复杂度和收敛性,并针对典型的旅行商问题进行了仿真实验,结果表明该算法获得的解质量高于其他已有算法.Ant-colony optimization algorithm（ACO） has been successfully applied to the optimization field, especially to combinatorial optimization problems. However, it may encounter premature convergence or costs an excessively long computation-time. To overcome these shortcomings, we present an improved ACO algorithm. This algorithm incorporates a random selection-strategy into the typical state transition rule, for ensuring its exploration ability. Meanwhile, the algorithm maintains a good-solution pool and alternately uses the optimal solution or the sub-optimal solution from the pool to update the pheromone. Thus, the intensification and the diversification of search are balanced. We also discuss the settings of related parameters, and analyze the computational complexity and convergence of the proposed algorithm. Additionally, simulation experiment is performed on typical traveling salesman problems. The results demonstrate that this algorithm generates higher quality solutions than existing algorithms.

关 键 词：蚁群算法 早熟收敛 状态转移规则 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]