|
Branching Ant Colony with Dynamic Perturbation Algorithm for Solving TSPs
LIU Xin-bao, YE Qiang, LIU Lin, YANG Shan-lin
2005, (6):
57-63.
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.
References |
Related Articles |
Metrics
|