期刊
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
卷 73, 期 1, 页码 52-61出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2012.01.003
关键词
Ant colony optimization; Parallel metaheuristics; GPU; CUDA; MMAS; Parallel ants; Multiple colonies
资金
- Agence Nationale de la Recherche (ANR) [ANR-2010-COSI-003-03]
The purpose of this paper is to propose effective parallelization strategies for the Ant Colony Optimization (ACO) metaheuristic on Graphics Processing Units (GPUs). The Max-Min Ant System (MMAS) algorithm augmented with 3-opt local search is used as a framework for the implementation of the parallel ants and multiple ant colonies general parallelization approaches. The four resulting GPU algorithms are extensively evaluated and compared on both speedup and solution quality on a state-of-the-art Fermi CPU architecture. A rigorous effort is made to keep parallel algorithms true to the original MMAS applied to the Traveling Salesman Problem. We report speedups of up to 23.60 with solution quality similar to the original sequential implementation. With the intent of providing a parallelization framework for ACO on GPUs, a comparative experimental study highlights the performance impact of ACO parameters, CPU technical configuration, memory structures and parallelization granularity. (C) 2012 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据