Home
News
Author
Q&A
Tutorials
GEP Biblio
Contacts

Visit Gepsoft

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

We have seen that translation results in the formation of sub-ETs with different complexity, but the complete expression of the genetic information requires the interaction of these sub-ETs with one another. Only then the individual will be fully expressed. A simple way of solving this problem consists in the linking of sub-ETs by a particular function. This process is similar to the assemblage of different protein subunits in a multi-subunit protein.

When the sub-ETs are algebraic expressions or Boolean expressions, any mathematical or Boolean function with more than one argument can be used to link the sub-ETs in a final, multi-subunit ET. The most frequently chosen functions to link the sub-ETs are addition or multiplication for algebraic sub-ETs, and OR, AND or IF for Boolean sub-ETs.

Consider the following chromosome, encoding three algebraic sub-ETs (the tails are shown in blue):

 012345678901201234567890120123456789012 QaQ+-Qbbaaaba+Q+ab+abababa*-**b+aabbaba (2.21)

The linking of its sub-ETs by addition is illustrated in Figure 2.9. Note that the multi-subunit ET encoded in chromosome (2.21) could be linearly encoded as the following K-expression:

 01234567890123456789012 ++*Q+-*aQ+*b+aab+abbaab (2.22)

However, the use of multigenic chromosomes is more appropriate to evolve solutions to complex problems, for they permit the modular construction of more complex, hierarchical structures, where each gene codes for a small building block (see chapter 7 for a discussion). These small building blocks are separated from each other and, therefore, can evolve with a certain degree of independence.

Figure 2.9. Expression of multigenic chromosomes encoding algebraic expressions 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.

Consider another chromosome, this time encoding three Boolean sub-ETs (the tails are shown in blue):

 012345678901234501234567890123450123456789012345 IOaIAcbaaacaacacAOcaIccabcbccbacIONAAbbbbacbcbbc (2.23)

The linking of its sub-ETs by IF is illustrated in Figure 2.10.

Figure 2.10. Expression of multigenic chromosomes encoding Boolean expressions 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 IF. The linking function is shown in gray.

Note again that the multi-subunit ET encoded in chromosome (2.23) could be linearized, forming the following K-expression:

 0123456789012345678901234567890 IIAIOaIOcONAAcbaaaIAbbbbacccaac (2.24)

Figure 2.11 shows another example of posttranslational modification, where the sub-ETs are of the simplest kind (one-element sub-ETs). In this case, nine one-element sub-ETs are linked three by three with the IF function, forming three new clusters which are, in their turn, also linked three by three with another IF function, forming the final multi-subunit ET. This kind of chromosomal architecture can be used to find solutions to complex Boolean problems.

Figure 2.11. Expression of multigenic chromosomes composed of one-element genes as expression trees. a) A nine-genic chromosome. b) The one-element sub-ETs codified by each gene. c) A fully expressed individual after linking with IF. The linking functions are shown in gray.

Note again that the individual of Figure 2.11 could be converted into the following K-expression:

 0123456789012 IIII2bba42a31 (2.25)

In summary, to express fully a chromosome, the information concerning the kind of interaction between the sub-ETs must also be provided. Therefore, for each problem, the type of linking function or type of interaction between sub-ETs is chosen a priori. We can start with addition for algebraic expressions or OR for Boolean problems but, in some cases, another linking function might be more appropriate (like multiplication or IF, for instance). The idea, of course, is to find a good solution, and different linking functions can be used to explore different recesses of the fitness landscape, increasing the odds of finding Mount Everest. Obviously, the basic gene expression algorithm can be easily modified to enable the evolution of the linking functions. An elegant and interesting way of solving this problem consists in the creation of homeotic genes encoding a developmental program (see next section).

In another kind of posttranslational interaction, the sub-ETs representing the coordinates of a point (for example, a city in the traveling salesperson problem) are linked by the distance between them. In other cases, the products of different multigene families are spatially organized and linked together, forming a complex network of interactions.

And finally, the full expression of certain chromosomes requires the sequential execution of small plans, where the first sub-ET does a little work, the second does a little more, and so forth. In this case, the final plan consists in the orderly action of all sub-plans.

These are only a few examples of interactions between sub-ETs, but other can be easily implemented to solve different problems.

Home | Contents | Previous | Next