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
Featureslil-gp features include:
KernelAt 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 ProblemsCreating 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 Populationslil-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.
Availabilitylil-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).
lil-gp Overview, Doug Zongker, last modified 6/6/1995