Improving the Quantum Multi-Swarm Optimization with Adaptive Differential Evolution for Dynamic Environments

Vladimir Stanovov, Shakhnaz Akhmedova, Alexey Vakhnin, Evgenii Sopov, Eugene Semenkin, Michael AffenzellerAlgorithms 2022 · DOI · OpenReview

TL;DR

This paper introduces a hybrid optimization algorithm, mQSODE, that combines Particle Swarm Optimization (PSO) with Differential Evolution (DE) to tackle dynamic optimization problems. By strategically incorporating DE's mutation operators into PSO, the algorithm demonstrates improved performance in environments where the optimal solution shifts over time, outperforming its base PSO counterpart.

What Problem Does This Paper Address?

Many real-world optimization problems occur in dynamic environments where the objective function changes over time. Traditional optimization algorithms, often designed for static environments, struggle to adapt to these changes and track the moving optima. While swarm intelligence algorithms like Particle Swarm Optimization (PSO) are popular for their ability to explore complex search spaces, they can sometimes converge prematurely. Differential Evolution (DE) offers robust exploration capabilities but can be slower to converge. This paper aims to bridge this gap by creating a hybrid algorithm that leverages the strengths of both PSO and DE to effectively navigate and optimize in dynamic environments.

Methods

The core of this research is the modification of the Quantum Multi-Swarm Optimization (mQSO) algorithm. The proposed approach, mQSODE, integrates Differential Evolution's (DE) mutation operators into the PSO framework. Specifically, the "rand/1" mutation strategy from DE is applied with a small probability (PDE) to the particles' positions. Crucially, the paper investigates two variants: applying DE mutation to the current positions of particles versus applying it to their personal best positions. The scaling factor (F) for DE mutation is sampled from a Cauchy distribution, a technique borrowed from adaptive DE algorithms, to introduce more diversity. The algorithm also retains mQSO's features like multiple swarms, exclusion, and anti-convergence mechanisms.

Datasets

The experiments were conducted using the Generalized Moving Peaks Benchmark (GMPB). This benchmark is designed to simulate dynamic optimization problems with configurable features such as the number of peaks, their movement (shift severity), and their complexity (irregularity parameters). The paper uses four specific settings of the GMPB, varying parameters like the number of components and shift severity, to test the algorithm's performance under different dynamic conditions.

Key Insights and Ideas

  • Personal Best is Key: Applying DE's mutation to a particle's personal best position significantly outperforms applying it to its current position. This suggests that personal best positions, which store historical information about good solutions, are more valuable for guiding the exploration in dynamic environments.
  • DE as a "Helper," Not a "Replacement": A small probability (PDE) of using DE operators is optimal. Increasing PDE too much leads to worse performance, indicating that PSO should remain the primary search mechanism, with DE acting as a complementary exploration tool.
  • Parameter Sensitivity: The scaling factor (F) for DE mutation is important, and sampling it from a Cauchy distribution helps. However, the crossover rate (Cr) of DE appears to have minimal impact on performance.
  • Diversity Matters: The hybrid mQSODE algorithm, especially when using DE mutation, tends to maintain higher population diversity compared to the base mQSO, which is crucial for tracking shifting optima.
  • Larger Swarms Can Be Better: For the GMPB benchmark, larger population sizes (more than 20 individuals per swarm) generally lead to better results, likely due to the increased diversity needed to explore complex, changing landscapes.

Key Results

  • The proposed mQSODE algorithm consistently outperformed the baseline mQSO algorithm across various settings, particularly in more challenging scenarios (e.g., with more components).
  • Using DE mutation on personal best positions (mQSODE,0.1,p) yielded significantly better results than using it on current positions (mQSODE,0.1,x). For instance, in Setting 3, mQSODE21,0.1,p achieved an EBBC of 9.09±1.06, while mQSODE21,0.1,x had 13.91±1.83.
  • Increasing the probability of DE mutation (PDE) beyond 0.1 led to a decrease in performance, reinforcing the idea of DE as an assistive operator.
  • Statistical tests (Mann-Whitney) confirmed that mQSODE21,0.1,p significantly outperformed mQSO21 in setting 3 (with 25 components). While mQSODE21,0.1,p generally performed better than mQSO29, these differences were not always statistically significant.
  • The algorithm showed good performance even when compared to other established methods like FTMPSO and MCMA-ES, especially in terms of offline error (Eo) in more complex settings.

Limitations and Future Work

  • Fixed PDE: The probability of applying DE (PDE) was set to a fixed value. The authors suggest that developing an adaptive mechanism for PDE would be beneficial, as a fixed high PDE can be detrimental.
  • Single DE Mutation Strategy: Only the "rand/1" mutation strategy was tested. Exploring other DE mutation operators could potentially yield further improvements.
  • Generalizability: While the study focused on mQSO, the authors believe the proposed hybrid scheme could be applied to other PSO-based algorithms. However, they recommend further experiments on different dynamic optimization scenarios to validate this.
  • Parameter Tuning: While the sensitivity analysis showed that DE parameters like F and Cr were not overly critical, further research into incorporating known adaptation schemes (e.g., success-history adaptation) for these parameters could be valuable.

Summary updated

Abstract

In this study, the modification of the quantum multi-swarm optimization algorithm is proposed for dynamic optimization problems. The modification implies using the search operators from differential evolution algorithm with a certain probability within particle swarm optimization to improve the algorithm’s search capabilities in dynamically changing environments. For algorithm testing, the Generalized Moving Peaks Benchmark was used. The experiments were performed for four benchmark settings, and the sensitivity analysis to the main parameters of algorithms is performed. It is shown that applying the mutation operator from differential evolution to the personal best positions of the particles allows for improving the algorithm performance.
BibTeX
@article{stanovov2022improving,
  author = {Vladimir Stanovov and Shakhnaz Akhmedova and Alexey Vakhnin and Evgenii Sopov and Eugene Semenkin and Michael Affenzeller},
  title = {{Improving the Quantum Multi-Swarm Optimization with Adaptive Differential Evolution for Dynamic Environments}},
  journal = {Algorithms},
  year = {2022},
  doi = {10.3390/a15050154},
}
Figure