
Summary: A few schema theorems for genetic programming (GP) have been proposed in the literature in the last few years. Since they consider schema survival and disruption only, they can only provide a lower bound for the expected value of the number of instances of a given schema at the next generation rather than an exact value. This paper presents theoretical results for GP with one-point crossover which overcome this problem. First, we give an exact formulation for the expected number of instances of a schema at the next generation in terms of microscopic quantities. Due to this formulation we are then able to provide an improved version of an earlier GP schema theorem in which some (but not all) schema creation events are accounted for. Then, we extend this result to obtain an exact formulation in terms of macroscopic quantities which makes all the mechanisms of schema creation explicit. This 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, to mention only some of the possibilities.
Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.), Computing methodologies and applications, Learning and adaptive systems in artificial intelligence, variable-length genetic algorithms, genetic programming, schema theory, one-point crossover
Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.), Computing methodologies and applications, Learning and adaptive systems in artificial intelligence, variable-length genetic algorithms, genetic programming, schema theory, one-point crossover
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 74 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
