An Overview of Schema Theory <s> Chebychev's Inequality gives: <s> This paper first analyses the impact of variance on schema transmission. Working from an exact derivation of the expected variance in schema transmission, it derives and analyses the signal-to-noise ratio for schemata. The paper then presents short term schema transmission probability results that focus on newly created schemata in the population. The analysis reveals the relative dependencies between schema transmission, population size, schema measured fitness, schema fragility and schema creation. <s> BIB001 </s> An Overview of Schema Theory <s> Chebychev's Inequality gives: <s> Two main weaknesses of GA and GP schema theorems are that they provide only information on the expected value of the number of instances of a given schema at the next generation E[m(H,t + 1)], and they can only give a lower bound for such a quantity. This paper presents new theoretical results on GP and GA schemata which largely overcome these weaknesses. Firstly, unlike previous results which concentrated on schema survival and disruption, our results extend to GP recent work on GA theory by Stephens and Waelbroeck, and make the effects and the mechanisms of schema creation explicit. This allows us to give an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. Thanks to this formulation we are then able to provide in improved version for an earlier GP schema theorem in which some schema creation events are accounted for, thus obtaining a tighter bound for E[m(H, t + 1)]. This bound 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 supports the existence of building blocks in GP which, however, are not necessarily all short, low-order or highly fit. Building on earlier work, we show how Stephens and Waelbroeck’s GA results and the new GP results described in the paper can be used to evaluate schema variance, signal-to-noise ratio and, in general, the probability distribution of m(H, t + 1). In addition, we show how the expectation operator can be removed from the schema theorem so as to predict with a known probability whether m(H, t + 1) (rather than E[m(H, t + 1)]) is going to be above a given threshold. <s> BIB002
Theorem 8 (Two-sided probabilistic Schema Theorem). In BIB002 and BIB001 , Poli asked whether the lower bound in the Schema Theorem was reliable. This led him to investigate the impact of variance on schema transmission. Let p s (H, t) be the probability that individuals in H will survive crossover and let p c (H, t) be the probability that offspring sampling H will be created by crossover between parents not sampling H. Poli observed that this selection/crossover process is a Bernoulli trial and thus we are dealing with a binomial stochastic variable: