research-article

Runtime analysis of mutation-based geometric semantic genetic programming on boolean functions

Authors:

Alberto Moraglio,

Andrea Mambrini,

Luca ManzoniAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 119 - 132

https://doi.org/10.1145/2460239.2460251

Published: 16 January 2013 Publication History

Abstract

Geometric Semantic Genetic Programming (GSGP) is a recently introduced form of Genetic Programming (GP), rooted in a geometric theory of representations, that searches directly the semantic space of functions/programs, rather than the space of their syntactic representations (e.g., trees) as in traditional GP. Remarkably, the fitness landscape seen by GSGP is always -- for any domain and for any problem -- unimodal with a linear slope by construction. This has two important consequences: (i) it makes the search for the optimum much easier than for traditional GP; (ii) it opens the way to analyse theoretically in a easy manner the optimisation time of GSGP in a general setting. The runtime analysis of GP has been very hard to tackle, and only simplified forms of GP on specific, unrealistic problems have been studied so far. We present a runtime analysis of GSGP with various types of mutations on the class of all Boolean functions.

References

[1]

A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics -- Foundations and Recent Developments. World Scientific, 2011.

Digital Library

[2]

L. Beadle and C. G. Johnson. Sematically driven crossover in genetic programming. In Proc. of IEEE WCCI '08, pages 111--116, 2008.

[3]

L. Beadle and C. G. Johnson. Semantic analysis of program initialisation in genetic programming. Genetic Programming and Evolvable Machines, 10(3):307--337, 2009.

Digital Library

[4]

M. Castelli, L. Manzoni, and L. Vanneschi. An efficient genetic programming system with geometric semantic operators and its application to human oral bioavailability prediction. Preprint arXiv:cs.NE/1208.2437v1, 2012.

[5]

G. Durrett, F. Neumann, and U.-M. O'Reilly. Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics. In Workshop on Foundations of Genetic Algorithms, 2011.

Digital Library

[6]

D. Jackson. Phenotypic diversity in initial genetic programming populations. In Proc. of EuroGP 2010, pages 98--109, 2010.

Digital Library

[7]

K. Krawiec and P. Lichocki. Approximating geometric crossover in semantic space. In Proc. of GECCO '09, pages 987--994, 2009.

Digital Library

[8]

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

[9]

W. Langdon and R. Poli. Foundations of Genetic Programming. Springer-Verlag, 2002.

Digital Library

[10]

P. K. Lehre and C. Witt. Black-box search by unbiased variation. In Proceedings of Genetic and Evolutionary Computation Conference, 2010.

Digital Library

[11]

N. F. McPhee, B. Ohs, and T. Hutchison. Semantic building blocks in genetic programming. In European Conference on Genetic Programming, 2008.

Digital Library

[12]

B. Mitavskiy and J. Rowe. Some results about the markov chains associated to GPs and to general EAs. Theoretical Computer Science, 361(1):72--110, 2006.

Digital Library

[13]

A. Moraglio. Towards a Geometric Unification of Evolutionary Algorithms. PhD thesis, University of Essex, 2007.

[14]

A. Moraglio. Abstract convex evolutionary search. In Workshop on the Foundations of Genetic Algorithms, pages 151--162, 2011.

Digital Library

[15]

A. Moraglio, K. Krawiec, and C. Johnson. Geometric semantic genetic programming. In Workshop on Theory of Randomized Search Heuristics, 2011.

[16]

A. Moraglio, K. Krawiec, and C. Johnson. Geometric semantic genetic programming. In Proceedings of Parallel Problem Solving from Nature, 2012.

Digital Library

[17]

A. Moraglio and R. Poli. Topological interpretation of crossover. In Proc. of GECCO '04, pages 1377--1388, 2004.

[18]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[19]

R. Poli, M. Graff, and N. McPhee. Free lunches for function and program induction. In Workshop on Foundations of Genetic Algorithms, 2009.

