An Improved Ant Colony Algorithm For TSP Problems

Combinatorial optimization problem is an important embranchment of operational research. The mathematical methods can be used to search optimization arrange, grouping, sequence or ridding of the discrete events. These problems belong to the Non-polynomial-complete (NPC) questions, which can't be solved in polynomial time. With the enlargement of the scale of question, the question space makes the characteristic of exploding up , is unlikely solved with general methods. As a NPC problem ,Traveling Salesman Problem (TSP) is a classical combinatorial optimization question, which now can only be solved by meta-heuristics to get the approximate solution.Since creating bionics in middle period of 1950's, people are being inspired from the mechanism of the biological evolution constantly. Many new methods had been applied to solve the complicated optimization problems are proposed. Such as neural network , genetic algorithm , simulated annealing , and evolution computation. These new methods had been successfully applied to solve the practice problems. Ant colony system(AS) was first proposed by Italy scholar M.Dorigo, V.Maniezzo, A.Colorni in 1992 as a novel bionic evolutionary algorithm for solving complicated combinatorial optimization problems, like the TSP, the quadratic assignment problem(QAP) and job-shop problem,etc. At present, the research work about AS already arouse the attention from more scholars and expert gradually. Though, this research approach lies at primary stage, but some research results have already demonstrated the superiority ofAS.This paper is based on the ideas of ant colony algorithm that had been proposed by scholars. We present a modified ant colony algorithm in which the precocity stagnation, which often happens in the standard any colony algorithm, is weakened by the introduction of an improved information updating strategy and a local optimization searching strategy. Experimental results for solving TSP problems with both standard ant colony algorithm and the suggested one show great effectiveness and efficiency of the proposed algorithm.