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 theoreticalresults 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 generaiton. 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 botainign 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 reult supports the existance of building blocks in GP which ,howeve,r are not necessarily all short, low-order or highly fit. Building on earlier work, we show how Stephens and Waelbroecks' GA results and the new GP results described in the paper can be used to evalaute 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.
展开▼
