TL;DR
This paper introduces novel "gene duplication" and "gene deletion" inspired operations for genetic programming (GP). These operations allow GP to dynamically evolve the architecture of computer programs (how subroutines are structured and called) concurrently with the code within those subroutines, mimicking natural evolution's approach to creating complex structures. This is a significant step towards more automated and flexible program synthesis.
What Problem Does This Paper Address?
The ultimate goal of automatic programming is to create computer programs that solve problems without explicit human programming. Genetic programming (GP) is a powerful technique that evolves programs using principles inspired by biological evolution. While early GP focused on evolving the "work-performing steps" of a program, it often required users to pre-define the program's overall structure (its architecture). This is problematic because determining the optimal architecture (e.g., how many subroutines are needed, how they should be organized) is often as challenging as solving the problem itself. Existing methods for evolving architecture either involved selecting from a pre-defined set of architectures or were less dynamic. This paper tackles the challenge of enabling GP to automatically and dynamically discover and modify the architecture of a multi-part program during the evolutionary process, mirroring how biological evolution creates complex structures through mechanisms like gene duplication.
Methods
The core innovation lies in six new "architecture-altering operations" for genetic programming, inspired by natural gene duplication and deletion. These operations allow a GP system to modify the structure of programs in its population. The key operations include:
- Branch Duplication: Duplicates an existing subroutine (an "automatically defined function" or ADF) and creates a new, identical subroutine. Invocations of the original subroutine can then be randomly switched to call the new one, allowing for potential divergence and specialization.
- Argument Duplication: Duplicates an argument of a subroutine, increasing its dimensionality and allowing for different ways to handle subproblems.
- Branch Creation: Adds a new, empty subroutine to a program.
- Argument Creation: Adds a new argument to an existing subroutine.
- Branch Deletion: Removes an existing subroutine.
- Argument Deletion: Removes an argument from a subroutine.
These operations, when integrated into a GP run, allow programs to grow in complexity (e.g., by adding subroutines or arguments) or shrink, all while the evolutionary process continues to select for fitter individuals. The paper also discusses "structure-preserving crossover" which ensures that even when programs have different architectures, the offspring remain syntactically valid.
Datasets
The paper uses the Boolean even-5-parity function as a benchmark for evaluating the new architecture-altering operations. This function is chosen because it's sensitive to changes in any single input, making it a good test for learning algorithms. The problem involves discovering a program that correctly computes the parity of 5 binary inputs.
Key Insights and Ideas
- Nature as a Blueprint for Program Architecture: The paper draws a powerful analogy between biological evolution's gene duplication and the dynamic evolution of program architecture. This suggests that complex computational structures can arise from simple, iterative modifications, much like life's complexity evolved.
- Decoupling Architecture and Code Evolution: By introducing architecture-altering operations, the paper separates the discovery of how a program should be structured from the discovery of what the program should do. This allows for more flexible and potentially more efficient problem-solving.
- Automatic Specialization and Generalization: Branch duplication, in particular, can be seen as a form of "case splitting." When the duplicated branches diverge, they can specialize to handle different aspects of the problem, akin to how biological genes can evolve new functions after duplication.
- Dynamic Problem Decomposition: The ability to create and modify subroutines on-the-fly allows GP to automatically decompose a problem into subproblems of varying complexity and dimensionality, and then assemble solutions.
Key Results
The paper demonstrates that using the architecture-altering operations (Approach C) significantly reduces computational effort and produces more parsimonious solutions (lower structural complexity, S) compared to GP without automatically defined functions (Approach A). While a fixed, user-defined architecture (Approach E) achieved the lowest computational effort, the architecture-altering approach (C) was competitive and offered the advantage of not requiring prior architectural knowledge. The results show that these operations enable GP to evolve both the structure and content of programs effectively.
Limitations and Future Work
- Computational Cost: While the architecture-altering operations reduce overall computational effort compared to basic GP, they still incur some overhead compared to using a pre-defined, optimal architecture. The paper notes that the cost of architecture-altering operations is not much greater than the cost of "point typing" (a method for handling architectural diversity).
- Parameter Tuning: The paper mentions that other minor parameters were chosen as in Koza 1994a, implying that the performance might be sensitive to the specific settings of these new operations and the overall GP run.
- Future Work: The paper implicitly suggests that further exploration of these operations and their combinations could lead to even more sophisticated program synthesis capabilities. The dynamic nature of these operations opens doors for tackling problems where the optimal structure is unknown or highly complex.
Summary updated