Price's Theorem and the MAX Problem

author = "W. B. Langdon and R. Poli",

title = "{Price's} Theorem and the {MAX} Problem",

institution = "University of Birmingham, School of Computer Science",

number = "CSRP-97-4",

month = jan,

year = "1997",

file = "/1997/CSRP-97-04.ps.gz",

keywords = "genetic algorithms, genetic programming",

URL = "

ftp://ftp.cs.bham.ac.uk/pub/tech-reports/1997/CSRP-97-04.ps.gz",

abstract = "We present a detailed analysis of the evolution of GP populations using the problem of finding a program which returns the maximum possible value for a given terminal and function set and a depth limit on the program tree (known as the MAX problem). We confirm the basic message of \cite{Gathercole:1996:aicrtd} that crossover together with program size restrictions can be responsible for premature convergence to a sub-optimal solution. We show that this can happen even when the population retains a high level of variety and show that in many cases evolution from the sub-optimal solution to the solution is possible if sufficient time is allowed. In both cases theoretical models are presented and compared with actual runs. Experimental evidence is presented that Price's Covariance and Selection Theorem can be applied to GP populations and the practical effect of program size restrictions are noted. Finally we show that covariance between gene frequency and fitness in the first few generations can be used to predict the course of GP runs.",