TL;DR
This paper introduces HMO-CMA-ES, a novel hybrid algorithm designed for efficient bi-objective optimization across a wide range of problems. By combining multiple CMA-ES variants and a warm-start strategy, it achieves strong "anytime" performance, meaning it provides good solutions even when computation time is limited.
What Problem Does This Paper Address?
Optimizing functions with multiple objectives (bi-objective optimization) is a challenging task. Unlike single-objective optimization where the goal is a single best solution, multi-objective problems often result in a set of "Pareto optimal" solutions, each representing a different trade-off between the objectives. The "anytime" aspect adds another layer of complexity: an algorithm needs to be effective not just at the end of a long computation, but also at intermediate stages. This means it should deliver reasonably good solutions quickly and continue to improve them as more computational resources (like function evaluations) become available. Existing methods might excel at one aspect but struggle with the other. This paper aims to bridge this gap by developing an algorithm that is robust and performs well across diverse bi-objective problems, providing good solutions at any point in time.
Methods
The core of the proposed algorithm, HMO-CMA-ES, is a hybrid approach that strategically combines several components:
- BOBYQA as a Warm Start: The algorithm begins by using BOBYQA, a trust-region method, to quickly find an initial approximation of the Pareto front. This is achieved by optimizing a scalarized version of the bi-objective function (a weighted sum of the two objectives) with different weights. This provides a good starting point for subsequent, more sophisticated algorithms.
- Steady-State MO-CMA-ES with Increasing Population Size: This component, referred to as ss-MO-CMA-ES, is a multi-objective version of the popular CMA-ES algorithm. It operates in a steady-state manner (updating the population incrementally) and gradually increases its population size. This helps in efficiently exploring the search space and covering the Pareto front.
- CMA-ES with Restarts on Scalarized Objectives: This variant, restart-CMA-ES, applies the standard CMA-ES algorithm to different scalarized versions of the bi-objective function. By restarting with new random aggregation coefficients, it aims to explore different parts of the Pareto front.
- Generational MO-CMA-ES with Restarts (IPOP-MO-CMA-ES): This is another multi-objective CMA-ES variant that doubles its population size after each restart. This approach is designed to improve performance with larger computational budgets.
These components are integrated into a four-phase algorithm. They are often run in parallel, with solutions from some components being injected into others to facilitate information sharing and improve overall performance.
Datasets
The paper evaluates HMO-CMA-ES on the COCO (COmparing Continuous Optimizers) framework's bi-objective problem suite (bbob-biobj). This benchmark suite consists of 55 scalable bi-objective functions, designed to cover a wide range of optimization challenges. These functions are formed by combining 10 different single-objective functions, resulting in diverse characteristics like high conditioning and multi-modality. The suite includes multiple instances and dimensions (e.g., 2D, 5D, 10D, 20D) for comprehensive evaluation.
Key Insights and Ideas
- Hybridization is Key for Anytime Performance: The paper strongly suggests that combining different optimization strategies is crucial for achieving good performance across a wide range of computational budgets (anytime performance). No single algorithm seems to be universally superior.
- Warm-Starting is Effective: Using a simpler, faster algorithm like BOBYQA to get an initial approximation of the Pareto front significantly benefits the subsequent, more complex algorithms.
- Parallelism and Information Sharing Enhance Robustness: Running different CMA-ES variants in parallel and allowing them to share information (e.g., injecting solutions) helps in covering more ground and improving the overall robustness of the optimizer.
- The Challenge of Balancing Exploration and Exploitation: The design of HMO-CMA-ES reflects a careful balance between exploring diverse regions of the Pareto front (via restarts and different scalarizations) and exploiting promising areas (via steady-state updates and population growth).
Key Results
The paper presents extensive results on the bbob-biobj benchmark suite. Key findings include:
- High Success Rate: HMO-CMA-ES successfully solves almost all of the 55 bi-objective problems in the benchmark suite, finding high-quality solution sets for most combinations of problem type and search space dimension, especially with larger computational budgets.
- Good Anytime Performance: The algorithm demonstrates strong performance across various computational budgets, as visualized by the empirical cumulative distribution plots of runtimes. It achieves good hypervolume values relatively early and continues to improve them.
- Efficiency: The paper reports CPU timing results, indicating that the algorithm is computationally efficient, with per-function-evaluation times in the order of microseconds.
- Comparison to Individual Components: While the hybrid approach is generally superior, the authors acknowledge that on some specific functions or at certain computational budgets, individual components of HMO-CMA-ES might outperform the entire hybrid. This is attributed to the "price of hybridization."
Limitations and Future Work
- Hyperparameter Tuning: The authors note that the algorithm has several hyperparameters (e.g., phase durations, restart frequencies) that are set as multiples of the problem dimension
n. Better tuning of these could potentially improve performance. - Adaptive Stopping Criteria: The fixed iteration counts for different phases could be replaced with adaptive stopping criteria for more flexibility.
- Online Prioritization: The authors suggest that further improvements could be made by dynamically prioritizing individual components based on their relative performance during the optimization process. This would help mitigate cases where individual components might outperform the hybrid.
- Comparison to Other State-of-the-Art: The paper mentions that a full comparison with other state-of-the-art multi-objective algorithms would be available once the results of the bbob-biobj 2016 edition are released.
Summary updated