Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/71908
Citations
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.date.issued2011en
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.identifier.isbn9781450305570en
dc.identifier.urihttp://hdl.handle.net/2440/71908-
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.language.isoenen
dc.publisherACM Pressen
dc.rightsCopyright 2011 ACMen
dc.source.urihttp://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2011.htmlen
dc.subjectGenetic programming; PAC learning; theory; runtime analysisen
dc.titlePAC learning and genetic programmingen
dc.typeConference paperen
dc.identifier.rmid0020118207en
dc.contributor.conferenceGenetic and Evolutionary Computation Conference (13th : 2011 : Dublin, Ireland)en
dc.identifier.doi10.1145/2001576.2001857en
dc.publisher.placeNew Yorken
dc.identifier.pubid24974-
pubs.library.collectionComputer Science publicationsen
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
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.