article

Genetic parallel programming: design and implementation

Authors:

Sin Man Cheang,

Kwong Sak Leung,

Kin Hong LeeAuthors Info & Claims

Evolutionary Computation, Volume 14, Issue 2

Pages 129 - 156

https://doi.org/10.1162/evco.2006.14.2.129

Published: 01 June 2006 Publication History

Abstract

This paper presents a novel Genetic Parallel Programming (GPP) paradigm for evolving parallel programs running on a Multi-Arithmetic-Logic-Unit (Multi-ALU) Processor (MAP). The MAP is a Multiple Instruction-streams, Multiple Data-streams (MIMD), general-purpose register machine that can be implemented on modern Very Large-Scale Integrated Circuits (VLSIs) in order to evaluate genetic programs at high speed. For human programmers, writing parallel programs is more difficult than writing sequential programs. However, experimental results show that GPP evolves parallel programs with less computational effort than that of their sequential counterparts. It creates a new approach to evolving a feasible problem solution in parallel program form and then serializes it into a sequential program if required. The effectiveness and efficiency of GPP are investigated using a suite of 14 well-studied benchmark problems. Experimental results show that GPP speeds up evolution substantially.

References

[1]

Andre, D. and Koza, J. R. (1996). Parallel genetic programming: a scalable implementation using the transputer network architecture. In Angeline, P. J. et al., editors, Advances in Genetic Programming 2, pages 317-337, MIT Press.]]

Digital Library

[2]

Andre, D. and Koza, J. R. (1997). Exploiting the fruits of parallelism: an implementation of parallel genetic programming that achieves super-linear performance. Information Science Journal, 106(3-4):201-218.]]

[3]

Banzhaf, W., Nordin, P., Keller, R. E., and Francone, F. D. (1998). Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and its Applications, Morgan Kaufmann.]]

Digital Library

[4]

Banzhaf, W., Koza, J. R., Ryan, C., Spector, L., and Jocob, C. (2000). Genetic programming. IEEE Intelligent Systems Journal, 15(3):74-84.]]

Digital Library

[5]

Brameier, M. and Banzhaf, W. (2001). A comparison of linear genetic programming and neural networks in medical data mining. IEEE Transactions on Evolutionary Computation, 5(1):17-26.]]

Digital Library

[6]

Brameier, M., Hoffmann, F., Nordin, P., Banzhaf, W., and Francone, F. (1999). Parallel machine code genetic programming. In Banzhaf, W., Daida, J., Eiben, A. E., Garzon, M. H., Honavar, V., Jakiela, M., and Smith, R. E., editors, Proceedings of 1999 Genetic and Evolutionary Computation Conference, pages 1228-1228, Morgan Kaufmann.]]

[7]

Cheang, S. M. (2003). An empirical study of the gpp accelerating phenomenon. In Vadakkepat, P., Wan, T. W., Chen, T. K., and Poh, L. A., editors, Proceedings of the Second International Conference on Computational Intelligence, Robotics and Autonomous Systems, pages PS04-4-03, National University of Singapore.]]

[8]

Cheang, S. M., Lee, K. H., and Leung, K. S. (2003). Evolving data classification programs using genetic parallel programming. In Proceedings of IEEE 2003 Congress on Evolutionary Computation , pages 248-255, IEEE Press.]]

[9]

Cheang, S. M., Lee, K. H., and Leung, K. S. (2004). Designing optimal combinational digital circuits using a multiple logic unit processor. In Keijzer, M., OReilly, U., Lucas, S. M., Costa, E., and Soule, T., editors, Proceedings of the Seventh European Conference on Genetic Programming, pages 23-34, Springer-Verlag.]]

[10]

Conrads, M., Nordin, P., and Banzhaf, W. (1998). Speech sound discrimination with genetic programming. In Banzhaf, W., Poli, R., Schoenauer, M., and Fogarty, T. C., editors, Proceedings of the First European Workshop on Genetic Programming, pages 113-129, Springer-Verlag.]]

Digital Library

[11]

