article

Hierarchical Processing for Evolving Recursive and Modular Programs Using Higher-Order Functions and Lambda Abstraction

Author:

Tina YuAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 2, Issue 4

Pages 345 - 380

https://doi.org/10.1023/A:1012926821302

Published: 01 December 2001 Publication History

Abstract

We present a novel approach using higher-order functions and λ abstraction to evolve recursive and modular programs. Moreover, a new term “structure abstraction” is introduced to describe the property emerged from the higher-order function program structure. We test this technique on the general even-parity problem. The results indicate that this approach is very effective with the general even-parity problem due to the appropriate selection of the foldr higher-order function. Initially, foldr structure abstraction identify the promising area of the search space at generation zero. Once the population is within the promising area, foldr structure abstraction provides hierarchical processing for search. Consequently, solutions to the general even-parity problem are found very efficiently. We identify the limitations of this new approach and conclude that only when the appropriate higher-order function is selected that the benefits of structure abstraction show.

References

[1]

1. P.J. Angeline and J. Pollack, "The evolutionary induction of subroutines," The Fourteenth Annual Conference of the Cognitive Science Society, Lawrence Erlbaum: Bloomington, Indiana, 1992, pp. 236-241.

[2]

2. P.J. Angeline and J. Pollack, "Evolutionary module acquisition," in Proc. Second Annual Conf. Evolutionary Programming, D.B. Fogel and W. Atmar (eds.), Evolutionary Programming Society: La Jolla, CA, 1993, pp. 154-163.

[3]

3. P.J. Angeline, "Genetic programming and emergent intelligence," in Advances in Genetic Programming, K.E. Kinnear, Jr. (ed.), MIT Press: Cambridge, MA, 1994, pp. 75-98.

Digital Library

[4]

4. P.J. Angeline, "A historical perspective on the evolution of executable structures," Fundamenta Informaticae, vol. 36(1-4), pp. 179-195, 1998.

Digital Library

[5]

5. W. Banzhaf, D. Banscherus, and P. Dittrich, "Hierarchical genetic programming using local modules," Reihe cl 56/98. SFB 531, University of Dortmund, 1998.

[6]

6. A.S. Bickel and R.W. Bickel, "Tree structured rules in genetic algorithms," in Genetic Algorithms and Their Applications, Proc. Second Int. Conf. Genetic Algorithms, J.J. Grefenstette (ed.), Lawrence Erlbaum: Cambridge, MA, pp. 77-81, 1987.

Digital Library

[7]

7. S. Brave, "Evolving recursive programs for tree search," Advances in Genetic Programming II, P.J. Angeline and K.E. Kinnear, Jr. (eds.), MIT Press: Cambridge, MA, 1996, pp. 203-219.

Digital Library

[8]

8. K. Chellapilla, "Evolving computer programs without subtree crossover," IEEE Trans. Evolutionary Comput., vol. 1(3), pp. 209-216, 1997.

Digital Library

[9]

9. N.L. Cramer, "Representation for the adaptive generation of simple sequential programs," in Proc. Int. Conf. Genetic Algorithms and Their Applications, J.J. Grefenstette (ed.), Lawrence Erlbaum: Hillsdale, NJ, 1985, pp. 183-187.

Digital Library

[10]

10. A. Dessi, A. Giani, and A. Starita, "An analysis of automatic subroutine discovery in genetic programming," in Proc. Genetic and Evolutionary Comput. Conf., W. Banzhaf, J. Daida, A. Eiben, M. Garzon, V. Hanavar, M. Jakiela, and R. Smith (eds.), Morgan Kaufmann: Los Altos, CA, 1999, pp. 996-1001.

[11]

11. Discipulus, Register Machine Learning Technologies, Inc. Littleton, CO, 1998.

[12]

12. L.J. Fogel, A.J. Owens, and M.J. Walsh, Artificial Intelligence through Simulated Evolution, Wiley: New York, 1966.

[13]

13. R.M. Friedberg, "A learning machine: Part I," IBM J. Research and Development, vol. 2(1), pp. 2- 13, 1958.

Digital Library

[14]

14. R.M. Friedberg, B. Dunham, and J.H. North, "A learning machine: Part II," IMB J. Research and Development, vol. 3, pp. 282-287, 1959.

Digital Library

[15]

15. C. Fujiki, An evaluation of Holland's genetic operators applied to a program generator, Master's thesis, University of Idaho, Moscow, ID.

