A Composite Decomposition Method for Large-Scale Global Optimization

Maojiang Tian, Minyang Chen, Wei Du, Yang Tang, Yaochu Jin, Gary G. Yen

TL;DR

Researchers have developed a new "Composite Separability Grouping" (CSG) method that efficiently breaks down massive optimization problems into smaller, manageable pieces. By intelligently combining fast traditional techniques with high-accuracy modern ones, CSG achieves state-of-the-art decomposition accuracy while using significantly fewer computational resources than previous methods.

What Problem Does This Paper Address?

In the world of artificial intelligence and engineering, we often face "Large-Scale Global Optimization" (LSGO) problems—tasks involving hundreds or thousands of decision variables (like tuning the weights of a neural network or planning a complex robotic path). These problems suffer from the curse of dimensionality: as the number of variables grows, the search space expands exponentially, making it nearly impossible to find the best solution.

The standard solution is a "divide-and-conquer" strategy called Cooperative Co-evolution (CC). CC breaks a big problem into smaller sub-problems (groups of variables) that can be solved independently. However, the success of CC depends entirely on the decomposition stage. If you group variables that actually interact with each other into different sets, the optimizer will fail.

Existing methods face a trade-off:

  1. Differential Grouping (DG): Fast, but only works for simple "additive" interactions.
  2. General Separability Grouping (GSG): Highly accurate for complex interactions, but incredibly "expensive" in terms of the number of function evaluations (FEs) required.

Methods

The authors propose Composite Separability Grouping (CSG), a four-stage framework that treats decomposition like a multi-stage filter. Instead of using a one-size-fits-all tool, it applies the most efficient tool for each specific type of variable interaction:

  1. Additive Identification: It first uses DG to quickly peel away variables that only have simple, additive relationships.
  2. Multiplicative Identification (MSVD): The authors introduce a new method called Multiplicatively Separable Variable Detection. It reuses data from the first step and applies a logarithmic transformation to identify variables that interact through multiplication.
  3. General Identification (GSVD): For the remaining variables, it uses the "minimum points shift principle" (checking if the optimal value of one variable changes when another is perturbed).
  4. Non-separable Grouping (NVG): Finally, it uses a new recursive grouping method to bundle the remaining highly-interdependent variables together.

By filtering out the "easy" variables first, CSG saves its most computationally expensive tools for only the most complex parts of the problem.

Datasets

The researchers evaluated CSG against several standard benchmarks:

  • CEC2010 & CEC2013: Industry-standard benchmarks for large-scale optimization.
  • BNS: A benchmark specifically designed to test different types of variable separability.
  • BMS (Benchmark based on Multiple Separability): A newly introduced benchmark by the authors. Unlike previous sets where a function usually has only one type of interaction, BMS functions mix additive, multiplicative, and complex non-separable interactions in a single problem, mimicking real-world complexity.

Key Insights and Ideas

  • The Efficiency of Hierarchy: The biggest "aha" moment is that decomposition doesn't have to be a single algorithm. By treating it as a sequence (Additive $\rightarrow$ Multiplicative $\rightarrow$ General), the system achieves the accuracy of the most complex methods at a fraction of the cost.
  • Data Recycling: The MSVD step is particularly clever because it leverages "historical information"—data already generated during the additive stage—to detect multiplicative interactions, essentially getting "free" insights.
  • The Minimum Points Shift: The paper reinforces that tracking how local minima move is a more robust way to detect interactions than simply looking at changes in fitness values, which can be noisy or misleading in complex landscapes.

Key Results

  • Computational Savings: On the BMS benchmark, CSG required roughly half the computational resources (Function Evaluations) compared to the high-accuracy GSG method.
  • Superior Accuracy: CSG achieved 100% grouping accuracy on almost all test functions, whereas older DG-series methods failed to correctly identify multiplicative or composite interactions.
  • Optimization Performance: When plugged into an actual optimizer (SaNSDE), CSG-based decomposition led to significantly better final solutions. In 1000-dimensional tests, it secured 14 out of 15 first-place results compared to other state-of-the-art decomposition methods.

Limitations and Future Work

While CSG is a major step forward, the authors note a few areas for growth:

  • Broadening Separability: The current definitions of "separability" are still mathematically rigid. Future work could explore more generalized or "fuzzy" definitions of interaction.
  • Deep Learning Integration: The authors suggest that the computational power of deep learning could eventually be used to "learn" the structure of an optimization problem even more efficiently than manual recursive checking.
  • Parameter Sensitivity: Like many decomposition methods, performance can vary based on the choice of epsilon ($\epsilon$) thresholds used to detect interactions.

Summary updated

Abstract

Cooperative coevolution (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 nonadditively 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 nonseparable variables by recursively considering the interactions between each nonseparable variable and the formed nonseparable groups. Furthermore, to enhance the efficiency and accuracy of CSG, we introduce two innovative methods: a multiplicatively separable variable detection method and a nonseparable variable grouping method. These two methods are designed to effectively detect multiplicatively separable variables and efficiently group nonseparable variables, respectively. 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.
BibTeX
@article{tian2024composite,
  author = {Maojiang Tian and Minyang Chen and Wei Du and Yang Tang and Yaochu Jin and Gary G. Yen},
  title = {{A Composite Decomposition Method for Large-Scale Global Optimization}},
  journal = {IEEE Trans. Artif. Intell.},
  year = {2024},
  url = {https://openreview.net/forum?id=SQG1KQTfdd},
}

Loading related content...

Figure