Folino, G., Pizzuti, C., and Spezzano, G. (2003). A scalable cellular implementation of parallel genetic programming. IEEE Transactions on Evolutionary Computation, 7(1):37-53.]]

Digital Library

[12]

Francone, F. D. (2001). Discipulus<sup>TM</sup> 3.0 Owners Manual, Register Machine Learning Technologies, Inc. {http://www.aimlearning.com}]]

[13]

Heywood, M. I. and Zincir-Heywood, A. N. (2000). Register based genetic programming on fpga computing platforms. In Poli, R., Banzhaf, W., Langdon, W. B., Miller, J., Nordin, P., and Fogarty, T. C., editors, Proceedings of the Third European Conference on Genetic Programming, pages 44-58, Springer-Verlag.]]

Digital Library

[14]

Heywood, M. I. and Zincir-Heywood, A. N. (2000a). Page-based linear genetic programming. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, pages 3823-3828. IEEE Press.]]

[15]

Heywood, M. I. and Zincir-Heywood, A. N. (2002). Dynamic page based crossover in linear genetic programming. IEEE Transactions on Systems, Man, and Cybernetics - Part B, 32(3):380-388.]]

Digital Library

[16]

Huelsbergen, L. (1997). Learning recursive sequences via evolution of machine-language programs. In Koza, J. R., Deb, K., Dorigo, M., Fogel, D. B., Garzon, M., Iba, H., and Riolo, R. L., editors, Proceedings of the Second Annual Conference on Genetic Programming, pages 186-194, Morgan Kaufmann.]]

[17]

Juille, H. and Pollack, J. B. (1995). Parallel genetic programming and fine-grained SIMD architecture. In Siegel, E. V. et al., editors, Working Notes for the AAAI Symposium on Genetic Programming , pages 31-37, MIT Press.]]

[18]

Kalganova, T. and Miller, J. F. (1999). Evolving more efficient digital circuits by allowing circuit layout evolution and multi-objective fitness. In Proceedings of the First NASA/DoD Workshop on Evolvable Hardware, pages 54-63, IEEE Press.]]

Digital Library

[19]

Kantschik, W. and Banzhaf, W. (2001). Linear-tree gp and its comparison with other gp structures. In Miller, J., Tomassini, M., Lanzi, P. L., Ryan, C., Tettamanzi, A. G. B., and Langdon, W. B., editors, Proceedings of the Fourth European Conference on Genetic Programming, pages 303-312, Springer-Verlag.]]

Digital Library

[20]

Kantschik, W. and Banzhaf, W. (2002). Linear-graph gp - a new gp structure. In Foster, J. A., Lutton, E., Miller, J., Ryan, C., and Tettamanzi, A. G. B., editors, Proceedings of the Fifth European Conference on Genetic Programming, pages 83-92, Springer-Verlag.]]

Digital Library

[21]

Kishore, J. K., Patnaik, L. M., Mani, V., and Agrawal, V. K. (2000). Application of genetic programming for multicategory pattern classification. IEEE Transactions on Evolutionary Computation, 4(3):242-258.]]

Digital Library

[22]

Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press.]]

Digital Library

[23]

Koza, J. R., Bennett III, F. H., Andre, D., and Keane, M. A. (1999). Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann.]]

Digital Library

[24]

Koza, J. R., Keane, M. A., Streeter, M. J., Mydlowec, W., Yu, J., and Lanza, G. (2003). Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic.]]

Digital Library

[25]

Krawiec, K. and Bhanu, B. (2003). Coevolution and linear genetic programming for visual learning. In Cantú-Paz, E. et al., editors, Proceedings of 2003 Genetic and Evolutionary Computation Conference, pages 332-343, Springer-Verlag.]]

[26]

Lau, W. S., Li, G., Lee, K. H., Leung, K. S. and Cheang, S. M. (2005). Multi-logic-unit processor : a combinational logic circuit evaluation engine for genetic parallel programming. In Keijzer, M., Tettamanzi, A., Collet, P., van Hemert, J., and Tomazzini, M., editors, Proceedings of the eighth European Conference on Genetic Programming, pages 167-177, Springer-Verlag.]]

