research-article

Memetic Semantic Genetic Programming

Authors:

Robyn Ffrancon,

Marc SchoenauerAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1023 - 1030

https://doi.org/10.1145/2739480.2754697

Published: 11 July 2015 Publication History

Abstract

Semantic Backpropagation (SB) was introduced in GP so as to take into account the semantics of a GP tree at all intermediate states of the program execution, i.e., at each node of the tree. The idea is to compute the optimal "should-be" values each subtree should return, whilst assuming that the rest of the tree is unchanged, so as to minimize the fitness of the tree. To this end, the Random Desired Output (RDO) mutation operator, proposed in [17], uses SB in choosing, from a given library, a tree whose semantics are preferred to the semantics of a randomly selected subtree from the parent tree. Pushing this idea one step further, this paper introduces the Brando (BRANDO) operator, which selects from the parent tree the overall best subtree for applying RDO, using a small randomly drawn static library. Used within a simple Iterated Local Search framework, BRANDO can find the exact solution of many popular Boolean benchmarks in reasonable time whilst keeping solution trees small, thus paving the road for truly memetic GP algorithms.

References

[1]

A. Bhardwaj and A. Tiwari. A Novel GP Based Classifier Design Using a New Constructive Crossover Operator with a Local Search Technique. In D. Huang et al., editor, Intelligent Computing Theories, volume 7995 of LNCS, pages 86--95. Springer Verlag, 2013.

Digital Library

[2]

R. M. Downing. Evolving Binary Decision Diagrams using Implicit Neutrality. In Proc. IEEE CEC, pages 2107--2113 Vol. 3, 2005.

[3]

B. E. Eskridge and D. F. Hougen. Memetic Crossover for Genetic Programming: Evolution Through Imitation. In K. Deb, editor, Proc. ACM-GECCO, pages 459--470. LNCS 3103, Springer Verlag, 2004.

[4]

D. E. Goldberg. Zen and the Art of Genetic Algorithms. In J. D. Schaffer, editor, Proc. 3rd ICGA, pages 80--85, 1989.

Digital Library

[5]

John R Koza. Genetic Programming: on the Programming of Computers by means of Natural Selection, volume 1. MIT press, 1992.

Digital Library

[6]

K. Krawiec and U.-M. O'Reilly. Behavioral Programming: A Broader and More Detailed Take on Semantic GP. In Dirk Arnold et al., editor, Proc. GECCO, pages 935--942. ACM Press, 2014.

Digital Library

[7]

K. Krawiec and T. Pawlak. Approximating Geometric Crossover by Semantic Backpropagation. In Ch. Blum and E. Alba, editors, Proc. 15th GECCO, pages 941--948. ACM, 2013.

Digital Library

[8]

N. F. McPhee, B. Ohs, and T. Hutchison. Semantic Building Blocks in Genetic Programming. In M. O'Neill et al., editor, Proc. 11th EuroGP, volume 4971 of LNCS, pages 134--145. Springer Verlag, 2008.

Digital Library

[9]

P. Moscato. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Caltech concurrent computation program, C3P Report, 826:1989, 1989.

[10]

Y. Nagata. New EAX Crossover for Large TSP Instances. In Th. P. Runarsson et al., editor, Proc. PPSN IX, pages 372--381. LNCS 4193, Springer Verlag, 2006.

Digital Library

[11]

F. Neri, C. Cotta, and P. Moscato, editors. Handbook of Memetic Algorithms. Number 379 in Studies in Computational Intelligence. Springer Verlag, 2012.

Digital Library

[12]

T. Pawlak, B. Wieloch, and K. Krawiec. Semantic Backpropagation for Designing Search Operators in Genetic Programming. Evolutionary Computation, IEEE Transactions on, PP(99):1--1, 2014.

[13]

K. Rasheed and H. Hirsh. Informed operators: Speeding up genetic-algorithm-based design optimization using reduced models. In D. Whitley et al., editor, Proc. ACM-GECCO, pages 628--635, 2000.

[14]

H. Sakanashi, T. Higuchi, H. Iba, and Y. Kakazu. Evolution of Binary Decision Diagrams for Digital Circuit Design using Genetic Programming. In T. Higuchi, M. Iwata, and W. Liu, editors, Evolvable Systems: From Biology to Hardware, pages 470--481. LNCS 1259, Springer Verlag, 1997.

Digital Library

[15]

L. Vanneschi, M. Castelli, and S. Silva. A Survey of Semantic Methods in GP. Genetic Programming and Evolvable Machines, 15(2):195--214, 2014.

Digital Library

[16]

P. Wang, K. Tang, E.P.K. Tsang, and X. Yao. A Memetic Genetic Programming with Decision Tree-based Local Search for Classification Problems. In Proc. IEEE-CEC, pages 917--924, June 2011.

