Article

Computational Complexity, Genetic Programming, and Implications

Authors:

Bart Rylander,

Terence Soule,

James A. FosterAuthors Info & Claims

EuroGP '01: Proceedings of the 4th European Conference on Genetic Programming

Pages 348 - 360

Published: 18 April 2001 Publication History

Abstract

Recent theory work has shown that a Genetic Program (GP) used to produce programs may have output that is bounded above by the GP itself [1]. This paper presents proofs that show that 1) a program that is the output of a GP or any inductive process has complexity that can be bounded by the Kolmogorov complexity of the originating program; 2) this result does not hold if the random number generator used in the evolution is a true random source; and 3) an optimization problem being solved with a GP will have a complexity that can be bounded below by the growth rate of the minimum length problem representation used for the implementation. These results are then used to provide guidance for GP implementation.

References

[1]

Rylander, B.: On GP Complexity, Proceedings of the Genetic and Evolutionary Computation Conference Workshop Program (2000), pp. 309-311.

Google Scholar

[2]

Soule, T., Foster, J., Dickinson, J.: Using Genetic Programming to Approximate Maximum Cliques, Proceedings Genetic Programming Conference (1998), pp. 400-405.

Crossref

Google Scholar

[3]

Li, M., Vitanyi, P.: Kolmogorov Complexity and its Applications, Handbook of Theoretical Computer Science Volume A. Algorithms and Complexity, pp. 189-254. The MIT Press, Cambridge, Massachusetts (1990).

Crossref

Google Scholar

[4]

O'Reilly, U.: An Analysis of Genetic Programming, Doctoral Thesis, School of Computer Science, Carleton University, Ottawa, Ontario, Canada (1995), pp. 14.

Crossref

Google Scholar

[5]

Rylander, B., Foster, J.: GA -Hard Problems, Proceedings of the Genetic and Evolutionary Computation Conference (2000), pp. 367.

Google Scholar

[6]

Rylander, B., Foster, J.: Computational Complexity and Genetic Algorithms, Proceedings of the World Science and Engineering Society's Conference on Soft Computing (2001).

Google Scholar

[7]

Rylander, B., Foster, J.: Genetic Algorithms, and Hardness, Proceedings of the World Science and Engineering Society's Conference on Soft Computing (2001).

Google Scholar

[8]

Langdon, W., Soule, T., Poli, R., Foster, J.: The Evolution of Size and Shape, Advances in Genetic Programming Volume III, pp. 163-190. The MIT Press, Cambridge, Massachusetts (1999).

Crossref

Google Scholar

[9]

Soule, T., Foster, J., Dickinson, J.: Code Growth in Genetic Programming, Proceedings Genetic Programming Conference (1996), pp. 215-223.

Crossref

Google Scholar

[10]

Rylander, B., Soule, T., Foster, J.: Quantum Genetic Algorithms, proceedings of the Genetic and Evolutionary Computation Conference (2000), pp. 373.

Google Scholar

[11]

Ge, Y., Watson, L., Collins, E.: Genetic Algorithms for Optimization on a Quantum Computer, Unconventional Models of Computation, Springer-Verlag, London (1998).

Google Scholar

[12]

Narayan, A., Moore, M.: Quantum Inspired Genetic Algorithms, Technical Report 344, Department of Computer Science, University of Exeter, England (1998).

Google Scholar

Cited By

View all

Barkaoui MBerger JBoukhtouta A(2019)An evolutionary approach for the target search problem in uncertain environmentJournal of Combinatorial Optimization10.1007/s10878-019-00413-138:3(808-835)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10878-019-00413-1
Udrescu MProdan LVlăduţiu MAlderighi MSalapura VMcKee S(2006)Implementing quantum genetic algorithmsProceedings of the 3rd conference on Computing frontiers10.1145/1128022.1128034(71-82)Online publication date: 3-May-2006
https://dl.acm.org/doi/10.1145/1128022.1128034

Computational Complexity, Genetic Programming, and Implications
1. Theory of computation

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 ...
Computational complexity and the genetic algorithm
Neural network crossover in genetic algorithms using genetic programming
Abstract
The use of genetic algorithms (GAs) to evolve neural network (NN) weights has risen in popularity in recent years, particularly when used together with gradient descent as a mutation operator. However, crossover operators are often omitted from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EuroGP '01: Proceedings of the 4th European Conference on Genetic Programming

April 2001

379 pages

ISBN:3540418997

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 April 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Barkaoui MBerger JBoukhtouta A(2019)An evolutionary approach for the target search problem in uncertain environmentJournal of Combinatorial Optimization10.1007/s10878-019-00413-138:3(808-835)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10878-019-00413-1
Udrescu MProdan LVlăduţiu MAlderighi MSalapura VMcKee S(2006)Implementing quantum genetic algorithmsProceedings of the 3rd conference on Computing frontiers10.1145/1128022.1128034(71-82)Online publication date: 3-May-2006
https://dl.acm.org/doi/10.1145/1128022.1128034

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Computational complexity analysis of multi-objective genetic programming

Computational complexity and the genetic algorithm

Neural network crossover in genetic algorithms using genetic programming

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations