Clojush

Lee Spector (lspector@hampshire.edu), started 20100227 See version history. Older version history is in old-version-history.txt.

This is the README file accompanying Clojush, an implementation of the Push programming language and the PushGP genetic programming system in the Clojure programming language. Among other features this implementation takes advantage of Clojure's facilities for multi-core concurrency.

Availability

https://github.com/lspector/Clojush/

Requirements

To use this code you must have a Clojure programming environment; see http://clojure.org/. The current version of Clojush requires Clojure 1.7.0.

Clojure is available for most OS platforms. A good starting point for obtaining and using Clojure.

Quickstart

Using Leiningen you can run an example from the OS command line (in the Clojush directory) with a call like:

lein run clojush.problems.demos.simple-regression

If you would like to change a parameter, you may do so at the command line. For example, to change the default population size from 1000 to 50, call:

lein run clojush.problems.demos.simple-regression :population-size 50

Additional parameters may also be specified. All valid parameters with their descriptions can be found in args.clj.

The above calls will load everything and run PushGP on a simple symbolic regression problem (symbolic regression of y=x^3-2x^2-x). Although the details will vary from run to run, and it's possible that it will fail, this usually succeeds in a few generations.

Another option is to evaluate in the leinigen REPL (Read Eval Print Loop):

sh> lein repl
...
clojush.core=> (use 'clojush.problems.demos.simple-regression)
...
clojush.core=> (pushgp argmap)

Arguments to pushgp are specified in the argmap variable in the problem's namespace.

To run the examples in an IDE (Integrated Development Environment) for Clojure such as Clooj or Eclipse/Counterclockwise, load one of the files in src/clojush/problems into the IDE's REPL, type (pushgp argmap) into the REPL's input area, and hit the enter key.

You can also use Docker to run examples, if you don't want to install Clojure on your machine directly.

# first build the image. This needs to be re-done if any of the code changes
docker build -t lspector/clojush .
# then run it on a specific problem
docker run --rm lspector/clojush lein run clojush.problems.demos.simple-regression

For large-scale runs you may want to provide additional arguments to Java in order to allow access to more memory and/or to take maximal advantage of Clojure's concurrency support in the context of Clojush's reliance on garbage collection. For example, you might want to provide arguments such as -Xmx2000m and -XX:+UseParallelGC. Details will depend on the method that you use to launch your code.

An additional tutorial is available in src/clojush/problems/demos/tutorial.clj.

Description

Clojush is a version of the Push programming language for evolutionary computation, and the PushGP genetic programming system, implemented in Clojure. More information about Push and PushGP can be found at http://hampshire.edu/lspector/push.html.

Clojush derives mainly from Push3 (for more information see http://hampshire.edu/lspector/push3-description.html, http://hampshire.edu/lspector/pubs/push3-gecco2005.pdf) but it is not intended to be fully compliant with the Push3 standard and there are a few intentional differences. It was derived most directly from the Scheme implementation of Push/PushGP (called Schush). There are several differences between Clojush and other versions of Push3 -- for example, almost all of the instruction names are different because the . character has special significance in Clojure -- and these are listed below.

If you want to understand the motivations for the development of Push, and the variety of things that it can be used for, you should read a selection of the documents listed at http://hampshire.edu/lspector/push.html, probably starting with the 2002 "Genetic Programming and Evolvable Machines" article that can be found at http://hampshire.edu/lspector/pubs/push-gpem-final.pdf. Bear in mind that Push has changed over the years, and that Clojush is closest to Push3 (references above).

Push can be used as the foundation of many evolutionary algorithms, not only PushGP (which is more or less a standard GP system except that it evolves Push programs rather than Lisp-style function trees -- which can make a big difference!). It was developed primarily for "meta-genetic-programming" or "autoconstructive evolution" experiments, in which programs and genetic operators co-evolve or in which programs produce their own offspring while also solving problems. But it turns out that Push has a variety of uniquely nice features even within a more traditional genetic programming context; for example it makes it unusually easy to evolve programs that use multiple data types, it provides novel and automatic forms of program modularization and control structure co-evolution, and it allows for a particularly simple form of automatic program simplification. Clojush can serve as the foundation for other evolutionary algorithms, but only the core Push interpreter and a version of PushGP are provided here.

Starting with version 2.0.0, the genomes of evolving individuals in Clojush are based on Plush (linear Push) genomes, which are translated into normal Push programs before execution. Plush genomes are composed of instruction maps, each of which contains an instruction and potentially other metadata describing whether that instruction should be silenced, whether closing parentheses should follow it, etc.

Usage

Example calls to PushGP are provided in other accompanying files.

Push programs are run calling run-push, which takes as arguments a Push program and a Push interpreter state that can be made with make-push-state. If you are planning to use PushGP then you will want to use this in the error function (a.k.a. fitness function) that you pass to the pushgp function. Here is a simple example of a call to run-push, adding 1 and 2 and returning the top of the integer stack in the resulting interpreter state:

(top-item :integer (run-push '(1 2 integer_add) (make-push-state)))

If you want to see every step of execution you can pass an optional third argument of true to run-push. This will cause a representation of the interpreter state to be printed at the start of execution and after each step. Here is the same example as above but with each step printed:

(top-item :integer (run-push '(1 2 integer_add) (make-push-state) true))

See the "parameters" section of the code for some parameters that will affect execution, e.g. whether code is pushed onto and/or popped off of the code stack prior to/after execution, along with the evaluation limits (which can be necessary for halting otherwise-infinite loops, etc.).

Run-push returns the Push state that results from the program execution; this is a Clojure map mapping type names to data stacks. In addition, the map returned from run-push will map :termination to :normal if termination was normal, or :abnormal otherwise (which generally means that execution was aborted because the evaluation limit was reached.

Random code can be generated with random-code, which takes a size limit and a list of "atom generators." Size is simply the length of the linear Plush genome. Each atom-generator should be a constant or the name of a Push instruction (in which case it will be used literally), or a Clojure function that will be called with no arguments to produce a constant or a Push instruction. This is how "ephemeral random constants" can be incorporated into evolutionary systems that use Clojush -- that is, it is how you can cause random constants to appear in randomly-generated programs without including all possible constants in the list of elements out of which programs can be constructed. Here is an example in which a random program is generated, printed, and run. It prints a message indicating whether or not the program terminated normally (which it may not, since it may be a large and/or looping program, and since the default evaluation limit is pretty low) and it returns the internal representation of the resulting interpreter state:

(let [s (make-push-state)
      c (random-push-code
          100                                  ;; size limit of 100 points
          (concat @registered-instructions     ;; all registered instrs
                  (list (fn [] (rand-int 100)) ;; random integers from 0-99
                        (fn [] (rand)))))]     ;; random floats from 0.0-1.0
  (printf "\n\nCode: %s\n\n" (apply list c))
  (run-push c s))

If you look at the resulting interpreter state you will see an "auxiliary" stack that is not mentioned in any of the Push publications. This exists to allow for auxiliary information to be passed to programs without using global variables; in particular, it is used for the "input instructions" in some PushGP examples. One often passes data to a Push program by push