Abstract: In the paper, a new class of ant colony optimization algorithm is proposed, in which pheromone is classified into finite grades, pheromone updating is realized by changing the grades, and the updated quantity of pheromone is independent of the objective function values. It is proved by means of finite Markov chains theory that the algorithm converges to the global optimal solutions linearly. Compared with MMAS, ACS and some other ant colony optimization algorithms for the Traveling Salesman Problem, the calculating results demonstrate that the proposed algorithm is effective and robust.