The fuzzy schemata introduced in this note encompass (Holland) schemata as well as their generalization by Vose to arbitrary predicates and allow to describe structural information contained in imprecise data. They are shown to satisfy a suitable version of the Schema Theorem, thus answering some questions raised by Holland concerning the existence of (generalized) schemata possessing this property. ยฉ 1998 Elsevier Science B.V.
Keywords." Artificial intelligence; Genetic algorithm; Schema 1. As pointed out in [1], it has remained an open question for a long time, whether there are subsets other than (Holland) schemata which, under appropriate genetic operators, behave according to the Schema Theorem. A positive answer has been given by Battle and Vose [1], based on transformation matrices, connected to isomorphisms of genetic algorithms.
The results in [1] may be viewed as an explicit example of a more general construction by Vose [5], who generalized the notion of schema to "arbitrary" predicates.
Let ~2 = {0, 1} l denote the space of length I binary strings and consider a real-valued functionf on ~2, the so-called fitness function, which we want to optimize. It is clear thatfmay only efficiently be optimized if it is "structured", i.e., if points close to a (local) maximum also have high fitness value. Here, "close" should, of course, be interpreted with respect to the Hamming distance, i.e., points are close if they share many bits.
To express these similarities, one may use length l (Holland) schemata [4], which are just strings H ~ {0, 1, .}t, where โข is a don't care or wildcard symbol. For example, if f(p) is above average for all strings in p ~ O starting with 10, we may express this by saying that the schema H = 10 * ... * has high fitness. If we define a string p E Q to belong to a schema H if p and H coincide in all locations different from โข in H (we write this as H --* p), it is thus clear that schemata may also be viewed as linear varieties in O.
- The Schema Theorem [4] stochastically describes how schemata are sampled, in terms of their average fitness in a current population and structural information (their "order" and "defining length", cf. [4] for details), showing these to be a very efficient tool when studying the behaviour and convergence properties of