Abstract
Cooperative co-evolution (CC) algorithms, based on the divide-and-conquer strategy, have emerged as the predominant approach to solving large-scale global optimization (LSGO) problems. The efficiency and accuracy of the grouping stage significantly impact the performance of the optimization process. While the general separability grouping (GSG) method has overcome the limitation of previous differential grouping (DG) methods by enabling the decomposition of non-additively separable functions, it suffers from high computational complexity. To address this challenge, this article proposes a composite separability grouping (CSG) method, seamlessly integrating DG and GSG into a problem decomposition framework to utilize the strengths of both approaches. CSG introduces a step-by-step decomposition framework that accurately decomposes various problem types using fewer computational resources. By sequentially identifying additively, multiplicatively and generally separable variables, CSG progressively groups non-separable variables by recursively considering the interactions between each non-separable variable and the formed non-separable groups. Furthermore, to enhance the efficiency and accuracy of CSG, we introduce two innovative methods: a multiplicatively separable variable detection method and a non-separable variable grouping method. Extensive experimental results demonstrate that CSG achieves more accurate variable grouping with lower computational complexity compared to GSG and state-of-the-art DG series designs.
Introduction
Large-Scale Global Optimization (LSGO) problems, involving hundreds or thousands of decision variables, are pervasive in artificial intelligence and engineering. These problems are plagued by the "curse of dimensionality," where the search space grows exponentially with the number of variables, making global optima difficult to locate. The standard strategy to mitigate this is Cooperative Co-evolution (CC), which employs a "divide-and-conquer" approach by decomposing the problem into smaller, independent sub-problems.
The effectiveness of CC is heavily dependent on the decomposition stage. Incorrectly grouping interacting variables into separate sub-problems leads to poor optimization performance. Current methods face a significant trade-off: Differential Grouping (DG) is computationally efficient but limited to additive interactions, while General Separability Grouping (GSG) is accurate for complex interactions but computationally prohibitive due to the high number of function evaluations (FEs) required.
The Composite Separability Grouping (CSG) Framework
To bridge the gap between efficiency and accuracy, the proposed Composite Separability Grouping (CSG) method utilizes a four-stage hierarchical framework. Instead of applying a single complex algorithm to the entire problem, CSG acts as a multi-stage filter, applying the most cost-effective tool for each type of variable interaction.
The framework consists of the following stages:
- Additive Identification (DG): Quickly identifies and removes variables with simple additive relationships.
- Multiplicative Identification (MSVD): Detects variables interacting through multiplication by applying a logarithmic transformation to data already generated in the first stage.
- General Identification (GSVD): Uses the "minimum points shift principle" to identify remaining complex interactions.
- Non-separable Grouping (NVG): Employs a recursive method to bundle highly interdependent variables.
Innovative Detection Methods
A key contribution of CSG is the Multiplicatively Separable Variable Detection (MSVD) method. MSVD is designed to be highly efficient by "recycling" historical information from the DG stage, thereby identifying multiplicative interactions with minimal additional computational cost.
Additionally, the Non-separable Variable Grouping (NVG) method enhances accuracy by recursively evaluating interactions between individual variables and existing non-separable groups, ensuring that complex dependencies are correctly captured.
Experimental Results
The CSG method was evaluated against standard benchmarks (CEC2010, CEC2013, BNS) and a new Benchmark based on Multiple Separability (BMS) that features mixed interaction types.
- Computational Efficiency: On the BMS benchmark, CSG reduced the required Function Evaluations (FEs) by approximately 50% compared to the GSG method while maintaining high accuracy.
- Grouping Accuracy: CSG achieved near-100% grouping accuracy across most test functions, significantly outperforming DG-series methods on multiplicative and composite interactions.
- Optimization Performance: When integrated with the SaNSDE optimizer, CSG-based decomposition yielded superior results, achieving 14 out of 15 first-place rankings in 1000-dimensional tests compared to other state-of-the-art methods.
Conclusion
CSG represents a significant advancement in LSGO by demonstrating that a hierarchical, composite approach to problem decomposition can achieve both high accuracy and computational efficiency. Future research will focus on broadening the definitions of separability, exploring deep learning for automated structure learning, and refining parameter sensitivity for more robust performance across diverse problem landscapes.
Summary updated