More Web Proxy on the site http://driver.im/

article

The Max problem revisited: The importance of mutation in genetic programming

Authors:

Andrew M. Sutton,

Una-May O'reillyAuthors Info & Claims

Theoretical Computer Science, Volume 545

Pages 94 - 107

https://doi.org/10.1016/j.tcs.2013.06.014

Published: 01 August 2014 Publication History

Abstract

We study the importance of mutation in genetic programming and contribute to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses for the well-known Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved efficiently using simple mutation-based genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutation-based genetic programming algorithms.

References

[1]

. In: Auger, A., Doerr, B. (Eds.), Theory of Randomized Search Heuristics: Foundations and Recent Developments, World Scientific.

[2]

Cathabard, S., Lehre, P.K. and Yao, X., Non-uniform mutation rates for problems with unknown solution lengths. In: Beyer, H.-G., Langdon, W.B. (Eds.), FOGA, ACM. pp. 173-180.

[3]

Durrett, G., Neumann, F. and O'Reilly, U.-M., Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics. In: Proc. of FOGA'11, pp. 69-80.

[4]

Feldman, V., Evolvability from learning algorithms. In: Dwork, C. (Ed.), STOC, ACM. pp. 619-628.

[5]

Gathercole, C. and Ross, P., An adverse interaction between crossover and restricted tree depth in genetic programming. In: Proceedings of the First Annual Conference on Genetic Programming, pp. 291-296.

[6]

Goldberg, D.E. and O'Reilly, U.-M., Where does the good stuff go, and why? How contextual semantics influences program structure in simple genetic programming. In: Banzhaf, W., Poli, R., Schoenauer, M., Fogarty, T.C. (Eds.), Lecture Notes in Comput. Sci., vol. 1391. Springer. pp. 16-36.

[7]

Ivchenko, G., Limit theorems in an occupancy problem. Theory Probab. Appl. v16 i2. 293-307.

[8]

Kötzing, T., Neumann, F. and Spöhel, R., PAC learning and genetic programming. In: Krasnogor, N., Lanzi, P.L. (Eds.), GECCO, ACM. pp. 2091-2096.

[9]

Kötzing, T., Sutton, A.M., Neumann, F. and O'Reilly, U.-M., The max problem revisited: the importance of mutation in genetic programming. In: Soule, T., Moore, J.H. (Eds.), Genetic and Evolutionary Computation Conference, ACM. pp. 1333-1340.

[10]

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

[11]

Langdon, W.B. and Poli, R., An analysis of the MAX problem in genetic programming. In: Advances in Genetic Programming 3, MIT Press. pp. 301-323.

[12]

Motwani, R. and Raghavan, P., Randomized Algorithms. 1995. Cambridge University Press.

[13]

Neumann, F., Computational complexity analysis of multi-objective genetic programming. In: Soule, T., Moore, J.H. (Eds.), Genetic and Evolutionary Computation Conference, ACM. pp. 799-806.

[14]

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

[15]

O'Reilly, U.-M., An analysis of genetic programming. 22 Sept. 1995. Carleton University, Ottawa-Carleton Institute for Computer Science, Ottawa, Ontario, Canada.

[16]

O'Reilly, U.-M. and Oppacher, F., Program search with a hierarchical variable length representation: Genetic programming, simulated annealing and hill climbing. In: Davidor, Y., Schwefel, H.-P., Manner, R. (Eds.), Lecture Notes in Comput. Sci., vol. 866. Springer-Verlag. pp. 397-406.

[17]

Valiant, L.G., Evolvability. J. ACM. v56 i1.

Cited By

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(2022)Genetic programming convergenceGenetic Programming and Evolvable Machines10.1007/s10710-021-09405-923:1(71-104)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10710-021-09405-9
Doerr BLissovoi AOliveto PAuger AStützle T(2019)Evolving boolean functions with conjunctions and disjunctions via genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321851(1003-1011)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321851
Show More Cited By

The Max problem revisited: The importance of mutation in genetic programming
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

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 ...
Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming
Abstract
For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation: the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 545, Issue

August, 2014

128 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2013.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 August 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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(2022)Genetic programming convergenceGenetic Programming and Evolvable Machines10.1007/s10710-021-09405-923:1(71-104)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10710-021-09405-9
Doerr BLissovoi AOliveto PAuger AStützle T(2019)Evolving boolean functions with conjunctions and disjunctions via genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321851(1003-1011)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321851
Lissovoi AOliveto PMcIlraith SWeinberger K(2018)On the time and space complexity of genetic programming for evolving boolean conjunctionsProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence10.5555/3504035.3504202(1363-1370)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.5555/3504035.3504202

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents