Fundamentals of Schema Theory
All developments described in this section assume the same scenario analyzed by Holland (1975), using a simple GA with proportionate selection operator, one-point crossover and bit-flip mutations. The population X is composed of n decision vectors xi = (x1,..., xℓ)T ∈ {0,1}ℓ.
In GA's context, each sample is called an individual, and the set of all individuals a populationX. Assuming that the search space is not random, if we take from the population those individuals which are best evaluated according to some function f(x), we are selecting solutions which share some important characteristics, measured by function f. Holland (1975) calls such features schema, since they identify the inner structure of the individuals which has made them to be selected at the first place.
A schema is a string representing similarities among the solutions in a population (Goldberg, 2002). Furthermore, using a simple similarity template we can represent any possible schema by adding a wild-card character, which will identify any dissimilarities among the n ℓ-bit strings.
We say that one solution x is represented by a schema S if x differs from S only in positions where si = *, for 1 ≤ i ≤ ℓ. Therefore, a schema S defines a set: