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.3973

@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