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

来源期刊：控制与决策2014年第10期

论文作者：杜鹏桢 唐振民 孙研

文章页码：1729 - 1736

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

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