Autoconstructive Evolution

I got to read Genetic Programming and Autoconstructive Evolution with the Push Programming Language. The paper’s basically an introduction to Push, PushGP, and Pushpop, detailing both how they work and why they do what they do.

Push, the Language

There are several requirements for a programming language to be an effective language in the evolutionary computing, genetic programming field. The first is that the language provide for autonomy – the programs must themselves “learn or evolve solutions to problems with minimal human intervention.” This requires at the very least that the language allows for code to manipulate itself.

The second is that the language should support multiple data types, and the ability to handle “errors” arising from using more than one type.

The third is that the code should be able to be modular, or able to replicate many identical groups of operations without explicitly stating the group of operations each time.

Lastly, the code must be able to evolve the methods through which the code evolves. While this may seem like circular logic, this is designed to simulate the evolution of life on Earth – “evolution … presumably began without the imposition of pre-specified mechanism for reproduction and diversification.” Autoconstructive evolution is defined in the paper to be “any evolutionary computation system that adaptively constructs its own mechanisms of reproduction and diversification as it runs.”

Push General Design Goals:

• expressive
  • multiple data types
  • modules
  • complex control structures including recursion
• self-manipulating
• syntactically uniform

Push fulfills all of those goals. Push has a very neat way of manipulating its own code, through the use of the CODE type. I found this to be one of the neatest things about Push. This one design choice enables the use of modularity, recursion, and self-manipulation. Push also incorporates other the typical numerical types (BOOLEAN, FLOAT, INTEGER) and nontypical ones as well (CHILD, TYPE) [don’t know what these are].

Push code is also designed to be syntactically uniform, and uses postfix notation. The postfix is because Push is a stack-based language as opposed to a register-based language, so whereas typical Lisp code would look like:

(+ 9 3)

and reading would go from left to right and execution would go from right to left, Push would have:

(3 9 +)

where the 3 is pushed onto the INTEGER stack, then the 9, then the + would be executed on the numbers. It is important that Push is syntactically uniform it allows Push to “follow ‘permissive execution’ precedent[s] established in previous stack-based genetic programming work.” This makes sure that an operator operating on too little arguments will be passed a NOOP.

As stated before, Push has multiple data types, and a stack for each one. Operators can also be typed to operate solely on the stack they were designed for, although conversions are also made possible using the CONVERT function.

[I would like to know more about the DO and DO* functions.]

Push itself is just a language devised for application in genetic programming systems, one of which is PushGP.

PushGP

Whereas Push is the code, PushGP is the framework under which the programmers devise the parameters that will hopefully lead to code generation and the evolution of programs that fit certain tasks.

The flow of the PushGP algorithm goes somewhat like this: Random population generation -> fitness testing -> (reproduction, mutation, crossover operators[?]) applied to fitter programs -> rinse and repeat until “fit” is found or maximum generation limit is reached. Quote: “In most of our experiments we use a traditional mutation operator that replaces a randomly chosen sub-expression with a new random subexpression.” [I’d like to know more about that.]

[Also, tournaments? And what’s the big deal with parity? Why was it such a big deal that Push was able to solve the even 4-parity problem?]

End of Part 1. Pushpop will be Part 2.