Microscopic and Macroscopic Schema Theories for Genetic Programming and Variable-length Genetic Algorithms with One-Point Crossover, their Use and their Relations with Earlier GP and GA Schema Theories

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

@TechReport{Poli00b,

• author = "Riccardo Poli",
• title = "Microscopic and Macroscopic Schema Theories for Genetic Programming and Variable-length Genetic Algorithms with One-Point Crossover, their Use and their Relations with Earlier GP and GA Schema Theories",
• institution = "University of Birmingham, School of Computer Science",
• number = "CSRP-00-15",
• month = oct,
• year = "2000",
• keywords = "genetic algorithms, genetic programming",
• email = "R.Poli@cs.bham.ac.uk",
• file = "/2000/CSRP-00-15.ps.gz",
• URL = "ftp://ftp.cs.bham.ac.uk/pub/tech-reports/2000/CSRP-00-15.ps.gz",
• abstract = "A few schema theorems for GP have been proposed in the literature in the last few years. One of their main weaknesses is that they provide only a lower bound for the expected value of the number of instances of a given schema H at the next generation, E[m(H,t+1)], rather than an exact value. This paper presents new theoretical results for GP with one-point crossover which overcome this problem. Firstly, we give an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation in terms of microscopic quantities. Thanks to this formulation we are then able to provide in improved version for an earlier GP schema theorem in which some (but not all) schema creation events are accounted for, thus obtaining a tighter bound for E[m(H,t+1)]. Then, we extend the microscopic schema theorem to obtain an exact formulation of E[m(H,t+1)] in terms of macroscopic quantities. In this formulation E[m(H,t+1)] is a function of the selection probabilities of the schema itself and of a set of lower-order schemata which one-point crossover uses to build instances of the schema. This result makes the effects and the mechanisms of schema creation explicit, unlike previous work which concentrated on schema survival and disruption. This supports the existence of building blocks in GP which, however, are not necessarily all short, low-order or highly fit. Also, the macroscopic schema theorem allows the exact formulation of the notion of effective fitness in GP and opens the way to future work on GP convergence, population sizing, operator biases, and bloat, only to mention some possibilities.",

}

Genetic Programming entries for Riccardo Poli

Citations