A Steady Performance Stopping Criterion for Pareto-based Evolutionary Algorithms

Olga Roudenko, Marc SchoenauerHAL 2004

TL;DR

This paper introduces a novel stopping criterion for multi-objective evolutionary algorithms (MOEAs) that aims to prevent wasted computation by detecting when an algorithm is no longer making significant progress. By monitoring the stability of the "crowding distance" – a measure of diversity among non-dominated solutions – the proposed method can automatically halt the search when further iterations are unlikely to yield substantial improvements, thus improving practical efficiency.

What Problem Does This Paper Address?

When solving multi-objective optimization problems, the goal is to find a set of solutions that represent the best possible trade-offs between competing objectives. Evolutionary algorithms (EAs) are powerful tools for this, but a crucial practical challenge is knowing when to stop the search. Unlike single-objective EAs that can often stop when the solution quality plateaus, multi-objective EAs deal with a set of solutions (the Pareto front), making "plateauing" harder to define. A common approach is to simply run the algorithm for a fixed number of generations, but this can lead to either stopping too early (missing good solutions) or running for far too long without meaningful progress, wasting valuable computational resources. This paper tackles the problem of developing an automatic, adaptive stopping criterion for Pareto-based EAs that signals when the algorithm is "stuck" or "wedged" and unlikely to find significantly better compromises.

Methods

The core of the proposed method lies in adapting the "steady-fitness" stopping criterion from single-objective EAs to the multi-objective domain. Since fitness is population-dependent in multi-objective EAs, the authors focus on a measure of diversity among the non-dominated solutions. Specifically, they leverage the crowding distance, a metric used in algorithms like NSGA-II to ensure a well-spread distribution of solutions along the Pareto front.

The proposed stopping criterion is based on the stabilization of the maximal crowding distance. The intuition is that as the algorithm approaches the true Pareto front and the solutions become more uniform, the crowding distance will eventually stabilize. The authors introduce a stability measure based on the standard deviation of the maximal crowding distance over a sliding window of L generations. The algorithm is stopped when this standard deviation falls below a predefined threshold (Slim). This approach aims to smooth out oscillations and provide a more robust signal of convergence than simply looking at the raw maximal crowding distance.

Datasets

The proposed stopping criterion was evaluated using the well-known ZDT benchmark functions (ZDT1, ZDT2, ZDT3, and ZDT4). These are standard test problems in evolutionary multi-objective optimization, designed to represent different challenges such as convex, concave, and discontinuous Pareto fronts, as well as problems with multiple local Pareto fronts (ZDT4). No new benchmarks were introduced.

Key Insights and Ideas

  • Crowding Distance as a Proxy for Progress: The paper cleverly uses the crowding distance, a measure of diversity, as an indirect indicator of progress towards the Pareto front. When the crowding distance stabilizes, it suggests that the algorithm is no longer effectively spreading solutions or finding new, better-compromised solutions.
  • "Steady Performance" is Achievable: The concept of a "steady-fitness" stopping criterion, common in single-objective optimization, can be adapted to multi-objective EAs by focusing on the stability of diversity measures.
  • ZDT4 Highlights "Wedged" Situations: The ZDT4 benchmark, with its multiple local Pareto fronts, effectively demonstrates the algorithm's ability to detect when NSGA-II gets "stuck" on a local optimum and prevent further useless iterations.
  • Parameter Sensitivity: The choice of parameters L (window size) and Slim (threshold) is crucial and needs to be adjusted based on factors like population size and the desired trade-off between stopping too early or too late.

Key Results

The paper presents experimental results demonstrating the effectiveness of the proposed stopping criterion on the ZDT benchmarks.

  • Convergence: For ZDT1, ZDT2, and ZDT3, the algorithm, when stopped by the proposed criterion, consistently found very good approximations of the exact Pareto fronts.
  • Efficiency: The criterion successfully stopped the algorithm in a reasonable number of generations, avoiding excessively long runs. For instance, for ZDT1, the average number of generations was 98, for ZDT2 it was 116, and for ZDT3 it was 110.
  • Interruption of "Wedged" Runs: For ZDT4, the criterion effectively detected when the algorithm was trapped on a local Pareto front, preventing further iterations. Figure 10 shows a run being stopped at generation 214, after which no significant improvement was observed.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that the choice of L and Slim is critical and suggest that these parameters depend on population size and the desired application context. They provide general suggestions but emphasize that fine-tuning might be necessary.
  • NSGA-II Specificity: The current study is limited to the NSGA-II algorithm. The authors note that the diversity-preserving mechanisms of other EMAs might differ, and the proposed criterion might need adaptation.
  • Higher Dimensions: The visual analysis of population dynamics, used in this study, becomes impossible for problems with more than two objectives. Future work will involve adapting the criterion to other EMAs like SPEA2 and testing its applicability to problems with 3-4 objectives, potentially using "running metrics" to evaluate performance.
  • Generalizability: While tested on common benchmarks, the authors suggest further research to establish the criterion's applicability across a wider range of multi-objective problems and algorithms.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{roudenko2004steady,
  author = {Olga Roudenko and Marc Schoenauer},
  title = {{A Steady Performance Stopping Criterion for Pareto-based Evolutionary Algorithms}},
  booktitle = {HAL},
  year = {2004},
}
Figure