Merged Differential Grouping for Large-Scale Global Optimization

Xiaoliang Ma, Zhitao Huang, Xiaodong Li, Lei Wang, Yutao Qi, Zexuan Zhu

Abstract

The divide-and-conquer strategy has been widely used in cooperative co-evolutionary algorithms to deal with large-scale global optimization problems, where a target problem is decomposed into a set of lower-dimensional and tractable subproblems to reduce the problem complexity. However, such a strategy usually demands a large number of function evaluations to obtain an accurate variable grouping. To address this issue, a merged differential grouping (MDG) method is proposed in this article based on the subset–subset interaction and binary search. In the proposed method, each variable is first identified as either a separable variable or a nonseparable variable. Afterward, all separable variables are put into the same subset, and the nonseparable variables are divided into multiple subsets using a binary-tree-based iterative merging method. With the proposed algorithm, the computational complexity of interaction detection is reduced to $O(\max \{n,n_{ns}\times \log _{2} k\})$ , where $n$ , $n_{ns}(\leq n)$ , and $k( < n)$ indicate the numbers of decision variables, nonseparable variables, and subsets of nonseparable variables, respectively. The experimental results on benchmark problems show that MDG is very competitive with the other state-of-the-art methods in terms of efficiency and accuracy of problem decomposition.
BibTeX
@article{ma2022merged,
  author = {Xiaoliang Ma and Zhitao Huang and Xiaodong Li and Lei Wang and Yutao Qi and Zexuan Zhu},
  title = {{Merged Differential Grouping for Large-Scale Global Optimization}},
  journal = {IEEE Trans. Evol. Comput.},
  year = {2022},
  doi = {10.1109/tevc.2022.3144684},
}

Loading related content...

Figure