When expressed in binary form, a number is said to have odd parity if it has an odd number of 1’s. And there is a class of so called odd-parity functions which return “1” or “true” if an
n-bit number is odd, “0” or “false” otherwise. So, the simplest odd-parity function is the identity function or the odd-1-parity function. Another simple and familiar odd-parity function is the XOR function also called odd-2-parity function. We will start our exploration of odd-parity functions from here and then go on finding solutions to more complex functions.
Let’s start then by evolving solutions to the XOR function. In this case, we are going to use only the basic Boolean functions in the function set, that is,
F = {N, A, O} and the linking will be done by AND. This problem is solved by GEP with 100% success rate using small populations of only 30 individuals
(Table 4.19, column 1). The solution below was obtained in the first run of this experiment (the sub-ETs are linked by AND):
| 012345678901234012345678901234 |
|
|
ANOAOOAabaabbbbOOAOAaObababaab |
(4.35) |
As you can see, this solution is far from parsimonious but, thankfully, for this simple problem it is possible to find out the most parsimonious solution. The function below is extremely parsimonious and was obtained using a unigenic system with an
h = 5:
| 01234567890 |
|
|
ANOAObababb |
(4.36) |
The discovery of parsimonious solutions to such basic Boolean functions is extremely important as these functions are frequently used as fundamental building blocks in the construction of more complex functions. As you can see in
Table 4.19, XOR itself was used to evolve solutions to more complex
odd-n-parity functions and, in fact, its inclusion in the function set was responsible for the high success rates observed in these experiments
(Table 4.19, columns 2-5). Note also that, in these experiments, XOR was also used to link the sub-ETs. The inclusion of such solutions in the function set or their use in the linking allows not only a much more efficient evolution but also the discovery of parsimonious solutions to more complex problems. Then, if it were necessary to revert to the basic Boolean functions, one only needs to replace these complex building blocks by their parsimonious representation.
Table 4.19
Parameters for the odd-n-parity problem using the basic GEA.
| |
Odd-2 |
Odd-3 |
Odd-4 |
Odd-5 |
Odd-6 |
| Number
of runs |
100 |
100 |
100 |
100 |
100 |
| Number
of generations |
50 |
50 |
50 |
100 |
200 |
| Population
size |
30 |
10 |
30 |
30 |
30 |
| Number
of fitness cases |
4 |
8 |
16 |
32 |
64 |
| Function
set |
A O N |
A O N
X |
A O N
X |
A O N
X |
(A O N
X)2 |
| Terminal
set |
a b |
a b c |
a b c
d |
a b c
d e |
a b c
d e f |
| Head
length |
7 |
7 |
7 |
7 |
7 |
| Number
of genes |
2 |
3 |
3 |
3 |
3 |
| Linking
function |
A |
X |
X |
X |
X |
| Chromosome
length |
30 |
45 |
45 |
45 |
45 |
| Mutation
rate |
0.044 |
0.044 |
0.044 |
0.044 |
0.044 |
| One-point
recombination rate |
0.3 |
0.3 |
0.3 |
0.3 |
0.3 |
| Two-point
recombination rate |
0.3 |
0.3 |
0.3 |
0.3 |
0.3 |
| Gene
recombination rate |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
| Gene
transposition rate |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
| IS
transposition rate |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
| IS
elements length |
1,2,3 |
1,2,3 |
1,2,3 |
1,2,3 |
1,2,3 |
| RIS
transposition rate |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
| RIS
elements length |
1,2,3 |
1,2,3 |
1,2,3 |
1,2,3 |
1,2,3 |
| Success
rate |
100% |
100% |
98% |
93% |
91% |
In the next section we are going to see another way of including such complex building blocks in the GEP toolkit, namely, through the use of user defined functions.
|