ACO with tabu search on a GPU for solving QAPs using move-cost adjusted thread assignment

Shigeyoshi Tsutsui, Noriyuki Fujimoto
Hannan University, Osaka, Japan
Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO ’11, 2011


   title={ACO with Tabu Search on a GPU for Solving QAPs using Move-Cost Adjusted Thread Assignment},

   author={Tsutsui, S. and Fujimoto, N.},



Download Download (PDF)   View View   Source Source   



This paper proposes a parallel ant colony optimization (ACO) for solving quadratic assignment problems (QAPs) on a graphics processing unit (GPU) by combining tabu (TS) with ACO in CUDA (ompute 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 O(1) and in the other group, the computing of move cost is 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: