Information Technology Reference
In-Depth Information
size of the evolving solutions. As explained in section 4.3.1, Fitness Functions
with Parsimony Pressure, this can be achieved by introducing a parsimony
term on the fitness function.
Let's see, for instance, what happens when the play tennis problem with
nominal attributes is solved with parsimony pressure. Thus, for the number
of hits fitness function, the fitness will be evaluated by equation (4.21). And
given that, for this problem, maximum raw fitness is equal to 14,
f
max
will be
equal to 14.0028.
Let's now choose a fairly redundant configuration for the head size, for
instance,
h
= 10, and observe how the parsimony pressure manifests itself on
the size of the evolving decision trees. (Except for the head size and the
number of generations, all the other settings used in this experiment remained
exactly as shown in Table 9.2.)
Consider, for instance, the evolutionary history presented below:
TWTabaWHWHabababaaaababaabbaaab-[0] = 10.00093 (17)
OWaObaWHWHabababbaaaabbabaaabab-[7] = 11.00103 (17)
OWaOWHbaWWabababaaaaaaabbaababb-[11] = 13.00121 (17)
OWaOWHbaWbbbabaababbbaabbababab-[14] = 13.00139 (15)
OWaOHHbTWHabaaabbabaaabbbababaa-[39] = 14.00103 (20)
OHaWWHbWTHbaaababbbaabbabbabbab-[78] = 14.00112 (19)
OHaWWaWWHbbabababbbabbbbaaaabab-[107] = 14.00140 (16)
OHaWbaHaHTbbaababbaababbbaabbbb-[108] = 14.00149 (15)
OHaWbabaHaabaaaabbbaaaabaaaaabb-[126] = 14.00215 (8)
As you can see, a perfect solution involving a total of 20 nodes was created
early on in generation 39. Then, by generation 78, a slightly shorter solution
with 19 nodes was created. Then an even more compact solution with just 16
nodes was created in generation 107. Then immediately in the next genera-
tion a slightly shorter solution was discovered using a total of 15 nodes. And
finally, by generation 126 an extremely compact solution with just eight nodes
was created. This is, as a matter of fact, the most compact configuration that
can be achieved to describe the data presented in Table 9.1.
Decision trees with numeric/mixed attributes can also be efficiently pruned
by applying parsimony pressure. Consider again the play tennis problem, but
this time using the data presented in Table 9.3. Again, we will use the same
basic settings presented in Table 9.4, with the difference that here we will
allow for the creation of twice as big decision trees and increase the number
of generations to 1000 to ensure that the most compact solution is indeed
