GEP Book

  Home
  News
  Author
  Q&A
  Tutorials
  Downloads
  GEP Biblio
  Contacts

  Visit Gepsoft

 

C. FERREIRA In N. Nedjah, L. de M. Mourelle, A. Abraham, eds., Genetic Systems Programming: Theory and Experiences, Studies in Computational Intelligence, Vol. 13, pp. 21-56, Springer-Verlag, 2006.

Automatically Defined Functions in Gene Expression Programming

The Multicellular System
 

For the multicellular system without random numerical constants, both the parameters and performance are shown in Table 5.

Table 5
Settings and performance for the sextic polynomial problem using a multicellular system encoding 1, 2, 3, and 4 ADFs.

  1 ADF 2 ADFs 3 ADFs 4 ADFs
Number of runs 100 100 100 100
Number of generations 200 200 200 200
Population size 50 50 50 50
Chromosome length 40 53 66 79
Number of genes/ADFs 1 2 3 4
Head length 6 6 6 6
Gene length 13 13 13 13
Function set of ADFs + - * / + - * / + - * / + - * /
Terminal set a a a a
Number of homeotic genes/cells 3 3 3 3
Head length of homeotic genes 4 4 4 4
Length of homeotic genes 9 9 9 9
Function set of homeotic genes + - * / + - * / + - * / + - * /
Terminal set of homeotic genes ADF 0 ADFs 0-1 ADFs 0-2 ADFs 0-3
Mutation rate 0.044 0.044 0.044 0.044
Inversion rate 0.1 0.1 0.1 0.1
RIS transposition rate 0.1 0.1 0.1 0.1
IS transposition rate 0.1 0.1 0.1 0.1
Two-point recombination rate 0.3 0.3 0.3 0.3
One-point recombination rate 0.3 0.3 0.3 0.3
Gene recombination rate 0.3 0.3 0.3 0.3
Gene transposition rate -- 0.1 0.1 0.1
Mutation rate in homeotic genes 0.044 0.044 0.044 0.044
Inversion rate in homeotic genes 0.1 0.1 0.1 0.1
RIS transposition rate in homeotic genes 0.1 0.1 0.1 0.1
IS transposition rate in homeotic genes 0.1 0.1 0.1 0.1
Number of fitness cases 50 50 50 50
Selection range 100 100 100 100
Precision 0.01 0.01 0.01 0.01
Success rate 98% 96% 95% 90%


As you can see, these multicellular systems with Automatically Defined Functions perform extremely well, even better than the multigenic system with static linking (see Table 2). And they are very interesting because they can also be used to solve problems with multiple outputs, where each cell is engaged in the identification of one class or output. Here, however, we are using a multicellular system to solve a problem with just one output, which means that all the cells are trying to find the same kind of solution and, therefore, for each individual, the fitness is determined by the best cell. Obviously, the greater the number of cells the higher the probability of evolving the perfect solution or cell. But there is one caveat though: one cannot go on increasing the number of cells indefinitely because it takes time and resources to express all of them. The use of three cells per individual seems a good compromise, and we are going to use just that in all the experiments of this section.

Let’s take a look at the structure of the first perfect solution found using the multicellular system encoding just one ADF (which cell is best is indicated after the coma):

0123456789012012345678012345678012345678

 

-*a*aaaaaaaaa-0-+000000***00000-**+00000,2

(24)

As its expression shows, the best main program invokes the ADF encoded in the conventional gene five times. Note, however, that this perfect solution is far from parsimonious and could indeed be simplified to (ADF)2.

It is also interesting to take a look at what the other cells are doing. For instance, Cell0 encodes zero and Cell1 encodes (ADF)4, both a far cry from the perfect solution.

Let’s also analyze the structure of a program with more than one ADF, the individual below with four ADFs and three cells (the best cell is indicated after the coma):

0123456789012

 

**-/aaaaaaaaa

 

/aaaa/aaaaaaa

 

*-a*/aaaaaaaa

 

/-***/aaaaaaa

 

*-*222301

 

*+2021323

 

-+0020321,1

(25)

As its expression shows, the best main program invokes two different ADFs (ADF0 and ADF2), but since ADF0 encodes zero, the best cell could be simplified to (ADF2)2, which is again a perfect solution built with just one kind of building block (a3-a). It is also worth noticing that two of the ADFs (ADF0 and ADF3) and one of the cells (Cell0) encode zero, and the numerical constant 1 is also encoded by ADF1; they are all good examples of the kind of neutral region that permeates all these solutions.

