机器学习

5.4 Hypothesis Space Search
As illustrated above, GAS employ a randomized beam search method to seek a maximally fit hypothesis.
This search is quite different from that of other learning methods we have considered in this book. To
contrast the hypothesis space search of GAS with that of neural network BACKPROPAGATION, for
example, the radiant descent search in BACKPROPAGATION moves smoothly from one hypothesis to a
new hypothesis that is very similar. In contrast, the GA search can move much more abruptly, replacing
a parent hypothesis by an offspring that may be radically different from the parent. Note the GA search
is therefore less likely to fall into the same kind of local minima that can plague gradient descent
methods.
One practical difficulty in some GA applications is the problem of crowding. Crowding is a phenomenon
in which some individual that is more highly fit than others in the population quickly reproduces, so that
copies of this individual and very similar individuals take over a large fraction of the population. The
negative impact of crowding is that it reduces the diversity of the population, thereby slowing further
progress by the GA. Several strategies have been explored for reducing crowding. One approach is to
alter the selection function, using criteria such as tournament selection or rank selection in place of
fitness proportionate roulette wheel selection. A related strategy is "fitness sharing," in which the
measured fitness of an individual is reduced by the presence of other, similar individuals in the
population. A third approach is to restrict the kinds of individuals allowed to recombine to form
offspring. For example, by allowing only the most similar individuals to recombine, we can encouragthe formation of clusters of similar individuals, or multiple "subspecies" within the population. A related
approach is to spatially distribute individuals and allow only nearby individuals to recombine. Many of
these techniques are inspired by the analogy to biological evolution.
Population Evolution and the Schema Theorem
It is interesting to ask whether one can mathematically characterize the evolution over time of the
population within a GA. The schema theorem provides one such characterization. It is based on the
concept of schemas, or patterns that describe sets of bit strings. To be precise, a schema is any string
composed of 0s, 1s, and *'s. Each schema represents the set of bit strings containing the indicated 0s
and 1s, with each “*” interpreted as a "don't care." For example, the schema 0*10 represents the set of
bit strings that includes exactly 0010 and 01 10.
An individual bit string can be viewed as a representative of each of the different schemas that it
matches. For example, the bit string 0010 can be thought of as a representative of 24 distinct schemas
including 00**, 0* 10, ****, etc. Similarly, a population of bit strings can be viewed in terms of the set
of schemas that it represents and the number of individuals associated with each of these schema.
The schema theorem characterizes the evolution of the population within a GA in terms of the number
of instances representing each schema. Let m(s, t) denote the number of instances of schema s in the
population at time t (i.e., during the tth generation). The schema theorem describes the expected value
of m(s,t+1) in terms of m(s, t) and other properties of the schema, population, and GA algorithm
parameters.
The evolution of the population in the GA depends on the selection step, the recombination step, and
the mutation step. Let us start by considering just the effect of the selection step. Let f denote the
fitness of the individual bit string h and 
 f t  denote the average fitness of all individuals in the
population at time t. Let n be the total number of individuals in the population. Let hs 
 p , indicate
t
that the individual h is both a representative of schema s and a member of the population at time t.
Finally, let u 
 s, t  denote the average fitness of instances of schema s in the population at time t.
We are interested in calculating the expected value of m(s,t+1), which we denote E[m(s,t+1)]. We can
calculate E[m(s,t+1)] using the probability distribution for selection given in Equation, which can be
restated using our current terminology as follows
Now if we select one member for the new population according to this probability distribution, then the
probability that we will select a representative of schema s is
108
The second step above follows from the fact that by definition,
Equation gives the probability that a single hypothesis selected by the GA will be an instance of schema
s. Therefore, the expected number of instances of s resulting from the n independent selection steps
that create the entire new generation is just n times this probability.
Equation states that the expected number of instances of schema s at generation t+1 is proportional to
the average fitness u 
  s , t  of instances of this schema at time t , and inversely proportional to the
average fitness 
 f t  of all members of the population at time t. Thus, we can expect schemas with
above average fitness to be represented with increasing frequency on successive generations. If we
view the GA as performing a virtual parallel search through the space of possible schemas at the same
time it performs its explicit parallel search through the space of individuals, then Equation indicates that
more fit schemas will grow in influence over time.
While the above analysis considered only the selection step of the GA, the crossover and mutation
steps must be considered as well. The schema theorem considers only the possible negative influence
of these genetic operators (e.g., random mutation may decrease the number of representatives of s,
independent of u 
 s, t  and considers only the case of single-point crossover. The full schema theorem
thus provides a lower bound on the expected frequency of schema s, as follows:
Here, p c is the probability that the single-point crossover operator will be applied
to an arbitrary individual, and pm, is the probability that an arbitrary bit of an arbitrary individual will be
mutated by the mutation operator. o(s) is the number of defined bits in schema s, where 0 and 1 are
defined bits, but * is not. d(s) is the distance between the leftmost and rightmost defined bits in s.
Finally, l is the length of the individual bit strings in the population. Notice the leftmost term in Equation
is identical to the term from Equation and describes the effect of the selection step. The middle term
describes the effect of the single-point crossover operator-in particular, it describes the probability that
an arbitrary individual representing s will still represent s following application of this crossover
operator. The rightmost term describes the probability that an arbitrary individual representing schema
s will still represent schema s following application of the mutation operator. Note that the effects of
single-point crossover and mutation increase with the number of defined bits o(s) in the schema and
with the distance d(s) between the defined bits. Thus, the schema theorem can be roughly interpreted
as stating that more fit schemas will tend to grow in influence, especially schemas containing a small
number of defined bits (i.e., containing a large number of *'s), and especially when these defined bits
109
are near one another within the bit string. The schema theorem is perhaps the most widely cited
characterization of population evolution within a GA. One way in which it is incomplete is that it fails to
consider the (presumably) positive effects of crossover and mutation. Numerous more recent
theoretical analyses have been proposed, including analyses based on Markov chain models and on
statistical mechanics models.