research-article

Genetic programming with polymorphic types and higher-order functions

Authors:

Amy FeltyAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1187 - 1194

https://doi.org/10.1145/1389095.1389330

Published: 12 July 2008 Publication History

Abstract

This article introduces our new approach to program representation for genetic programming (GP). We replace the usual s-expression representation scheme by a strongly-typed abstraction-based representation scheme. This allows us to represent many typical computational structures by abstractions rather than by functions defined in the GP system's terminal set. The result is a generic GP system that is able to express programming structures such as recursion and data types without explicit definitions. We demonstrate the expressive power of this approach by evolving simple boolean programs without defining a set of terminals. We also evolve programs that exhibit recursive behavior without explicitly defining recursion specific syntax in the terminal set. In this article, we present our approach and experimental results.

References

[1]

H. Barendregt. Lambda calculi with types. In Handbook of Logic in Computer Science, Volumes 1 (Background: Mathematical Structures) and 2 (Background: Computational Structures), Abramsky & Gabbay & Maibaum (Eds.), Clarendon. Oxford University Press, 1992.

Digital Library

[2]

F. Binard and A. Felty. An abstraction-based genetic programming system. In P. A. N. Bosman, editor, Late breaking paper at Genetic and Evolutionary Computation Conference (GECCO'2007), pages 2415--2422, London, United Kingdom, 7-11 July 2007. ACM Press.

Digital Library

[3]

S. Brave. Using genetic programming to evolve recursive programs for tree search. In Proceedings of the Fourth Golden West Conference on intelligent Systems, pages 60--65, NC, 1995. International Society for Computers and Their Applications, Raleigh.

[4]

C. Clack and T. Yu. Performance enhanced genetic programming. In P. J. Angeline, R. G. Reynolds, J. R. McDonnell, and R. Eberhart, editors, Evolutionary Programming VI, pages 87--100, Berlin, 1997. Springer.

Digital Library

[5]

J. Girard. Une extension de l'interprétation de gödel à l'analyse, et son application à l'élimination des coupures dans l'analyse et la théorie des types. In J. Fenstadt, editor, Proc. 2nd Scandinavian Logic Symp., pages 63--92, Amsterdam, 1971. North-Holland.

[6]

J. Girard et al. Proofs and types. Cambridge University Press New York, 1989.

Digital Library

[7]

T. Haynes, R. Wainwright, S. Sen, and D. Schoenefeld. Strongly typed genetic programming in evolving cooperation strategies. In L. Eshelman, editor, Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95), pages 271--278, Pittsburgh, PA, USA, 15-19 1995. Morgan Kaufmann.

Digital Library

[8]

W. A. Howard. The formulae-as-type notion of construction, 1969. In To H. B. Curry: Essays in Combinatory Logic, Lambda Calculus, and Formalism, pages 479--490. Academic Press, 1980.

[9]

L. J.Y. Girard and Taylor. Proofs and Types. Cambridge University Press., 1997.

Digital Library

[10]

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

Digital Library

[11]

J. R. Koza. The genetic programming paradigm: Genetically breeding populations of computer programs to solve problems. In B. Soucek and the IRIS Group, editors, Dynamic, Genetic, and Chaotic Programming, pages 203--321. John Wiley, New York, 1992.

[12]

J. R. Koza. Genetic programming version 2. Submitted for inclusion in the Encyclopaedia of Computer Science and Technology, 1997.

[13]

D. Montana. Strongly Typed Genetic Programming. Evolutionary Computation, 3:199--230, 1995.

Digital Library

[14]

J. C. Reynolds. Towards a theory of type structure. In Colloque sur la Programmation, volume 19 of LNCS, pages 408--425. Springer-Verlag, 1974.

Digital Library

[15]

A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230--265, 1936.

[16]

T. Yu and C. Clack. Recursion, lambda abstractions and genetic programming. In 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, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 422--431, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.

Cited By

Hong QAiken A(2024)Recursive Program Synthesis using ParamorphismsProceedings of the ACM on Programming Languages10.1145/36563818:PLDI(102-125)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656381
Fonseca APoças DSilva SPaquete L(2023)Comparing the expressive power of Strongly-Typed and Grammar-Guided Genetic ProgrammingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590507(1100-1108)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590507
Garrow FLones MStewart RWagner M(2022)Why functional program synthesis matters (in the realm of genetic programming)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534045(1844-1853)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534045
Show More Cited By

Index Terms

Genetic programming with polymorphic types and higher-order functions
1. Mathematics of computing
  1. Continuous mathematics
    1. Calculus
      1. Lambda calculus
  2. Mathematical analysis
    1. Calculus
      1. Lambda calculus

Recommendations

Polymorphic functions with set-theoretic types: part 1: syntax, semantics, and evaluation
POPL '14: Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

This article is the first part of a two articles series about a calculus with higher-order polymorphic functions, recursive types with arrow and product type constructors and set-theoretic type connectives (union, intersection, and negation).

In this ...
Polymorphic functions with set-theoretic types: part 1: syntax, semantics, and evaluation
POPL '14

This article is the first part of a two articles series about a calculus with higher-order polymorphic functions, recursive types with arrow and product type constructors and set-theoretic type connectives (union, intersection, and negation).

In this ...
Polymorphic Functions with Set-Theoretic Types: Part 2: Local Type Inference and Type Reconstruction
POPL '15: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

This article is the second part of a two articles series about the definition of higher order polymorphic functions in a type system with recursive types and set-theoretic type connectives (unions, intersections, and negations).

In the first part, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
191
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hong QAiken A(2024)Recursive Program Synthesis using ParamorphismsProceedings of the ACM on Programming Languages10.1145/36563818:PLDI(102-125)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656381
Fonseca APoças DSilva SPaquete L(2023)Comparing the expressive power of Strongly-Typed and Grammar-Guided Genetic ProgrammingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590507(1100-1108)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590507
Garrow FLones MStewart RWagner M(2022)Why functional program synthesis matters (in the realm of genetic programming)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534045(1844-1853)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534045
Fonseca ASantos PEspada GSilva S(2022)Grammatical Evolution Mapping for Semantically-Constrained Genetic ProgrammingGenetic Programming Theory and Practice XVIII10.1007/978-981-16-8113-4_3(45-62)Online publication date: 11-Feb-2022
https://doi.org/10.1007/978-981-16-8113-4_3
Kren TPilat MNeruda R(2017)Multi-objective evolution of machine learning workflows2017 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2017.8285357(1-8)Online publication date: Nov-2017
https://doi.org/10.1109/SSCI.2017.8285357
Kren TMoudrik JNeruda R(2017)Combining top-down and bottom-up approaches for automated discovery of typed programs2017 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2017.8285209(1-8)Online publication date: Nov-2017
https://doi.org/10.1109/SSCI.2017.8285209
Gerules GJanikow C(2016)A survey of modularity in genetic programming2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7748328(5034-5043)Online publication date: Jul-2016
https://doi.org/10.1109/CEC.2016.7748328
Ken TPilat MNeruda R(2015)Evolving Workflow Graphs Using Typed Genetic Programming2015 IEEE Symposium Series on Computational Intelligence10.1109/SSCI.2015.200(1407-1414)Online publication date: Dec-2015
https://doi.org/10.1109/SSCI.2015.200
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
Kren TNeruda R(2014)Generating lambda term individuals in typed genetic programming using forgetful A∗2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900547(1847-1854)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900547
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