A hierarchical parallel algorithm of ant system and local search for TSPs

Author

Dong, Gaifang ; Fu, Xueliang

Author_Institution

College of Computer and Information Engineering, Inner Mongolia Agricultural University, Hohhot, China

fYear

2010

fDate

4-6 Dec. 2010

Firstpage

4834

Lastpage

4837

Abstract

Ant colony optimization algorithm is an important swarm intelligence algorithm. It has been applied to many fields of combinatorial optimization because of its parallel, distributed computing and running speed. But, ant colony optimization algorithm has some shortcomings. For example, searching process may stagnate. Local search is a good method when cooperate with other algorithms. But hybrid algorithm of local search and other methods will increase the running time. This paper devises a hierarchical parallel algorithm of ant colony optimization and local search for TSPs and computes the hierarchical parallel algorithm with 4 processors. Computation results show that the hierarchical parallel algorithm can improve the running time about 2.5 times.

Keywords

Ant colony optimization; Computers; Educational institutions; Optimization; Parallel algorithms; Search problems; Traveling salesman problems; ant system; combinatorial optimization; local search; parallel algorithm; traveling salesman problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Science and Engineering (ICISE), 2010 2nd International Conference on

Conference_Location

Hangzhou, China

Print_ISBN

978-1-4244-7616-9

Type

conf

DOI

10.1109/ICISE.2010.5690468

Filename

5690468