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.
|