Sample Runs

Let's now look at some sample runs of the application. While the application emits quite a bit of debugging data, including the fitness trends to file stats.txt , we'll look simply at the results.

The first test was to create an instruction sequence that solved Equation 6.2:

(6.2)  

The resulting program evolved with the application was:

• DUP MUL DUP MUL DUP MUL

In summary, the sequence first calculates the square of x, then squares that value and squares it once more, each time using the DUP instruction.

The next test involved three variables , shown in Equation 6.3:

(6.3)  

The instruction sequence evolved for this equation was:

• ADD DUP ADD SWAP ADD

The evolved program is an optimization of the equation where x and y are first summed before multiplying them by 2 (through a DUP ADD sequence). The final ADD instruction adds in the z component. Note that in this case a SWAP instruction was generated. This instruction has no value, but it still resulted in a working program.

Another interesting evolution was found for Equation 6.4:

(6.4)  

The resulting program evolved with the application was:

• OVER ADD MUL ADD

This program first duplicates the second item on the stack (y) and places it on the top of the stack. Next, it adds x and y together, and multiplies it by y. Finally, z is added in with the final ADD instruction. This is yet another optimization (simplification) of the original equation.

Finally, let's look at a more complicated example in Equation 6.5:

(6.5)  

This equation was solved by the following evolved instruction sequence:

• DUP DUP MUL MUL SWAP DUP MUL SWAP ADD SWAP SWAP ADD

The first four instructions (DUP DUP MUL MUL) calculate the x ³ term . Next, we swap the top two elements of the stack so that the y element is now on top. The DUP MUL sequence calculates the y ² term. Finally, the remaining five instructions add the three terms together. Note that the SWAP instructions are superfluous, but did not destroy the sequence and were therefore not evolved away.

Figure 6.14 shows the progress of the algorithm in evolving the instruction sequence for Equation 6.5. It's interesting to note the gradual improvement of the average fitness in this example. After 10,000 generations, the plot shows gradual improvement until around 20,000 generations. At this point, there is a step improvement in the maximum and average fitness of the population. The maximum fitness of the population then hovers near the highest fitness (2510) until around 30,000 generations when the problem is finally solved.

Figure 6.14: Plot of fitness over time in evolving for Equation 6.5.

What's interesting about this plot is the gradual improvement of the fitness. This proves that the genetic algorithm is useful in solving symbolic problems such as these. While chromosomes are selected that don't solve the problem completely, mutating and crossing -over with other chromosomes in the population lead to increased fitness until the problem is ultimately solved.