|
Block stacking
In block stacking, the goal is to find a plan that takes any initial configuration of
blocks randomly distributed between the stack and the table and place them in the stack in the correct order (Fig. 1).
Stack Table
usra i e n l v
|
--->
|
Stack Table
universal -
|
Figure 1
One initial state for the block stacking problem.
The objective is to find a program that will stack the blocks spelling the word "universal"
from any initial state.
Table 1
Parameters for the block stacking problem
|
| Function set |
C,R,N,=,A |
| Terminal set |
u,p,t |
| Number of fitness cases |
10 |
| Number of runs |
100 |
| Number of generations |
100 |
| Population size |
30 |
| Success rate |
70% |
Notes:
C- move to stack, R- remove from stack, N- not, '='- equal, A- do until true
u- current stack, t- top correct block, p- next needed block
Table 2
Comparison of GP and GEP on the sequence induction problem
|
| |
Exp |
Gen |
Pop |
Fit. cases |
Succ |
Rz |
Fz |
GP |
O'Reilly and
Oppacher[1] |
51 |
500 |
167 |
0.767 |
4 |
17,034,000 |
GEP |
Table 1 |
100 |
30 |
10 |
0.77 |
4 |
120,000 |
Conclusion:
In this case, GEP outperforms GP in 142 times (see How to evaluate the performance for details). It is worth noticing that GP uses 167 fitness cases, cleverly constructed to cover the various classes of possible initial states whereas GEP uses only 10 initial states, 9 of which randomly generated with 1 to 9 letters in the stack, and 1 empty stack (in fact, this empty stack is unnecessary for GEP to work efficiently: it only prevents failed runs).
Download the executable
Bibliography:
1. O'Reilly, U-M, and F. Oppacher (1996). A comparative analysis of GP. Chapter 2 of Advances in Genetic Programming 2, ed. P. J. Angeline and K. E. Kinnear, MIT Press.
Back
***
|
