 |
jGE Experiments - Proof of Concept
jGE "Proof of Concept" Experiments and Results
Experiments by Michael O’Neill and Conor Ryan show that Grammatical Evolution is able to solve Symbolic Regression, Trigonometric Identity, and Symbolic Integration Problems. The adoption of the Steady State approach (O’Neill and Ryan) improved dramatically the performance of the Grammatical Evolution algorithm, making it as efficient in the mentioned problems types as the Genetic Programming algorithm. Also, O’Neill demonstrated the generation of multi-line code in the classical Santa Fe Ant Trail problem. Indeed, the last experiment showed that Grammatical Evolution outperforms Genetic Programming in this specific problem when GP does not use the solution length fitness measure.
The following “proof-of-concept” experiments (except the Hamming Distance experiments) with the jGE v0.1 are based on the Grammatical Evolution experiments which have been performed by Michael O’Neill and Conor Ryan. The objective of these experiments is to demonstrate the applicability and effectiveness of the jGE v0.1 library for the execution of Evolutionary Algorithms (mainly Grammatical Evolution algorithm) experiments.
A. Hamming Distance Experiments
Hamming Distance problem involves the finding of a given binary string.
The target string is: 111000111000101010101010101010.
For this problem Grammatical Evolution, Standard GA, and Steady-State GA are compared.
A.1 Hamming Distance Tableau for GE (O’Neill Style)
| Objective: |
Find the target binary string |
| Terminal Operands: |
0 and 1 |
| Terminal Operators: |
none |
| Fitness cases: |
The target string |
| Raw Fitness: |
Target String Length – Hamming Distance |
| Standardised Fitness: |
Same as raw fitness. |
| Wrapper: |
None |
| Parameters: |
Population Size (M) = 50,
Maximum Generations (G) = 100,
Prob. Mutation (Pm) = 0.01,
Prob. Crossover (Pc) = 0.9,
Prob. Duplication (Pd) = 0.01,
Prob. Pruning (Pp) = 0.01,
Selection Mechanism = Steady State GA with Generation Gap (G) = 0.9
Codon Size = 8 |
A.2 BNF Grammar
<phenotype> ::= <binary><binary><binary><binary><binary><binary><binary><binary><binary>
<binary><binary><binary><binary><binary><binary><binary><binary><binary>
<binary><binary><binary><binary><binary><binary><binary><binary><binary>
<binary><binary><binary>
<binary> ::= 0|1
A.3 Results
| |
Standard GA |
Steady-State GA |
Grammatical Evolution |
| Run |
Generation |
Raw Fitness |
Generations |
Raw Fitness |
Generations |
Raw Fitness |
| 1 |
100 |
27 |
43 |
30 |
100 |
26 |
| 2 |
100 |
2 |
30 |
30 |
39 |
30 |
| 3 |
100 |
28 |
41 |
30 |
32 |
30 |
| 4 |
100 |
2 |
40 |
30 |
100 |
26 |
| 5 |
100 |
26 |
19 |
30 |
100 |
26 |
| 6 |
100 |
26 |
37 |
30 |
4 |
30 |
| 7 |
100 |
27 |
24 |
30 |
46 |
30 |
| 8 |
100 |
27 |
33 |
30 |
48 |
30 |
| 9 |
100 |
29 |
27 |
30 |
100 |
26 |
| 10 |
64 |
30 |
26 |
30 |
100 |
26 |
| Average |
96.4 |
22.4 |
32 |
30 |
66.9 |
28 |
B. Symbolic Regression Experiments
Symbolic Regression problems are problems of finding some mathematical expression in symbolic form that matches a given set of input and output pairs.
The particular function examined is f(x) = x4 + x3 + x2 + x
B.1 Symbolic Regression Tableau for GE (O"Neill-style)
| Objective: |
Find a function of one independent variable and one dependent variable, in symbolic form that fits a given sample of 20 (xi, yi) data points, where the target function is the quadratic polynomial x4 + x3 + x2 + x |
| Terminal Operands: |
x (the independent variable), the constant 1.0 |
| Terminal Operators: |
The binary operators +, -, /, *, and -
The unary operators Math.sin, Math.cos, and Math.log |
| Fitness cases: |
The given sample of the pairs (xi, yi) of 20 data points in the interval [-1, +1].
The input data points (xi) are randomly created and their corresponding output points (yi) are automatically created by the expression x4 + x3 + x2 + x |
| Raw Fitness: |
The sum, of the absolute values of errors taken over the fitness cases (xi, yi).
With the above Raw Fitness the best individuals have lower values.
For this reason a kind of Adjusted Fitness is used and assigned to each individual.
Adjusted Fitness of an individual i is typically defined as following:
Fa(i) = 1 / (1 + Fs(i)) where Fs the Standardised Fitness of i.
In this case the Adjusted Fitness of an individual i is calculated as following:
Fa(i) = 1 / (1 + Fr(i)) where Fr the Raw Fitness of i.
The fitness value varies from 0 to 1 and Invalid individuals will have Raw Fitness Value 0. |
| Standardised Fitness: |
Same as raw fitness. |
| Wrapper: |
Standard productions to generate a Java Class with a main() method which prints the fitness values in the standard output |
| Parameters: |
Population Size (M) = 500,
Maximum Generations (G) = 50,
Prob. Mutation (Pm) = 0.01,
Prob. Crossover (Pc) = 0.9,
Prob. Duplication (Pd) = 0.01,
Prob. Pruning (Pp) = 0.01,
Selection Mechanism = Steady State GA with Generation Gap (G) = 0.9
Codon Size = 8 |
B.2 BNF Grammar (A)
<expr> ::= <expr> <op> <expr> | ( <expr> <op> <expr> ) | <pre-op> ( <expr> ) | <var>
<op> ::= + | - | / | *
<pre-op> ::= Math.sin | Math.cos | Math.log
<var> ::= x | 1.0
B.3 Symbolic Regression Results (A)
| Run |
Generations |
Phenotype |
Raw Fitness |
| 1 |
50 |
( ( 1.0 + x ) * x ) / Math.sin ( Math.cos ( x ) ) |
0.4694745127276528 |
| 2 |
50 |
( 1.0 + x ) * Math.sin ( x / Math.sin ( Math.cos ( ( Math.log ( 1.0 ) + x ) - x * Math.log ( Math.cos ( Math.log ( Math.sin ( Math.cos ( 1.0 ) ) ) ) ) ) ) ) |
0.6421964929997449 |
| 3 |
50 |
x * x + ( Math.sin ( x ) + x ) + x * Math.sin ( x ) |
0.2013364798843769 |
| 4 |
50 |
x + ( 1.0 * ( ( x * x ) * ( x + Math.sin ( 1.0 ) + 1.0 ) ) ) |
0.35628132431978915 |
| 5 |
50 |
( x * ( 1.0 + ( x + x * ( x * 1.0 ) + x ) ) ) |
0.27187284673050927 |
| 6 |
50 |
x * ( 1.0 + ( Math.sin ( x ) + x + Math.cos ( 1.0 ) ) ) |
0.23027579709471763 |
| 7 |
50 |
( x * ( x + ( 1.0 / Math.sin ( 1.0 ) ) ) ) |
0.20312605083167595 |
| 8 |
50 |
1.0 + x - Math.cos ( ( x + Math.cos ( x - 1.0 ) ) ) / 1.0 |
0.12454074453273598 |
| 9 |
50 |
( x / 1.0 * ( x + ( 1.0 + ( Math.cos ( 1.0 ) + x ) * x * 1.0 ) ) ) |
0.36138848058931 |
| 10 |
50 |
1.0 + Math.sin ( x ) + Math.sin ( x - Math.cos ( x ) + Math.sin ( Math.sin ( x - Math.cos ( x ) * 1.0 ) ) ) |
0.16294511118210622 |
B.4 BNF Grammar (B)
<expr> ::= <expr><op><expr>|<var>
<op> ::= + | - | / | *
<var> ::= x
B.5 Symbolic Regression Results (B)
| Run |
Generations |
Phenotype |
Raw Fitness |
| 1 |
50 |
x + x * x |
0.28564566880148 |
| 2 |
50 |
x * x + x * x * x + x |
0.2551146843044831 |
| 3 |
40 |
x * x * x + x * x * x / x * x * x / x * x / x * x * x / x + x * x + x / x * x |
1.0 |
| 4 |
50 |
x * x + x + x * x + x / x * x * x * x |
0.2697923828640847 |
| 5 |
50 |
x * x * x * x + x * x + x + x * x * x |
0.9999999999999991 |
| 6 |
50 |
x - x + x + x + x * x - x * x / x + x * x * x * x - x * x + x * x - x + x + x * x * x |
0.9999999999999991 |
| 7 |
50 |
x * x * x + x + x * x + x - x + x + x * x - x * x + x + x * x - x - x |
0.2467044521737591 |
| 8 |
50 |
x + x * x + x * x * x - x + x * x * x * x + x /x * x |
0.9999999999999998 |
| 9 |
50 |
x * x + x |
0.1996232819981532 |
| 10 |
50 |
x * x * x + x * x * x * x + x + x * x |
0.9999999999999998 |
C. Trigonometric Identity Experiments
The particular function examined is Cos 2x, and the desired trigonometric identity is 1-2Sin2x (for this reason the unary operator Math.cos is not included in the BNF Grammar of this problem).
The objective of these experiments is to be found a mathematical expression which will match the sample data points which are automatically created by the examined function.
C.1 Trigonometric Identity Tableau for GE (O"Neill-style)
| Objective: |
Find a new mathematical expression, in symbolic form that equals a given mathematical expression, for all values of its independent variables.
Examined Function: Math.cos(2 * x)
Desired Trigonometric Identity: 1-2Sin2x
|
| Terminal Operands: |
x, the constant 1.0 |
| Terminal Operators: |
The binary operators +, -, /, *, and -
The unary operator Math.sin |
| Fitness cases: |
The given sample of the pairs (xi, yi) of 20 data points in the interval [0, 2π].
The input data points (xi) are randomly created and their corresponding output points (yi) are automatically created by the expression Math.cos(2 * x) |
| Raw Fitness: |
The sum, of the absolute values of errors taken over the fitness cases (xi, yi).
With the above Raw Fitness the best individuals have lower values.
For this reason a kind of Adjusted Fitness will be used and assigned to each individual.
Adjusted Fitness of an individual i is typically defined as following:
Fa(i) = 1 / (1 + Fs(i)) where Fs the Standardised Fitness of i.
In this case the Adjusted Fitness of an individual i is calculated as following:
Fa(i) = 1 / (1 + Fr(i)) where Fr the Raw Fitness of i.
The fitness value varies from 0 to 1 and Invalid individuals will have Raw Fitness Value 0. |
| Standardised Fitness: |
Same as raw fitness. |
| Wrapper: |
Standard productions to generate a Java Class with a main() method which prints the fitness values in the standard output |
| Parameters: |
Population Size (M) = 500,
Maximum Generations (G) = 50,
Prob. Mutation (Pm) = 0.01,
Prob. Crossover (Pc) = 0.9,
Prob. Duplication (Pd) = 0.01,
Prob. Pruning (Pp) = 0.01,
Selection Mechanism = Steady State GA with Generation Gap (G) = 0.9
Codon Size = 8 |
C.2 BNF Grammar
<expr> ::= <expr> <op> <expr> | ( <expr> <op> <expr> ) | <pre-op> ( <expr> ) | <var>
<op> ::= + | - | / | *
<pre-op> ::= Math.sin
<var> ::= x | 1.0
C.3 Trigonometric Identity Results
| Run |
Generations |
Phenotype |
Raw Fitness |
| 1 |
50 |
Math.sin ( x + ( x + 1.0 ) ) |
0.10793425584713574 |
| 2 |
50 |
Math.sin ( x + x + 1.0 + Math.sin ( Math.sin ( 1.0 ) ) ) |
0.31125330920116906 |
| 3 |
40 |
Math.sin ( Math.sin ( ( x + x ) + 1.0 + Math.sin ( Math.sin ( 1.0 ) ) ) * 1.0 ) |
0.25691103931194736 |
| 4 |
50 |
Math.sin ( ( 1.0 - x ) + ( 1.0 - x ) ) |
0.1466328694322308 |
| 5 |
50 |
Math.sin ( ( x + ( Math.sin ( 1.0 * Math.sin ( 1.0 ) / 1.0 ) + Math.sin ( 1.0 ) ) + x / 1.0 ) ) |
0.84065701811658 |
| 6 |
50 |
Math.sin ( ( 1.0 - ( x - Math.sin ( Math.sin ( Math.sin ( Math.sin ( Math.sin ( Math.sin ( 1.0 ) ) ) ) ) ) + x ) ) ) |
0.8182130706092126 |
| 7 |
50 |
Math.sin ( 1.0 + ( x + Math.sin ( Math.sin ( 1.0 ) ) ) + x ) |
0.3567880989976856 |
| 8 |
50 |
Math.sin ( ( x + ( 1.0 / 1.0 + ( Math.sin ( Math.sin ( Math.sin ( Math.sin ( 1.0 ) ) ) ) + x ) ) ) ) |
0.5933482508093464 |
| 9 |
50 |
Math.sin ( ( x + x + ( Math.sin ( 1.0 ) + ( ( 1.0 + x + x + Math.sin ( Math.sin ( 1.0 ) ) ) - 1.0 - x ) - x ) ) ) |
0.8178615390653478 |
| 10 |
50 |
Math.sin ( Math.sin ( Math.sin ( 1.0 ) ) + x + Math.sin ( Math.sin ( 1.0 ) ) + x ) |
0.5348593720523398 |
|
