TY - JOUR

T1 - On the strength of size limits in linear genetic programming

AU - McPhee, Nicholas Freitag

AU - Jarvis, Alex

AU - Crane, Ellery Fussell

PY - 2004/12/1

Y1 - 2004/12/1

N2 - Bloat is a common and well studied problem in genetic programming. Size and depth limits are often used to combat bloat, but to date there has been little detailed exploration of the effects and biases of such limits. In this paper we present empirical and theoretical analyses of the effect of size limits on variable length linear structures. Specifically, we examine the relationship between size limits and the average size of individuals in a population and define the notion of size limit strength. When a size limit is strong, the average size of a population converges to a relatively stable value. When a size limit is weak, no such convergence occurs. The average size instead appears to perform a random walk within a bounded region. We use schema theory to show this is likely a result of uneven sampling of the search space.

AB - Bloat is a common and well studied problem in genetic programming. Size and depth limits are often used to combat bloat, but to date there has been little detailed exploration of the effects and biases of such limits. In this paper we present empirical and theoretical analyses of the effect of size limits on variable length linear structures. Specifically, we examine the relationship between size limits and the average size of individuals in a population and define the notion of size limit strength. When a size limit is strong, the average size of a population converges to a relatively stable value. When a size limit is weak, no such convergence occurs. The average size instead appears to perform a random walk within a bounded region. We use schema theory to show this is likely a result of uneven sampling of the search space.

UR - http://www.scopus.com/inward/record.url?scp=32444435471&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=32444435471&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:32444435471

SN - 0302-9743

VL - 3103

SP - 593

EP - 604

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -