GEP chromosomes are usually composed of more than one gene of equal length. For each problem or run, the number of genes, as well as the length of the head, are a priori chosen. Each gene codes for a sub-ET and the sub-ETs interact with one another forming a more complex multi-subunit ET.
Consider, for example, the following chromosome with length 45, composed of three genes (the tails are shown in
blue):
|
012345678901234012345678901234012345678901234 |
|
|
Q/*b+Qababaabaa-abQ/*+bababbab**-*bb/babaaaab |
(2.8) |
It has three ORFs, and each ORF codes for a sub-ET (Figure
3). Position 0 marks the start of each gene. The end of each ORF, though, is only evident upon construction of the respective sub-ET. As shown in
Figure 3, the first ORF ends at position 8 (sub-ET1); the second ORF ends at position 2 (sub-ET2); and the last ORF ends at position 10 (sub-ET3). Thus, GEP chromosomes contain several ORFs, each ORF coding for a structurally and functionally unique sub-ET. Depending on the problem at hand, these sub-ETs may be selected individually according to their respective fitness (for example, in problems with multiple outputs), or they may form a more complex, multi-subunit ET where individual sub-ETs interact with one another by a particular kind of posttranslational interaction or linking. For instance, when the sub-ETs are algebraic or Boolean expressions, any algebraic or Boolean function with more than one argument can be used to link the sub-ETs in a final, multi-subunit ET. The functions most chosen are addition or multiplication for algebraic sub-ETs, and OR or IF for Boolean
sub-ETs.
Fig. 3. Expression of GEP genes as sub-ETs. a) A three-genic chromosome with the tails shown in bold. Position 0 marks the start of each gene.
b) The sub-ETs codified by each gene.
Figure 4 illustrates the linking of three sub-ETs by addition.
Fig. 4. Expression of multigenic chromosomes as multi-subunit expression trees.
a) A three-genic chromosome with the tails shown in bold. b) The sub-ETs codified by each gene.
c) The result of posttranslational linking with addition. The linking functions are shown in gray.
Note that the final ET could be linearly encoded as the following K-expression:
|
012345678901234567890123456789012 |
|
|
++*+-Q*bQ-ba*-*/b/aba*ba/aa+baaab |
(2.9) |
However, to evolve solutions to complex problems, it is more effective the use of multigenic chromosomes, for they permit the modular construction of complex, hierarchical structures, where each gene codes for a small building block. These small building blocks are separated from each other, and thus can evolve independently. Not surprisingly, these multigenic systems are much more efficient than unigenic ones. Indeed, GEP is effectively a hierarchical invention system capable of discovering simple blocks and using them to form more complex structures.
|