tutorial

Acceleration of grammatical evolution using graphics processing units: computational intelligence on consumer games and graphics hardware

Authors:

Petr Pospichal,

Michael O'Neill,

Jiri JarosAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Pages 431 - 438

https://doi.org/10.1145/2001858.2002030

Published: 12 July 2011 Publication History

Abstract

Several papers show that symbolic regression is suitable for data analysis and prediction in financial markets. Grammatical Evolution (GE), a grammar-based form of Genetic Programming (GP), has been successfully applied in solving various tasks including symbolic regression. However, often the computational effort to calculate the fitness of a solution in GP can limit the area of possible application and/or the extent of experimentation undertaken. This paper deals with utilizing mainstream graphics processing units (GPU) for acceleration of GE solving symbolic regression. GPU optimization details are discussed and the NVCC compiler is analyzed. We design an effective mapping of the algorithm to the CUDA framework, and in so doing must tackle constraints of the GPU approach, such as the PCI-express bottleneck and main memory transactions.

This is the first occasion GE has been adapted for running on a GPU. We measure our implementation running on one core of CPU Core i7 and GPU GTX 480 together with a GE library written in JAVA, GEVA.

Results indicate that our algorithm offers the same convergence, and it is suitable for a larger number of regression points where GPU is able to reach speedups of up to 39 times faster when compared to GEVA on a serial CPU code written in C. In conclusion, properly utilized, GPU can offer an interesting performance boost for GE tackling symbolic regression.

References

[1]

A. Brabazon and M. O'Neill. Biologically Inspired Algorithms for Financial Modelling. Springer, 2006.

Digital Library

[2]

J. Byrne, J. McDermott, E. Galvan-Lopez, and M. O'Neill. Implementing an intuitive mutation operator for interactive evolutionary 3d design. In IEEE Congress on Evolutionary Computation, 2010.

[3]

J. Byrne, M. O'Neill, and A. Brabazon. Structural and nodal mutation in grammatical evolution. In GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1881--1882, Montreal, Québec, Canada, 8-12 July 2009. ACM.

Digital Library

[4]

I. Dempsey, M. O'Neill, and A. Brabazon. Foundations in Grammatical Evolution for Dynamic Environments. Studies in Computational Intelligence. Springer, 2009.

Digital Library

[5]

E. Galvan-Lopez, J. Swafford, and M. O'Neill. Evolving a ms.pac-man controller using grammatical evolution. In EvoGAMES 2010 the 2nd European event on Bio-inspired Algorithms in Games. Springer, 2010.

Digital Library

[6]

S. Harding and W. Banzhaf. Fast genetic programming on gpus. In Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 90--101. Springer Berlin / Heidelberg, 2007.

[7]

R. Harper and A. Blair. A structure preserving crossover in grammatical evolution. In IEEE Congress on Evolutionary Computation, pages 349--358, 2001.

[8]

J. Jaros. Evolutionary optimization of multistage interconnection networks performance. In GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1537--1544, Montreal, Québec, Canada, 8-12 July 2009. ACM.

Digital Library

[9]

D. Kirk and W. Whu. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2010.

Digital Library

[10]

A. Klockner, N. Pinto, Y. Lee, B. Catazaro, P. Ivanov, and A. Fasih. Pycuda: Gpu run-time code generation for high-performance computing.

[11]

J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

[12]

W. B. Langdon and W. Banzhaf. A simd interpreter for genetic programming on gpu graphics cards. In Proceedings of the 11th European conference on Genetic programming, EuroGP'08, pages 73--85, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

[13]

R. McKay, X. Nguyen, P. Whigham, Y. Shan, and M. O'Neill. Grammar-based genetic programming: a survey. Genetic Programming and Evolvable Machines, 11(3-4):365--296, 2010.

Digital Library

[14]

Nguyen and Hubert. Gpu gems 3. Addison-Wesley Professional, 2007.

Digital Library

[15]

nVidia. Cuda c best practices guide.

[16]

nVidia. Cuda programming guide 3.0.

[17]

M. O'Neill, T. Brabazon, C. Ryan, and J. Collins. Evolving market index trading rules using grammatical evolution. In EvoIASP 2001, 2001.

Digital Library

[18]

M. O'Neill, E. Hemberg, C. Gilligan, E. Bartley, J. McDermott, and A. Brabazon. GEVA: Grammatical evolution in java. SIGEVOlution, 3(2), 2008.

Digital Library

[19]

M. O'Neill and C. Ryan. Grammatical evolution. In IEEE Transactions on Evolutionary Computation, pages 349--358, 2001.

Digital Library

[20]

M. O'Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in a Arbitrary Language. Genetic programming. Kluwer Academic Publishers, 2003.

Digital Library

[21]

M. O'Neill, J. Swafford, J. McDermott, J. Byrne, A. Brabazon, E. Shotton, C. McNally, and M. Hemberg. Shape grammars and grammatical evolution for evolutionary design. In GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1035--1042, Montreal, Québec, Canada, 8-12 July 2009. ACM.

Digital Library

[22]

M. Pharr and R. Fernando. GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation. Addison-Wesley Professional, 2005.

Digital Library

[23]

