An Improved Ant Colony Algorithm For Shortest Path

The shortest path problem (SP) is one of the classical optimal problems, so it has been widely studied for last semicentury. The shortest path problem is to find a path of two points with the minimum total weight. At present, the exact algorithm of SP has been perfect, while with the rapid development of information technology and artificial intelligence, more attentions were given to heuristic algorithm. Exact algorithm and heuristic algorithm for shortest path were reviewed in this work. Ant colony algorithm and the essence of it were introduced, at the same time, an improved ant colony algorithm were given in this work. According to some defect of ant colony algorithm such as be short of initial information and it can easily run into the local optimum, it was improved through followings: adjust parameter q₀ for dynamic problems, standardization ofτ_ij and a new global updating equation is designed. The complexity and convergence of the improved algorithm were also analyzed. Finally, the discussion of the effect of parameter on algorithm was performed.