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

摘要：

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

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

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目91220301,61371040；高等学校学科创新引智计划课题B13022

在线出版日期：2014-10-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1729-1736