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.nthat take a code block (as an argument) and assign it a tagn. - Retrieval Functions: Introducing functions like
tagged.nthat search for and execute the code block associated with the closest matching tagn.
They explore two key implementation details for tree-based GP:
- Silent Tagging: The
tag.nfunction returns a default value without executing the tagged code. - Non-Silent Tagging: The
tag.nfunction executes the tagged code and returns its result.
They also address potential issues like:
- Return Values: How
tag.nandtagged.nfunctions 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