摘要
蚁群优化算法是一种求解组合优化难题的强启发式算法,它利用正反馈和并行计算原理,具备很强的搜索能力。近年来,蚁群优化算法广泛应用于TSP问题的研究。本文提出分支蚁群动态扰动(DPBAC)算法,该算法主要从5个方面对基本蚁群算法做出改进:引入分支策略选取出发城市;改进状态转移规则;引入变异策略改进蚂蚁路径;改进信息素更新规则;引入条件动态扰动策略。实验表明,该算法可以有效改善基本蚁群算法搜索时间较长、容易陷入局部极小等缺点。
Ant Colony Optimization（ ACO） algorithm is a kind of meta- heuristic algorithm for solving NP- hard problems. Using positive feedback and parallel- computing principle, it has strong capability to explore solution. Recently,ACO algorithm is widely used to study TSP problems. This paper proposes Branching Ant Colony with Dynamic Perturbation（DPBAC）algorithm,which improves traditional ACO algorithm in 5 aspects： introducing Branching Method to choose starting points, improving state transition rules, introducing Mutation Method to shorten tours, improving pheromone updating rules and introducing Conditional Dynamic Perturbation Method. Showed by simulated experiments, DPBAC algorithm can improve the shortcomings, as costing too much time and tending to stick in local minimum and so on,of traditional ACO algorithm.
出处
《中国管理科学》
CSSCI
2005年第6期57-63,共7页
Chinese Journal of Management Science
基金
教育部科学技术研究重点项目(104107)
安徽省教育厅自然科学重点科研项目(2004kj308zd)
安徽省自然科学基金项目(050460401)
关键词
TSP
蚁群优化算法
分支策略
条件动态扰动策略
Traveling Salesman Problem
Ant Colony Optimization algorithm
Branching Method
Conditional Dynamic Perturbation Method
