Abstract
In this paper, we propose to parallelize a Hybrid Genetic Algorithm (HGA) on Graphics Processing Units (GPUs) which are available and installed on ubiquitous personal computers. HGA extends the classical genetic algorithm by incorporating the Cauchy mutation operator from evolutionary programming. In our parallel HGA, all steps except the random number generation procedure are performed in GPU and thus our parallel HGA can be executed effectively and efficiently. We suggest and develop the novel pseudo-deterministic selection method which is comparable to the traditional global selection approach with significant execution time performance advantages.We perform experiments to compare our parallel HGA with our previous parallel FEP (Fast Evolutionary programming) and demonstrate that the former is much more effective and efficient than the latter. The parallel and sequential implementations of HGA are compared in a number of experiments, it is observed that the former outperforms the latter significantly. The effectiveness and efficiency of the pseudo-deterministic selection method is also studied.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press (1975)
Oh, I.S., Lee, J.S., Moon, B.R.: Hybrid Genetic Algorithms for Feature Selection. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(11), 1424–1437 (2004)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)
Freitas, A.A.: Data Mining and Knowledge Discovery with Evolutionary Algorithms. Springer, Heidelberg (2002)
Myers, J.W., Laskey, K.B., DeJong, K.A.: Learning Bayesian Networks from Incomplete Data using Evolutionary Algorithms. In: Proceedings of the First Annual Conference on Genetic and Evolutionary Computation Conference, pp. 458–465 (1999)
Larrañaga, P., Poza, M., Yurramendi, Y., Murga, R., Kuijpers, C.: Structural Learning of Bayesian Network by Genetic Algorithms: A Performance Analysis of Control Parameters. IEEE Transactions on Pattern Analysis and Machine Intelligence 18(9), 912–926 (1996)
GPGPU: General-Purpose Computation Using Graphics Hardware, http://www.gpgpu.org/
Moreland, K., Angel, E.: The FFT on a GPU. In: Proceedings of 2003 SIGGRAPH/Eurographics Workshop on Graphics Hardware, pp. 112–119 (2003)
Wang, J.Q., Wong, T.T., Heng, P.A., Leung, C.S.: Discrete Wavelet Transform on GPU. In: Proceedings of ACM Workshop on General Purpose Computing on Graphics Processors C-41 (2004)
Jiang, C., Snir, M.: Automatic Tuning Matrix Multiplication Performance on Graphics Hardware. In: Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, pp. 185–196 (2005)
Galoppo, N., Govindaraju, N.K., Henson, M., Manocha, D.: LU-GPU: Efficient Algorithms for Solving Dense Linear Systems on Graphics Hardware. In: Proceedings of the ACM/IEEE SC 2005 Conference 3 (2005)
Fok, K.L., Wong, T.T., Wong, M.L.: Evolutionary Computing on Consumer-Level Graphics Hardware. IEEE Intelligent Systems 22(2), 69–78 (2007)
Wong, M.L., Wong, T.T., Fok, K.L.: Parallel Evolutionary Algorithms on Graphics Processing Unit. In: Proceedings of IEEE Congress on Evolutionary Computation 2005 (CEC 2005), pp. 2286–2293 (2005)
Yao, X., Liu, Y.: Fast Evolutionary Programming. In: Proceedings of the 5th Annual Conference on Evolutionary Programming, pp. 451–460 (1996)
Yao, X., Liu, Y., Lin, G.: Evolutionary Programming Made Faster. IEEE Transactions on Evolutionary Computation 3(2), 82–102 (1999)
Fogel, D.B.: Evolutionary Computation: Toward a New Philosohpy of Machine Intelligence. IEEE Press, Los Alamitos (2000)
Fogel, L., Owens, A., Walsh, M.: Artificial Intelligence Through Simulated Evolution. John Wiley and Sons, Chichester (1966)
Angeline, P.: Genetic Programming and Emergent Intelligent. In: Kinnear, K.E. (ed.) Advances in Genetic Programming, pp. 75–97. MIT Press, Cambridge (1994)
Cantú-Paz, E.: Efficient and Accurate Parallel Genetic Algorithms. Kluwer Academic Publishers, Dordrecht (2000)
Bäck, T., Fogel, D.B., Michalewicz, Z.: Evolutionary Computation 2: Advanced Algorithms and Operators. Insitute of Physic Publishing (2000)
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)
Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G.: Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic Publishers, Dordrecht (2003)
Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D.: Genetic Programming: An Introduction. Morgan Kaufmann, San Francisco (1998)
Schewefel, H.P.: Numerical Optimization of Computer Models. John Wiley and Sons, Chichester (1981)
Bäck, T.: Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Wong, M.L., Wong, T.T. (2009). Implementation of Parallel Genetic Algorithms on Graphics Processing Units. In: Gen, M., et al. Intelligent and Evolutionary Systems. Studies in Computational Intelligence, vol 187. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-95978-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-95978-6_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-95977-9
Online ISBN: 978-3-540-95978-6
eBook Packages: EngineeringEngineering (R0)