next up previous
Next: Conclusions Up: Grammatical Evolution : Solving Previous: The Problem Space


GE successfully found the $1 - 2Sin^2\;x$ identity for $Cos \; 2x$on the majority of runs. An example of how one solution was arrived at will now be given. Early on in the run very simple expressions existed, such as 1.0 which had a fitness 0.08 (The best fitness an individual may have is 1.0), $Sin \; x$ whose fitness was 0.07, $Sin \; 1.0$ whose fitness was 0.10, and $(Sin\; x) * (Sin \; x)$ whose fitness was 0.06, while not particularly fit these individuals are the essential building blocks for the ultimate solution.

After the first 20 generations the best individuals were

$Sin(1.0)-Sin(Sin(Sin \; 1.0))*x$ which had a fitness 0.08,

$1.0-Sin(Sin \; x)*x$ which had a fitness 0.13,

$1.0-Sin(Sin \; x*Sin \; x)$ which had a fitness 0.15.

Shortly after this, two individuals appeared that gradually spread amongst the population. These were

$1.0-(Sin \; x)*(Sin \; x)$,

$Sin \; 1.0 - (Sin \; x)*(Sin \; x)$,

whose fitness were 0.17 and 0.20 respectively. Again, while not particularly fit themselves, they are important steps on the path to the solution. All that was needed now was another $-(Sin \; x)*(Sin \; x)$ to be added onto the first of these expressions. Generation 39 saw this come to pass with a slight variation, the individual being

$1.0-(Sin \; x)*(Sin \; x)+1.0-1.0-(Sin \; x)*(Sin \; x)$,

which had the fitness of 1.00.

Figure 3: Some interesting individuals.

Subsequent runs produced other notable individuals. One individual seen in Figure 3,

$1.0-Sin \; x*(x+Sin(Sin(Sin \; x)))$,

approximated the function $Cos \; 2x$ very closely in the range -1 to +1 but outside this range it deviated from $Cos \; 2x$. Others resembled the target functions overall appearance almost exactly, but were phase shifted away by a very small number of radians, one of these individuals seen in Figure 3 was


Another interesting individual


seen in Figure 4, was almost identical to the target function. Interestingly, in this individual we can see the successive application of the Sin function to the constant 1.0. Koza also observed a similar phenomenon with Genetic Programming [Koza 92]. Effectively GE is evolving a numerical constant. Successive application of the Sin function to 1.0 results in a constantly decreasing value. After four applications of Sin to 1.0 the result is 0.628, and then the subsequent reciprocal produces 1.59. This is close to $\pi /2$ which is approximately 1.57. Simplified the expression can now be shown as follows: Sin(2x+1.59) , which is very close to another well known indentity of $Cos \; 2x$, that being $Sin( \pi /2 -2x)$.

Figure: Generating numerical constants to give $Sin( \pi /2 -2x)$.

Figure 5: Cumulative frequency measure of when the solution was found.

Figure 5 shows a cumulative frequency measure of when the solution was arrived at. When compared with Genetic Programming, GE is somewhat slower at generating the solution for this particular problem. We are not unduly concerned at GP being faster, as we don't expect GE to be viewed as a replacement to GP. Rather, that it complements GP, and is intended to be used for the generation of functions of arbitray complexity. We are more concerned with proving that this system can generate functions of this type. It is envisaged that when it comes to problems requiring multi-line function solutions, GE will come into it's own.

next up previous
Next: Conclusions Up: Grammatical Evolution : Solving Previous: The Problem Space