Digital Library

[27]

Lee, K. H., Leung, K. S., and Cheang, S. M. (1990). A Microprogrammable List Processor for Personal Computers. IEEE Micro Journal, 10(4):50-61.]]

Digital Library

[28]

Leung, K. S., Lee, K. H., and Cheang, S. M. (2002). Genetic parallel programming-evolving linear machine codes on a multiple-ALU processor. In Yaacob, S., Nagarajan, M., and Chekima, A., editors, Proceedings of the International Conference on Artificial Intelligence in Engineering and Technology, pages 207-213, University of Malaysia Sabah.]]

[29]

Leung, K. S., Lee, K. H., and Cheang, S. M. (2002a). Evolving parallel machine programs for a multi-ALU processor. In Proceedings of 2002 Congress on Evolutionary Computation, pages 1703-1708, IEEE Press.]]

Digital Library

[30]

Leung, K. S., Lee, K. H., and Cheang, S. M. (2003). Parallel programs are more evolvable than sequential programs. In Ryan, C., Soule, T., Keijzer, M., Tsang, E., Poli, R., and Costa E., editors, Proceedings of the Sixth European Conference on Genetic Programming, pages 107-118, Springer-Verlag.]]

[31]

Lim, T. S., Loh, W. Y., and Shih, Y. S. (2000). A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms. Machine Learning , Kluwer Academic, 40:203-229.]]

Digital Library

[32]

Mahfoud, S. W. (1992). Crowding and preselection revisited. In Manner, R. and Manderick, B., editors, Proceedings of Conference on Parallel Problem Solving from Nature, pages 27-36, Elsevier Science Publishers.]]

[33]

Martin, W. N., Lienig, J., and Cohoon, J. P. (1997). Island (migration) models: evolutionary algorithms based in punctuated equilibria. In Bäck, T. et al., editors, Handbook of Evolutionary Computation, pages C6.3:1-16, Oxford University Press.]]

[34]

Merz, C. J. and Murphy, P. M. (1996). UCI Repository of Machine Learning Databases, 1996. University of California.]]

[35]

Miller, J. F. (1999). An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In Banzhaf, W., Daida, J., Eiben, A. E., Garzon, M. H., Honavar, V., Jakiela, M., and Smith, R. E., editors, Proceedings of 1999 Genetic and Evolutionary Computation Conference, pages 1135-1142, Morgan Kaufmann.]]

[36]

Miller, J. F. and Thomson, P. (2000). Cartesian genetic programming. In Poli, R., Banzhaf, W., Langdon, W. B., Miller, J., Nordin, P., and Fogarty, T. C., editors, Proceedings of the Third European Conference on Genetic Programming, pages 121-132, Springer-Verlag.]]

Digital Library

[37]

Miller, J. F., Job, D., and Vassilev, V. K. (2000). Principles in the evolutionary design of digital circuits - part I. Genetic Programming and Evolvable Machines, 1(1):7-35.]]

Digital Library

[38]

Moore, G. E. (1996). Can Moorés Law Continue Indefinitely? Computerworld Leadership Series, 2(6):2-7.]]

[39]

Muni, D. P., Pal, N. R. and Das, J. (2004). A novel approach to design classifiers using genetic programming. IEEE Transactions on Evolutionary Computation, 8(2):183-196.]]

Digital Library

[40]

Nordin, P. (1994). A compiling genetic programming system that directly manipulates the machine code. In Kinnear Jr., K. E., editor, Advances in Genetic Programming, pages 311-331, MIT Press]]

Digital Library

[41]

Nordin, P., Hoffmann, F., Francone, F. D., Brameier, M., and Banzhaf, W. (1999). AIM-GP and parallelism. In Proceedings of IEEE 1999 Congress on Evolutionary Computation, pages 1059-1066, IEEE Press.]]

[42]

