The Architectures of GeneXproTools Learning Algorithms

Multigenic Chromosomes and Linking Functions
 
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 GeneXproTools 4.0 they interact through special functions, the so called linking functions: addition, subtraction, multiplication, and division for mathematical models and And, Or, Nand, Nor, Xor, Nxor, Less Than, Greater Than, Less Or Equal, and Greater Or Equal for Logic Synthesis problems.

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.

Home | Contents | Previous  | Next