Abstract: Dynamic multi-objective optimization problems (DMOPs) present unique challenges due to time-varying objective functions and constraints. However, the evaluation of purpose-built algorithms for DMOPs often lacks rigor, relying on narrow problem selections and weak baselines. This paper introduces the DMOP Parameter Testing Platform (DPTP), an extension of PlatEMO, designed to facilitate reproducible and standardized benchmarking. By systematically mapping the performance of standard evolutionary algorithms across a wide range of change frequencies and severities, we establish a "minimum bar" for specialized dynamic algorithms. Our analysis reveals that the common "random restart" baseline is often misleadingly weak and identifies significant variations in benchmark difficulty across the parameter space.
Introduction
In real-world optimization scenarios, objective functions and constraints are rarely static. Dynamic multi-objective optimization problems (DMOPs) require algorithms to adapt to changes over time. While many specialized dynamic multi-objective evolutionary algorithms (DMOEAs) have been developed, the field suffers from a lack of consistent evaluation frameworks. New algorithms are frequently tested on arbitrary problem instances and compared against weak baselines, such as non-dynamic algorithms that simply restart upon change. This makes it difficult to discern genuine algorithmic breakthroughs from artifacts of poor baseline selection.
The DPTP Platform
We present the DMOP Parameter Testing Platform (DPTP), a MATLAB-based tool extending the PlatEMO framework. DPTP allows for fine-grained control over dynamic problem parameters, specifically:
- Frequency ($\tau_t$): The number of generations between environmental changes.
- Severity ($1/n_t$): The magnitude of the change in the problem landscape.
By systematically varying these parameters, researchers can generate performance heatmaps that provide a comprehensive view of an algorithm's capabilities across the entire difficulty landscape.
Experimental Setup
To establish a baseline, we evaluated four classic multi-objective evolutionary algorithms (MOEAs): NSGA-II, NSGA-III, MOEA/D, and SPEA2. We tested these algorithms with four response mechanisms to handle environmental changes:
- DR0 (None): The algorithm continues without explicit change handling, relying on natural selection.
- DR1 (Random Addition): 20% of the population is replaced with random solutions after a change.
- DR2 (Mutated Addition): 20% of the population is replaced with mutated versions of existing solutions.
- 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.
The "Random Restart" Fallacy
A critical insight from our study is that the "random restart" (DR3) strategy is often a poor baseline. As shown in Figure 1 for the dMOP2 benchmark, DR3 consistently exhibits the highest HVD (darkest cells) across all frequencies and severities. Static algorithms that either do nothing (DR0) or use minor diversity injections (DR1/DR2) perform significantly better. Using DR3 as a primary baseline can make mediocre new algorithms appear artificially superior.
Benchmark Sensitivity and Difficulty
Our results demonstrate that problem difficulty is a function of both frequency and severity. Some benchmarks, like dMOP1, are essentially "solved" by standard algorithms across most parameter ranges. Conversely, the DIMP2 benchmark (Figure 2) remains consistently difficult, with standard algorithms struggling to maintain performance regardless of the settings. This highlights the need for researchers to select benchmarks that are sufficiently challenging to justify specialized dynamic mechanisms.
Conclusion and Future Work
By mapping the maximum capability of non-dynamic algorithms, DPTP provides a clear "minimum bar" for the development of new DMOEAs. A specialized algorithm is only truly useful if it can outperform these tuned static baselines in challenging regions of the parameter space. Future work will expand DPTP to include more complex benchmark suites and state-of-the-art dynamic algorithms. The platform is available on GitHub to support community-wide adoption of reproducible benchmarking practices.
Summary updated