research-article

A GPU-based implementation of an enhanced GEP algorithm

Authors:

Hao ChenAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Pages 999 - 1006

https://doi.org/10.1145/2330163.2330302

Published: 07 July 2012 Publication History

Abstract

Gene expression programming (GEP) is a functional genotype/phenotype system. The separation scheme increases the efficiency and reliability of GEP. However, the computational cost increases considerably with the expansion of the scale of problems. In this paper, we introduce a GPU-accelerated hybrid variant of GEP named pGEP (parallel GEP). In order to find the optimal constant coefficients locally on the fixed function structure, the Method of Least Square (MLS) has been embedded into the GEP evolutionary process. We tested pGEP using a broad problem set with a varying number of instances. In the performance experiment, the GPU-based GEP, when compared with the traditional GEP version, increased speeds by approximately 250 times. We compared pGEP with other well-known constant creation methods in terms of accuracy, demonstrating MLS performs at several orders of magnitude higher in terms of both the best residuals and average residuals.

References

[1]

C. Ferreira. Gene expression programming. 2001. A new adaptive algorithm for solving problems. Complex Systems, 13(2):87--129.

[2]

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

Digital Library

[3]

Michael Schmidt, Hod Lipson. 2009. Distilling Free-Form Natural Laws from Experimental Data. Vol 324, SCIENCE 2009.

[4]

Michael Schmidt, Hod Lipson. 2009. Solving Iterated Functions Using Genetic Programming. GECCO'09, ACM 978-1-60558-505-5/09/07.

Digital Library

[5]

Michael Schmidt, Hod Lipson. 2009. Discovering a Domain Alphabet. GECCO'09, ACM 1-58113-000-0/00/0004.

Digital Library

[6]

Michael Schmidt, Hod Lipson. 2009. Incorporating Expert Knowledge in Evolutionary Search: A Study of Seeding Methods. GECCO'09, ACM 1-58113-000-0/00/0004.

Digital Library

[7]

Michael Schmidt, Hod Lipson. 2010. Symbolic Regression of Implicit Equations. Genetic Programming Theory and Practive VII, Genentic and Evolutionary Computation. Springer Science + Business Media, LLC.

[8]

M. Mitchell. 1996. An Introduction to Genetic Algorithms. MIT Press.

[9]

Owens, J. D., Houston, M., Luebke, D., Green, S., Stone, J. E., and Phillips, J. C. 2008. GPU computing. IEEE Proceedings, May 2008, 879--899.

[10]

NVIDIA CUDA. http://developer.nvidia.com/category/zone/cuda-zone.

[11]

CUDA C Programming Guide 3.2, 2010.

[12]

Steven J. Miller. 2006. The Method of Least Squares. Mathematics Department Brown University, pp. 1--7. Providence: Brown University.

[13]

Matthew Evett, Thomas Fernandez. 1998. Numeric Mutation Improves the Discovery of Numeric Constants in Genetic Programming. Proceedings of the Third Annual Genetic Programming Conference. Madison, Wisconsin 66--71.

[14]

Alexander Topchy, William F. Punch. 2001. Faster Genetic Programming based on Local Gradient Search of Numeric Leaf Values. Proceedings of the Genetic and Evolutionary Computation Conference. San Francisco, California 155--162.

[15]

D. B. Kirk and W. mei W. Hwu. 2010. Programming Massively Parallel Processors. Morgan Kaufmann, first edition.

Digital Library

[16]

Koza, J. 1997. Tutorial on advanced genetic programming, at genetic programming.

[17]

C. Ferreira. 2002. Function finding and the creation of numerical constants in gene expression programming. In: 7th Online World Conference on Soft Computing in Industrial Applications, September - October.

[18]

X. Li, C. Zhou, P. C. Nelson, T. M. Tirpak. 2004. Investigation of constant creation techniques in the context of gene expression programming. In: Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference, Seattle, Washington, USA, July.

