Abstract: 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.

Key words: Traveling Salesman Problem, Ant Colony Optimization algorithm, Branching Method, Conditional Dynamic Perturbation Method