TL;DR
This paper introduces an improved local search algorithm, Iterated Greedy Local Tree Improvement (IGLTI), for Genetic Programming (GP). IGLTI excels at finding smaller, more concise program solutions by incorporating semantic information and a greedy approach to tree improvement, outperforming previous methods on both Boolean and categorical benchmarks.
What Problem Does This Paper Address?
Genetic Programming (GP) aims to evolve computer programs (represented as trees) that solve specific problems. A major challenge in GP is finding solutions that are not only accurate but also small and interpretable. Larger programs are often harder to understand and can suffer from overfitting. Traditional local search methods in GP can get stuck in local optima or are computationally expensive. This paper addresses the need for efficient local search algorithms that can discover smaller, high-quality solutions by leveraging the "semantics" of program subtrees. Semantic GP approaches consider the actual behavior of subtrees, not just their structure, to guide the search.
Methods
The core of this work is the Iterated Greedy Local Tree Improvement (IGLTI) algorithm. It builds upon the Semantic Backpropagation (SB) concept, which calculates optimal "should-be" values for each subtree to guide the search.
Here's a breakdown of the key methods:
- Semantic Backpropagation (SB): This technique analyzes each node (and its subtree) within a program tree. It determines the ideal output values for that node, assuming the rest of the tree is optimal. This allows for a more informed evaluation of subtree quality.
- Greedy Local Tree Improvement (GLTI): This is the core improvement procedure. For a given node in the program tree, GLTI searches a pre-defined "subtree library" for the best replacement. The "best" replacement is defined by two criteria:
- Minimizing local error: The replacement should lead to the greatest improvement in the node's local fitness (how well it matches its target "should-be" value).
- Minimizing size increase: If multiple replacements offer the same local error improvement, the one that results in the smallest increase in the overall tree size is chosen. This directly addresses the goal of finding smaller solutions.
- Iterated GLTI (IGLTI): GLTI is applied iteratively to the same program tree. This means the algorithm repeatedly refines the program by making greedy local improvements, aiming to converge towards a small, accurate solution.
- Subtree Library: A crucial component is the library of candidate subtrees. The paper explores libraries built from subtrees of varying depths (e.g., depth 2 or depth 3). The library is ordered by tree size, ensuring that smaller subtrees are considered first when multiple options offer similar improvements.
- Modified ILTI: The authors also mention a modification to a previous algorithm (Iterated Local Tree Improvement - ILTI) to prevent infinite loops by ensuring a library tree isn't repeatedly inserted at the same position.
Datasets
The paper evaluates IGLTI on two types of benchmarks:
- Boolean Benchmarks: These include standard problems like the Comparator (Cmp), Majority (Maj), Multiplexer (Mux), and Parity (Par) problems, with variations in input bit sizes (e.g., 6-bit and 8-bit).
- Categorical Benchmarks: These are based on finite algebras, specifically focusing on problems involving ternary (3-valued) or quaternary (4-valued) domains. Examples include discriminator term tasks and MalâĂŹcev term tasks for algebras like A4 and B1. These benchmarks are more challenging due to the discrete, non-binary nature of the values.
Key Insights and Ideas
- Greediness for Size Reduction: The paper demonstrates that a greedy approach, prioritizing both local fitness improvement and minimal size increase, is highly effective for finding compact solutions in GP.
- Semantic Information is Key: Leveraging semantic information (how subtrees actually behave) is crucial for guiding local search effectively, allowing it to make more informed decisions than purely structural approaches.
- Library Depth Trade-off: While a larger library (e.g., depth 3 vs. depth 2) can sometimes lead to better solutions, it's not always the case. The paper suggests that an overly large library might lead the greedy algorithm away from the globally optimal small solution by getting "stuck" on locally good but not globally optimal improvements.
- Categorical Domains are Tractable: IGLTI shows strong performance on categorical benchmarks, which are often more complex than Boolean ones, indicating the robustness of the semantic approach.
Key Results
- Smaller Solutions: IGLTI consistently found smaller program solutions (measured by the number of nodes) compared to the baseline ILTI algorithm across both Boolean and categorical benchmarks. For instance, on the Mux06 benchmark, IGLTI found solutions of identical size.
- Improved Performance on Categorical Benchmarks: IGLTI outperformed all known results for three variable finite algebras, finding solutions that are small enough for human mathematicians to analyze.
- Runtime: While IGLTI generally found better (smaller) solutions, the modified ILTI algorithm was faster in terms of runtime. This suggests a trade-off between solution quality (size) and computational speed.
- Spread of Solutions: The spread of solution sizes was generally narrower for IGLTI, indicating more consistent performance.
Limitations and Future Work
- Greediness: The authors acknowledge that the greedy nature of IGLTI might sometimes lead it away from the best solutions.
- Future Work:
- Less Greedy IGLTI: Developing modifications to IGLTI to make it less greedy, perhaps by incorporating more stochasticity to accept slightly worse intermediate results, is a promising direction.
- Dynamic Libraries and Populations: Exploring dynamic libraries and population-based approaches, similar to those in other semantic GP schemes, could further enhance performance.
- Pseudo-inverse Functions: Further testing of pseudo-inverse functions within different semantic frameworks is suggested.
Summary updated