分支蚁群动态扰动算法求解TSP问题

• 作 者: 刘心报 叶强 刘林 杨善林
• 机 构: 合肥工业大学管理学院
• 出 处: 中国管理科学
• 发表日期: 2005年6期
• 关键词: TSP 蚁群优化算法 分支策略 条件动态扰动策略 Traveling Salesman Problem Ant Colony Optimization alg
• 基金项目: 重庆市应用基础研究基金，安徽省教育厅科研项目，安徽省自然科学基金

蚁群优化算法是一种求解组合优化难题的强启发式算法,它利用正反馈和并行计算原理,具备很强的搜索能力.近年来,蚁群优化算法广泛应用于TSP问题的研究.本文提出分支蚁群动态扰动(DPBAC)算法,该算法主要从5个方面对基本蚁群算法做出改进:引入分支策略选取出发城市;改进状态转移规则;引入变异策略改进蚂蚁路径;改进信息素更新规则;引入条件动态扰动策略.实验表明,该算法可以有效改善基本蚁群算法搜索时间较长、容易陷入局部极小等缺点.