TL;DR
This paper introduces novel parent selection strategies for the Multi-Objective Covariance Matrix Adaptation Evolution Strategy (MO-CMA-ES) to accelerate its convergence on complex optimization problems. By adapting principles from tournament selection and Multi-Armed Bandits, the proposed methods significantly outperform existing MO-CMA-ES variants, especially on unimodal problems, by more intelligently choosing which parent should generate the next offspring.
What Problem Does This Paper Address?
Multi-objective optimization (MOO) problems involve finding solutions that simultaneously optimize multiple, often conflicting, objectives. The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is a powerful algorithm for single-objective continuous optimization, and its multi-objective extension, MO-CMA-ES, has shown promise. However, standard MO-CMA-ES can be slow to converge. Specifically, the steady-state variants (SS-MO-CMA-ES), which generate one offspring at a time, rely on a simple parent selection mechanism (e.g., uniform random selection). The authors hypothesize that not all parents are equally valuable for generating offspring that lead to rapid progress towards the Pareto front. They aim to improve the efficiency of SS-MO-CMA-ES by developing more sophisticated parent selection strategies that can better identify "good" parents.
Methods
The paper proposes new parent selection operators for SS-MO-CMA-ES, which are integrated into the existing framework at line 4 of Algorithm 1. These operators consist of two main components: a selection mechanism and a rewarding procedure.
- Selection Mechanisms:
- Tournament Selection: A standard approach where a small subset of parents is randomly selected, and the "best" among them (based on MOO criteria like Pareto rank and hypervolume contribution) is chosen as the parent. The paper explores tournament sizes of 2 and 10.
- Multi-Armed Bandit (MAB) Inspired Selection: This approach borrows from MAB theory, where each parent is an "arm" and the goal is to maximize cumulative rewards. The algorithm balances "exploration" (trying less-selected parents) and "exploitation" (choosing parents that have historically yielded good results). The reward is based on a time-windowed average of past performance.
- Rewarding Procedures: These procedures assign a "reward" to parents based on the quality of their offspring. The paper investigates several reward definitions:
- (μ + 1succ): A binary reward: 1 if the offspring survives to the next generation, 0 otherwise.
- (μ + 1rank): A rank-based reward, where the reward depends on the Pareto rank of the offspring.
- (μ + 1ΔH₁): Rewards based on the increase in the hypervolume contribution of the offspring.
- (μ + 1ΔH;): A refined hypervolume-based reward that also considers dominated points and penalizes based on Pareto rank.
The paper then combines these selection mechanisms with the reward definitions to create new variants of SS-MO-CMA-ES, such as (μ + 1rank)-MO-CMA.
Datasets
The paper evaluates the proposed algorithms on the following benchmark problems:
- ZDT1-3, ZDT6: Standard bi-objective problems.
- Rotated Variants (IHR1-3, IHR6): Rotated versions of ZDT problems.
- LZ09-1-5: A set of benchmark problems with complicated Pareto fronts in the decision space.
The authors also mention using shifted ZDT problems (sZDT) for an unbiased assessment.
Key Insights and Ideas
- Parental Value Varies: The core idea that not all parents are equal is validated. Intelligent selection of parents can significantly speed up convergence.
- MAB for Dynamic Environments: Adapting MAB principles to the non-stationary environment of evolutionary algorithms (where the Pareto front is constantly evolving) is a promising direction. The trade-off between exploration and exploitation is crucial.
- Hypervolume Contribution is Key: Rewards based on hypervolume contribution, especially the refined (μ + 1ΔH;) version, tend to be more robust and effective than simpler rewards.
- Greediness vs. Diversity: While greedy selection strategies (like tournament selection with larger sizes or MAB with high exploitation) excel on unimodal problems, they can lead to premature convergence and loss of diversity on multi-modal or problems with easily reachable segments of the Pareto front.
- Steady-State Advantage: Steady-state variants of MO-CMA-ES generally outperform their generational counterparts on unimodal benchmark problems.
Key Results
- The proposed SS-MO-CMA-ES variants, particularly (μ + 1rank)-MO-CMA and (μ +10 1)-MO-CMA, generally outperform baseline MO-CMA-ES algorithms.
- On unimodal problems (sZDT, IHR), the new methods achieve significantly better performance, often requiring fewer function evaluations to reach a target precision. For example, (μ + 1rank)-MO-CMA on sZDT1 and IHR1 shows a substantial speedup compared to the baseline (μ + 1)-MO-CMA.
- The (μ + 1rank)-MO-CMA variant is highlighted for its robustness and ability to approximate Pareto fronts well, even matching the performance of other MOEAs on LZ09 problems.
- However, on problems with concave or disconnected Pareto fronts (like LZ09-5), greedy strategies can suffer from premature convergence, leading to a loss of diversity.
Limitations and Future Work
- Premature Convergence: The paper acknowledges that the proposed greedy parent selection strategies can lead to premature convergence and loss of diversity on multi-modal or problems with easily reachable Pareto front segments. This is partly attributed to the non-dominated sorting and fixed population size.
- Future Work:
- Maintaining Diversity: Developing strategies to preserve diversity, possibly by keeping points at the border of the explored region or by using techniques similar to BIPOP-CMA-ES (which uses a large exploration population and a small exploitation population).
- Integrated Reward Mechanisms: Tighter integration of the reward mechanism with the internal update rules of CMA-ES. This could involve using success rates for parental selection or incorporating information from discarded offspring into the covariance matrix updates.
- Comparison with State-of-the-Art: Further comparison with other advanced MOEAs, such as SMS-EMOA, and extending the proposed ideas to non-separable problems.
- Handling Borderline Points: Developing methods to handle and assign rewards to points that are on the border of the explored region.
Summary updated