P. Pospichal, J. Schwarz, and J. Jaros. Parallel genetic algorithm on the cuda architecture. In Applications of Evolutionary Computation, LNCS 6024, pages 442--451. Springer Verlag, 2010.

[24]

P. Pospichal, J. Schwarz, and J. Jaros. Parallel genetic algorithm solving 0/1 knapsack problem running on the gpu. In 16th International Conference on Soft Computing MENDEL 2010, pages 64--70. Brno University of Technology, 2010.

[25]

D. Tarjan, K. Skadron, and P. Micikevicius. The art of performance tuning for cuda and manycore architectures.

Cited By

Wang GWang ELi ZZhou JSun Z(2024)Exploring the mathematic equations behind the materials science data using interpretable symbolic regressionInterdisciplinary Materials10.1002/idm2.12180Online publication date: 29-May-2024
https://doi.org/10.1002/idm2.12180
Dufek AAugusto DBarbosa Hda Silva Dias P(2018)Multi- and Many-Threaded Heterogeneous Parallel Grammatical EvolutionHandbook of Grammatical Evolution10.1007/978-3-319-78717-6_9(219-244)Online publication date: 12-Sep-2018
https://doi.org/10.1007/978-3-319-78717-6_9
Russo IBernardino HBarbosa H(2017)A massively parallel Grammatical Evolution technique with OpenCLJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.06.017109:C(333-349)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2017.06.017
Show More Cited By

Recommendations

A performance study of general-purpose applications on graphics processors using CUDA

Graphics processors (GPUs) provide a vast number of simple, data-parallel, deeply multithreaded cores and high memory bandwidths. GPU architectures are becoming increasingly programmable, offering the potential for dramatic speedups for a variety of ...
Massively parallel differential evolution--pattern search optimization with graphics hardware acceleration: an investigation on bound constrained optimization problems

This paper presents a novel parallel Differential Evolution (DE) algorithm with local search for solving function optimization problems, utilizing graphics hardware acceleration. As a population-based meta-heuristic, DE was originally designed for ...
Parallel ant colony for nonlinear function optimization with graphics hardware acceleration
SMC'09: Proceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics

This paper presents a massively parallel Ant Colony Optimization - Pattern Search (ACO-PS) algorithm with graphics hardware acceleration on nonlinear function optimization problems. The objective of this study is to determine the effectiveness of using ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

July 2011

1548 pages

ISBN:9781450306904

DOI:10.1145/2001858

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
188
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang GWang ELi ZZhou JSun Z(2024)Exploring the mathematic equations behind the materials science data using interpretable symbolic regressionInterdisciplinary Materials10.1002/idm2.12180Online publication date: 29-May-2024
https://doi.org/10.1002/idm2.12180
Dufek AAugusto DBarbosa Hda Silva Dias P(2018)Multi- and Many-Threaded Heterogeneous Parallel Grammatical EvolutionHandbook of Grammatical Evolution10.1007/978-3-319-78717-6_9(219-244)Online publication date: 12-Sep-2018
https://doi.org/10.1007/978-3-319-78717-6_9
Russo IBernardino HBarbosa H(2017)A massively parallel Grammatical Evolution technique with OpenCLJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.06.017109:C(333-349)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2017.06.017
Hidalgo JCervigón CVelasco JColmenar JGarcía-Sánchez CBotella G(2017)Embedded Grammars for Grammatical Evolution on GPGPUApplications of Evolutionary Computation10.1007/978-3-319-55849-3_51(789-805)Online publication date: 25-Mar-2017
https://doi.org/10.1007/978-3-319-55849-3_51
Zamuda AMlakar U(2016)Tiled EvoLisa image evolution with blending triangle brushstrokes and gene compression DE2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7744116(2618-2625)Online publication date: Jul-2016
https://doi.org/10.1109/CEC.2016.7744116
Da Silva CDias DBentes CPacheco MCupertino L(2015)Evolving GPU machine codeThe Journal of Machine Learning Research10.5555/2789272.283113616:1(673-712)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2831136
Kojecky LZelinka I(2015)CUDA-based Analytic Programming by Means of SOMA AlgorithmMendel 201510.1007/978-3-319-19824-8_14(171-180)Online publication date: 7-Jun-2015
https://doi.org/10.1007/978-3-319-19824-8_14
Chennupati GAzad RRyan CArnold D(2014)Multi-core GEProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2605670(1041-1044)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2605670
Chennupati GFitzgerald JRyan C(2014)On the efficiency of Multi-core Grammatical Evolution (MCGE) evolving multi-core parallel programs2014 Sixth World Congress on Nature and Biologically Inspired Computing (NaBIC 2014)10.1109/NaBIC.2014.6921885(238-243)Online publication date: Jul-2014
https://doi.org/10.1109/NaBIC.2014.6921885
Turner-Baggs JHeywood M(2013)On GPU based fitness evaluation with decoupled training partition cardinalityProceedings of the 16th European conference on Applications of Evolutionary Computation10.1007/978-3-642-37192-9_49(489-498)Online publication date: 3-Apr-2013
https://dl.acm.org/doi/10.1007/978-3-642-37192-9_49
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten