Computational Complexity, Genetic Programming, and Implications

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@InProceedings{rylander:2001:EuroGP,

• author = "Bart Rylander and Terry Soule and James Foster",
• title = "Computational Complexity, Genetic Programming, and Implications",
• booktitle = "Genetic Programming, Proceedings of EuroGP'2001",
• year = "2001",
• editor = "Julian F. Miller and Marco Tomassini and Pier Luca Lanzi and Conor Ryan and Andrea G. B. Tettamanzi and William B. Langdon",
• volume = "2038",
• series = "LNCS",
• pages = "348--360",
• address = "Lake Como, Italy",
• publisher_address = "Berlin",
• month = "18-20 " # apr,
• organisation = "EvoNET",
• publisher = "Springer-Verlag",
• keywords = "genetic algorithms, genetic programming, Computational Complexity, Quantum Computing: Poster",
• ISBN = "3-540-41899-7",
• URL = "http://faculty.up.edu/rylander/my%20pubs/egpfin.pdf",
• DOI = "doi:10.1007/3-540-45355-5_28",
• size = "13 pages",
• 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 [l]. 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.",
• notes = "EuroGP'2001, part of \cite{miller:2001:gp}",

}

Genetic Programming entries for Bart I Rylander Terence Soule James A Foster

Citations