改进的蚁群与粒子群混合算法求解旅行商问题  

Improved Ant Colony-Particles Swarm Hybrid Algorithm for Solving TSP

作　　者：汪冲[1,2] 李俊[1,2] 李波[1,2] 张粤[1,2] 

机构地区：[1]武汉科技大学计算机科学与技术学院,湖北武汉430065 [2]智能信息处理与实时工业系统湖北省重点实验室,湖北武汉430065

出　　处：《计算机仿真》2016年第11期274-279,共6页Computer Simulation

基　　金：国家自然科学基金(61273303;61572381);武汉科技大学研究生创新创业基金(JCX2015009);武汉科技大学大学生科技创新基金(15ZRC101)

摘　　要：针对蚁群算法在求解旅行商问题时易陷入局部最优,且寻优速度慢的问题,提出改进的蚁群与粒子群混合算法用于求解旅行商问题。在初始阶段,改进算法采用贪婪算法初始化粒子,生成信息素分布。在迭代运行过程中,采用改进蚁群算法的信息素更新方式,增加信息素调节算子。同时,采取与全局最优粒子自适应交叉变异策略,根据粒子适应度值的变化采取对粒子位置的更新。通过对TSPLIB标准库中5个实例进行仿真测试,结果表明,改进的算法能有效避免陷入局部最优,具有较快的收敛速度和较高收敛精度。为求解旅行商问题提供一种有效的方法。Aiming at the problem that ant colony optimization algorithm is easy to fall into local optimum and has slow convergence speed, an improved ant colony-particle swarm hybrid algorithm was proposed to solve the traveling salesman problem. In the initial stage of the new method, we used the greedy algorithm to initialize the particle and generated a pheromone distribution. In the iterative operation, we modified the ant colony algorithm pheromone update format and added pheromone regulate operator. Meanwhile, the adaptive crossover and mutation strategy were used for the global optimal particle, which changed the particle＇ s position according to the fitness. Simulation experiments on 5 TSP problems from TSPLIB show that, the improved algorithm can effectively avoid falling into local opti- mum, and has better convergence speed and higher convergence precision. It provides an effective method for solving the traveling salesman problem.

关 键 词：蚁群算法 粒子群算法 旅行商问题 信息素 全局最优 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]