Journal of Systems Engineering and Electronics ›› 2010, Vol. 21 ›› Issue (2): 329-333.doi: 10.3969/j.issn.1004-4132.2010.02.025

• SOFTWARE ALGORITHM AND SIMULATION • Previous Articles     Next Articles

Improved ant colony optimization algorithm for the  traveling salesman problems

Rongwei Gan1,Qingshun Guo2,Huiyou Chang1,and Yang Yi1,*   

  1. 1.School of Information Science and Technology,Sun Yat-sen University,Guangzhou 510275,P.R.China;
    2.Information and Network Center,Sun Yat-sen University,Guangzhou 510275,P.R.China
  • Online:2010-04-26 Published:2010-01-03

Abstract:

Ant colony optimization(ACO)is a new heuristic algo-
rithm which has been proven a successful technique and applied
to a number of combinatorial optimization problems.The traveling
salesman problem(TSP)is among the most important combinato-
rial problems.An ACO algorithm based on scout characteristic is
proposed for solving the stagnation behavior and premature con-
vergence problem of the basic ACO algorithm on TSP.The main
idea is to partition artificial ants into two groups:scout ants and
common ants.The common ants work according to the search
manner of basic ant colony algorithm,but scout ants have some
differences from common ants,they calculate each route’s muta-
tion probability of the current optimal solution using path evaluation
model and search around the optimal solution according to the
mutation probability.Simulation on TSP shows that the improved
algorithm has high efficiency and robustness.