改进的智能蚁群算法在TSP问题中的应用  

Application of Improved Intelligent Ant Colony Algorithm in TSP

作　　者：尚鲜连[1] 陈静[1] 姒茂新[1] 

机构地区：[1]苏州市职业大学,江苏苏州215104

出　　处：《计算机仿真》2009年第12期160-163,共4页Computer Simulation

摘　　要：研究旅行商领域优化路径问题,解决目前蚁群算法易陷入局部最优、搜索时间长等问题。为加快算法的速度优化结果,提出了一种改进的求解TSP问题的智能蚊群优化算法。算法前期采用了一种最近节点选择策略对路径进行优化,提高了搜索效率,使之适应大规模问题求解;后期改进了基本蚁群算法中信息素、挥发因子的更新规则,通过改进使得每轮搜索后信息素的增量能更好地反映求解的质量,有效地避免陷入局部最优,加快了收敛。通过改进后的蚁群算法,对TSPLIB中部分问题的仿真结果表明,在避免陷入局部最优和缩短搜索时间方面都取得了很好的效果。证明采取的优化蚁群算法,是可行有效的。To solve the problems such as local optimum and long searching time in ACA （Ant Colony Algorithm）, an improved intelligent Ant Colony Optimization Algorithm for TSP（ Traveling Salesman Problem） is proposed. It uses recent node selection strategy to optimize the path, improve search efficiency, thus making it adapted to solve large - scale problem. It modifies the rule of updating pheromones and volatile factor in the latter algorithm, so that after every round of search, the increment of pheromone can better reflect the quality of a solution to effectively avoid local optimum and quicken the convergence. The simulation results for part of the TSPLIB problems show that the improved ant colony algorithm for solving the optimal solution and convergence properties has achieved very good results. Therefore, this Ant Colony Optimization Algorithm proved to be feasible and effective.

关 键 词：智能蚁群算法 最近节点选择 自适应调整 信息素 旅行商问题 

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