DG2: A faster and more accurate differential grouping for large-scale black-box optimization

Mohammad Nabi OMIDVAR, Ming YANG, Yi MEI, Xiaodong LI, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

247 Citations (Scopus)

Abstract

Identification of variable interaction is essential for an efficient implementation of a divide-and-conquer algorithm for large-scale black-box optimization. In this paper, we propose an improved variant of the differential grouping (DG) algorithm, which has a better efficiency and grouping accuracy. The proposed algorithm, DG2, finds a reliable threshold value by estimating the magnitude of roundoff errors. With respect to efficiency, DG2 reuses the sample points that are generated for detecting interactions and saves up to half of the computational resources on fully separable functions. We mathematically show that the new sampling technique achieves the lower bound with respect to the number of function evaluations. Unlike its predecessor, DG2 checks all possible pairs of variables for interactions and has the capacity to identify overlapping components of an objective function. On the accuracy aspect, DG2 outperforms the state-of-the-art decomposition methods on the latest large-scale continuous optimization benchmark suites. DG2 also performs reliably in the presence of imbalance among contribution of components in an objective function. Another major advantage of DG2 is the automatic calculation of its threshold parameter (), which makes it parameter-free. Finally, the experimental results show that when DG2 is used within a cooperative co-evolutionary framework, it can generate competitive results as compared to several state-of-the-art algorithms.
Original languageEnglish
Pages (from-to)929-942
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume21
Issue number6
Early online date25 Apr 2017
DOIs
Publication statusPublished - Dec 2017
Externally publishedYes

Bibliographical note

This work was supported in part by the EPSRC under Grant EP/K001523/1 and Grant EP/J017515/1, in part by the ARC Discovery under Grant DP120102205, in part by the National Natural Science Foundation of China under Grant 61305086 and Grant 61329302, and in part by the Open Research Project of the Hubei Key Laboratory of Intelligent Geo-Information Processing under Grant KLIGIP201602. The work of X. Yao was supported by the Royal Society Wolfson Research Merit Award.

Keywords

  • Cooperative co-evolution
  • Differential grouping (DG)
  • Large-scale global optimization
  • Problem decomposition

Fingerprint

Dive into the research topics of 'DG2: A faster and more accurate differential grouping for large-scale black-box optimization'. Together they form a unique fingerprint.

Cite this