research-article

Single- and multi-objective genetic programming: new bounds for weighted order and majority

Authors:

Anh Nguyen,

Tommaso Urli,

Markus WagnerAuthors Info & Claims

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

Pages 161 - 172

https://doi.org/10.1145/2460239.2460254

Published: 16 January 2013 Publication History

Get Access

Abstract

We consolidate the existing computational complexity analysis of genetic programming (GP) by bringing together sound theoretical proofs and empirical analysis. In particular, we address computational complexity issues arising when coupling algorithms using variable length representation, such as GP itself, with different bloat-control techniques. In order to accomplish this, we first introduce several novel upper bounds for two single- and multi-objective GP algorithms on the generalised Weighted ORDER and MAJORITY problems. To obtain these, we employ well-established computational complexity analysis techniques such as fitness-based partitions, and for the first time, additive and multiplicative drift.

The bounds we identify depend on two measures, the maximum tree size and the maximum population size, that arise during the optimization run and that have a key relevance in determining the runtime of the studied GP algorithms. In order to understand the impact of these measures on a typical run, we study their magnitude experimentally, and we discuss the obtained findings.

References

[1]

Doerr, B., Johannsen, D., and Winzen, C. (2010). Multiplicative drift analysis. In Pelikan, M. and Branke, J., editors, GECCO, pages 1449--1456. ACM.

Digital Library

Google Scholar

[2]

Droste, S., Jansen, T., and Wegener, I. (2002). On the analysis of the (1 +1) evolutionary algorithm. Theoretical Computer Science, 276:51--81.

Digital Library

Google Scholar

[3]

Durrett, G., Neumann, F., and O'Reilly, U.-M. (2011). Computational complexity analysis of simple genetic programing on two problems modeling isolated program semantics. In FOGA, pages 69--80. ACM.

Digital Library

Google Scholar

[4]

Goldberg, D. E. and O'Reilly, U.-M. (1998). Where does the good stuff go, and why? How contextual semantics influences program structure in simple genetic programming. In EuroGP, volume 1391 of LNCS, pages 16--36. Springer.

Digital Library

Google Scholar

[5]

Kötzing, T., Sutton, A. M., Neumann, F., and O'Reilly, U.-M. (2012). The max problem revisited: the importance of mutation in genetic programming. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference, GECCO '12, pages 1333--1340, New York, NY, USA. ACM.

Digital Library

Google Scholar

[6]

Neumann, F. (2012). Computational complexity analysis of multi-objective genetic programming. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference, GECCO '12, pages 799--806, New York, NY, USA. ACM.

Digital Library

Google Scholar

[7]

Oliveto, P. S. and Witt, C. (2011). Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3):369--386.

Digital Library

Google Scholar

[8]

Poli, R., Langdon, W. B., and McPhee, N. F. (2008). A Field Guide to Genetic Programming. lulu.com.

Digital Library

Google Scholar

[9]

Urli, T., Wagner, M., and Neumann, F. (2012). Experimental supplements to the computational complexity analysis of genetic programming for problems modelling isolated program semantics. In PPSN. Springer. (to be published).

Digital Library

Google Scholar

[10]

Wagner, M. and Neumann, F. (2012). Parsimony pressure versus multi-objective optimization for variable length representations. In PPSN. Springer. (to be published).

Digital Library

Google Scholar

[11]

Wegener, I. (2002). Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In Evolutionary Optimization, pages 349--369. Kluwer.

Google Scholar

Cited By

View all

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
Langdon W(2021)Genetic programming convergenceGenetic Programming and Evolvable Machines10.1007/s10710-021-09405-923:1(71-104)Online publication date: 30-Aug-2021
https://doi.org/10.1007/s10710-021-09405-9
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
Show More Cited By

Index Terms

Single- and multi-objective genetic programming: new bounds for weighted order and majority
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Computational complexity analysis of multi-objective genetic programming
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

The computational complexity analysis of genetic programming (GP) has been started recently in [7] by analyzing simple (1+1) GP algorithms for the problems ORDER and MAJORITY. In this paper, we study how taking the complexity as an additional criteria ...
PAC learning and genetic programming
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Genetic programming (GP) is a very successful type of learning algorithm that is hard to understand from a theoretical point of view. With this paper we contribute to the computational complexity analysis of genetic programming that has been started ...
The max problem revisited: the importance of mutation in genetic programming
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the well-studied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

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: 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

9
Total Citations
View Citations
94
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

View all

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
Langdon W(2021)Genetic programming convergenceGenetic Programming and Evolvable Machines10.1007/s10710-021-09405-923:1(71-104)Online publication date: 30-Aug-2021
https://doi.org/10.1007/s10710-021-09405-9
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
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
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
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
Shi JQian CYu Y(2017)Evolutionary multi-objective optimization made faster by sequential decomposition2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969607(2488-2493)Online publication date: Jun-2017
https://doi.org/10.1109/CEC.2017.7969607
Wagner MNeumann FUrli T(2015)On the performance of different genetic programming approaches for the sorting problemEvolutionary Computation10.1162/EVCO_a_0014923:4(583-609)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1162/EVCO_a_00149
Wagner MNeumann F(2014)Single- and multi-objective genetic programming: New runtime results for sorting2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900310(125-132)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900310

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

Computational complexity analysis of multi-objective genetic programming

PAC learning and genetic programming

The max problem revisited: the importance of mutation in genetic programming