一种求解TSP问题的多策略改进蚁群算法

作者：尚宝平; 焦建强^*; 裴杰; 周坤; 闫富宏

来源：数学的实践与认识, 2019, 49(02): 215-224.

• 旅行商问题
• 蚁群算法
• 均值交叉算子
• 精英策略

蚁群算法是一种求解复杂组合优化问题的启发式仿生进化算法,并是求解TSP问题行之有效的一种随机算法.但此算法仍存在求解精度低、易陷入局部最优及求解效率低的问题,针对该问题提出一种多策略改进蚁群算法.采用最近邻法影响初始信息素的分布,达到降低算法初期较短路径上信息素浓度的目的,并在转移规则变异调整的基础上,结合路径的均值交叉进化策略,增强算法探索全局解空间和避免陷入局部最优的能力.然后,结合迭代和精英策略对信息素更新机制进行改进,进一步提高化算法的求解性能及求解效率,最后,对从TSPLIB数据库选出的8个实例进行求解并与其他算法进行对比,实验结果表明,改进算法在求解旅行商问题时的高效性,且具有较高的运算性能.

• 单位
  郑州轻工业学院; 机电工程学院