The chromosomes of gene expression programming are usually composed of more than one
gene of equal length. For each problem or run, the number of genes, as well as the
size of the head, are a priori chosen. Each gene codes for a sub-expression
tree (sub-ET) and the sub-ETs interact with one another forming a more complex multi-subunit expression tree.
Consider, for example, the following chromosome with length 39, composed of three genes, each with length
13 (the
heads are shown in blue):
012345678901201234567890120123456789012
QaQ+-Qbbaaaba+Q+ab+abababa*-**b+aabbaba
It has obviously three open reading frames
(ORFs), and each ORF codes for a sub-ET:
The start of each ORF is always given by position 0; the end of each ORF, though, is only evident upon construction of the corresponding sub-ET. As shown in the
Figure above, the first ORF ends at position 1; the second ORF ends at position
7; and the last ORF ends at position 10. Thus, GEP chromosomes contain several ORFs of different sizes, each ORF coding for a structurally and functionally unique sub-ET.
Obviously, these sub-ETs or sub-programs must interact with one another. And in APS 3.0 they interact
through special functions, the so called linking functions: addition, subtraction, multiplication, and division.
The linking by addition of all the three sub-ETs shown in the Figure above is illustrated
below (the linking functions are shown in gray):
Note that the final program represented in the Figure above could be linearly encoded as the following
K-expression:
01234567890123456789012
++*Q+-*aQ+*b+aab+abbaab
However, the use of multigenic chromosomes is more appropriate to evolve solutions to complex problems, for they permit the modular construction of complex, hierarchical structures, where each gene codes for a smaller and simpler building block. These smaller building blocks are separated from each other, and thus can evolve independently and may, therefore, give rise to new useful building blocks.
|