A Comprehensive Overview of Holt’s Differential Prediction Correction-Based Dynamic Multi-Objective Optimization Algorithm

0
0
0

A Comprehensive Overview of Holt’s Differential Prediction Correction-Based Dynamic Multi-Objective Optimization Algorithm

Introduction

Dynamic Multi-Objective Optimization Problems (DMOPs) are prevalent in real-world applications such as mechanical design, resource scheduling, and wastewater treatment. These problems involve optimizing multiple conflicting objectives that change over time or environmental conditions. Traditional optimization methods often struggle to adapt to such dynamic environments, necessitating the development of specialized algorithms. This paper introduces a novel Dynamic Multi-Objective Evolutionary Algorithm (DMOEA) called HD-DMOEA, which integrates environmental sensing and prediction correction to efficiently track the evolving Pareto frontier.

The primary challenge in DMOPs lies in balancing convergence and diversity while responding to environmental changes. Existing approaches often rely on random reinitialization, memory-based strategies, or prediction models. However, these methods may suffer from high computational costs, reliance on historical data accuracy, or limited adaptability to varying change intensities. HD-DMOEA addresses these limitations by introducing three key strategies:

  1. Environmental Change Detection and Intensity Assessment: A Wilcoxon signed-rank test detects environmental changes, while a novel environmental sensing operator quantifies change intensity.
  2. Holt’s Differential Prediction Correction Model: This model predicts the next positions of population individuals and corrects predictions using reference points to enhance accuracy.
  3. Environment-Aware Dual Mutation: A mutation strategy adapts to environmental change intensity, maintaining population diversity and reducing the risk of local optima.

Background and Related Work

Dynamic Multi-Objective Optimization

A DMOP involves minimizing multiple conflicting objective functions that vary over time. The Pareto optimal solution set (PS) consists of solutions that are not dominated by any other solution in the decision space. The Pareto frontier (PF) represents the mapping of these solutions in the objective space. The goal is to continuously track the evolving PF as the environment changes.

Existing DMOEAs focus on three main aspects:
• Environmental Change Detection: Methods include random sampling of individuals, ranking-based fitness evaluation, and probability distribution analysis.

• Response Mechanisms: Common strategies include random reinitialization, memory-based reinitialization, and prediction-based reinitialization.

• Static Optimization Efficiency: Techniques like decomposition-based methods (e.g., MOEA/D) are used to accelerate convergence.

Prediction Strategies in DMOPs

Prediction-based methods leverage historical data to forecast future changes. Popular models include autoregressive (AR) and moving average (MA) models. However, these models are often complex and suitable only for short-term predictions. Recent studies have explored simpler yet effective models, such as Holt’s linear exponential smoothing and differential prediction models.

Algorithm Design

Environmental Detection Mechanism

Wilcoxon Signed-Rank Test

The Wilcoxon signed-rank test is employed to detect environmental changes by comparing fitness values across time windows. The test calculates a p-value to determine if significant changes have occurred. If the p-value falls below a threshold (e.g., 0.05), an environmental change is flagged.

Environmental Sensing Operator

A novel operator evaluates the intensity of environmental changes. It compares the current population’s mean squared error (MSE) with historical MSE values to classify changes as mild or severe. This classification guides the algorithm’s response strategy.

Environment-Aware Dual Mutation

Based on the change intensity, the algorithm adjusts the number of mutated individuals:
• Mild Changes: A subset of individuals undergoes crossover and mutation to accelerate convergence.

• Severe Changes: Individuals closest to the reference point are mutated, while the rest are reinitialized to enhance diversity.

Prediction Correction Mechanism

Pareto Triad Solutions

Three key individuals are selected to represent the population’s movement:

  1. Elite Solution: The individual closest to the reference point, representing the current best solution.
  2. Balanced Solution: An individual maintaining a moderate distance from the reference point.
  3. Diversity Solution: The farthest individual from the reference point, ensuring population diversity.

Holt’s Prediction Model

The model predicts the next positions of the Pareto triad using exponential smoothing. The predictions are adjusted based on a memory decay factor, which varies with environmental change intensity.

Differential Correction

A second-order differential model refines the predictions by accounting for acceleration in population movement. This correction improves prediction accuracy, especially in non-linear environments.

Algorithm Framework

The HD-DMOEA framework operates as follows:

  1. Initialization: Set up the population, weight vectors, and neighborhood structures.
  2. Environmental Detection: Use the Wilcoxon test and sensing operator to detect and classify changes.
  3. Prediction and Correction: Apply Holt’s model and differential correction to forecast future positions.
  4. Mutation and Selection: Adapt the mutation strategy based on change intensity and update the population.

Experimental Results

Test Functions and Performance Metrics

The algorithm was evaluated on seven benchmark functions (FDA1–FDA4, dMOP1–dMOP3) with varying characteristics:
• Type I: PS changes, PF remains stable.

• Type II: Both PS and PF change.

• Type III: PS remains stable, PF changes.

Performance was measured using the Mean Inverted Generational Distance (MIGD), which assesses convergence and diversity over multiple time windows.

Comparative Analysis

HD-DMOEA was compared against five state-of-the-art algorithms:

  1. IT-DMOEA: Individual-based transfer learning.
  2. KT-DMOEA: Knee point-based transfer learning.
  3. HPS-DMOP: Hybrid prediction strategy with social learning.
  4. SGEA: Steady-state generational evolutionary algorithm.
  5. MDP: Multi-directional prediction strategy.

Key Findings

  1. Superior Performance: HD-DMOEA achieved the lowest MIGD values in most test cases, demonstrating robust convergence and diversity.
  2. Stability: The algorithm maintained consistent performance across varying change intensities (nt = 5, 10, 20) and frequencies (τt = 20).
  3. Effectiveness in Type II Problems: HD-DMOEA excelled in problems with shifting PFs, outperforming other methods in FDA2, FDA3, and dMOP2.

Environmental Detection Validation

The Wilcoxon test effectively detected changes in Type II problems, with p-values consistently below the threshold during environmental shifts. This confirmed the reliability of the detection mechanism.

Ablation Studies

  1. Parameter Sensitivity: The memory decay factor (a) was optimized at a1 = 0.8 (severe changes) and a2 = 0.2 (mild changes).

  2. Component Analysis:
    • Prediction Correction: The combined Holt-differential model outperformed standalone Holt or differential models.

    • Dual Mutation: The adaptive mutation strategy enhanced diversity, particularly in PF-shifting scenarios.

Conclusion

HD-DMOEA presents a robust solution for dynamic multi-objective optimization by integrating environmental sensing, prediction correction, and adaptive mutation. Key contributions include:
• A Wilcoxon-based detection mechanism paired with an environmental sensing operator for accurate change classification.

• A novel Holt’s differential prediction model that corrects forecasts using reference points, improving accuracy.

• An environment-aware dual mutation strategy that balances diversity and convergence.

Experimental results demonstrated HD-DMOEA’s superiority over existing methods, particularly in handling complex, non-linear changes. Future work will explore applications in real-world problems like edge computing resource scheduling, focusing on practical, time-efficient solutions.

doi.org/10.19734/j.issn.1001-3695.2024.04.0124

Was this helpful?

0 / 0