High-dimensional Black-box Optimization via Divide and Approximate Conquer

Abstract

Divide and Conquer (DC) is conceptually well suited to high-dimensional optimization by decomposing a problem into multiple small-scale sub-problems. However, appealing performance can be seldom observed when the sub-problems are interdependent. This paper suggests that the major difficulty of tackling interdependent sub-problems lies in the precise evaluation of a partial solution (to a sub-problem), which can be overwhelmingly costly and thus makes sub-problems non-trivial to conquer. Thus, we propose an approximation approach, named Divide and Approximate Conquer (DAC), which reduces the cost of partial solution evaluation from exponential time to polynomial time. Meanwhile, the convergence to the global optimum (of the original problem) is still guaranteed. The effectiveness of DAC is demonstrated empirically on two sets of non-separable high-dimensional problems.

7 pages, 2 figures, conference

References in corpus (1)

• Toward the Coevolution of Novel Vertical-Axis Wind Turbines

Cited by in corpus (9)

• Derivative-Free Reinforcement Learning: A Review
• A Parallel Divide-and-Conquer based Evolutionary Algorithm for Large-scale Optimization
• Evolutionary Reinforcement Learning via Cooperative Coevolutionary Negatively Correlated Search
• Parallel Exploration via Negatively Correlated Search
• A Fast Differential Grouping Algorithm for Large Scale Black-Box Optimization
• Variable Division and Optimization for Constrained Multiobjective Portfolio Problems
• An Eigenspace Divide-and-Conquer Approach for Large-Scale Optimization
• A Dynamic Aggregation Strategy Enhanced Efficient Global Optimization Algorithm for Solving High-Dimensional Turbomachinery Design Problems
• A Surrogate-Assisted Variable Grouping Algorithm for General Large Scale Global Optimization Problems