Information Technology Reference
In-Depth Information
parsimonious solution to the problem at hand, any increase in gene length can
lead to the evolution of perfect, less parsimonious solutions in which both
neutral blocks and noncoding regions might appear.
For problems exactly solved by the algorithm, the most compact organiza-
tion can be found in most cases. As shown in Figure 12.11, the test function
(4.1) can be compactly encoded using a head length of six (corresponding to
g
= 13). One such solution composed of 13 nodes is shown below:
0123456789012
*++*//aaaaaaa
Note that, in this case, all the elements of the gene are expressed and there-
fore no noncoding regions exist.
The test sequence (5.14), however, requires more nodes for its correct and
parsimonious expression using the chosen set of functions. As shown in Fig-
ure 12.11, an
h
= 14 (corresponding to
g
= 29) is the minimum head length
necessary to solve this problem. The two perfect, parsimonious solutions
shown below are expressed using, respectively, 25 and 23 nodes:
01234567890123456789012345678
+*aa+*++**++/+aaaaaaaaaaaaaaa
01234567890123456789012345678
**a+a*a++/+/+/aaaaaaaaaaaaaaa
Note that the first gene has a small noncoding region composed of four ele-
ments, whereas the second has a larger noncoding region with six elements.
As Figure 12.11 emphasizes, the most compact organizations are not the
most efficient. For instance, in the function finding problem, the success rate
obtained for the most compact organization (
g
= 13) is only 2% whereas the
highest success rate, obtained for a chromosome length of 37, is 76%. In the
sequence induction problem, an identical behavior is observed with a suc-
cess rate of only 1% for the most compact organization (
g
= 29) and 43% for
the best chromosome length (
g
= 79). Therefore, a certain amount of redun-
dancy is fundamental for evolution to occur efficiently. Indeed, in both ex-
amples, a plateau was found where the system evolves best. Note also that
highly redundant systems adapt, nonetheless, considerably better than highly
compact systems, showing that evolutionary systems can cope fairly well
with genetic redundancy. For instance, in the function finding experiment,
the most redundant system with a gene length of 169, has a success rate of
32%, considerably higher than the 2% obtained for the most compact organi-