Digital Library

[20]

R. Poli and N. F. McPhee. Parsimony pressure made easy: Solving the problem of bloat in gp. In Y. Borenstein and A. Moraglio, editors, Theory and Principled Methods for Designing Metaheuristics, chapter 9. Springer, 2012.

[21]

N. Q. Uy, N. X. Hoai, M. O'Neill, R. McKay, and E. Galván-López. Semantically-based crossover in genetic programming: Application to real-valued symbolic regression. Genetic Programming and Evolvable Machines, 12(2):91--119, 2011.

Digital Library

Cited By

Corus DOliveto P(2024)On the Generalisation Performance of Geometric Semantic Genetic Programming for Boolean Functions: Learning Block MutationsACM Transactions on Evolutionary Learning and Optimization10.1145/36771244:4(1-33)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3677124
Doerr BKötzing TGregor Lagodzinski JLengler J(2020)The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run timeTheoretical Computer Science10.1016/j.tcs.2020.01.011Online publication date: Jan-2020
https://doi.org/10.1016/j.tcs.2020.01.011
Moraglio AKrawiec KAuger AStützle T(2019)Semantic genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323378(1032-1055)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323378
Show More Cited By

Index Terms

Runtime analysis of mutation-based geometric semantic genetic programming on boolean functions
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Semantic Genetic Programming
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Semantic genetic programming is a recent, rapidly growing trend in Genetic Programming (GP) that aims at opening the 'black box' of the evaluation function and make explicit use of more information on program behavior in the search. In the most common ...
Geometric semantic genetic programming for recursive boolean programs
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Geometric Semantic Genetic Programming (GSGP) induces a unimodal fitness landscape for any problem that consists in finding a function fitting given input/output examples. Most of the work around GSGP to date has focused on real-world applications and ...
Runtime analysis of mutation-based geometric semantic genetic programming for basis functions regression
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Geometric Semantic Genetic Programming (GSGP) is a recently introduced form of Genetic Programming (GP) that searches the semantic space of functions/programs. The fitness landscape seen by GSGP is always -- for any domain and for any problem -- ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
104
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Corus DOliveto P(2024)On the Generalisation Performance of Geometric Semantic Genetic Programming for Boolean Functions: Learning Block MutationsACM Transactions on Evolutionary Learning and Optimization10.1145/36771244:4(1-33)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3677124
Doerr BKötzing TGregor Lagodzinski JLengler J(2020)The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run timeTheoretical Computer Science10.1016/j.tcs.2020.01.011Online publication date: Jan-2020
https://doi.org/10.1016/j.tcs.2020.01.011
Moraglio AKrawiec KAuger AStützle T(2019)Semantic genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323378(1032-1055)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323378
Kötzing TLagodzinski JLengler JMelnichenko A(2019)Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programmingTheoretical Computer Science10.1016/j.tcs.2019.11.036Online publication date: Dec-2019
https://doi.org/10.1016/j.tcs.2019.11.036
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
Kötzing TLagodzinski JLengler JMelnichenko A(2018)Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic ProgrammingParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99259-4_4(42-54)Online publication date: 21-Aug-2018
https://doi.org/10.1007/978-3-319-99259-4_4
Moraglio AMcDermott JO’Neill M(2018)Geometric Semantic Grammatical EvolutionHandbook of Grammatical Evolution10.1007/978-3-319-78717-6_7(163-188)Online publication date: 12-Sep-2018
https://doi.org/10.1007/978-3-319-78717-6_7
Doerr BKötzing TLagodzinski JLengler JBosman P(2017)Bounding bloat in genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071271(921-928)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071271
Moraglio AKrawiec KBosman P(2017)Geometric semantic genetic programming for recursive boolean programsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071266(993-1000)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071266
Moraglio AKrawiec KNeumann FSutton A(2016)Semantic Genetic ProgrammingProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2926990(639-662)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2926990
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