A Parallel Genetic Algorithm Based on OpenCL in Resolving 0/1 Knapsack Problems

Abstract:

This paper mainly focused on 0/1 knapsack problems based on the genetic algorithm (GA). According to characteristics of the individual independence in GA, a parallel segmentation method was presented using the OpenCL technology in resolving the 0/1 knapsack problems. Moreover, the local memory was partially optimized in the statistical operation of GA. Experiment results in comparing serial and parallel algorithm implementations showed that the parallel algorithm implementation was operative and the execution time of the parallel algorithm implementation increased linearly according to the increment of problem scale. By comparing the execution time of implementations on CPU and GPU under various individuals and iterations conditions, the effects on CPU and GPU of this method were also analyzed.

• Periodical: Advanced Materials Research (Volumes 1030-1032)
• Pages: 1633-1637
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1030-1032.1633
• Online since: September 2014
• Authors: Long Chang*, Lin Shi
• Keywords: 0/1 Knapsack Problem, Genetic Algorithm (GA), OpenCL, Parallel Computing

References

[1] Merkle R, Hellman M. Hiding Information and Signatures in Trapdoor Knapsack s[J]. IEEE Transactions on Information Theory, 1978, 24(5): 525-530.

DOI: 10.1109/tit.1978.1055927

[2] J.H. Holland, Adaptation in Natural and Artificial Systems, vol. Ann Arbor, no. 53. University of Michigan Press, 1975, p.211.

[3] Sarma, Kamal C., and Hojjat Adeli. Bilevel parallel genetic algorithms for optimization of large steel structures., Computer-Aided Civil and Infrastructure Engineering 16. 5 (2001): 295-304.

DOI: 10.1111/0885-9507.00234

[4] Pospíchal, Petr, Jiri Jaros, and Josef Schwarz. Parallel genetic algorithm on the cuda architecture., Applications of Evolutionary Computation. Springer Berlin Heidelberg, 2010. 442-451.

DOI: 10.1007/978-3-642-12239-2_46

[5] Benedict R. Gaster, Lee Howes and David Kaeli: Heterogeneous Computing with OpenCL (Elsevier, U.S. A 2012).

[6] Blum Lenore, Manuel Blum, and Mike Shub. A simple unpredictable pseudo-random number generator. SIAM Journal on computing 15, no. 2 (1986): 364-383.

DOI: 10.1137/0215025

[7] S.K. Park and K.W. Miller (1988). Random Number Generators: Good Ones Are Hard To Find,. Communications of the ACM 31 (10): 1192–1201.

DOI: 10.1145/63039.63042

[8] Ling, Zhang, and Zhang Bo. Good point set based genetic algorithm., Chinese Journal of Computers 24. 9 (2001): 917-922.

[9] GeForce GTX 765M vs GT 755M, http: /gpuboss. com/gpus/GeForce-GTX-765M-vs-GeForce -GT-755M.

DOI: 10.2172/1173292

[10] Intel® XTU, http: /www. intel. com/content/www/us/en/motherboards/desktop-motherboards /desktop-boards-software-extreme-tuning-utility. html.