Java-based Push Genetic Programming

Russ Abbott (RAbbott@CalStateLA.edu)

An initial version of a Java Push Genetic Programming system is available as a zip file.

Briefly, Push is a stack-based language developed for genetic programming by Lee Spector. (See Push-GP for details.) A Push world (as implemented here) consists of agents, each of which has a number of stacks that are operated on by postfix-like programs. For example, when executed, the program (3 4 +)produces the following trace.

1. INTEGER.3: [] -> [3]
2. INTEGER.4: [3] -> [3, 4]
3. INTEGER.+: [3, 4] -> [7]
Finished executing: (3 4 +)
Agent: Agent_2 {}
INTEGER: [7]
CODE: [(3 4 +)]
NAME: []
FLOAT: []
BOOLEAN: []
TYPE: [NAME, TYPE, CODE, BOOLEAN, INTEGER]

The integers 3 and then 4 are pushed onto the Integer Stack. The operation + pops and then adds the top two elements of the Integer Stack and pushes the result back onto the Integer stack.

The Code Stack contains the program being executed.

As the example shows, Push agents have a separate stack for each of number of types. This facilitates type-safe programs without the need for implicit casting. Again, see Push-GP for details.

The Java code is organized into two packages: pushInterpreter and gp.

The pushInterpreter package contains classes that implement the Push language. Many of the classes have main() methods, used primarily for testing.

The TestCases class includes a runInput() method. (TestCases.main() is currently set up to call it.) When executed, TestCases.runInput() will produce a primitive GUI consisting of a series of JOptionPane windows into which the user can interactively enter input and see the results.

The gp package contains classes that implement genetic programming. An abstract Problem class defines the methods a problem to be solved is required to implement. An example problem has been implemented in the Even class. It looks for programs that when given an integer on the Integer stack will leave true or false on the Boolean stack depending on whether or not the integer is even.

Even.main() is currently set up to generate 10 results. (Usually they are distinct, but no effort is made to avoid duplicates.) Results that use the mod operator have been produced as well as results that use the nth operator as described in Spector's paper. Whenever the system generates a new best result, it applies a simplification algorithm to it and adds the simplified expression back into the population.
- An interesting (simplified) mod-based results was: (dup * 4 mod =). In this program, the input is squared (duplicated and then multiplied by itself). The result is then tested to see if it is equal to 0 mod 4.
- An interesting (simplified) nth-based result was: ((nth not) doDie). In this program, the input is used to select the n^th element of the program itself. (If the input is greater than the number of elements in the program, nth wraps around. In this case, nth selects the (input mod 2)^th element of the program.) If the input is even, (nth not) is pushed onto the Code Stack. (The original program continues executing, though.)
  
  In the next step, the not operation is executed. not is defined to negate the top element of the Boolean stack. If the Boolean stack is empty, it simply pushes false onto the Boolean stack. (As was the case in many of the generated programs, the default behavior of operators when there were insufficient arguments on the stacks was critical to the success of the program. In the MOD program, for example, if there is only one element on the stack, = compares that element to 0.)
  
  doDie then executes the top element of the Code stack, which is now (nth not). nth again pushes something onto the Code stack. (It doesn't matter what it is.), and not negates the false on the Boolean Stack, making it true—the correct answer for an even input.
  
  If the input had been odd, doDie would have been pushed onto the Code Stack instead of (nth not). doDie is defined so that it can only execute once in any program. If it attempts to execute a second time, execution of the entire program is terminated. This leaves the false (originally generated by not) on the Boolean stack—the right answer for odd inputs.
  
  Another nth-based result in which doDie plays an even more direct role is ((true nth doDie) false). In this program, if the input is 0 mod 2, the doDie instruction terminates the entire program and blocks the false from pushing itself onto the Boolean Stack.
  
  Ugly as these programs are, they illustrate an important feature of genetic programming—which parallels evolution in nature. In natural evolution, the "blind watchmaker" puts together whatever is available to get a desired result.
  
  The implication of this is that one should not expect a genetic programming system to produce elegant programs. One should expect it to produce chunks of useful black box functionality that may be strung together to produce more useful black box functionality.