Reproducibility and baseline reporting for dynamic multi-objective benchmark problems

Daniel Herring, Michael Kirley, Xin Yao

TL;DR

This paper introduces the DMOP Parameter Testing Platform (DPTP) to bring much-needed reproducibility and standardized benchmarking to dynamic multi-objective optimization. By systematically mapping the performance of standard evolutionary algorithms across a wide range of change frequencies and severities, the authors establish a "minimum bar" for new algorithms and demonstrate that the common "random restart" baseline is often misleadingly weak.

What Problem Does This Paper Address?

In real-world scenarios, optimization problems are rarely static; objective functions and constraints often shift over time. While researchers have developed many "dynamic" multi-objective evolutionary algorithms (DMOEAs), the field lacks a consistent evaluation framework.

Currently, new algorithms are often tested on a narrow, arbitrary selection of problem instances. Furthermore, they are frequently compared against weak baselines—like non-dynamic algorithms that simply restart from scratch whenever a change occurs. This makes it difficult to determine if a new algorithm offers a genuine breakthrough or if it's simply outperforming a poorly implemented baseline on an "easy" problem. The authors aim to fix this by providing a platform for fine-grained, reproducible experimentation.

Methods

The authors developed DPTP, a MATLAB-based platform extending the existing PlatEMO framework. DPTP allows researchers to systematically vary two key parameters of dynamic problems:

  • Frequency ($\tau_t$): How many generations pass between changes.
  • Severity ($1/n_t$): The magnitude of the change in the problem's landscape.

They conducted an extensive study (over 10,000 runs per repeat) using four classic "static" multi-objective algorithms: NSGA-II, NSGA-III, MOEA/D, and SPEA2. To establish a baseline, they tested these algorithms with four response mechanisms:

  1. DR0 (None): The algorithm continues as-is, naturally adapting through its existing population.
  2. DR1 (Random Addition): 20% of the population is replaced with random solutions after a change.
  3. DR2 (Mutated Addition): 20% of the population is replaced with mutated versions of existing solutions.
  4. DR3 (Random Restart): The entire population is re-initialized after every change.

Performance was measured using Mean Hypervolume Difference (HVD), which tracks the gap between the algorithm's achieved Pareto front and the theoretical optimum just before a change occurs.

Datasets

The study evaluates four representative benchmark problems from the literature:

  • dMOP1 & dMOP2: Standard benchmarks representing different types of dynamics (Type III and Type II).
  • DIMP2: A more complex problem designed to be challenging for diversity maintenance.
  • HE1: A problem with a complex Pareto front shape.

These were chosen to represent a spectrum of difficulty and dynamic characteristics (Type I, II, and III dynamics).

Key Insights and Ideas

  • The "Random Restart" Fallacy: The study proves that "random restart" (DR3) is a terrible baseline. In almost every scenario, static algorithms that simply "do nothing" (DR0) or use minor diversity injections (DR1/DR2) perform significantly better. Using DR3 as a baseline can make a mediocre new algorithm look artificially superior.
  • Identifying "Easy" vs. "Hard" Benchmarks: The authors found that some popular benchmarks, like dMOP1, are essentially "solved" by standard static algorithms across most parameter ranges. Conversely, DIMP2 proved to be a "hard" benchmark where static algorithms failed consistently, making it a much better testbed for novel dynamic-specific methods.
  • Difficulty is a Landscape: Problem difficulty isn't a single number; it's a function of both frequency and severity. The authors use heatmaps to show that performance can vary drastically and non-linearly across this parameter space.
  • Establishing a "Minimum Bar": By mapping the maximum capability of non-dynamic algorithms, the authors provide a clear threshold. A new dynamic algorithm is only truly "useful" if it can outperform these tuned static baselines in the challenging regions of the parameter space.

Key Results

  • Baseline Performance: Figure 1 demonstrates that for dMOP2, the random restart strategy (DR3) is clearly the worst performer across all frequencies and severities. Frequency and severity heatmaps of HVD on dMOP2 for each response type. DR3 (far right) shows significantly darker cells, indicating poorer performance compared to others.
Frequency and severity heatmaps of HVD on dMOP2 for each response type. DR3 (far right) shows significantly darker cells, indicating poorer performance compared to others.
  • Benchmark Difficulty: The heatmaps for dMOP1 (Figure 3) are mostly white/light gray, indicating that standard algorithms achieve near-optimal hypervolume easily. In contrast, the heatmaps for DIMP2 (Figure 4) are almost entirely dark, showing that these same algorithms struggle regardless of the settings. Heatmaps of HVD on dMOP1 (left) vs DIMP2 (right). dMOP1 is largely "white" (easy), while DIMP2 is a "sea of gray" (hard).
Heatmaps of HVD on dMOP1 (left) vs DIMP2 (right). dMOP1 is largely "white" (easy), while DIMP2 is a "sea of gray" (hard).
  • Parameter Recommendations: Based on their results, the authors recommend specific "challenging" parameter ranges for future research. For example, they suggest that for dMOP2, researchers should focus on reciprocal severity values of at least 0.05 to ensure the problem remains difficult enough to justify a specialized dynamic algorithm.

Limitations and Future Work

The authors acknowledge that this study covers only a subset of available benchmarks. They plan to expand DPTP to include more recent and complex benchmark suites (such as SDP, RDP, and JY) and to integrate state-of-the-art purpose-built dynamic algorithms for direct comparison.

The DPTP platform is available on GitHub, and the authors encourage the community to use it to ensure future research in dynamic multi-objective optimization is both rigorous and reproducible.

Summary updated

BibTeX
@inproceedings{herring2022reproducibility,
  author = {Daniel Herring and Michael Kirley and Xin Yao},
  title = {{Reproducibility and baseline reporting for dynamic multi-objective benchmark problems}},
  booktitle = {GECCO},
  year = {2022},
  doi = {10.1145/3512290.3528791},
}

Loading related content...

Figure