[17]

B. Wieloch and K. Krawiec. Running Programs Backwards: Instruction Inversion for Effective Search in Semantic Spaces. In Ch. Blum and E. Alba, editors, Proc. 15th GECCO, pages 1013--1020. ACM, 2013.

Digital Library

[18]

M. Yanagiya. Efficient Genetic Programming based on Binary Decision Diagrams. In Proc. IEEE-CEC, volume 1, pages 234--239, 1995.

Cited By

Huang ZMei YZhong J(2024)Semantic Linear Genetic Programming for Symbolic RegressionIEEE Transactions on Cybernetics10.1109/TCYB.2022.318146154:2(1321-1334)Online publication date: Feb-2024
https://doi.org/10.1109/TCYB.2022.3181461
Shi XMinku LYao X(2024)Tree-Based Genetic Programming for Evolutionary Analog Circuit with Approximate Shapley ValueArtificial Intelligence XLI10.1007/978-3-031-77915-2_18(253-267)Online publication date: 29-Nov-2024
https://doi.org/10.1007/978-3-031-77915-2_18
Leite ASchoenauer M(2023)Memetic Semantic Genetic Programming for Symbolic RegressionGenetic Programming10.1007/978-3-031-29573-7_13(198-212)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-3-031-29573-7_13
Show More Cited By

Index Terms

Memetic Semantic Genetic Programming
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Linear scaling with and within semantic backpropagation-based genetic programming for symbolic regression
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

Semantic Backpropagation (SB) is a recent technique that promotes effective variation in tree-based genetic programming. The basic idea of SB is to provide information on what output is desirable for a specified tree node, by propagating the desired ...
Greedy Semantic Local Search for Small Solutions
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Semantic Backpropagation (SB) was introduced in GP so as to take into account the semantics of a GP tree at all intermediate states of the program execution, i.e., at each node of the tree. The idea is to compute the optimal "should-be" values each ...
Impact of Crossover Bias in Genetic Programming
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

In tree-based genetic programming (GP) with sub-tree crossover, the parent contributing the root portion of the tree (the root parent) often contributes more to the semantics of the resulting child than the non-root parent. Previous research ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 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 the author(s) 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: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

INRIA

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
162
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang ZMei YZhong J(2024)Semantic Linear Genetic Programming for Symbolic RegressionIEEE Transactions on Cybernetics10.1109/TCYB.2022.318146154:2(1321-1334)Online publication date: Feb-2024
https://doi.org/10.1109/TCYB.2022.3181461
Shi XMinku LYao X(2024)Tree-Based Genetic Programming for Evolutionary Analog Circuit with Approximate Shapley ValueArtificial Intelligence XLI10.1007/978-3-031-77915-2_18(253-267)Online publication date: 29-Nov-2024
https://doi.org/10.1007/978-3-031-77915-2_18
Leite ASchoenauer M(2023)Memetic Semantic Genetic Programming for Symbolic RegressionGenetic Programming10.1007/978-3-031-29573-7_13(198-212)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-3-031-29573-7_13
Jeong HKim JChoi SLee SHeo IKim K(2022)Semantic Cluster Operator for Symbolic Regression and Its ApplicationsAdvances in Engineering Software10.1016/j.advengsoft.2022.103174172:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.advengsoft.2022.103174
Moscato PSun HHaque M(2021)Analytic Continued Fractions for Regression: A Memetic Algorithm ApproachExpert Systems with Applications10.1016/j.eswa.2021.115018179(115018)Online publication date: Oct-2021
https://doi.org/10.1016/j.eswa.2021.115018
Liu WYang JZhong JWang S(2021)Genetic programming with separability detection for symbolic regressionComplex & Intelligent Systems10.1007/s40747-020-00240-6Online publication date: 4-Jan-2021
https://doi.org/10.1007/s40747-020-00240-6
Hodan DMrazek VVasicek Z(2021)Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit designGenetic Programming and Evolvable Machines10.1007/s10710-021-09416-6Online publication date: 2-Oct-2021
https://doi.org/10.1007/s10710-021-09416-6
Hodan DMrazek VVasicek ZCoello Coello C(2020)Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit designProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390188(940-948)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390188
Zhong JFeng LCai WOng Y(2020)Multifactorial Genetic Programming for Symbolic Regression ProblemsIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2018.285371950:11(4492-4505)Online publication date: Nov-2020
https://doi.org/10.1109/TSMC.2018.2853719
Liang JXue YWang J(2020)Bi-objective memetic GP with dispersion-keeping Pareto evaluation for real-world regressionInformation Sciences10.1016/j.ins.2020.05.136Online publication date: Jun-2020
https://doi.org/10.1016/j.ins.2020.05.136
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.

Media

Figures

Other

Tables

View Table of Contents