机器学习

The problem addressed by GAS is to search a space of candidate hypotheses to identify the best
hypothesis. In GAS the "best hypothesis" is defined as the one that optimizes a predefined numerical
measure for the problem at hand, called b the hypothesis fitness. For example, if the learning task is the
problem of approximating an unknown function given training examples of its input and output, then
fitness could be defined as the accuracy of the hypothesis over this training data. If the task is to learn a
strategy for playing chess, fitness could be defined as the number of games won by the individual when
playing against other individuals in the current population.
Although different implementations of genetic algorithms vary in their details, they typically share the
following structure: The algorithm operates by iteratively updating a pool of hypotheses, called the
population. On each iteration, all members of the population are evaluated according to the fitness
function. A new population is then generated by probabilistically selecting the fit individuals from the
current population. Some of these selected individuals are carried forward into the next generation
population intact. Others are used as the basis for creating new offspring individuals by applying genetic
operations such as crossover and mutation.
The inputs to this algorithm include the fitness function for ranking candidate hypotheses, a
threshold defining an acceptable level of fitness for terminating the algorithm, the size of the
population to be maintained, and parameters that determine how successor populations are to be
generated: the fraction of the population to be replaced at each generation and the mutation rate.
Notice in this algorithm each iteration through the main loop produces a new generation of hypotheses
based on the current population. First, a certain number of hypotheses from the current population are
selected for inclusion in the next generation. These are selected probabilistically, where the probability
of selecting hypothesis hi is given by
Thus, the probability that a hypothesis will be selected is proportional to its own fitness and is
inversely proportional to the fitness of the other competing hypotheses in the current population.
Once these members of the current generation have been selected for inclusion in the next generation
population, additional members are generated using a crossover operation. Crossover, defined in detail
in the next section, takes two parent hypotheses from the current generation and creates two offspring
hypotheses
by recombining portions of both parents. The parent hypotheses are chosen probabilistically from the
current population, again using the probability function given by Equation (9.1). After new members
have been created by this crossover operation, the new generation population now contains the
101
desired number of members. At this point, a certain fraction m of these members are chosen at
random, and random mutations all performed to alter these members.
This GA algorithm thus performs a randomized, parallel beam search for hypotheses that perform well
according to the fitness function. In the following subsections, we describe in more detail the
representation of hypotheses and genetic operators used in this algorithm.
Representing Hypotheses
Hypotheses in GAS are often represented by bit strings, so that they can be easily manipulated
by genetic operators such as mutation and crossover. The hypotheses represented by these bit strings
can be quite complex. For example, sets of if-then rules can easily be represented in this way, by
choosing an encoding of rules that allocates specific substrings for each rule precondition and
postcondition.
To see how if-then rules can be encoded by bit strings, .first consider how we might use a bit
string to describe a constraint on the value of a single attribute. To pick an example, consider the
attribute Outlook, which can take on any of the three values Sunny, Overcast, or Rain. One obvious way
to represent a constraint on Outlook is to use a bit string of length three, in which each bit position
corresponds to one of its three possible values. Placing a 1 in some position indicates that the attribute
is allowed to take on the corresponding value. For example, the string 010 represents the constraint
that Outlook must take on the second of these values, or Outlook = Overcast. Similarly, the string 011
represents the more general constraint that allows two possible values, or (Outlook = Overcast v Rain).
Note 11 1 represents the most general possible constraint, indicating that we don't care which of its
possible values the attribute takes on.
Given this method for representing constraints on a single attribute, conjunctions of constraints
on multiple attributes can easily be represented by concatenating the corresponding bit strings. For
example, consider a second attribute, Wind, that can take on the value Strong or Weak. A rule
precondition such as
(Outlook = Overcast ^Rain) A (Wind = Strong)
can then be represented by the following bit string of length five:
Outlook Wind
01 1
 10
Rule postconditions (such as PlayTennis = yes) can be represented in a similar fashion. Thus, an entire
rule can be described by concatenating the bit strings describing the rule preconditions, together with
the bit string describing the rule postcondition. For example, the rule
IF Wind = Strong THEN PlayTennis = yes
would be represented by the string
Outlook Wind PlayTennis
111
 10
 10
where the first three bits describe the "don't care" constraint on Outlook, the next two bits describe the
constraint on Wind, and the final two bits describe the rule postcondition (here we assume PlayTennis
102
can take on the values Yes or No). Note the bit string representing the rule contains a substring for each
attribute in the hypothesis space, even if that attribute is not constrained by the rule preconditions. This
yields a fixed length bit-string representation for rules, in which substrings at specific locations describe
constraints on specific attributes. Given this representation for single rules, we can represent sets of
rules by similarly concatenating the bit string representations of the individual rules.
In designing a bit string encoding for some hypothesis space, it is useful to arrange for every
syntactically legal bit string to represent a well-defined hypothesis. To illustrate, note in the rule
encoding in the above paragraph the bit string 11 1 10 11 represents a rule whose postcondition does
not constrain the target attribute PlayTennis. If we wish to avoid considering this hypothesis, we may
employ a different encoding (e.g., allocate just one bit to the PlayTennis postcondition to indicate
whether the value is Yes or No), alter the genetic operators so that they explicitly avoid constructing
such bit strings, or simply assign a very low fitness to such bit strings.
In some GAS, hypotheses are represented by symbolic descriptions rather than bit strings.
Genetic Operators
The generation of successors in a GA is determined by a set of operators that recombine and
mutate selected members of the current population. These operators correspond to idealized versions
of the genetic operations found in biological evolution. The two most common operators are crossover
and mutation.
The crossover operator produces two new offspring from two parent strings, by copying
selected bits from each parent. The bit at position i in each offspring is copied from the bit at position i
in one of the two parents. The choice of which parent contributes the bit for position i is determined by
an additional string called the crossover mask. To illustrate, consider the single-point crossover
operator at the top of Table Consider the topmost of the two offspring in this case. This offspring takes
its first five bits from the first parent and its remaining six bits from the second parent, because the
crossover mask 11 11 1000000 specifies these choices for each of the bit positions. The second offspring
uses the same crossover mask, but switches the roles of the two parents. Therefore, it contains the bits
that were not used by the first offspring. In single-point crossover, the crossover mask is always
constructed so that it begins with a string containing n contiguous Is, followed by the necessary number
of 0s to complete the string. This results in offspring in which the first n bits are contributed by one
parent and the remaining bits by the second parent. Each time the single-point crossover operator is
applied the crossover point n is chosen at random, and the crossover mask is then created and applied.
103
In two-point crossover, offspring are created by substituting intermediate segments of one parent into
the middle of the second parent string. Put another way, the crossover mask is a string beginning with
no zeros, followed by a contiguous string of nl ones, followed by the necessary number of zeros to
complete the string. Each time the two-point crossover operator is applied, a mask is generated by
randomly choosing the integers no and nl.
Fitness Function and Selection
The fitness function defines the criterion for ranking potential hypotheses and for
probabilistically selecting them for inclusion in the next generation population. If the task is to learn
classification rules, then the fitness function typically has a component that scores the classification
accuracy of the rule over a set of provided training examples. Often other criteria may be included as
well, such as the complexity or generality of the rule. More generally, when the bit-string hypothesis is
interpreted as a complex procedure (e.g., when the bit string represents a collection of if-then rules that
will be chained together to control a robotic device), the fitness function may measure the overall
performance of the resulting procedure rather than performance of individual rules.
In our prototypical GA shown in above Table , the probability that a hypothesis will be selected is given
by the ratio of its fitness to the fitness of other members of the current population as seen in Equation
above . This method is sometimes called fitness proportionate selection, or roulette wheel selection.
Other methods for using fitness to select hypotheses have also been proposed. For example, in
tournament selection, two hypotheses are first chosen at random from the current population. With
some predefined probability p the more fit of these two is then selected, and with probability (1 - p) the
less fit hypothesis is selected. Tournament selection often yields a more diverse population than fitness
proportionate selection. In another method called rank selection, the hypotheses in the current
population are first sorted by fitness. The probability that a hypothesis will be selected is then
proportional to its rank in this sorted list, rather than its fitness.