A Comprehensive Overview of a Triple Selection Mechanism-Based Multi-Population Multi-Strategy Differential Evolution Algorithm

0
0
0

A Comprehensive Overview of a Triple Selection Mechanism-Based Multi-Population Multi-Strategy Differential Evolution Algorithm

Introduction

Differential Evolution (DE) has emerged as one of the most powerful evolutionary algorithms for solving complex optimization problems due to its simplicity, efficiency, and robustness. However, despite its advantages, DE often suffers from premature convergence and stagnation in local optima, particularly when dealing with high-dimensional or multimodal problems. To address these limitations, researchers have proposed numerous enhancements, including adaptive parameter control, hybrid mutation strategies, and population restructuring. Among these improvements, multi-population approaches have gained significant attention for their ability to balance exploration and exploitation effectively.

This article presents a novel variant of DE called the Triple Selection Mechanism-based Multi-Population Multi-Strategy Differential Evolution (TSMDE) algorithm. TSMDE introduces a hierarchical population structure, adaptive mutation strategies, and a unique triple selection mechanism to enhance convergence speed, solution accuracy, and robustness. The algorithm dynamically adjusts sub-population sizes, employs multiple mutation strategies tailored to different evolutionary stages, and incorporates an efficient information-sharing mechanism to guide the optimization process.

Background and Motivation

Traditional DE algorithms rely on a single population structure and a fixed mutation strategy, which may not be sufficient for complex optimization landscapes. The primary challenges include:

  1. Premature Convergence: The algorithm may converge too quickly to suboptimal solutions, especially in multimodal problems.
  2. Poor Exploration-Exploitation Balance: Fixed strategies may not adapt well to different phases of the search process.
  3. Parameter Sensitivity: The performance of DE heavily depends on control parameters such as the scaling factor (F) and crossover rate (CR).

To mitigate these issues, recent studies have explored multi-population frameworks where different sub-populations employ distinct strategies. However, most existing approaches either use static sub-population sizes or lack an efficient mechanism to share information among sub-populations. TSMDE addresses these gaps by introducing dynamic sub-population resizing, adaptive strategy selection, and a triple selection mechanism that enhances diversity and accelerates convergence.

Algorithm Design

  1. Hierarchical Population Structure

TSMDE divides the main population into three sub-populations based on fitness values:

• Elite Sub-Population (NPA): Contains the best-performing individuals, focusing on local exploitation.

• Intermediate Sub-Population (NPB): Balances exploration and exploitation.

• Inferior Sub-Population (NPC): Comprises low-fitness individuals, emphasizing global exploration.

The sizes of these sub-populations are dynamically adjusted during the optimization process. Initially, NPC is larger to promote exploration, while NPA gradually increases in later stages to enhance exploitation. This adaptive resizing ensures efficient resource allocation throughout the evolutionary process.

  1. Mutation Strategies

TSMDE employs five improved mutation strategies, each tailored to different sub-populations and evolutionary states:

  1. DE/current-erand/1: Combines the current individual with an elite individual to guide the search toward promising regions.
  2. DE/current-best/1: Uses the global best individual to refine solutions in elite sub-populations.
  3. DE/current-to-wrand/1: Introduces weighted random selection to maintain diversity in intermediate sub-populations.
  4. DE/werand-wcurrent/1: Balances exploration and exploitation by combining weighted random and current individuals.
  5. DE/werand-wmrand/1: Designed for inferior sub-populations to escape local optima by leveraging diverse search directions.

These strategies are selected based on the individual’s evolutionary state (e.g., success or failure in previous iterations) and the current optimization phase.

  1. Triple Selection Mechanism

The core innovation of TSMDE is its triple selection mechanism, which consists of three stages:

  1. Individual Selection:
    • Elite sub-population uses a depth-first search strategy, where a single individual undergoes multiple mutations until improvement stagnates.

    • Intermediate and inferior sub-populations follow a normal selection approach, allowing all individuals equal opportunities for mutation.

  2. Strategy Selection:
    • Individuals choose mutation strategies based on their fitness and historical performance.

    • Elite individuals prioritize exploitation, while inferior individuals focus on exploration.

  3. Stagnation Handling:
    • If an individual fails to improve over several iterations, it is replaced by a candidate from one of two external archives:

    ◦ Historical Best Archive (HB): Stores the best experimental vectors encountered during optimization.

    ◦ Historical Best Discarded Archive (HB_dis): Contains high-quality solutions that were previously discarded.

    • This mechanism prevents premature convergence and maintains population diversity.

  4. Parameter Adaptation

