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

蚁群算法的改进大多从算法本身入手或与其他算法相结合,未充分利用待解决问题所包含的信息,提升效果较为有限.对此,提出一种面向对象的多角色蚁群算法.该算法充分利用旅行商问题(TSP)对象的空间信息,采用k-均值聚类将城市划分为不同类别;同时,对蚁群进行角色划分,不同角色的蚁群针对城市类别关系执行各自不同的搜索策略,增强了蚁群的搜索能力,较大幅度地提高了求解质量.每进行一次迭代,仅各角色最优个体进行信息素更新,防止算法退化为随机的贪婪搜索.将精英策略与跳出局部最优相结合可避免算法的停滞.50个经典TSP实例仿真实验表明:所提出的算法可以在较少的迭代次数内获得或非常接近于问题的已知最优解;对于大规模TSP问题所得结果也远超所对比的算法.

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

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 ??-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.