一种面向对象的多角色蚁群算法及其TSP问题求解  

An object-oriented multi-role ant colony optimization algorithm for solving TSP problem

作　　者：杜鹏桢 唐振民[1] 孙研[1] 

机构地区：[1]南京理工大学计算机科学与工程学院,南京210094

出　　处：《控制与决策》2014年第10期1729-1736,共8页Control and Decision

基　　金：国家自然科学基金项目(91220301;61371040);高等学校学科创新引智计划课题(B13022)

摘　　要：蚁群算法的改进大多从算法本身入手或与其他算法相结合,未充分利用待解决问题所包含的信息,提升效果较为有限.对此,提出一种面向对象的多角色蚁群算法.该算法充分利用旅行商问题(TSP)对象的空间信息,采用k-均值聚类将城市划分为不同类别;同时,对蚁群进行角色划分,不同角色的蚁群针对城市类别关系执行各自不同的搜索策略,增强了蚁群的搜索能力,较大幅度地提高了求解质量.每进行一次迭代,仅各角色最优个体进行信息素更新,防止算法退化为随机的贪婪搜索.将精英策略与跳出局部最优相结合可避免算法的停滞.50个经典TSP实例仿真实验表明:所提出的算法可以在较少的迭代次数内获得或非常接近于问题的已知最优解;对于大规模TSP问题所得结果也远超所对比的算法.Most of the improvements on the ant colony algorithm are based on the algorithm itself or combined with other algorithms, which underutilizes information of the problems to be solved, so the effect is not ideal. An object-oriented multi-role ant colony optimization（OMACO） algorithm is proposed to deal with the characteristics of traveling salesman problem（TSP） on the basis of k-means, which divides the cities into different categories with full use of the TSP spatial information and divides the colony into different roles. Each role solves the problem independently according to their respective strategies, which enhances the algorithm＇s search capability and improves the quality of solution. After each iteration, only the optimal solution of each role is applied to update the pheromone, which prevents premature convergence. The elitist strategy combined with local optima jumping is used again to the stagnation of the algorithm. Many experiments of 50 classic TSP instances show that the OMACO algorithm can obtain the known optimal solution in fewer iterations. For large-scale TSP instances, the proposed algorithm is also far better than the comparison algorithms.

关 键 词：蚁群算法 面向对象 多角色 K-均值 旅行商问题 2-Opt 

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