BibTex RIS Kaynak Göster

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

Yıl 2016, Cilt: 17 Sayı: 1, 167 - 180, 25.04.2016
https://doi.org/10.18038/btda.15399

Öz

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. 

Kaynakça

  • 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.

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

Yıl 2016, Cilt: 17 Sayı: 1, 167 - 180, 25.04.2016
https://doi.org/10.18038/btda.15399

Öz

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

Kaynakça

  • 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.
Toplam 30 adet kaynakça vardır.

Ayrıntılar

Bölüm Araştırma Makalesi
Yazarlar

ERDENER Özçetin

GÜRKAN Öztürk

Yayımlanma Tarihi 25 Nisan 2016
Yayımlandığı Sayı Yıl 2016 Cilt: 17 Sayı: 1

Kaynak Göster

APA Özçetin, E., & Öztürk, G. (2016). A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering, 17(1), 167-180. https://doi.org/10.18038/btda.15399
AMA Özçetin E, Öztürk G. A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units. AUBTD-A. Haziran 2016;17(1):167-180. doi:10.18038/btda.15399
Chicago Özçetin, ERDENER, ve GÜRKAN Öztürk. “A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units”. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 17, sy. 1 (Haziran 2016): 167-80. https://doi.org/10.18038/btda.15399.
EndNote Özçetin E, Öztürk G (01 Haziran 2016) A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 17 1 167–180.
IEEE E. Özçetin ve G. Öztürk, “A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units”, AUBTD-A, c. 17, sy. 1, ss. 167–180, 2016, doi: 10.18038/btda.15399.
ISNAD Özçetin, ERDENER - Öztürk, GÜRKAN. “A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units”. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 17/1 (Haziran 2016), 167-180. https://doi.org/10.18038/btda.15399.
JAMA Özçetin E, Öztürk G. A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units. AUBTD-A. 2016;17:167–180.
MLA Özçetin, ERDENER ve GÜRKAN Öztürk. “A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units”. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering, c. 17, sy. 1, 2016, ss. 167-80, doi:10.18038/btda.15399.
Vancouver Özçetin E, Öztürk G. A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units. AUBTD-A. 2016;17(1):167-80.