MAX-MIN Ant System on GPU with CUDA

Author

Bai, Hongtao ; Ouyang, Dantong ; Li, Ximing ; He, Lili ; Yu, Haihong

Author_Institution

Coll. of Comput. Sci. & Technol., Jilin Univ., Changchun, China

fYear

2009

fDate

7-9 Dec. 2009

Firstpage

801

Lastpage

804

Abstract

We propose a parallel MAX-MIN Ant System (MMAS) algorithm that is suitable for an implementation on graphics processing units (GPUs). Multi ant colonies with respective parameter settings are whole offloaded to the GPU in parallel. We have implemented this GPU-based MMAS on the GPU with compute unified device architecture (CUDA). Some performance optimization means for kernel program of GPU are introduced. Experimental results that are based on simulations for the traveling salesperson problem are presented to evaluate the proposed techniques.

Keywords

computer graphic equipment; coprocessors; optimisation; parallel algorithms; parallel architectures; GPU; ant colony optimization; compute unified device architecture; graphics processing units; kernel program; parallel max-min ant system; performance optimization; traveling salesperson problem; Ant colony optimization; Clustering algorithms; Computational modeling; Computer architecture; Computer science; Concurrent computing; Control systems; Educational institutions; Graphics; Laboratories;

fLanguage

English

Publisher

ieee

Conference_Titel

Innovative Computing, Information and Control (ICICIC), 2009 Fourth International Conference on

Conference_Location

Kaohsiung

Print_ISBN

978-1-4244-5543-0

Type

conf

DOI

10.1109/ICICIC.2009.255

Filename

5412455