An Ant Colony System Hybridized with Randomized Algorithm for TSP

Author

Qi, Chengming

Author_Institution

Beijing Union Univ., Beijing

Volume

3

fYear

2007

fDate

July 30 2007-Aug. 1 2007

Firstpage

461

Lastpage

465

Abstract

Ant algorithms are a recently developed, population- based approach which has been successfully applied to several NP-hard combinatorial optimization problems. In this paper, through an analysis of the constructive procedure of the solution in the ant colony system (ACS),we present an ant colony system hybridized with randomized algorithm(RAACS). In RAACS, only partial cities are randomly chosen to compute the state transition probability. Experimental results for solving the traveling salesman problems(TSP) with both ACS and RAACS demonstrate that averagely speaking, the proposed method is better in both the quality of solutions and the speed of convergence compared with the ACS.

Keywords

probability; randomised algorithms; travelling salesman problems; NP-hard combinatorial optimization problem; ant colony system; randomized algorithm; state transition probability; traveling salesman problems; Ant colony optimization; Artificial intelligence; Automation; Cities and towns; Distributed computing; Educational institutions; Runtime; Software algorithms; Software engineering; Traveling salesman problems; Ant Colony System; Combinatorial Optimization; Randomized Algorithm; TSP;

fLanguage

English

Publisher

ieee

Conference_Titel

Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2007. SNPD 2007. Eighth ACIS International Conference on

Conference_Location

Qingdao

Print_ISBN

978-0-7695-2909-7

Type

conf

DOI

10.1109/SNPD.2007.545

Filename

4287897