Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study

ABSTRACT

This paper describes designing a parallel GA with GPU computation to solve the quadratic assignment problem (QAP) which is one of the hardest optimization problems in permutation domains. For the parallel method, a multiple-population, coarse-grained GA model was used. Each subpopulation is evolved by a multiprocessor in a GPU (NVIDIA GeForce GTX285). At predetermined intervals of generations all individuals in subpopulations are shuffled via the VRAM of the GPU. The instances on which this algorithm was tested were taken from the QAPLIB benchmark library. Results were promising, showing a speedup ration from 3 to 12 times, compared to the Intel i7 965 processor.

REFERENCES

• 1: QAPLIB -- a quadratic assignment problem library, 2009. http://www.seas.upenn.edu/qaplib.
• 2: W. Banzhaf, S. Harding, W. Langdon, and G. Wilson. Accelerating Genetic Programming through Graphics Processing Units. Springer, 2008.
• 3: Erick Cantu-Paz, Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 4: Thomas F. Clayton , Leena N. Patel , Gareth Leng , Alan F. Murray , Iain A.B. Lindsay, Rapid evaluation and evolution of neural models using graphics card hardware, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389149]
• 5: Ka-Ling Fok , Tien-Tsin Wong , Man-Leung Wong, Evolutionary Computing on Consumer Graphics Hardware, IEEE Intelligent Systems, v.22 n.2, p.69-78, March 2007 [doi>10.1109/MIS.2007.28]
• 6: N. Fujimoto. Dense matrix-vector multiplication on the CUDA architecture. Parallel Processing Letters, 18(4), 2008.
• 7: N. Fujimoto. Faster matrix-vector multiplication on GeForce 8800GTX. In Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2008.
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: S. Grauer-Gray, C. Kambhamettu, and K. Palaniappan. Gpu implementation of belief propagation using cuda for cloud tracking and reconstruction. In Proceedings of the 5th IAPR Workshop on Pattern Recognition in Remote Sensing (PRRS), 2008.
• 10: K. Gulati and S. Khatri. In Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, 2009.
• 11: Timothy D.R. Hartley , Umit Catalyurek , Antonio Ruiz , Francisco Igual , Rafael Mayo , Manuel Ujaldon, Biomedical image analysis on a cooperative cluster of GPUs and multicores, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece [doi>10.1145/1375527.1375533]
• 12: T. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. Econometrica, 25, 1957.
• 13: S. Lahabar and P. Narayanan. Singular value decomposition on gpu using cuda. In Proceedings of the IEEE International Parallel & Distributed Processing Symposium (IPDPS), (to appear), 2009.
• 14: W. Langdon and W. Banzhaf. A simd interpreter for genetic programming on gpu graphics cards. In Proceedings of the 11th European Conference on Genetic Programming. Springer, 2008.
• 15: W. B. Langdon , A. P. Harrison, GP on SPMD parallel graphics hardware for mega Bioinformatics data mining, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.12 n.12, p.1169-1183, July 2008 [doi>10.1007/s00500-008-0296-x]
• 16: Erik Lindholm , John Nickolls , Stuart Oberman , John Montrym, NVIDIA Tesla: A Unified Graphics and Computing Architecture, IEEE Micro, v.28 n.2, p.39-55, March 2008 [doi>10.1109/MM.2008.31]
• 17: Y. Liu, E. Zhang, and X. Shen. A cross-input adaptive framework for gpu programs optimization. In Proceedings of the IEEE International Parallel & Distributed Processing Symposium (IPDPS) (to appear), 2009.
• 18: P. Maciol and K. Banas. Testing tesla architecture for scientific computing: The performance of matrix-vector product. In Proceedings of the International Multiconference on Computer Science and Information Technology, 2008.
• 19: Samir W. Mahfoud, A Comparison of Parallel and Sequential Niching Methods, Proceedings of the 6th International Conference on Genetic Algorithms, p.136-143, July 15-19, 1995
• 20: S. Manavski. Cuda compatible gpu as an efficient hardware accelerator for cryptography. In Proceedings of the IEEE International Conference on Signal Processing and Communication (ICSPC 2007), 2007.
• 21: Vittorio Maniezzo , Alberto Colorni, The Ant System Applied to the Quadratic Assignment Problem, IEEE Transactions on Knowledge and Data Engineering, v.11 n.5, p.769-778, September 1999 [doi>10.1109/69.806935]
• 22: Satoshi Matsuoka, The Rise of the Commodity Vectors, High Performance Computing for Computational Science - VECPAR 2008: 8th International Conference, Toulouse, France, June 24-27, 2008. Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-92859-1_7]
• 23: NVIDIA, 2009. http://www.nvidia.com/page/home.html.
• 24: I. Oliver, D. Smith, and J. Holland. A study of permutation crossover operators on the travel salesman problem. In Proceedings of the 2nd International Conference on Genetic Algorithms. L. Erlbaum Associates Inc., 1987.
• 25: Martin Pelikan , Shigeyoshi Tsutsui , Rajiv Kalapala, Dependency trees, permutations, and quadratic assignment problem, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277089]
• 26: D. Robilliard, V. Marion-Poty, and C. Fonlupt. Population parallel gp on the g80 gpu. In Proceedings of the 11th European Conference on Genetic Programming. Springer, 2008.
• 27: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 28: Maraike Schellmann , Jürgen Vörding , Sergei Gorlatch , Dominik Meiländer, Cost-effective medical image reconstruction: from clusters to graphics processing units, Proceedings of the 5th conference on Computing frontiers, May 05-07, 2008, Ischia, Italy [doi>10.1145/1366230.1366278]
• 29: Thomas Stützle , Holger H. Hoos, MAX-MIN Ant system, Future Generation Computer Systems, v.16 n.9, p.889-914, June 2000
• 30: É. Taillard. taboo search code. 2004. http://mistic.heig-vd.ch/taillard/codes.dir/tabou_qap.cpp.
• 31: Shigeyoshi Tsutsui, Parallel Ant Colony Optimization for the Quadratic Assignment Problems with Symmetric Multi Processing, Proceedings of the 6th international conference on Ant Colony Optimization and Swarm Intelligence, September 22-24, 2008, Brussels, Belgium [doi>10.1007/978-3-540-87527-7_38]
• 32: L. Darrell Whitley , Timothy Starkweather , D'Ann Fuquay, Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator, Proceedings of the 3rd International Conference on Genetic Algorithms, p.133-140, June 01, 1989
• 33: G. Wilson and W. BanzhafLinear. Linear genetic programming gpgpu on microsoft's xbox 360. In Proceedings of the IEEE Congress on Evolutionary Computation 2008 (CEC'08), 2008.
• 34: M. Wong and T. Wong. Parallel hybrid genetic algorithms on consumer-level graphics hardware. In Proceedings of IEEE Congress on Evolutionary Computation 2006 (CEC'06), 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming; Parallel programming

General Terms:
Algorithms

Keywords:
GPU computation, distributed genetic algorithm, genetic algorithm, parallel computation, quadratic assignment problem