[16]

16. C. Fujiki and J. Dickinson, "Using the genetic algorithm to generate LISP source code to solve the prisoner's dilemma," in Genetic Algorithms and Their Applications, Proc. Second Int. Conf. Genetic Algorithms, J.J. Grefenstette (ed.), Lawrence Erlbaum: Hillsdale, NJ, 1987, pp. 236-240.

Digital Library

[17]

17. C. Gathercole and P. Ross, "Tackling the boolean even n parity problem with genetic programming and limited-error fitness," in Genetic Programming 1997, Proc. Second Ann. Conf., Stanford University, J.R. Koza, K. Deb, M. Dorigo, D.B. Fogel, M. Garzon, H. Iba, and R.L. Riolo (eds.), Morgan Kaufmann: Los Altos, CA, 1997, pp. 119-127.

[18]

18. S.G. Handley, "The automatic generations of plans for a mobile robot via genetic programming with automatically defined functions," Advances in Genetic Programming, K.E. Kinnear, Jr. (ed.), MIT Press: Cambridge, MA, 1994, pp. 391-401.

Digital Library

[19]

19. J.F. Hicklin, Application of the genetic algorithm to automatic program generation, Master Thesis, University of Idaho, Moscow, ID, 1986.

[20]

20. C.A.R. Hoare, "Algorithm 63, Partition, Algorithm 64, Quicksort," Commun. ACM, vol. 4, p. 321, 1961.

Digital Library

[21]

21. P. Hudak, "Conception, evolution, and application of functional programming languages," ACM Comput. Surveys, vol. 21(3), pp. 359-411, 1989.

Digital Library

[22]

22. K.E. Kinnear Jr., "Alternatives in automatic function definition: A comparison of performance," Advances in Genetic Programming, K.E. Kinnear, Jr. (ed.), MIT Press: Cambridge, MA, 1994, pp. 119-141.

Digital Library

[23]

23. J.R. Koza, D. Andre, F.H. Bennett III, and M. Keane, "Use of automatically defined functions and architecture-altering operations in automated circuit synthesis using genetic programming," in Genetic Programming 1996, Proc. First Ann. Conf., Stanford University, CA, J.R. Koza, D.E. Goldberg, D.B. Fogel and R.L. Riolo (eds.), MIT Press: Cambridge, 1996, MA, pp. 132-149.

Digital Library

[24]

24. J.R. Koza, "Hierarchical genetic algorithms operating on populations of computer programs," in Proc. 11th Int. Conf. Artificial Intell., Detroit, MI, N.S. Sridharan (ed.), vol. I, Morgan Kaufmann: Los Altos, CA, 1989, pp. 768-774.

[25]

25. J.R. Koza, "Genetically breeding populations of computer programs to solve problems in Artificial Intelligence," in Proc. Second Int. Conf. Tools for AI, IEEE Computer Society Press: Herndon, Virginia, 1990, pp. 819-827.

[26]

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

Digital Library

[27]

27. J.R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press: Cambridge, MA, 1994.

Digital Library

[28]

28. J.R. Koza, "Scalable learning in genetic programming using automatic function definition," Advances in Genetic Programming, K.E. Kinnear, Jr. (ed.), MIT Press: Cambridge, MA, 1994, pp. 99-117.

Digital Library

[29]

29. J.R. Koza, "Evolving the architecture of a multi-part program in genetic programming using architecture-altering operations," in Evolutionary Programming IV, Proc. Fourth Ann. Conf. Evolutionary Programming, San Diego, CA, J.R. McDonnell, R.G. Reynolds, and D.B. Fogel (eds.), MIT Press: Cambridge, MA, 1995, pp. 695-717.

[30]

30. W. B. Langdon and R. Poli, "Why 'building blocks' don't work on parity problems," Technical report CSRP-98-17, The University of Birmingham, 1998.

[31]

31. W.B. Langdon, "Scaling of program fitness space," Evolutionary Comput., vol. 7(4), pp. 339-421, 1999.

Digital Library

[32]

32. N.J. Nillson, Principles of Artificial Intelligence, Morgan Kaufmann: Los Altos, CA, 1980.

Digital Library

[33]