Let’s now analyze the behavior of the multicellular system when random numerical constants are also incorporated in the Automatically Defined Functions.

For that purpose a similar set of experiments were done, using also 1, 2, 3, and 4 ADFs (Table 6). And as expected, a considerable decrease in performance was observed comparatively to the performance obtained in the multicellular system without random numerical constants (see Table 5). Notwithstanding, ADFs with random numerical constants perform quite well despite the additional complexity, and they may prove valuable in problems where random numerical constants are crucial to the discovery of good solutions.

Table 6
Settings and performance for the sextic polynomial problem using a multicellular system encoding 1, 2, 3, and 4 ADFs with random numerical constants.

  1 ADF 2 ADFs 3 ADFs 4 ADFs
Number of runs 100 100 100 100
Number of generations 200 200 200 200
Population size 50 50 50 50
Chromosome length 29 67 87 107
Number of genes/ADFs 1 2 3 4
Head length 6 6 6 6
Gene length 20 20 20 20
Function set of ADFs + - * / + - * / + - * / + - * /
Terminal set a ? a ? a ? a ?
Number of homeotic genes/cells 1 3 3 3
Head length of homeotic genes 4 4 4 4
Length of homeotic genes 9 9 9 9
Function set of homeotic genes + - * / + - * / + - * / + - * /
Terminal set of homeotic genes ADF 0 ADFs 0-1 ADFs 0-2 ADFs 0-3
Mutation rate 0.044 0.044 0.044 0.044
Inversion rate 0.1 0.1 0.1 0.1
RIS transposition rate 0.1 0.1 0.1 0.1
IS transposition rate 0.1 0.1 0.1 0.1
Two-point recombination rate 0.3 0.3 0.3 0.3
One-point recombination rate 0.3 0.3 0.3 0.3
Gene recombination rate 0.3 0.3 0.3 0.3
Gene transposition rate -- 0.1 0.1 0.1
Random constants per gene 5 5 5 5
Random constants data type Integer Integer Integer Integer
Random constants range 0-3 0-3 0-3 0-3
Dc-specific mutation rate 0.044 0.044 0.044 0.044
Dc-specific inversion rate 0.1 0.1 0.1 0.1
Dc-specific IS transposition rate 0.1 0.1 0.1 0.1
Random constants mutation rate 0.01 0.01 0.01 0.01
Mutation rate in homeotic genes 0.044 0.044 0.044 0.044
Inversion rate in homeotic genes 0.1 0.1 0.1 0.1
RIS transposition rate in homeotic genes 0.1 0.1 0.1 0.1
IS transposition rate in homeotic genes 0.1 0.1 0.1 0.1
Number of fitness cases 50 50 50 50
Selection range 100 100 100 100
Precision 0.01 0.01 0.01 0.01
Success rate 79% 60% 58% 50%


Let’s take a look at the structure of a perfect solution found using the multicellular system encoding just one ADF with random constants (the best cell is indicated after the coma):

01234567890123456789012345678012345678012345678

 

-***a?aaa???a4000424+/0+00000*0*/00000-+*-00000,1

 
   

A = {3, 1, 1, 1, 1}

(26)

As its expression shows, the main program encoded in Cell1 is far from parsimonious, but it encodes nonetheless a perfect solution to the sextic polynomial (14). The only available ADF is called four times from the main program, but in essence it could have been called just twice as it can be simplified to (ADF)2.

Let’s now analyze the structure of a program with more than one ADF, the individual below with four ADFs and three cells (the best cell is indicated after the coma):

01234567890123456789

 

-a*-*a?aa????2322013

 

?-*//aaa?aa?a2412442

 

*a+a*aa?aaaaa4024010

 

*-a?a?aaa????3224232

 
   

A0 = {0, 0, 0, 1, 0}

 

A1 = {2, 0, 0, 2, 2}

 

A2 = {2, 1, 3, 0, 0}

 

A3 = {2, 1, 3, 0, 0}

 
   

012345678012345678012345678

 

*2*/00213/-+*03022233201102,0

(27)

As its expression shows, the best main program invokes two different ADFs (ADF0 and ADF2), but the calls to ADF2 cancel themselves out, and the main program is reduced to (ADF0)2, which, of course is a perfect solution to the problem at hand.

Home | Contents | Previous | Next