Nordin, P., Banzhaf, W., and Francone, F. D. (1999a). Efficient evolution of machine code for CISC architectures using instruction blocks and homologous crossover. In Spector, L. et al., editors, Advances in Genetic Programming Volume 3, pages 275-299, MIT Press.]]

Digital Library

[43]

O'Neill, M. and Ryan, C. (1999). Evolving multi-line compilable c programs. In Poli, R., Nordin, P, Langdon, W. B., and Fogarty, T. C., editors, Proceedings of the 2nd European Workshop on Genetic Programming, pages 83-92, Springer-Verlag.]]

Digital Library

[44]

Perkis, T. (1994). Stack-based genetic programming. In Proceedings of the first IEEE International Conference on Evolutionary Computation, pages 148-153, IEEE Press.]]

[45]

Poli, R. (1999). Parallel distributed genetic programming. In Come, D., Dorigo, M., and Glover, F., editors, New Ideas in Optimization, Section 6, McGraw-Hill.]]

Digital Library

[46]

Potter, M. A. (1997). The Design and Analysis of a Computational Model of Cooperative Coevolution. PhD Thesis, George Mason University.]]

Digital Library

[47]

Potter, M. A. and De Jong, K. A. (2000). Cooperative Coevolution: An architecture for evolving coadapted subcomponenets. Evolutionary Computation Journal, 8(1):1-29.]]

Digital Library

[48]

Ryan, C. (2000). Automatic Re-Engineering of Software Using Genetic Programming, Kluwer Academic.]]

Digital Library

[49]

Ryan, C. and Ivan, L. (2000). Paragen - the first results. In Poli, R., Banzhaf, W., Langdon, W. B., Miller, J., Nordin, P., and Fogarty, T. C., editors, Proceedings of the Third European Conference on Genetic Programming, pages 338-348, Springer-Verlag.]]

Digital Library

[50]

Stoffel, K. and Spector, L. (1996). High-performance, parallel, stack-based genetic programming. In Koza, J. R., Goldberg, D. E., Fogel, D. B., and Riolo, R. L., editors, Proceedings of the First Annual Conference on Genetic Programming, pages 224-229, MIT Press.]]

[51]

Svangård, N., Nordin, P., Lloyd, S., and Wihlborg, C. (2002). Evolving short-term trading strategies using genetic programming. In Proceedings of IEEE 2002 Congress on Evolutionary Computation , pages 2006-2010, IEEE Press.]]

Digital Library

[52]

Teller, A. and Veloso, M. (1996). Pado: a new learning architecture for object recognition. In Symbolic Visual Learning, pages 81-116, Oxford University Press.]]

Digital Library

[53]

Tomassini, M. (1999). Parallel and distributed evolutionary algorithms: a review. In Neittaanmki, P. et al., editors, Evolutionary Algorithms in Engineering and Computer Science, pages 113-133, Wiley.]]

[54]

Trenaman, A. (1999). The Evolution of Autonomous Agents Using Concurrent Genetic Programming. PhD Thesis, National University of Ireland.]]

[55]

Walker, J. A. and Miller, J. F. (2004). Evolution and acquisition of modules in cartesian genetic programming. In Keijzer, M., O'Reilly, U., Lucas, S. M., Costa, E., and Soule, T., editors, Proceedings of the Seventh European Conference on Genetic Programming, pages 187-197, Springer-Verlag.]]

[56]

Wong, M. L. and Leung, K. S. (2000). Data Mining Using Grammar Based Genetic Programming and the Applications, Kluwer Academic.]]

Digital Library

Cited By

Crary CPiard WStitt GHicks BBean CBurlacu BBanzhaf W(2025)Using FPGA devices to accelerate the evaluation phase of tree-based genetic programming: an extended analysisGenetic Programming and Evolvable Machines10.1007/s10710-024-09505-226:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10710-024-09505-2
Kouchakpour PZaknich ABräunl T(2018)A survey and taxonomy of performance improvement of canonical genetic programmingKnowledge and Information Systems10.5555/3225671.322602521:1(1-39)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.5555/3225671.3226025
Pinel FDorronsoro B(2018)SavantInternational Journal of Hybrid Intelligent Systems10.3233/HIS-14020011:4(287-302)Online publication date: 14-Dec-2018
https://dl.acm.org/doi/10.3233/HIS-140200
Show More Cited By

