Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKotzing, T.en
dc.contributor.authorNeumann, F.en
dc.contributor.authorSpohel, R.en
dc.identifier.citationGECCO'11: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, held in Dublin, Ireland, 12-16 July, 2011: pp.2091-2096en
dc.description.abstractGenetic 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 recently. We analyze GP in the well-known PAC learning framework and point out how it can observe quality changes in the the evolution of functions by random sampling. This leads to computational complexity bounds for a linear GP algorithm for perfectly learning any member of a simple class of linear pseudo-Boolean functions. Furthermore, we show that the same algorithm on the functions from the same class finds good approximations of the target function in less time.en
dc.description.statementofresponsibilityTimo Kötzing, Frank Neumann and Reto Spöhelen
dc.publisherACM Pressen
dc.rightsCopyright 2011 ACMen
dc.subjectGenetic programming; PAC learning; theory; runtime analysisen
dc.titlePAC learning and genetic programmingen
dc.typeConference paperen
dc.contributor.conferenceGenetic and Evolutionary Computation Conference (13th : 2011 : Dublin, Ireland)en
dc.publisher.placeNew Yorken
pubs.library.collectionComputer Science publicationsen
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]en
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_71908.pdfRestricted Access511.41 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.