Abstract
Evolutionary Algorithms (EAs) often struggle to balance exploitation and exploration, particularly in hierarchical optimization problems. This paper introduces GI-GOMEA, an algorithm that integrates Gene-invariance (GI) into the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA). By ensuring that no genetic material is lost from the population, GI-GOMEA maintains diversity without requiring massive populations. Our results demonstrate that GI-GOMEA can solve complex hierarchical problems that are intractable for standard GOMEA, though it faces specific challenges in bimodal landscapes.
Introduction
In discrete optimization, the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) has emerged as a powerful tool due to its "Optimal Mixing" (OM) operator. OM acts as a greedy local search, efficiently exploiting promising regions of the search space. However, this high selection pressure often leads to premature convergence, especially in hierarchical problems where essential "building blocks" for higher-level solutions may be discarded early in the search process. To address this, researchers have introduced Gene-invariance, a technique that ensures genetic diversity is preserved throughout the evolutionary process.
Methods: Preserving Genetic Diversity
GI-GOMEA addresses the diversity loss in standard GOMEA by incorporating the principle of Gene-invariance (GI). Unlike standard EAs that replace parents with offspring, GI-GOMEA performs variations directly within the population.
Key technical components include:
- Probabilistically Complete (PC) Initialization: The population is initialized such that every bit position has an exact 50/50 split of 0s and 1s, ensuring all genetic material is present at the start.
- GI-GOM Operator: When a "parent" and a "mate" swap genes based on a linkage model, the algorithm ensures that the total count of 0s and 1s in the population for every position remains constant. This preservation of genetic material allows the algorithm to "rediscover" necessary building blocks at later stages of the hierarchy.
- Linkage Trees (LT): The algorithm uses hierarchical models, built using Mutual Information (MI) or prior knowledge, to decide which groups of genes should be moved together.
Experimental Results and Scalability
The effectiveness of GI-GOMEA was evaluated across several benchmarks, including deceptive traps and hierarchical functions. A key finding is the algorithm's superior scalability. As illustrated in Figure 1, GI-GOMEA achieves successful convergence with significantly smaller population sizes compared to standard GOMEA. On hierarchical problems like HTrap3, where standard GOMEA fails as dimensionality increases, GI-GOMEA maintains robust performance.
The Pitfall of Symmetry and Solving the "Unsolvable"
Interestingly, the authors noted a "cheating" behavior on perfectly symmetric problems like HIFF. Due to the GI property, GI-GOMEA can solve such problems with a population of only two, as the complement of any local optimum is guaranteed to exist. To provide a more rigorous evaluation, the authors introduced asymmetric variants (e.g., AsymHTrap4). GI-GOMEA continued to demonstrate its ability to solve these previously "unsolvable" hierarchical structures because it preserves the "discarded" building blocks from lower levels.
Limitations and Bimodal Landscapes
Despite its strengths, GI-GOMEA exhibits a "negative scaling" effect on bimodal trap problems. Because the algorithm preserves but does not replicate alleles, it relies solely on moving existing building blocks between individuals. In bimodal landscapes, this can lead to a quadratic increase in mixing attempts to correctly align the necessary components. Figure 2 highlights these performance characteristics across different trap variants, showing how evaluations scale with population size.
Conclusion
GI-GOMEA represents a significant step forward in model-based evolutionary optimization. By shifting the focus from population size to genetic preservation, it offers a more efficient path to solving complex hierarchical problems, often requiring 10x smaller populations than standard GOMEA. Future research will focus on fitness-based linkage learning to better handle the "preserved noise" inherent in gene-invariant populations, making the algorithm even more robust for real-world NP-hard problems.
Summary updated