TSMDE employs distinct parameter adaptation mechanisms for each sub-population:

• Elite Sub-Population: Uses Gaussian distribution-based updates for F and CR to ensure small, controlled variations.

• Intermediate Sub-Population: Adjusts parameters using a sinusoidal function in early iterations and switches to adaptive methods later.

• Inferior Sub-Population: Combines Cauchy distribution and rank-based adaptation to promote exploration.

These adaptive mechanisms ensure that the algorithm remains flexible across different optimization landscapes.

Experimental Validation

Benchmark Functions

TSMDE was evaluated on the CEC2014 benchmark suite, which includes 30 functions categorized as:
• Unimodal (f1–f3): Test convergence speed.

• Simple Multimodal (f4–f16): Assess exploration capability.

• Hybrid (f17–f22): Combine multiple function types to evaluate robustness.

• Composition (f23–f30): Simulate real-world optimization challenges.

Comparative Analysis

TSMDE was compared against 13 state-of-the-art DE variants, including:
• Fixed Population Algorithms: JADE, EPSDE, RNEGDE, SHADE, CIPDE, PALMDE, TPDE.

• Dynamic Population Algorithms: LSHADE, jSO, APSDE, LPALMDE, EBLSHADE, Hip-DE.

Key findings include:

  1. Solution Accuracy: TSMDE outperformed most competitors on unimodal, multimodal, and hybrid functions. For example, on f6 (a simple multimodal function), TSMDE achieved significantly better results than JADE and EPSDE.
  2. Convergence Speed: While TSMDE exhibited slower initial convergence on some functions (e.g., f3), it consistently reached superior solutions in later iterations.
  3. Robustness: The triple selection mechanism effectively prevented stagnation, as evidenced by TSMDE’s performance on composition functions (e.g., f30).

Sensitivity Analysis

Experiments were conducted to assess the impact of key parameters:
• Population Size (NP): NP = 200 yielded the best balance between exploration and exploitation.

• Stagnation Threshold (T): T = 48 (maximum allowed failures before replacement) optimized diversity maintenance.

• Sub-Population Ratios: The configuration k1 = 7/20, k2 = 1/5, and k3 = 2/5 provided the most effective resource allocation.

Advantages of TSMDE

  1. Dynamic Population Management: The adaptive resizing of sub-populations ensures efficient computation resource utilization.
  2. Enhanced Exploration-Exploitation Balance: Multiple mutation strategies cater to different evolutionary needs.
  3. Improved Diversity Maintenance: The triple selection mechanism, particularly stagnation handling, prevents premature convergence.
  4. Reduced Parameter Sensitivity: Adaptive parameter control minimizes reliance on manual tuning.

Limitations and Future Work

Despite its strengths, TSMDE has some limitations:
• Computational Overhead: The triple selection mechanism increases runtime compared to simpler DE variants.

• Parameter Tuning: While adaptive, the algorithm still requires careful initialization of sub-population ratios.

Future research directions include:
• Dynamic Mutation Strategy Pool: Automatically adjusting the number of active strategies during optimization.

• Hybridization with Local Search: Combining TSMDE with gradient-based methods for faster convergence.

• Real-World Applications: Testing TSMDE on practical problems such as engineering design and scheduling.

Conclusion

TSMDE represents a significant advancement in DE algorithms by integrating dynamic population management, adaptive mutation strategies, and a novel triple selection mechanism. Experimental results demonstrate its superiority in solution accuracy, convergence speed, and robustness compared to existing DE variants. The algorithm’s ability to balance exploration and exploitation makes it particularly suitable for complex, high-dimensional optimization problems. Future enhancements will focus on reducing computational costs and expanding its applicability to real-world scenarios.

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

Was this helpful?

0 / 0