research-article

Running programs backwards: instruction inversion for effective search in semantic spaces

Authors:

Bartosz Wieloch,

Krzysztof KrawiecAuthors Info & Claims

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

Pages 1013 - 1020

https://doi.org/10.1145/2463372.2463493

Published: 06 July 2013 Publication History

Get Access

Abstract

The instructions used for solving typical genetic programming tasks have strong mathematical properties. In this study, we leverage one of such properties: invertibility. A search operator is proposed that performs an approximate reverse execution of program fragments, trying to determine in this way the desired semantics (partial outcome) at intermediate stages of program execution. The desired semantics determined in this way guides the choice of a subprogram that replaces the old program fragment. An extensive computational experiment on 20 symbolic regression and Boolean domain problems leads to statistically significant evidence that the proposed Random Desired Operator outperforms all typical combinations of conventional mutation and crossover operators.

References

[1]

W. Banzhaf et al. Genetic Programming -- An Introduction; On the Automatic Evolution of Computer Programs and its Applications. Morgan Kaufmann, San Francisco, CA, USA, January 1998.

Digital Library

Google Scholar

[2]

J. Derrac et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 2011.

Google Scholar

[3]

N. X. Hoai et al. Solving the symbolic regression problem with tree-adjunct grammar guided genetic programming: The comparative results. In D. B. Fogel et al., editors, Proceedings of the 2002 Congress on Evolutionary Computation CEC2002, pages 1326--1331. IEEE Press, 12--17 May 2002.

Digital Library

Google Scholar

[4]

C. Johnson. Genetic programming crossover: Does it cross over? In Proceedings of the 12th European Conference on Genetic Programming, EuroGP 2009, volume 5481 of LNCS, pages 97--108, Tuebingen, April 15--17 2009. Springer.

Digital Library

Google Scholar

[5]

M. Keijzer. Improving symbolic regression with interval arithmetic and linear scaling. In C. Ryan et al., editors, Genetic Programming, Proceedings of EuroGP'2003, volume 2610 of LNCS, pages 70--82, Essex, 14--16 April 2003. Springer-Verlag.

Digital Library

Google Scholar

[6]

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

Digital Library

Google Scholar

[7]

K. Krawiec and T. Pawlak. Approximating geometric crossover by semantic backpropagation. In C. Blum et al., editor, GECCO'13: Proceedings of the 15th annual conference on Genetic and evolutionary computation, Amsterdam, The Netherlands, 2013. ACM.

Digital Library

Google Scholar

[8]

K. Krawiec and B. Wieloch. Analysis of semantic modularity for genetic programming. Foundations of Computing and Decision Sciences, 34(4):265--285, 2009.

Google Scholar

[9]

S. Luke. The ECJ Owner's Manual -- A User Manual for the ECJ Evolutionary Computation Library, zeroth edition, online version 0.2 edition, October 2010.

Google Scholar

[10]

J. F. Miller. An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, pages 1135--1142, Orlando, Florida, USA, 13--17 July 1999. Morgan Kaufmann.

Google Scholar

[11]

Q. U. Nguyen et al. Semantic aware crossover for genetic programming: The case for real-valued function regression. In Proceedings of the 12th European Conference on Genetic Programming, EuroGP 2009, volume 5481 of LNCS, pages 292--302, Tuebingen, April 15--17 2009. Springer.

Digital Library

Google Scholar

[12]

Q. U. Nguyen et al. Self-adapting semantic sensitivities for semantic similarity based crossover. In 2010 IEEE World Congress on Computational Intelligence, pages 4034--4040, Barcelona, Spain, 18--23 July 2010. IEEE Computational Intelligence Society, IEEE Press.

Google Scholar

[13]

J. A. Walker and J. F. Miller. Investigating the performance of module acquisition in cartesian genetic programming. In H.G. Beyer et al., editors, GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, volume 2, pages 1649--1656, Washington DC, USA, 25--29 June 2005. ACM Press.

Digital Library

Google Scholar

Cited By

View all

Virgolin MKrawiec K(2021)Genetic programming is naturally suited to evolve bagging ensemblesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459278(830-839)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459278
Cheng TZhong J(2020)An efficient memetic genetic programming framework for symbolic regressionMemetic Computing10.1007/s12293-020-00311-812:4(299-315)Online publication date: 13-Oct-2020
https://doi.org/10.1007/s12293-020-00311-8
Virgolin MAlderliesten TBosman PAuger AStützle T(2019)Linear scaling with and within semantic backpropagation-based genetic programming for symbolic regressionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321758(1084-1092)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321758
Show More Cited By

Index Terms

Running programs backwards: instruction inversion for effective search in semantic spaces
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Approximating geometric crossover by semantic backpropagation
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

We propose a novel crossover operator for tree-based genetic programming, that produces approximately geometric offspring. We empirically analyze certain aspects of geometry of crossover operators and verify performance of the new operator on both, ...
New search operators for node-depth based encoding
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Node-Depth Based Encoding is a representation for Evolutionary Algorithms applied to problems modelled by trees, storing nodes and their respective depths in an appropriately ordered list. This representation was highlighted by the results obtained, ...
New operators for non-functional genetic improvement
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Genetic improvement uses automated search to find improved versions of existing software. Typically software is modified using either delete, copy or replace operations at the level of source code, its abstract syntax tree, binary or assembly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
119
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Virgolin MKrawiec K(2021)Genetic programming is naturally suited to evolve bagging ensemblesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459278(830-839)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459278
Cheng TZhong J(2020)An efficient memetic genetic programming framework for symbolic regressionMemetic Computing10.1007/s12293-020-00311-812:4(299-315)Online publication date: 13-Oct-2020
https://doi.org/10.1007/s12293-020-00311-8
Virgolin MAlderliesten TBosman PAuger AStützle T(2019)Linear scaling with and within semantic backpropagation-based genetic programming for symbolic regressionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321758(1084-1092)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321758
Pawlak TKrawiec K(2018)Competent geometric semantic genetic programming for symbolic regression and boolean function synthesisEvolutionary Computation10.1162/evco_a_0020526:2(177-212)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1162/evco_a_00205
Oliveira LMartins JMiranda LPappa GTakadama K(2018)Analysing symbolic regression benchmarks under a meta-learning approachProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208293(1342-1349)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208293
Szubert MKodali AGanguly SDas KBongard J(2016)Semantic Forward Propagation for Symbolic RegressionParallel Problem Solving from Nature – PPSN XIV10.1007/978-3-319-45823-6_34(364-374)Online publication date: 31-Aug-2016
https://doi.org/10.1007/978-3-319-45823-6_34
Ffrancon RSchoenauer MEsparcia-Alcázar A(2015)Greedy Semantic Local Search for Small SolutionsProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768504(1293-1300)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2768504
Ffrancon RSchoenauer MEsparcia-Alcázar A(2015)Memetic Semantic Genetic ProgrammingProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754697(1023-1030)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754697
Pawlak TWieloch BKrawiec K(2015)Semantic Backpropagation for Designing Search Operators in Genetic ProgrammingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2014.232125919:3(326-340)Online publication date: Jun-2015
https://doi.org/10.1109/TEVC.2014.2321259
Pawlak TWieloch BKrawiec K(2015)Review and comparative analysis of geometric semantic crossoversGenetic Programming and Evolvable Machines10.1007/s10710-014-9239-816:3(351-386)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s10710-014-9239-8
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.

Cited By

Index Terms

Recommendations

Approximating geometric crossover by semantic backpropagation

New search operators for node-depth based encoding

New operators for non-functional genetic improvement