TL;DR
This paper explores how to improve genetic programming (GP) by strategically duplicating "coding segments" within chromosomes. By removing non-coding segments and then replicating the essential coding parts, they found a significant speedup in learning for the clique detection problem, suggesting a generalizable method for enhancing GP performance.
What Problem Does This Paper Address?
Genetic programming (GP), like genetic algorithms (GAs), uses evolutionary principles to evolve computer programs. A key challenge in GP is identifying and preserving "building blocks" – fundamental components of a solution that, when combined, lead to better fitness. Non-coding segments (analogous to introns in biology) have been proposed to protect these building blocks from destructive crossover operations, which can randomly break up chromosomes. However, simply removing non-coding segments can lead to premature convergence, as it strips away this protective mechanism. This paper investigates a method to overcome this by not just removing non-coding segments but then actively duplicating the essential coding segments to reinforce them.
Methods
The core of the proposed method involves two main steps:
- Removal of Non-Coding Segments: The GP chromosome is first processed to identify and remove any non-coding segments. These are defined as parts of the chromosome that do not contribute to the calculation of the individual's fitness.
- Duplication of Coding Segments: After removing the non-coding parts, the remaining "coding segments" (those essential for fitness) are duplicated. These duplicated segments are then spliced back into the chromosome. The paper explores varying the number of duplications.
This process is applied during the "repair" phase, which occurs during chromosome evaluation. The authors also contrast this with simple repair mechanisms that only remove non-coding segments without duplication.
Datasets
The primary benchmark used in this paper is the clique detection problem on a 10-node graph. This problem was chosen because it allows for the enumeration of all building blocks, facilitating a controlled study of how duplication affects their evolution. The authors note that the principles are intended to be generalizable to other GP domains.
Key Insights and Ideas
- Non-coding segments are a double-edged sword: While they protect building blocks from destructive crossover, their complete removal can hinder the recombination and evolution of these blocks.
- Duplication as a reinforcement strategy: Instead of just removing non-coding segments, duplicating the essential coding segments acts as a form of "reinforcement learning" at the genetic level, making building blocks more robust.
- Phenotype vs. Genotype: The paper highlights that duplicated coding segments can result in different genotypes (chromosome structures) that evaluate to the same phenotype (fitness), demonstrating the flexibility of GP representations.
- Repair mechanism's impact: The timing and nature of the repair process (e.g., whether repaired chromosomes are returned to the population) can significantly influence performance.
Key Results
- Premature Convergence Avoided: Complete removal of non-coding segments led to premature convergence.
- Improved Learning Rate: Duplicating coding segments significantly sped up the learning process for the clique detection problem.
- Effect of Duplication Count: Increasing the number of duplicates of coding segments led to progressively faster learning. For instance, using three duplicates resulted in a significant savings of 108 generations compared to a base case, and seven duplicates saved 183 generations.
- Repair Rate Interaction: The learning rate increased with higher repair rates when multiple duplicates were added, contradicting some previous findings.
- Significant Speedups: With seven copies of the coding segment, the computational effort to find the optimal solution was at least halved, and in some cases, an 84% increase in finding the optimal solution was observed over the base case.
Limitations and Future Work
- Domain Specificity Questioned: While the clique detection domain is well-suited for studying building blocks, the authors assert that their results are not domain-dependent and can be applied to any GP domain.
- Repair Rate Sensitivity: The paper notes that repair rates greater than 0.5% (which are considered small and desirable) either degraded performance or caused premature convergence in some scenarios, suggesting a need for careful tuning.
- Future Work: The authors plan to investigate extending this approach to propositional inference domains, where linear non-coding segments naturally appear and building blocks are harder to identify. They also propose exploring new crossover functions that could incorporate repair and duplication more directly into the reproduction stage.
Summary updated