lil-gp is a C language system for developing genetic programming applications based on the LISP work of John Koza at Stanford University. lil-gp evolves trees whose nodes are C function pointers, so tree evaluation is done entirely with complied code. This gives us a manyfold speed increase, allows us to handle much large problems (bigger populations, more generations), and is portable to a wide variety of platforms. This system is the first (that we know of) to support multiple-population runs with arbitrary interchange topologies. lil-gp has many many options for controlling breeding, and is capable of emulating Koza and Rice's "Simple LISP Code", given in the appendix of Koza's Genetic Programming as well as the parameters given in chapter 7, "Detailed Description of Genetic Programming," in that book.

Features

lil-gp features include:
  • ease-of-use: options are specified via a flexible format parameter file; command line arguments lend the system to batch operation for long series of runs
  • supports multiple subpopulations with arbitrary exchange topologies
  • written in C for portability to a wide variety of Unix/DOS/Mac platforms
  • 7 selection methods: fitness-proportionate, greedy overselection, inverse-fitness, variable-size tournament, random, best, worst
  • 3 genetic operators: crossover, reproduction, mutation
  • writes and restarts from checkpoint files
  • optional per-node point postmutation
  • optional node and/or depth limitations on tree size
  • support for ephemeral random constants
  • extensive output, including statistics files ready for import into plotting/analysis packages

Kernel

At lil-gp's core is a tree representation that is compact yet amenable to extremely fast evaluation. Trees are stored as preorder expressions, with special symbols inserted to indicate ephemeral random constants and conditionally evaluated subtrees. The compactness of the representation allows larger populations to be stored in real memory, and the fact that trees are stored as contiguous blocks of memory minimizes the impact of paging on performance. The selection methods and genetic operators are implemented in an object-oriented fashion, allowing new routines to be added easily. Checkpoint files save the entire state of the run, allowing a promising run to be extended, or an interrupted run to be completed. A portable random number generator provides consistent results across platforms.

Specification of Problems

Creating a program in lil-gp is done with a minimum of code writing. The use must provide one C function for each GP function and terminal, in addition to a fitness evaluation function. Several callback hooks are provided for initialization, customized output, and reading and writing user state information to checkpoint files. Once the user code is written, the executable need only be compiled once--all parameters and operators are available--even switch between single and multiple population runs--just by modifying the parameter file.

Multiple Populations

lil-gp's support for multiple population problems includes user-specified exchange topology and interval. A few of the possible topologies are shown below. The parameter file specifies how the individuals to be exchanged from each subpopulation are selected, and where they go. The output files include statistics on fitness and tree size for each subpopulation and for the entire population, both for the current generation and the entire run to that point.

Availability

lil-gp is currently available as a beta test version. We have implemented three of the "standard problems" of GP--the Boolean 11-multiplexer, symbolic regression, and the artificial ant--and are getting results comparable to those reported by Koza. The beta version has a fully functional kernel code but fairly minimal documentation--it is enough to get the sample problems compiled, play with the options, and write some applications of your own.

Version 1.0 will include more complete documentation of the kernel, how to add your own selection methods and genetic operators, and have automatically defined functions (ADFs).

back to the lil-gp home page.

lil-gp Overview, Doug Zongker, last modified 6/6/1995