An Ant System based on Moderate Search for TSP

Ping Guo1 and Zhujin Liu1

  1. College of Computer Science, Chongqing University, Chongqing, China
    Chongqing Key Laboratory of Software Theory & Technology, Chongqing 400044, China
    guoping@cqu.edu.cn

Abstract

Ant Colony Optimization (ACO) algorithms often suffer from criticism for the local optimum and premature convergence. In order to overcome these inherent shortcomings shared by most ACO algorithms, we divide the ordinary ants into two types: the utilization-oriented ants and the exploration-oriented ants. The utilization-oriented ants focus on constructing solutions based on the learned experience like ants in many other ACO algorithms. On the other hand, inspired by the adaptive behaviors of some real-world Monomorium ant species who tend to select paths with moderate pheromone concentration, a novel search strategy, that is, a completely new transition rule is designed for the exploration-oriented ants to explore more unknown solutions. In addition, a new corresponding update strategy is also employed. Moreover, applying the new search strategy and update strategy, we propose an improved version of ACO algorithm—Moderate Ant System. This improved algorithm is experimentally turned out to be effective and competitive.

Key words

Ant Colony Optimization; Adaptive behavior; Traveling Salesman Problem; Local optimum; Premature convergence

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS120302057G

Publication information

Volume 9, Issue 4 (December 2012)
Special Issue on Recent Advances in Systems and Informatics
Year of Publication: 2012
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Guo, P., Liu, Z.: An Ant System based on Moderate Search for TSP. Computer Science and Information Systems, Vol. 9, No. 4, 1533-1552. (2012), https://doi.org/10.2298/CSIS120302057G