ABSTRACT
GPU-based metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 9.7 Case study: accelerating large neighborhood LS method on
GPUs for solving the Q3AP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 9.7.1 The quadratic 3-dimensional assignment problem . . . . . . 204 9.7.2 Iterated tabu search algorithm for the Q3AP . . . . . . . . . . . 205 9.7.3 Neighborhood functions for the Q3AP . . . . . . . . . . . . . . . . . . 206 9.7.4 Design and implementation of a GPU-based iterated
tabu search algorithm for the Q3AP . . . . . . . . . . . . . . . . . . . . 207
9.7.5 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 9.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
This chapter presents GPU-based parallel metaheuristics, challenges, and issues related to the particularities of the GPU architecture and a synthesis on the different implementation strategies used in the literature. The implementation of parallel metaheuristics on GPUs is not straightforward. The traditional models used in CPUs must be rethought to meet the new requirements of GPU architectures. This chapter is organized as follows. Combinatorial optimization and resolution methods are introduced in Section 9.2. The main traditional parallel models used for metaheuristics are recalled in Section 9.3. Section 9.4 highlights the main challenges related to the GPU implementation of metaheuristics. A state-of-the-art of GPU-based parallel metaheuristics is summarized in Section 9.5. In Section 9.6, the main developed GPU-based frameworks for metaheuristics are described. Finally, a case study is presented in Section 9.7 and some concluding remarks are given in Section 9.8
Combinatorial optimization (CO) is a branch of applied and discrete mathematics. It consists in finding optimal configuration(s) among a finite set of possible configurations (or solutions) of a given combinatorial optimization problem (COP). The set of all possible solutions noted S is called solution space or search space. Each solution in S is defined by its real cost calculated by an objective function. COPs are generally defined as follows [5]:
A combinatorial problem P = (S, f) can be defined by
• a set of decision variables X,
• an objective function f to optimize (minimize or maximize) over the set S,
• subject to constraints on the decision variables.
