Page 222 -

210 5 Neural Networks

a chromosome template, represented by a sequence using the special symbol * as a
representation of any gene value. Consider, for instance, a chromosome with three
binary genes. Each possible genetic combination corresponds to a vertex of a 3-
dimensional cube. Consider now the schema:

This schema represents the vertices { 101) and (1 11 ), i.e., the cube edge
corresponding to a fixed value of 1 for the first and third genes. In general, a
schema acts like a hyperplane separating sets of chromosomes.
Let us denote:
- k, order of schema H, defined as the number of fixed positions in the schema.
The above example has k=2. An order of zero corresponds to the full search
space.
- n(g) , number of instances of g in the population of chromosomes.
- n(H)= x n(g) , number of schemata in the population of chromosomes.
ge H

With this notation we can express, as follows, the average fitness at time t for all
sequences in the population that belong to a schema H:

where n(H, t) is the number of schemata at time t.
Using roulette-wheel, the expected number of selections of g is:

where T(t) is the average fitness of all chromosomes at time t. Therefore, the
number of schemata Hat time t+l is:

This shows that the number of schemata with above average fitness will
increase, while the others, with below average fitness, will decrease. In particular,
if f (H, t)l f c)= a > 1 then an exponential growth n(H, t)= n(~,~)a' will be
observed.
Let us analyse now the effect of 1-point crossover. For this purpose let us denote
by d(H) the length of a schema, defined as the distance between the first and last
fixed positions of the schema; d(H) E [0, m-1] for chromosomes with m genes.