33. R. Poli, J. Page, and W.B. Langdon, "Smooth uniform crossover, sub-machine code GP and demes: A recipe for solving high-order boolean parity problem," in Proc. Genetic and Evolutionary Comput. Conf., Orlando, Florida, W. Banzhaf, J. Daida, A. Eiben, M. Garzon, V. Hanavar, M. Jakiela, and R. Smith (eds.), Morgan Kaufmann: Los Altos, CA, 1999, pp. 1162-1169.

[34]

34. S.C. Robert, D. Howard, and J.R. Koza, "Evolving modules in genetic programming by subtree encapsulation," in Proc. Fourth European Conf. Genetic Programming, Lake Como, Italy, J.F. Miller, M. Tomassini, P.L. Lanzi, C. Ryan, A.G.B. Tettamanzi, and W.B. Langdon (eds.), Springer: Berlin, 2001, pp. 160-175.

Digital Library

[35]

35. J.P. Rosca and D.H. Ballard, "Hierarchical self-organization in genetic programming," in Proc. Eleventh Int. Conf. Machine Learning, Morgan Kaufmann: Los Altos, CA, 1994, pp. 251-258.

Digital Library

[36]

36. J.P. Rosca and D.H. Ballard, "Discovery of subroutines in genetic programming," Advances in Genetic Programming II, P.J. Angeline and K.E. Kinnear, Jr. (eds.), MIT Press: Cambridge, MA, 1996, pp. 177-201.

Digital Library

[37]

37. J.P. Rosca, "Genetic programming exploratory power and the discovery of functions," in Evolutionary Programming IV, Proc. Fourth Ann. Conf. Evolutionary Programming, San Diego, CA, J.R. McDonnell, R G. Reynolds and D.B. Fogel (eds.), MIT Press: Cambridge, MA, 1995, pp. 719-736.

[38]

38. J.P. Rosca, Hierarchical Learning with Procedural Abstraction Mechanisms, Ph.D. Thesis, University of Rochester, Rochester, NY.

Digital Library

[39]

39. L. Spector, "Simultaneous evolution of programs and their control structures," Advances in Genetic Programming II, P.J. Angeline and K.E. Kinnear, Jr. (eds.), MIT Press: Cambridge, MA, 1996, pp. 137-154.

Digital Library

[40]

40. A.M. Turing, "On computable numbers, with an application to the entscheidungs problem," in Proc. London Math. Soc., Series 2, vol. 42, 1936-1937, pp. 230-265.

[41]

41. P.A. Whigham and R.I. McKay, "Genetic approaches to learning recursive relations," in Progress in Evolutionary Computation, Yao, X. (ed.), Springer-Verlag: Heidelberg, Germany, 1995, pp. 17-27.

Digital Library

[42]

42. P.A. Whigham, Grammatical Bias for Evolutionary Learning, Ph.D. Thesis, University of New South Wales, Australian Defence Force Academy, 1996.

Digital Library

[43]

43. D.H. Wolpert and W.G. Macready, "No free lunch theorems for optimization," IEEE Trans. Evolut. Comput., vol. 1(1), pp. 67-82, 1997.

Digital Library

[44]

44. M.L. Wong and K.S. Leung, "Evolving recursive functions for the even-parity problem using genetic programming," in Advances in Genetic Programming II, P.J. Angeline and K.E. Kinnear, Jr. (eds.), MIT Press: Cambridge, MA, 1996, pp. 222-240.

Digital Library

[45]

45. T. Yuand P. Bentley, "Methods to evolve legal phenotypes," in Fifth Int. Conf. Parallel Problem Solving from Nature, A.E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel (eds.), Springer: Amsterdam, 1998, pp. 280-291.

Digital Library

[46]

46. T. Yu and C. Clack, "PolyGP: a polymorphic genetic programming system in Haskell," in Genetic Programming 1998, Proc. Third Ann. Conf., University of Wisconsin, Madison, WI, J.R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D.B. Fogel, M.H. Garzon, D.E. Goldberg, H. Iba, and R. Riolo (eds.), pp. 416-421, Morgan Kaufmann: Los Altos, CA, 1998.

[47]

47. T. Yu and J. Miller, "Neutrality and the evolvability of boolean function landscape," in Proc. Fourth European Conf. Genetic Programming, Lake Como, Italy, J.F. Miller, M. Tomassini, P.L. Lanzi, C. Ryan, A.G.B. Tettamanzi and W.B. Langdon (eds.), Springer: Berlin, 2001, pp. 204-217.

