A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units

Year 2016, Volume: 17 Issue: 1, 167 - 180, 25.04.2016

ERDENER Özçetin , GÜRKAN Öztürk

https://doi.org/10.18038/btda.15399

Cited By: 1

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

A HYBRID GENETIC ALGORITHM FOR THE QUADRATIC ASSIGNMENT PROBLEM ON GRAPHICS PROCESSING UNITS

Abstract

Bu çalışmada karesel atama probleminin çözümü için melez bir genetik algoritma önerilmiştir. Önerilen algoritmanın en zaman alıcı bölümleri amaç fonksiyonun hesaplanması ve yerel arama operatörüdür. Bu nedenle algoritmanın söz konusu bölümlerinin paralelleştirilmesi ve grafik işlem birimleri üzerinde uygulanması üzerinde durulmuştur. Algoritmanın seri ve paralel versiyonu 49 adet literatür problemi üzerinde test edilmiş ve karşılaştırmalar yapılmıştır. Test edilen literatur problemlerinden 34'ü için bilinen en iyi sonuçlara ulaşılmıştır. Deneysel çalışmalar önerilen algoritmanın kısa sürede etkin sonuçlar verebildiğini ortaya koymuştur. Önerilen paralel algoritmanın ortalama 17 kat olmak üzere 51 kata kadar seri algoritmaya göre hızlı çalıştığı raporlanmıştır

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.
• M Wilhelm, T Ward. Solving quadratic assignment problems by simulated annealing. IIE Transactions 1987; 19: 107–119.
• T Abreu, N Querido, N Boaventura. A simulated annealing for the quadratic assignment problem. Rairo-Operations Research 1999; 33: 249–273. [16] T Stützle and M Dorigo. ACO algorithms for the quadratic assignment problem. In: New ideas in optimization, David Corne, Marco Dorigo, Fred Glover, Dipankar Dasgupta, Pablo Moscato, Riccardo Poli, and Kenneth V. Price editors. Maidenhead, UK, England: McGraw-Hill Ltd, 1999. pp. 33-50.
• M Dorigo. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernet ics-Part B: Cybernetics 1996; 26 (1): 1–13.
• S Tsutsui, N Fujimoto. Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study. In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation (GECCO 2009), pp. 2523–2530.
• S Tsutsui, N Fujimoto. Fast QAP solving by ACO with 2-opt local search on a GPU. In 2011
• IEEE Congress of Evolutionary Computation (CEC 2011). pp. 812–819.
• T Luong, N Melab, E. Talbi. Parallel hybrid evolutionary algorithms on GPU. In IEEE World Congress on Computational Intelligence, 2010. [21] W Zhu, J Curry, A Marquez. SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration. International Journal of Production Research 2010; 48(4): 1035-1047.
• M Czapinski. An effective parallel multistart tabu search for quadratic assignment problem on CUDA platform, Journal of Parallel and Distributed Computing 2013; 73: 1461–1468.
• J M Cecilia, J M Garcia, A Nisbet, M Amos, M Ujaldon. Enhancing data parallelism for ant colony optimization on GPUs. Journal of Parallel and Distributed Computing 2013; 73 (1): 42–51.
• A Delevacq, P Delisle, M Gravel, M Krajecki. Parallel ant colony optimization on graphics processing units, Journal of Parallel and Distributed Computing 2013; 73: 52–61.
• C Schulz. Efficient local search on the GPU investigation on the vehicle routing problem. Journal of Parallel and Distributed Computing 2013; 73: 14–31.
• C Groer, B Golden, E Wasil. A parallel algorithm for the vehicle routing problem, Informs Journal on Computing 2011; 23: 315–330.
• C -S. Huang, Y-C. Huang, P.-J. Lai. Modified genetic algorithms for solving fuzzy flow shop scheduling problems and their implementation with CUDA. Expert Systems with Applications 2012; 39: 4999–5005.
• M Czapinski, S Barnes, Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform, Journal of Parallel and Distributed Computing 2011; 71: 802–811.
• W Bozejko. On single-walk parallelization of the job shop problem solving algorithms, Computers & Operations Research 2012; 39: 2258–2264.
• R T Kneusel. Curve-Fitting on Graphics Processors Using Particle Swarm Optimization, International Journal of Computational Intelligence Systems. 2013; 7 (2): 213–224.
• D Kirk, W.-M. W. Whu. Programming massively parallel processors. Burlington, USA: Elsevier Inc., 2010.
• NVIDIA. NVIDIAs next generation CUDA computer architecture Fermi (white paper). NVIDIA, 2011.
• J H Holland. Adaptation in natural and artificial systems. USA: A Bradford Book, 1992.
• R Burkard, S Karisch, F Rendl. QAPLIB-a quadratic assignment problem library. European Journal of Operational Research 1991; 55(1): 115–119.