This chapter describes genetic programming, and describes how to use genetic programming in breve simulations using an evolvable language called "Push".
Many artificial life simulations are designed around the concept of evolving agents: agents in a simulated world use evolution in order to find better and better solutions to some task such as locomotion, survival or some sort of "intelligent" behavior.
Evolution of agent behaviors is typically accomplished in one of two ways: optimizing a set of parameters, a technique known as "genetic algorithms" (GA); or by developing evolved computer programs, a technique known as "genetic programming".
Genetic programming involves random crossover and mutation of computer
programs. Most computer languages designed for people are picky about
syntax and variable types and are not well suited to
evolution—most random crossovers and mutations would produce code
that simply does not compile (like x = y +
=;), or code that does compile, but does not make sense
semantically (like x = sqrt( "puppydog"
);).
The "Push" language is designed specifically for genetic programming and other evolutionary computational applications. Push is designed to avoid most of the complications that can arise when evolving code. In fact, Push code is almost never written by hand. This chapter is intended as a short introduction to using Push in breve simulations and is not a definitive overview of Push or its features. More information about Push and how it is being used can be found on this page.
The Push language is well suited for evolution because of its extremely simple syntax, and its stack-based typing system. The simple syntax helps to ensure that any kind of genetic operator (including the commonly used crossover and mutation) will produce a syntactically valid individual. The stack-based typing system—in which instructions look for operators on typed stacks—ensures that all push programs are semantically valid.
Arguments are passed to instructions using a set of stacks, one for each variable type. When an instruction is executed, it reads and removes argument values from the tops of the relevant stacks, it performs a computation, and then it pushes any output values onto the relevant stacks. If a stack is empty and cannot provide input values for an instruction, the instruction performs a "NOOP" and does nothing. This scheme ensures that instructions are always provided with input data of the correct type.
The version of push built into breve 2.0 provides support for the following native types: integer, float, name, vector and code.
A Push program is made up of lists of the following elements: instructions, literal values, and sublists of these elements. Execution of a Push program begins by placing the entire expression onto the code stack and proceeds recursively as follows:
To execute program P:
If P is a single instruction then execute it.
Else if P is a literal then push it onto the appropriate stack.
Else (P must be a list) sequentially execute each of the Push programs in P.
Here's a sample Push program which does some mathematical and logical computations:
( 2 3 INTEGER.* 4.1 5.2 FLOAT.+ TRUE FALSE BOOLEAN.OR )
After execution of the program, the stacks are left in the following states:
# the program we started with
CODE STACK: ( ( 2 3 INTEGER.* 4.1 5.2 FLOAT.+ TRUE FALSE BOOLEAN.OR ) )
# the result of the code TRUE FALSE BOOLEAN.OR
BOOLEAN STACK: ( TRUE )
# the result of the code 4.1 5.2 FLOAT.+
FLOAT STACK: ( 9.3 )
# the result of the code 2 3 INTEGER.*
INTEGER STACK: ( 6 )
Real push programs are far more complex: instructions are provided to allow push programs to modify their own code, perform logical and program flow control operations. and even create and run new programs on-the-fly (automatically providing support for elements which resemble macros and "automatically defined functions"). For a full list of Push instructions and features, see this page.