MEDAL Report 2011005
ACO with Tabu Search on a GPU for Solving QAPs using Move-Cost Adjusted Thread Assignment
Shigeyoshi Tsutsui and Noriyuki Fujimoto  (2011)

Abstract. This paper proposes an ant colony optimization (ACO) for solving quadratic assignment problems (QAPs) on a graphics processing unit (GPU) by combining tabu (TS) with ACO in CUDA (compute unified device architecture). In TS for QAP, all neighbor moves are tested. These moves form two groups based on computing of move cost. In one group, the computing of cost is ${\cal O}(1)$ and in the other group, the computing of move cost is ${\cal O}(n)$. We compute these two groups of moves in parallel by assigning the computations to threads of CUDA. In this assignment, we propose an efficient method which we call Move-Cost Adjusted Thread Assignment (MATA). The results with GPU computation with MATA show a promising speedup compared to computation with the CPU. It is also shown that MATA is effective in applying 2-opt local search.

Download PDF

Download PS

Go back

Missouri Estimation of Distribution Algorithms Laboratory
Department of Mathematics and Computer Science
University of Missouri-St. Louis, St. Louis, MO


            Web design by Martin Pelikan