A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization

Mei YI, Li XIAODONG, Yao XIN, Mohammad Nabi OMIDVAR

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

145 Citations (Scopus)

Abstract

This article proposes a competitive divide-and-conquer algorithm for solving large-scale black-box optimization problems for which there are thousands of decision variables and the algebraic models of the problems are unavailable. We focus on problems that are partially additively separable, since this type of problem can be further decomposed into a number of smaller independent subproblems. The proposed algorithm addresses two important issues in solving large-scale black-box optimization: (1) the identification of the independent subproblems without explicitly knowing the formula of the objective function and (2) the optimization of the identified black-box subproblems. First, a Global Differential Grouping (GDG) method is proposed to identify the independent subproblems. Then, a variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is adopted to solve the subproblems resulting from its rotation invariance property. GDG and CMA-ES work together under the cooperative co-evolution framework. The resultant algorithm, named CC-GDG-CMAES, is then evaluated on the CEC'2010 large-scale global optimization (LSGO) benchmark functions, which have a thousand decision variables and black-box objective functions. The experimental results show that, on most test functions evaluated in this study, GDG manages to obtain an ideal partition of the index set of the decision variables, and CC-GDG-CMAES outperforms the state-of-the-art results. Moreover, the competitive performance of the well-known CMA-ES is extended from low-dimensional to high-dimensional black-box problems. © 2016 ACM.
Original languageEnglish
Pages (from-to)1-24
Number of pages24
JournalACM Transactions on Mathematical Software
Volume42
Issue number2
DOIs
Publication statusPublished - 3 Jun 2016
Externally publishedYes

Keywords

  • Cooperative coevolution
  • Covariance matrix adaptation evolutionary strategy (CMA-ES)
  • Decomposition
  • Differential grouping
  • Large-scale black-box optimization

Fingerprint

Dive into the research topics of 'A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization'. Together they form a unique fingerprint.

Cite this