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

Abstract

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.