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 Unigenic System
 

For this analysis, we are going to use the basic Gene Expression Algorithm both with and without random constants. In both cases, though, a single tree structure encoded in a single gene will be evolved.

As it is customary, the parameters used per run are summarized in a table (Table 1). Note that, in these experiments, small population sizes of only 50 individuals were used, incomparably smaller than the 4,000 individuals used by Koza to solve this same problem (indeed, this population size of 50 individuals is kept constant throughout this work in order to allow a more fruitful comparison between the different systems). Also worth pointing out is that, throughout this study and whenever possible, a maximum program size around 50 points was used so that comparisons could be made between all the experiments (to be more precise, for the unigenic systems a head length of 24 gives maximum program size 49, whereas for the multigenic systems with four genes with head length six, maximum program size equals 52). So, for the unigenic systems of this study, chromosomes with a head length h = 24 were chosen, giving maximum program length of 49 (note, however, that the chromosome length in the system with random numerical constants is larger on account of the Dc domain).

Table 1
Settings for the sextic polynomial problem using a unigenic system with (ugGEP-RNC) and without (ugGEP) random numerical constants.

 

ugGEP

ugGEP-RNC
Number of runs 100 100
Number of generations 200 200
Population size 50 50
Chromosome length 49 74
Number of genes 1 1
Head length 24 24
Gene length 49 74
Terminal set a a ?
Function set + - * / + - * /
Mutation rate 0.044 0.044
Inversion rate 0.1 0.1
RIS transposition rate 0.1 0.1
IS transposition rate 0.1 0.1
Two-point recombination rate 0.3 0.3
One-point recombination rate 0.3 0.3
Random constants per gene -- 5
Random constants data type -- Integer
Random constants range -- 0-3
Dc-specific mutation rate -- 0.044
Dc-specific inversion rate -- 0.1
Dc-specific IS transposition rate -- 0.1
Random constants mutation rate -- 0.01
Number of fitness cases 50 50
Selection range 100 100
Precision 0.01 0.01
Success rate 26% 4%


As shown in Table 1, the probability of success for this problem using the unigenic system without random numerical constants is considerably higher than the success rate obtained with the ugGEP-RNC algorithm (26% as opposed to just 4%), which, again, shows that, for this kind of simple, modular problem, evolutionary algorithms fare far better if the numerical constants are created from scratch by the algorithm itself through the evolution of simple mathematical expressions. This is not to say that, for complex real-world problems of just one variable or really complex problems of higher dimensions, random numerical constants are not important; indeed, most of the time, they play a crucial role in the discovery of good solutions.

Let’s take a look at the structure of the first perfect solution found using the unigenic system without the facility for the manipulation of random numerical constants:

0123456789012345678901234567890123456789012345678  

*++a/****+-a--*/aa*/*---aaaaaaaaaaaaaaaaaaaaaaaaa

(16)

As its expression shows, it contains a relatively big neutral region involving a total of nine nodes and two smaller ones involving just three nodes each. It is also worth pointing out the creation of the numerical constant 1 through the simple arithmetic operation a/a.

It is also interesting to take a look at the structure of the first perfect solution found using the unigenic system with the facility for the manipulation of random numerical constants:

01234567890123456789012345678901234567890123456789012345678901234567890123

 

*a+*aa+*a*/aa-a*++-?aa*a?aaa???aaaaaa?a?a?a???a?a0210121021334303442030040

 

 

 

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

(17)

As its expression reveals, it is a fairly compact solution with no obvious neutral regions that makes good use of the random numerical constant 1 to evolve a perfect solution.

 

Home | Contents | Previous | Next