Index Terms

Genetic parallel programming: design and implementation

Recommendations

Caching for parallel linear genetic programming
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Parallel Linear Genetic Programming (PLGP) is an exciting new approach to Linear Genetic Programming (LGP) which decreases building block disruption and significantly improves performance by the introduction of a parallel architecture. We introduce a ...
Parallel linear genetic programming for multi-class classification

Motivated by biological inspiration and the issue of instruction disruption, we develop a new form of Linear Genetic Programming (LGP) called Parallel LGP (PLGP) for classification problems. PLGP programs consist of multiple lists of instructions. These ...
A hybridized genetic parallel programming based logic circuit synthesizer
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Genetic Parallel Programming (GPP) is a novel Genetic Programming paradigm. Based on the GPP paradigm and a local search operator - FlowMap, a logic circuit synthesizing system integrating GPP and FlowMap, a Hybridized GPP based Logic Circuit ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 14, Issue 2

June 2006

126 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 June 2006

Published in EVOL Volume 14, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
223
Total Downloads

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

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Crary CPiard WStitt GHicks BBean CBurlacu BBanzhaf W(2025)Using FPGA devices to accelerate the evaluation phase of tree-based genetic programming: an extended analysisGenetic Programming and Evolvable Machines10.1007/s10710-024-09505-226:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10710-024-09505-2
Kouchakpour PZaknich ABräunl T(2018)A survey and taxonomy of performance improvement of canonical genetic programmingKnowledge and Information Systems10.5555/3225671.322602521:1(1-39)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.5555/3225671.3226025
Pinel FDorronsoro B(2018)SavantInternational Journal of Hybrid Intelligent Systems10.3233/HIS-14020011:4(287-302)Online publication date: 14-Dec-2018
https://dl.acm.org/doi/10.3233/HIS-140200
Krömer PPlatoš JSnášel V(2018)Nature-Inspired Meta-Heuristics on Modern GPUsInternational Journal of Parallel Programming10.1007/s10766-013-0292-342:5(681-709)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s10766-013-0292-3
Robilliard DMarion-Poty VFonlupt C(2018)Genetic programming on graphics processing unitsGenetic Programming and Evolvable Machines10.1007/s10710-009-9092-310:4(447-471)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10710-009-9092-3
Minarik MSekanina L(2014)Exploring the Search Space of Hardware / Software Embedded Systems by Means of GPRevised Selected Papers of the 17th European Conference on Genetic Programming - Volume 859910.1007/978-3-662-44303-3_10(112-123)Online publication date: 23-Apr-2014
https://dl.acm.org/doi/10.1007/978-3-662-44303-3_10
Byers CCheng BMcKinley PMoore J(2012)Exploring the evolution of internal control structure using digital enzymesProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330956(1407-1408)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330956
Robilliard DMarion VFonlupt CFolino GKrasnogor NMastroianni CZambonelli F(2009)High performance genetic programming on GPUProceedings of the 2009 workshop on Bio-inspired algorithms for distributed systems10.1145/1555284.1555299(85-94)Online publication date: 19-Jun-2009
https://dl.acm.org/doi/10.1145/1555284.1555299
Sun KLin YWu CHuang Y(2009)An application of the genetic programming technique to strategy developmentExpert Systems with Applications: An International Journal10.1016/j.eswa.2008.06.06636:3(5157-5161)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1016/j.eswa.2008.06.066
Hadjam FMoraga CBenmohamed MBosman PYu TEkárt A(2007)Cluster-based evolutionary design of digital circuits using all improved multi-expression programmingProceedings of the 9th annual conference companion on Genetic and evolutionary computation10.1145/1274000.1274013(2475-2482)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1274000.1274013

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents