Tag-Based Modules in Genetic Programming

Lee Spector
Cognitive Science, Hampshire College
(lspector@hampshire.edu, http://hampshire.edu/lspector)

Brian Martin
Cognitive Science, Hampshire College

Kyle Harrington
Computer Science, Brandeis University

Thomas Helmuth
Computer Science, University of Massachusetts, Amherst


This page contains material related to "Tag-Based Modules in Genetic Programming," a paper in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2011), published by The Association of Computing Machinery.


Abstract

In this paper we present a new technique for evolving modular programs with genetic programming. The technique is based on the use of “tags” that evolving programs may use to label and later to refer to code fragments. Tags may refer inexactly, permitting the labeling and use of code fragments to co-evolve in an incremental way. The technique can be implemented as a minor modification to an existing, general purpose genetic programming system, and it does not require pre-specification of the module architecture of evolved programs. We demonstrate that tag-based modules readily evolve and that this allows problem solving effort to scale well with problem size. We also show that the tag-based module technique is effective even in complex, non-uniform problem environments for which previous techniques perform poorly. We demonstrate the technique in the context of the stack-based genetic programming system PushGP, but we also briefly discuss ways in which it may be used with other kinds of genetic programming systems.

Citation

Spector, L., B. Martin, K. Harrington, and T. Helmuth. 2011. Tag-Based Modules in Genetic Programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2011). ACM Press. pp. 1419-1426.

Full paper

Full paper in PDF format: spector-tags-gecco-2011-with-citation.pdf (528KB).

Presentation Slides

spector-GECCO-2011-tagmodularity.pdf (1.2 MB).

Source Code

Clojush-GECCO2011-20110621.tar.gz: This is the source code for the bugfixed version (see below). The archive contains the full set of libraries required to run the code, which is written in the Clojure programming language, and also all of the problem files that were distributed with the Clojush PushGP system at the time; the relevant problem files are src/examples/lawnmower.clj and src/examples/dsoar.clj.

Acknowledgments

Thanks to Daniel Gerow, Nathan Whitehouse, and Rebecca Neimark for feedback that helped us to improve this work in several ways, to Josiah Erikson for systems support, and to Hampshire College for support for the Hampshire College Institute for Computational Intelligence. Thanks also to Jordan Pollack and the Brandeis DEMO lab for computational resources. This material is based upon work supported by the National Science Foundation under Grant No. 1017817. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Error Notice

As this paper was going to press we discovered that our implementation of frog was buggy and acted as a no-op. The numbers presented in the paper are nonetheless valid for a version of the problem in which frogging is disabled, although we did find one other error when we re-audited the results: We had lost 28 out of the 1,500 run logs due to file name conflicts. The impact of the data loss was minimal because the primary measures that we reported (computational effort and mean best fitness) were scaled based on the true number of log files.

We have since conducted new runs with all bugs fixed, and the new results (below) show that the qualitative effects described in the paper still hold.

The results with all bugs fixed are as follows:

Lawnmower problem, computational effort, 100 runs/condition:
problem size
8x4 8x6 8x8 8x10 8x12
instr set
basic 10000 30000 114000 320000 630000
tag 7000 2000 29000 <1000 5000
exec 12000 5000 28000 5000 17000


Lawnmower problem, mean best fitness, 100 runs/condition:
problem size
8x4 8x6 8x8 8x10 8x12
instr set
basic 0.00 0.00 0.00 0.02 0.14
tag 0.00 0.00 0.00 0.00 0.00
exec 0.00 0.00 0.00 0.00 0.00


DSOAR, computational effort, 100 runs/condition:
problem size
8x4 8x6 8x8 8x10 8x12
instr set
basic 1584000 430083000 inf inf inf
tag 216000 864000 3420000 2599000 3051000
exec 450000 2125000 4332000 16644000 7524000


DSOAR, mean best fitness, 100 runs/condition:
problem size
8x4 8x6 8x8 8x10 8x12
instr set
basic 0.42 3.49 8.68 14.20 21.45
tag 0.10 0.56 2.08 2.79 5.12
exec 0.29 1.08 3.78 4.35 5.72
Computational effort plot for the Lawnmower problem:

Lawnmower problem:
        computational effort
Computational effort plot for the DSOAR problem:

DSOAR problem:
        computational effort
Computational effort plot for the DSOAR problem, with Basic instruction data omitted (and axes rescaled):

DSOAR problem:
        computational effort with Basic instruction data omitted and
        axes rescaled