GEP Book

  Home
  News
  Author
  Q&A
  Tutorials
  Downloads
  GEP Biblio
  Contacts

  Visit Gepsoft

 

C. FERREIRA 9th Online World Conference on Soft Computing in Industrial Applications, 2004

Designing Neural Networks Using Gene Expression Programming

Neural network for the exclusive-or problem
 
The XOR is a simple Boolean function of two activities and, therefore, can be easily solved using linearly encoded neural networks. Its rule table is shown in Table 1.

Table 1
Lookup table for the exclusive-or function.

The functions used to solve this problem have connectivities 2, 3, and 4, and are represented, respectively, by "D", "T", and "Q", thus the function set F = {D, T, Q}; the terminal set T = {a, b}; and the set of weights W = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} with values randomly chosen from the interval [-2, 2]. For the experiment summarized in the first column of Table 2, an h = 4 was chosen and, therefore, hundreds of different correct solutions to the XOR function were found. Most of them are more complicated than the conventional solution (2.1) shown in section 2 which uses seven nodes; others have the same degree of complexity evaluated in terms of total nodes; but surprisingly others are more parsimonious than the mentioned conventional solution for the XOR function as will next be shown.

Table 2
Parameters for the exclusive-or problem.

   Redundant System Compact System
Number of runs 100 100
Number of generations 50 50
Population size 30 30
Number of fitness cases 4 4
Function set D T Q D T Q
Terminal set a b a b
Weights array length 10 10
Weights range [-2, 2] [-2, 2]
Head length 4 2
Number of genes 1 1
Chromosome length 33 17
Mutation rate 0.061 0.118
One-point recombination rate 0.7 0.7
IS transposition rate 0.1 --
IS elements length 1 --
RIS transposition rate 0.1 --
RIS elements length 1 --
Dw-specific transposition rate 0.1 0.1
Dw-specific IS elements length 2,3,5 2,3,5
Success rate 77% 30%


The first solution found in run 0 of the experiment summarized in the first column of Table 2 is shown below:

012345678901234567890123456789012
TQaTaaababbbabaaa6085977238275036

W = {1.175, 0.315, -0.738, 1.694, -1.215, 1.956, -0.342, 1.088, -1.694, 1.288}

Its expression is shown in Figure 4. It is a rather complicated solution to the XOR function, but remember that evolutionary algorithms thrive in slightly redundant architectures (Ferreira 2002) and, as shown in Table 2, the success rate for this problem using this non-compact chromosomal organization is higher (77%) than the obtained with more compact organizations with h = 2 (30%).


Figure 4. A perfect, slightly complicated solution to the exclusive-or problem evolved with GEP neural networks. a) Its chromosome and respective weights. b) The fully expressed neural network encoded in the chromosome.

However, GEP can be useful to search for parsimonious solutions, and a very interesting parsimonious solution to the XOR function was found in another experiment. The parameters used per run in this experiment are summarized on the second column of Table 2. Note that the compact organization with h = 2 was chosen in order to search for solutions more parsimonious than the canonical solution to the XOR function. One such solution is shown below:

01234567890123456
TDbabaabb88399837

W = {0.713, -0.774, -0.221, 0.773, -0.789, 1.792, -1.77, 0.443, -1.924, 1.161}

which is a perfect, extremely parsimonious solution to the XOR problem. Its full expression is shown in Figure 5. Indeed, several perfect solutions with this kind of structure were found in this experiment.


Figure 5. A perfect, extremely parsimonious solution to the exclusive-or problem discovered with GEP designed neural networks. a) Its chromosome and corresponding array of weights. b) The fully expressed neural network encoded in the chromosome.

Home | Contents | Previous | Next