基于聚类集成的蚁群优化与受限解空间的TSP算法

作者：庞永明; 钟才明; **

来源：中国科学技术大学学报, 2016, 46(09): 780-787.

• 蚁群算法
• TSP
• 关联矩阵
• 受限解空间

蚁群算法是一种元启发式搜索算法,能有效地解决TSP这类NP问题.针对该算法的信息素更新机制易导致陷入局部最优的缺点,提出了一种基于聚类集成的蚁群优化与受限解空间的TSP算法.其主要思想如下:先用三角形TSP算法生成初始TSP并构建蚁群的初始转移概率矩阵,以减少蚂蚁选择的随机性;然后运用k-means聚类集成生成关联矩阵,作为扰动因子以优化蚂蚁对城市的选择概率,即关联城市相互吸引,不关联城市相互排斥,以避免过早陷入局部最优;最后提出一种重组受限解空间的边的方法再次优化蚁群的解.实验结果表明,与同类算法相比,该算法具有较优的结果.

• 单位
  宁波大学科学技术学院; 宁波大学