A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units
Abstract
In this paper, a hybrid genetic algorithm is proposed for the quadratic assignment problem. The most time-consuming parts of the proposed algorithm are the calculation of objective function values and the local search operator. Therefore, the parallelization and implementation on graphics processing units of these parts was addressed. This parallel algorithm and its sequential version have been tested and compared for 49 instances in the literature. The best-known solutions were obtained for 34 of these instances. Computational experiments show that the proposed algorithm is capable of providing good quality solutions in a short time. Indeed, it can be observed that the parallel algorithm works up to 51 times faster---17 times faster on average---than the sequential algorithm.
Keywords
Quadratic assignment problem (QAP), parallel programming, graphics processing units (GPU), CUDA
References
- T C Koopmans and M Beckmann. Assignment problems and the location of economic activities. Econometrica: Journal of the Econometric 1957; 25 (1): 53–76.
- A N Elshafei. Hospital layout as a Quadratic Assignment Problem. Operations Research Quarterly 1977; 28: 167–179.
- L Steinberg. The backboard wiring problem: a placement algorithm. SIAM Review 1961; 3: 37–50. [4] A Haghani and M -C. Chen, Optimizing gate assignments at airport terminals, Transportation Research Part A: Policy and Practice 32 (1998) 437–454.
- S Sahni and T Gonzalez. OP-Complete approximation problems. Journal of the ACM 1976; 23: 555-565. [6] Z Drezner, P M Hahn, E D Taillard. Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Annals of Operations 2005; 139: 65–94.
- J S Kochhar, B T Foster, S S Heragu. HOPE: A genetic algorithm for the unequal area facility layout problem. Computers & Operations Research 1998; 25(7-8): 583–594.
- Z Drezner. A new genetic algorithm for the quadratic assignment problem. Informs Journal on Computing 2003; 15: 320–330.
- J Skorin-Kapov. Tabu search applied to the quadratic assignment problem, ORSA Journal on Computing. 1990; 2: 33–45.
- E Taillard. Robust taboo search for the quadratic assignment problem. Parallel Computing 1991; 17: 443–455.
- A Misevicius, A Osterika. Defining tabu tenure for the quadratic assignment problem. Information Technology and Control 2007; 36 (4): 341–347. [12] A Misevicius. An implementation of the iterated tabu search algorithm for the quadratic assignment problem. OR Spectrum 2012; 34(3): 665-690.
- R Burkard, F Rendl. A thermodynamically motivated simulation procedure for combinatorial optimization problems. European Journal of Operational Research 1984; 17(2): 169–174.