An Overview of Schema Theory <s> E(m(H, t + 1)) = nα(H, t) and V ar(m(H, t + 1)) = nα(H, t)(1 − α(H, t)) <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> E(m(H, t + 1)) = nα(H, t) and V ar(m(H, t + 1)) = nα(H, t)(1 − α(H, t)) <s> This paper presents two new schema theorems in which expectations are absent. The first theorem provides confidence intervals for the number of instances of a schema at the next generation. The second gives a lower bound for the same quantity. <s> BIB002
These equations immediately yield an improvement to the Probabilistic Schema Theorem: This theorem holds regardless of the representation adopted, operators used, or definition of schema. Thus, it applies to genetic algorithms with bit-string representations of varying length. This is one of several instances where genetic programming schema theory yields useful applications to genetic algorithm schema theory and vice versa. From this theorem we go in two directions. First, we define the signal-to-noise ratio When this number is large the number of schemata in generation t + 1 will be very close to the expected number. When the ratio is small the number of schemata in generation t + 1 will be effectively random. Poli shows that as α(H, t) → 1 the ratio approaches infinity. A corollary of these calculations is the probability of extinction in any generation: Clearly this quantity approaches zero as α(H, t) grows and so heuristically a schema is expected to survive if α(H, t) > 4/n. However, newly created schema are very likely to go extinct. Calculations show the probability of extinction in the first generation after creation is above 37%. The probability of extinction within the first two generations is above 50%. This evidence suggests that more selection pressure or a steady-state genetic algorithm will be more likely to preserve high fitness newly created schemata. These heuristics come from useful bounds developed on the expectation and variance of m(H, t + 1). These bounds can be found in BIB001 . Combining the probabilistic theorems with the exact, microscopic, and macroscopic theorems gives a host of new and powerful theorems. Many of these theorems have not been explicitly stated, and this is one area for future research discussed in Section 8. The second direction to go from the probabilistic schema theorem is to fix the value of x and attempt to solve for the right-hand side y of the equation. This is what Poli refers to as "predicting the past from the future" because we are fixing the future and finding what we need in the past to guarantee that future. Unfortunately, the solution is expressed in terms of the hypergeometric probability distribution (see BIB002 , so this is a hard problem. Some of the necessary mathematics has been done, and the α from the next section is one such inverse function. An application of Chebychev's Inequality using k = (1 − y) −1/2 can give a simpler answer but one without as much accuracy. At this point Poli also considered the effect of using Chernoff-Hoeffding bounds rather than the onesided Chebychev inequality. The result is a slightly better bound on y from x and also confidence intervals. A more careful application of the various inequalities in probability theory may yield yet tighter bounds.