[19]

Q. Zhang, C. Zhou, W. Xiao, Peter C. Nelson, X. Li. 2006. Using Differential Evolution for GEP Constant Creation. In: Late breaking paper at Genetic and Evolutionary Computation Conference (GECCO 2006), Seattle, WA, USA.

[20]

X. Li, C. Zhou, P. C. Nelson, T. M. Tirpak. 2004. Investigation of constant creation techniques in the context of gene expression programming. In: Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference, Seattle, Washington, USA, July.

[21]

NVIDIA. Data-Parallel algorithms. http://developer.download.nvidia.com/compute/cuda/1_1/Website/Data-Parallel_Algorithms.html#reduction, December 2011.

Cited By

Na SXuan M(2024)An Improved Particle Swarm Optimization Algorithm Based Computer Unified Device Architecture to Symbolic Regression2024 20th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)10.1109/ICNC-FSKD64080.2024.10702232(1-6)Online publication date: 27-Jul-2024
https://doi.org/10.1109/ICNC-FSKD64080.2024.10702232
Fan LSu ZLiu XWang Y(2024)Decomposition based cross-parallel multiobjective genetic programming for symbolic regressionApplied Soft Computing10.1016/j.asoc.2024.112239167:PAOnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.112239
Zhong JFeng LOng Y(2017)Gene Expression Programming: A Survey [Review Article]IEEE Computational Intelligence Magazine10.1109/MCI.2017.270861812:3(54-72)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1109/MCI.2017.2708618
Show More Cited By

Index Terms

A GPU-based implementation of an enhanced GEP algorithm
1. Computing methodologies
  1. Machine learning
    1. Learning settings
  2. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Out-of-core implementation for accelerator kernels on heterogeneous clouds

Cloud environments today are increasingly featuring hybrid nodes containing multicore CPU processors and a diverse mix of accelerators such as Graphics Processing Units (GPUs), Intel Xeon Phi co-processors, and Field-Programmable Gate Arrays (FPGAs) to ...
Acceleration of grammatical evolution using graphics processing units: computational intelligence on consumer games and graphics hardware
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

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 ...
Architecture-Aware Mapping and Optimization on a 1600-Core GPU
ICPADS '11: Proceedings of the 2011 IEEE 17th International Conference on Parallel and Distributed Systems

The graphics processing unit (GPU) continues to make in-roads as a computational accelerator for high-performance computing (HPC). However, despite its increasing popularity, mapping and optimizing GPU code remains a difficult task, it is a multi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

July 2012

1396 pages

ISBN:9781450311779

DOI:10.1145/2330163

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 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: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
154
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Na SXuan M(2024)An Improved Particle Swarm Optimization Algorithm Based Computer Unified Device Architecture to Symbolic Regression2024 20th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)10.1109/ICNC-FSKD64080.2024.10702232(1-6)Online publication date: 27-Jul-2024
https://doi.org/10.1109/ICNC-FSKD64080.2024.10702232
Fan LSu ZLiu XWang Y(2024)Decomposition based cross-parallel multiobjective genetic programming for symbolic regressionApplied Soft Computing10.1016/j.asoc.2024.112239167:PAOnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.112239
Zhong JFeng LOng Y(2017)Gene Expression Programming: A Survey [Review Article]IEEE Computational Intelligence Magazine10.1109/MCI.2017.270861812:3(54-72)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1109/MCI.2017.2708618
Du XNi YYe PXiao R(2015)A new automatic GEP-Cluster algorithmInternational Journal of Wireless and Mobile Computing10.1504/IJWMC.2015.0731009:3(224-230)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1504/IJWMC.2015.073100
Wang BSingh HRay T(2015)A multi-objective genetic programming approach to uncover explicit and implicit equations from data2015 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2015.7257016(1129-1136)Online publication date: May-2015
https://doi.org/10.1109/CEC.2015.7257016

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