Digital Library

[48]

48. T. Yu, An Analysis of the Impact of Functional Programming Techniques on Genetic Programming, Ph.D. Thesis, University College London, London, United Kingdom, 1999.

Cited By

Langdon W(2023)Jaws 30Genetic Programming and Evolvable Machines10.1007/s10710-023-09467-x24:2Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1007/s10710-023-09467-x
Agapitos AO'neill MKattan ALucas S(2017)Recursion in tree-based genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-016-9277-518:2(149-183)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10710-016-9277-5
Byrne JFenton MHemberg EMcDermott JO'Neill M(2015)Optimising complex pylon structures with grammatical evolutionInformation Sciences: an International Journal10.1016/j.ins.2014.03.010316:C(582-597)Online publication date: 20-Sep-2015
https://dl.acm.org/doi/10.1016/j.ins.2014.03.010
Show More Cited By

Hierarchical Processing for Evolving Recursive and Modular Programs Using Higher-Order Functions and Lambda Abstraction
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Mining the use of higher-order functions:: An exploratory study on Scala programs
Abstract
A higher-order function takes one or more functions as inputs or outputs to support the generality of function definitions. In modern programming languages, higher-order functions are designed as a feature to enhance usability and scalability. ...
Intensional computation with higher-order functions
Abstract
Intensional computations are those that query the internal structure of their arguments. In a higher-order setting, such queries perform program analysis. This is beyond the expressive power of traditional term rewriting systems, such ...
Local higher-order fixpoint iteration
Abstract
Local fixpoint iteration describes a technique that restricts fixpoint iteration in function spaces to needed arguments only. It has been studied well for first-order functions in abstract interpretation and also in model checking. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 2, Issue 4

December 2001

94 pages

ISSN:1389-2576

Issue’s Table of Contents

Copyright © Copyright © 2001 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Langdon W(2023)Jaws 30Genetic Programming and Evolvable Machines10.1007/s10710-023-09467-x24:2Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1007/s10710-023-09467-x
Agapitos AO'neill MKattan ALucas S(2017)Recursion in tree-based genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-016-9277-518:2(149-183)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10710-016-9277-5
Byrne JFenton MHemberg EMcDermott JO'Neill M(2015)Optimising complex pylon structures with grammatical evolutionInformation Sciences: an International Journal10.1016/j.ins.2014.03.010316:C(582-597)Online publication date: 20-Sep-2015
https://dl.acm.org/doi/10.1016/j.ins.2014.03.010
Nogueira ARibeiro JFernández de Vega FZenha-Rela M(2014)Object-Oriented Evolutionary TestingInternational Journal of Natural Computing Research10.4018/ijncr.20141001024:4(15-35)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.4018/ijncr.2014100102
Křen TNeruda RArnold D(2014)Utilization of reductions and abstraction elimination in typed genetic programmingProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598361(943-950)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598361
Agapitos AMcdermott JO'Neill MKattan ABrabazon A(2014)Higher Order Functions for Kernel RegressionRevised Selected Papers of the 17th European Conference on Genetic Programming - Volume 859910.1007/978-3-662-44303-3_1(1-12)Online publication date: 23-Apr-2014
https://dl.acm.org/doi/10.1007/978-3-662-44303-3_1
McDermott JWhite DLuke SManzoni LCastelli MVanneschi LJaskowski WKrawiec KHarper RDe Jong KO'Reilly UMoore J(2012)Genetic programming needs better benchmarksProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330273(791-798)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330273
Liu YTempesti GWalker JTimmis JTyrrell ABremner P(2011)A self-scaling instruction generator using cartesian genetic programmingProceedings of the 14th European conference on Genetic programming10.5555/2008307.2008335(298-309)Online publication date: 27-Apr-2011
https://dl.acm.org/doi/10.5555/2008307.2008335
Harding SMiller JBanzhaf W(2010)Developments in Cartesian Genetic ProgrammingGenetic Programming and Evolvable Machines10.1007/s10710-010-9114-111:3-4(397-439)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1007/s10710-010-9114-1
Ramos-Munoz JYamamoto LTschudin C(2008)Serial experiments onlineACM SIGCOMM Computer Communication Review10.1145/1355734.135573838:2(31-42)Online publication date: 31-Mar-2008
https://dl.acm.org/doi/10.1145/1355734.1355738
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents