机器学习

A genetic algorithm can be viewed as a general optimization method that searches a large space
of candidate objects seeking one that performs best according to the fitness function. Although not
guaranteed to find an optimal object, GAS often succeed in finding an object with high fitness. GAS have
been applied to a number of optimization problems outside machine learning, including problems such
as circuit layout and job-shop scheduling. Within machine learning, they have been applied both to
function-approximation problems and to tasks such as choosing the network topology for artificial
neural network learning systems.
To illustrate the use of GAS for concept learning, we briefly summarize the GABIL system
described by DeJong et al. (1993). GABIL uses a GA to learn boolean concepts represented by a
disjunctive set of propositional rules. In experiments over several concept learning problems, GABIL was
found to be roughly comparable in generalization accuracy to other learning algorithms such as the
decision tree learning algorithm C4.5 and the rule learning system AQ14. The learning tasks in this study
included both artificial learning tasks designed to explore the systems' generalization accuracy and the
real world problem of breast cancer diagnosis.
The specific instantiation of the GA algorithm in GABIL can be summarized as follows:
Representation. Each hypothesis in GABIL corresponds to a disjunctive set of propositional rules,
encoded as described in Section 9.2.1. In particular, the hypothesis space of rule preconditions consists
of a conjunction of constraints on a fixed set of attributes, as described in that earlier section. To
represent a set of rules, the bit-string representations of individual rules are concatenated. To illustrate,
consider a hypothesis space in which rule preconditions are conjunctions of constraints over two
Boolean attributes, a1 and a2.The rule postcondition is described by a single bit that indicates the
predicted value of the target attribute c. Thus, the hypothesis consisting of the two rules
IF al=T^a2=F THEN c=T; IF a2=T THEN c=F
would be represented by the string
a1 a2 c
10 01 1
a1 a2 c
11 01 0
Note the length of the bit string grows with the number of rules in the hypothesis. This variable bit-
string length requires a slight modification to the crossover operator, as described below.
Genetic operators. GABIL uses the standard mutation operator of above Table in which a single
bit is chosen at random and replaced by its complement. The crossover operator that it uses is a fairly
standard extension to the two-point crossover operator described in Table 9.2. In particular, to
accommodate the variable-length bit strings that encode rule sets, and to constrain the system so that
crossover occurs only between like sections of the bit strings that encode rules, the following approach
is taken. To perform a crossover operation on two parents, two crossover points are first chosen at
random in the first parent string. Let dl (dz) denote the distance from the leftmost (rightmost) of these
two crossover points to the rule boundary immediately to its left. The crossover points in the second
parent are now randomly chosen, subject to the constraint that they must have the same dl and d2
value. For example, if the two parent strings are
and the crossover points chosen for the first parent are the points following bit positions 1 and 8,
where "[" and "1" indicate crossover points, then dl = 1 and dz = 3. Hence the allowed pairs of crossover
points for the second parent include the pairs of bit positions (1,3), (1,8), and (6,8). If the pair (1,3)
happens to be chosen,
then the two resulting offspring will be
As this example illustrates, this crossover operation enables offspring to contain a different number of
rules than their parents, while assuring that all bit strings generated in this fashion represent well-
defined rule sets.
Fitness function. The fitness of each hypothesized rule set is based on its classification accuracy over
the training data. In particular, the function used to measure fitness is
where correct is the percent of all training examples correctly classified by hypothesis h.
In experiments comparing the behavior of GABIL to decision tree learning algorithms such as
C4.5 and ID5R, and to the rule learning algorithm AQ14report roughly comparable performance among
these systems, tested on a variety of learning problems. For example, over a set of 12 synthetic
problems, GABIL achieved an average generalization accuracy of 92.1 %, whereas the performance of
the other systems ranged from 91.2 % to 96.6 %.
Extensions
106
In one set of experiments they explored the addition of two new genetic operators that were
motivated by the generalization operators common in many symbolic learning methods. The first of
these operators, AddAlternative, generalizes the constraint on a specific attribute by changing a 0 to a
1 in the substring corresponding to the attribute. For example, if the constraint on an attribute is
represented by the string 10010, this operator might change it to 101 10. This operator was applied
with probability .O1 to selected members of the population on each generation. The second operator,
Dropcondition performs a more drastic generalization step, by replacing all bits for a particular attribute
by a 1. This operator corresponds to generalizing the rule by completely dropping the constraint on the
attribute, and was applied on each generation with probability .60. The authors report this revised
system achieved an average performance of 95.2% over the above set of synthetic learning tasks,
compared to 92.1% for the basic GA algorithm.
In the above experiment, the two new operators were applied with the same probability to each
hypothesis in the population on each generation. In a second experiment, the bit-string representation
for hypotheses was extended to include two bits that determine which of these operators may be
applied to the hypothesis. In this extended representation, the bit string for a typical rule set hypothesis
would be
where the final two bits indicate in this case that the AddAlternative operator may be applied to this bit
string, but that the Dropcondition operator may not. These two new bits define part of the search
strategy used by the GA and are themselves altered and evolved using the same crossover and mutation
operators that operate on other bits in the string. While the authors report mixed results with this
approach (i.e., improved performance on some problems, decreased performance on others), it
provides an interesting illustration of how GAS might in principle be used to evolve their own
hypothesis search methods.