TL;DR
This paper investigates how local search (LS) techniques can be effectively integrated with evolutionary algorithms (EAs) in a Black-Box Optimization (BBO) setting. They introduce "Optimal Mixing" (OM) as a superior method for combining LS and EAs, demonstrating its effectiveness in improving performance and reducing computational cost compared to traditional approaches.
What Problem Does This Paper Address?
Evolutionary Algorithms (EAs) are powerful for exploring complex search spaces, but can be slow to converge. Local Search (LS) techniques excel at quickly finding good solutions within a local neighborhood but can get stuck in local optima. Combining them, as in Memetic Algorithms (MAs) or Evolutionary Local Search (ELS), often yields better results than either alone. However, a key advantage of LS is its ability to use "partial evaluations" – quickly assessing the impact of small changes – which is often not possible in a Black-Box Optimization (BBO) setting where the internal structure of the problem is unknown. This paper explores how LS, model building (like in Estimation-of-Distribution Algorithms - EDAs), and a novel integration strategy called "Optimal Mixing" (OM) perform in this challenging BBO context, aiming to find the best way to leverage their strengths without problem-specific knowledge.
Methods
The authors explore several combinations of EAs and LS techniques, focusing on their performance in a BBO setting. Key methods include:
- Evolutionary Algorithms (EAs): Simple Genetic Algorithm (SGA), Extended Compact Genetic Algorithm (ECGA), and Linkage Tree Genetic Algorithm (LTGA).
- Local Search (LS): Hill Climbing (HC) variants (simple, steepest ascent, and a combination) applied to different variable structures (univariate, Marginal Product Model - MPM, Linkage Tree - LT).
- Model Building: Primarily using MPMs and LTs to identify dependencies (linkage) between variables.
- Optimal Mixing (OM): A novel approach where LS is integrated directly into the variation operator. Instead of generating a full offspring and then evaluating it, OM clones a parent and iteratively improves it by incorporating partial solutions. Each improvement step is checked, ensuring that the solution quality monotonically improves during variation. This is contrasted with traditional MA/ELS approaches where LS is applied after variation.
- Population-based Local Search (PLS) and Population-based Best Only Local Search (PBOLS): These are presented as more traditional LS approaches that utilize a population, bridging the gap between single-solution LS and EAs.
Datasets
The paper uses two standardized, "GA-hard" benchmark problems for evaluation:
- Deceptive Trap Functions: These are additively decomposable functions where detecting and exploiting linkage between variables is crucial for efficient optimization. The authors use subfunctions with k=5.
- NK Landscapes: Specifically, an additively decomposable composition of predetermined, but random, subfunctions of length k=5 with a maximum overlap of 4. This benchmark allows for controlled analysis of interdependencies.
Both problems are treated as BBO problems, meaning no partial evaluations are possible.
Key Insights and Ideas
- Optimal Mixing (OM) is a Superior Integration Strategy: The paper strongly suggests that OM, which fuses LS directly into the variation operator, is more effective than traditional MA/ELS approaches where LS is applied post-variation. OM ensures that variation itself leads to improvements, mimicking LS's local exploitation.
- Model Building Enhances LS and EA Performance: Identifying variable dependencies (linkage) through model building (MPM, LT) significantly improves the effectiveness of LS, especially when applied substructurally (following the identified dependencies). This reduces noise and the required population size for EAs.
- Substructural LS is Key: Applying LS based on identified variable dependencies (substructural LS) is more beneficial than univariate LS (e.g., bit-flipping) for complex problems with linkage.
- LTGA/LT-GOMEA is a Promising Algorithm: The Linkage Tree Genetic Algorithm (LTGA), which uses Optimal Mixing and a Linkage Tree for model building, emerges as a highly competitive algorithm, often outperforming others.
- BBO Constraints Matter: The absence of partial evaluations in BBO significantly impacts the performance of LS-heavy approaches. OM's ability to integrate LS directly into variation helps mitigate this.
- Population-Based LS can be Efficient for Separable Problems: For highly separable problems like the trap functions, population-based LS methods (like PBOLS) can outperform EAs, highlighting the trade-off between exploration (EA) and exploitation (LS).
Key Results
- OM Outperforms MA/ELS: Optimal Mixing (OM) consistently led to better performance (fewer evaluations, faster runtime) compared to traditional MA/ELS approaches across the tested problems.
- LT-GOMEA is Highly Competitive: LT-GOMEA (an implementation of OM with a Linkage Tree) was found to be superior on both benchmark problems, often requiring fewer function evaluations and less computation time.
- Substructural LS Improves Scalability: Algorithms employing substructural LS (following LT or MPM structures) showed better scalability and performance on the NK landscapes compared to univariate LS.
- Population Size Reduction: Integrating LS, especially with model building, generally led to a significant reduction in the required population size for EAs.
- Trap Functions vs. NK Landscapes: The performance of algorithms varied significantly between the two problem types, underscoring the importance of problem structure (separability vs. overlapping dependencies) in algorithm design. For trap functions, LS-heavy approaches excelled, while for NK landscapes, EA-like approaches with effective model building and OM were superior.
Limitations and Future Work
- BBO Focus: The study is conducted from a BBO perspective, meaning partial evaluations are not possible. The authors acknowledge that the results might differ in non-BBO settings where partial evaluations are feasible, though they hypothesize OM would still remain strong.
- Further Testing of OM: The authors suggest future work should involve testing OM on specific combinatorial optimization problems, both in a problem-specific manner and from a BBO perspective.
- Exploring Stochastic LS: The paper briefly mentions Stochastic Hill Climbing (SHC) and its relation to GOMEA, suggesting further exploration of stochastic LS variants within the GOMEA framework.
- Model Building as a "Powertool": The linkage tree is highlighted as a powerful tool for model building, and future work could involve further leveraging its capabilities.
Summary updated