Tag-Based Modules in Genetic Programming

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:


Computational effort plot for the DSOAR problem:


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