Buy the Book

  GEP Biblio

  Visit Gepsoft


© C. FERREIRA, 2002 (Terms of Use) ISBN: 9729589054

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

Finding solutions to odd-parity functions with the basic gene expression algorithm
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):




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:




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.

Home | Contents | Previous | Next