Tag-based modularity in tree-based genetic programming

Lee Spector, Kyle Ira Harrington, Thomas HelmuthGECCO 2012 · DOI

TL;DR

This paper explores how to integrate "tag-based modularity" – a technique for evolving reusable code blocks using arbitrary identifiers – into standard tree-based genetic programming. While successful on a lawnmower problem, the approach struggled with a Boolean parity problem, highlighting challenges in argument passing and unbounded recursion that require further research.

What Problem Does This Paper Address?

Genetic programming (GP) aims to automatically generate computer programs. A major hurdle to scaling GP to complex problems is the lack of modularity in evolved programs. Standard GP often produces monolithic, hard-to-understand code. While techniques like Automatically Defined Functions (ADFs) exist, they typically require pre-specifying the module architecture (e.g., number of modules, their arguments). This paper addresses the need for a more flexible, automatic way to introduce modularity into GP, specifically by adapting a promising "tag-based" approach, previously demonstrated in the PushGP system, to the more common tree-based GP paradigm.

Methods

The core idea is to introduce "tags" – arbitrary identifiers – to code blocks (modules). When a program needs to use a module, it references its tag. The system then retrieves the module whose tag is the "closest match" to the requested tag.

The authors adapt this to tree-based GP by:

  • Tagging Functions: Introducing functions like tag.n that take a code block (as an argument) and assign it a tag n.
  • Retrieval Functions: Introducing functions like tagged.n that search for and execute the code block associated with the closest matching tag n.

They explore two key implementation details for tree-based GP:

  • Silent Tagging: The tag.n function returns a default value without executing the tagged code.
  • Non-Silent Tagging: The tag.n function executes the tagged code and returns its result.

They also address potential issues like:

  • Return Values: How tag.n and tagged.n functions should return values in a tree-based system where all subtrees must return a value.
  • Unbounded Recursion: Implementing execution step limits to prevent infinite loops, and penalizing programs that hit these limits.

Datasets

The paper evaluates the proposed tag-based modularity technique on two well-known benchmark problems:

  • 8x8 Lawnmower Problem: A simulated robot mowing a grid.
  • Boolean Even-4-Parity Problem: Determining if an even number of four Boolean inputs are true.

These problems were chosen because they have previously shown benefits from modularity techniques like ADFs.

Key Insights and Ideas

  • Tag-based modularity is not a universal solution: While beneficial for some problems (like the lawnmower), it can be detrimental to others (like even-4-parity).
  • Argument passing is a major challenge: The simple tag-based approach tested here only supports zero-argument modules. This severely limits its applicability to problems where functions naturally take arguments, as seen in the parity problem.
  • Unbounded recursion is a significant hurdle: Tagging can easily lead to infinite loops, which are heavily penalized in tree-based GP. This penalty can discourage tag usage altogether, even for beneficial modules. PushGP's stack-based nature handles this more gracefully.
  • Silent vs. Non-Silent Tagging: Non-silent tagging showed significant benefits on the lawnmower problem, while silent tagging had mixed results.

Key Results

  • Lawnmower Problem:
    • Non-silent tag-based modularity dramatically improved performance across all measures (success rate, mean best fitness, computational effort) compared to the baseline (no tags, no no-ops).
  • Silent tagging showed some improvement in success rate and computational effort but worse mean best fitness.
  • No-op functions (used as a control) generally worsened performance.
  • Boolean Even-4-Parity Problem:
    • Tag-based modularity (both silent and non-silent) significantly worsened performance across all measures.
  • The simplest condition (no tagging, no no-ops) yielded the best results.

Limitations and Future Work

  • Zero-Argument Modules: The current implementation only supports zero-argument modules, which is a significant limitation. Future work should explore mechanisms for passing arguments to tagged modules, such as "substitution-based" arguments or using tags to simulate arguments.
  • Unbounded Recursion: The penalty for unbounded recursion can hinder tag adoption. Future work should focus on techniques to prevent or mitigate unbounded recursion, such as "un-tagging" code during retrieval or modifying the syntax to avoid depth issues.
  • Program Size and Depth: Tagging increases program size and depth, which can lead to hitting depth limits and negatively impacting performance. Alternative approaches to manage this are needed.
  • Broader Problem Exploration: The authors suggest conducting experiments on a wider range of problems to better understand when and why tag-based modularity is effective.
  • Comparison with ADFs: Comparing tag-based modularity with ADFs on similar problems would be valuable.
  • Applicability to Other GP Variants: The authors believe tag-based modularity could be beneficial in other GP paradigms (e.g., Cartesian GP, grammatical evolution) where the limitations encountered in tree-based GP might not be as severe.

Summary updated

BibTeX
@inproceedings{spector2012tag,
  author = {Lee Spector and Kyle Ira Harrington and Thomas Helmuth},
  title = {{Tag-based modularity in tree-based genetic programming}},
  booktitle = {GECCO},
  year = {2012},
  doi = {10.1145/2330163.2330276},
}

Loading related content...

Figure