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

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

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

英文关键词  ant-colony optimization algorithm  premature convergence  state transition rule

中文摘要

      蚁群算法在优化领域, 尤其在组合优化问题中获得了较为成功的应用, 然而它存在易于早熟收敛、搜索时间长等不足. 针对该问题, 提出了一种改进算法. 该算法一方面在典型的状态转移规则中融合了一种随机选择策略, 保证算法始终具有一定的探索能力; 另一方面在搜索过程中保持一个优解池, 通过交替使用池中最优解和其它次优解更新信息素, 达到平衡算法强化搜索和分散搜索的目的. 文中讨论了相关参数的选取方法, 分析了所提算法的计算复杂度和收敛性, 并针对典型的旅行商问题进行了仿真实验, 结果表明该算法获得的解质量高于其他已有算法.

英文摘要

      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.