More Web Proxy on the site http://driver.im/

research-article

A Competitive Divide-and-Conquer Algorithm for Unconstrained Large-Scale Black-Box Optimization

Authors:

Mohammad Nabi Omidvar,

Xin YaoAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 42, Issue 2

Article No.: 13, Pages 1 - 24

https://doi.org/10.1145/2791291

Published: 03 June 2016 Publication History

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.

References

[1]

D. Andrews and Y. Whang. 1990. Additive interactive regression models: Circumvention of the curse of dimensionality. Econometric Theory 6, 4, 466--479.

[2]

D. Azulay and J. Pique. 2001. A revised simplex method with integer Q-matrices. ACM Transactions on Mathematical Software 27, 3, 350--360.

Digital Library

[3]

J. C. Bezdek, R. J. Hathaway, R. E. Howard, C. A. Wilson, and M. P. Windham. 1987. Local convergence analysis of a grouped variable version of coordinate descent. Journal of Optimization Theory and Applications 54, 3, 471--477.

[4]

M. Blondel, K. Seki, and K. Uehara. 2013. Block coordinate descent algorithms for large-scale sparse multiclass classification. Machine Learning 93, 1, 31--52.

Digital Library

[5]

T. R. Browning. 2001. Applying the design structure matrix to system decomposition and integration problems: A review and new directions. IEEE Transactions on Engineering Management 48, 3, 292--306.

[6]

W. Chen, T. Weise, Z. Yang, and K. Tang. 2010. Large-scale global optimization using cooperative coevolution with variable interaction learning. Parallel Problem Solving from Nature, (PPSN XI’10), 300--309.

Digital Library

[7]

A. L. Custódio and L. N. Vicente. 2007. Using sampling and simplex derivatives in pattern search methods. SIAM Journal on Optimization 18, 2, 537--555.

Digital Library

[8]

G. B. Dantzig and M. N. Thapa. 1997. Linear Programming: 1: Introduction. Vol. 1. Springer.

Digital Library

[9]

R. Eberhart and J. Kennedy. 1995. A new optimizer using particle swarm theory. In Proceedings of the 6th International Symposium on Micro Machine and Human Science (MHS’95). IEEE, 39--43.

[10]

J. Friedenberg and G. Silverman. 2006. Mind as a black box: The behaviorist approach. In Cognitive Science: An Introduction to the Study of Mind. Sage Thousand Oaks, CA, 85--88.

[11]

J. H. Friedman and B.W. Silverman. 1989. Flexible parsimonious smoothing and additive modeling. Technometrics 31, 1, 3--21.

[12]

W. W. Hager and H. Zhang. 2006. Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent. ACM Transactions on Mathematical Software 32, 1, 113--137.

Digital Library

[13]

N. Hansen. 2011. The CMA Evolution Strategy: A Tutorial. Technical Report, Machine Learning and Optimization group (TAO), Inria, France.

[14]

N. Hansen, A. Auger, R. Ros, S. Finck, and P. Pošík. 2010. Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009. In Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation. ACM, 1689--1696.

Digital Library

[15]

N. Hansen and A. Ostermeier. 1996. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Proceedings of 1996 IEEE International Conference on Evolutionary Computation. IEEE, 312--317.

[16]

G. R. Harik. 1997. Learning Gene Linkage to Efficiently Solve Problems of Bounded Difficulty using Genetic Algorithms. Ph.D. Dissertation. The University of Michigan, Ann Arbor, MI.

Digital Library

[17]

J. H. Holland. 1975. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. The University of Michigan Press, Ann Arbor, MI.

[18]

R. Hooke and T. A. Jeeves. 1961. “Direct search” solution of numerical and statistical problems. Journal of the ACM 8, 2, 212--229.

Digital Library

[19]

J. E. Hopcroft and R. E. Tarjan. 1973. Efficient algorithms for graph manipulation. Communications of the ACM 16, 6, 372--378.

Digital Library

[20]

P. Larrañaga and J.A. Lozano. 2002. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Vol. 2. Springer.

[21]

G. Li, C. Rosenthal, and H. Rabitz. 2001. High dimensional model representations. The Journal of Physical Chemistry A 105, 33, 7765--7777.

[22]

X. Li and X. Yao. 2012. Cooperatively coevolving particle swarms for large scale optimization. IEEE Transactions on Evolutionary Computation 16, 2, 210--224.

Digital Library

[23]

Y. Liu, X. Yao, Q. Zhao, and T. Higuchi. 2001. Scaling up fast evolutionary programming with cooperative coevolution. In Proceedings of the 2001 Congress on Evolutionary Computation, Vol. 2. IEEE, 1101--1108.

[24]

I. Loshchilov, M. Schoenauer, and M. Sebag. 2011. Adaptive coordinate descent. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. ACM, 885--892.

Digital Library

[25]

Y. Mei, X. Li, and X. Yao. 2014. Cooperative co-evolution with route distance grouping for large-scale capacitated arc routing problems. IEEE Transactions on Evolutionary Computation 18, 3, 435--449.

[26]

D. Molina, M. Lozano, and F. Herrera. 2010. MA-SW-chains: Memetic algorithm based on local search chains for large scale continuous global optimization. In IEEE Congress on Evolutionary Computation (CEC’10). IEEE, 1--8.

[27]

J. A. Nelder and R. Mead. 1965. A simplex method for function minimization. The Computer Journal 7, 4, 308--313.

[28]

M. N. Omidvar and X. Li. 2010. A comparative study of CMA-ES on large scale global optimisation. In AI 2010: Advances in Artificial Intelligence. Springer, 303--312.

[29]

M. N. Omidvar, X. Li, Y. Mei, and X. Yao. 2014. Cooperative co-evolution with differential grouping for large scale optimization. IEEE Transactions on Evolutionary Computation 18, 3 (2014), 378--393.

[30]

M. N. Omidvar, X. Li, Z. Yang, and X. Yao. 2010a. Cooperative co-evolution for large scale optimization through more frequent random grouping. In Proceedings of the 2010 IEEE Congress on Evolutionary Computation. 1--8.

[31]

M. N. Omidvar, X. Li, and X. Yao. 2010b. Cooperative co-evolution with delta grouping for large scale non-separable function optimization. In Proceedings of the 2010 IEEE Congress on Evolutionary Computation (CEC’10). 1762--1769.

[32]

M. N. Omidvar, X. Li, and X. Yao. 2011. Smart use of computational resources based on contribution for cooperative co-evolutionary algorithms. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. ACM, 1115--1122.

Digital Library

[33]

M. N. Omidvar, Y. Mei, and X. Li. 2014. Optimal decomposition of large-scale separable continuous functions for cooperative co-evolutionary algorithms. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation (CEC’14). IEEE.

[34]

M. A. Potter and K. De Jong. 1994. A cooperative coevolutionary approach to function optimization. Parallel Problem Solving from Nature (PPSN) 249--257.

Digital Library

[35]

P. Richtárik and M. Takáč. 2012. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming 1--38.

[36]

L. M. Rios and N. V. Sahinidis. 2012. Derivative-free optimization: A review of algorithms and comparison of software implementations. Journal of Global Optimization 1--47.

[37]

R. Ros and N. Hansen. 2008. A simple modification in CMA-ES achieving linear time and space complexity. In Parallel Problem Solving from Nature--PPSN X. Springer, 296--305.

[38]

H. H. Rosenbrock. 1960. An automatic method for finding the greatest or least value of a function. Computer Journal 3, 3, 175--184.

[39]

S. Shan and G. Wang. 2010. Survey of modeling and optimization strategies to solve high-dimensional design problems with computationally-expensive black-box functions. Structural and Multidisciplinary Optimization 41, 2, 219--241.

[40]

D. J. Sheskin. 2003. Handbook of Parametric and Nonparametric Statistical Procedures. CRC Press, Boca Raton, FL.

[41]

Y. Shi, H. Teng, and Z. Li. 2005. Cooperative co-evolutionary differential evolution for function optimization. In Proceedings of the 1st International Conference on Advances in Natural Computation. Lecture Notes in Computer Science, Vol. 3611, Springer, Berlin, 1080--1088.

Digital Library

[42]

J. Smith and T. C. Fogarty. 1995. An adaptive poly-parental recombination strategy. In Evolutionary Computing. Springer, 48--61.

Digital Library

[43]

C. J. Stone. 1985. Additive regression and other nonparametric models. The Annals of Statistics 689--705.

[44]

K. Tang, X. Li, P. N. Suganthan, Z. Yang, and T. Weise. 2009. Benchmark Functions for the CEC’10 Special Session and Competition on Large-Scale Global Optimization. Technical Report. Nature Inspired Computation and Applications Laboratory, USTC, China. Retrieved April 7, 2016 from http://nical.ustc.edu.cn/cec10ss.php.

[45]

P. Tseng. 2001. Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of Optimization Theory and Applications 109, 3, 475--494.

Digital Library

[46]

F. Van den Bergh and A. P. Engelbrecht. 2004. A cooperative approach to particle swarm optimization. IEEE Transactions on Evolutionary Computation 8, 3, 225--239.

Digital Library

[47]

J. Weglarz, J. Blazewicz, W. Cellary, and R. Slowinski. 1977. Algorithm 520: An automatic revised simplex method for constrained resource network scheduling {H}. ACM Transactions on Mathematical Software 3, 3, 295--300.

Digital Library

[48]

K. Weicker and N. Weicker. 1999. On the improvement of coevolutionary optimizers by learning variable interdependencies. In Proceedings of the 1999 IEEE Congress on Evolutionary Computation. IEEE.

[49]

F. Wilcoxon. 1945. Individual comparisons by ranking methods. Biometrics Bulletin 1, 6, 80--83.

[50]

Z. Yang, K. Tang, and X. Yao. 2008. Large scale evolutionary optimization using cooperative coevolution. Information Sciences 178, 15, 2985--2999.

Digital Library

[51]

X. Yao, Y. Liu, and G. Lin. 1999. Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation 3, 2, 82--102.

Digital Library

[52]

C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal. 1997. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions on Mathematical Software 23, 4, 550--560.

Digital Library

Cited By

Gu QRong LWang DLiu D(2025)An enhanced competitive swarm optimizer with strongly robust sparse operator for large-scale sparse multi-objective optimization problemInformation Sciences10.1016/j.ins.2024.121569690(121569)Online publication date: Feb-2025
https://doi.org/10.1016/j.ins.2024.121569
Xu XCheng DWang DLi QYu F(2024)An Improved NSGA-III with a Comprehensive Adaptive Penalty Scheme for Many-Objective OptimizationSymmetry10.3390/sym1610128916:10(1289)Online publication date: 1-Oct-2024
https://doi.org/10.3390/sym16101289
Istiono W(2024)Analyzing Time and Space Complexity: Kadane vs. Divide and Conquer Algorithms for Maximum Sub-Array ProblemSSRN Electronic Journal10.2139/ssrn.4643200Online publication date: 2024
https://doi.org/10.2139/ssrn.4643200
Show More Cited By

Index Terms

A Competitive Divide-and-Conquer Algorithm for Unconstrained Large-Scale Black-Box Optimization
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Nonconvex optimization
      2. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Divide and conquer

Recommendations

Large-scale optimization using immune algorithm
GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation

Immune-inspired optimization algorithms encoded the parameters into individuals where each individual represents a search point in the space of potential solutions. A large number of parameters would result in a large search space. Nowadays, there is ...
A Multi-objective Evolutionary Algorithm based on Hierarchical Grouping for Large-scale Multi-objective Optimization
GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Variable decomposition have been widely applied to large-scale multi-objective problems. Existing studies usually consume a large amount of computational resources in the decomposition phase. To this end, this paper proposes a multi-objective ...
How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism

Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 42, Issue 2

June 2016

156 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2936306

Editor:
Michael A. Heroux
Sandia National Laboratories, USA

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2016

Accepted: 01 June 2015

Revised: 01 January 2015

Received: 01 March 2014

Published in TOMS Volume 42, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

EPSRC
Royal SocietyWolfson Research Merit Award
ARC Discovery
NSFC

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

188
Total Citations
View Citations
1,011
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gu QRong LWang DLiu D(2025)An enhanced competitive swarm optimizer with strongly robust sparse operator for large-scale sparse multi-objective optimization problemInformation Sciences10.1016/j.ins.2024.121569690(121569)Online publication date: Feb-2025
https://doi.org/10.1016/j.ins.2024.121569
Xu XCheng DWang DLi QYu F(2024)An Improved NSGA-III with a Comprehensive Adaptive Penalty Scheme for Many-Objective OptimizationSymmetry10.3390/sym1610128916:10(1289)Online publication date: 1-Oct-2024
https://doi.org/10.3390/sym16101289
Istiono W(2024)Analyzing Time and Space Complexity: Kadane vs. Divide and Conquer Algorithms for Maximum Sub-Array ProblemSSRN Electronic Journal10.2139/ssrn.4643200Online publication date: 2024
https://doi.org/10.2139/ssrn.4643200
Kim K(2024)Multi-Armed Bandit-based Cooperative Co-Evolutionary Algorithm for Large-Scale Global Optimization of Non-Linear FunctionsThe Journal of Korean Institute of Information Technology10.14801/jkiit.2024.22.5.11522:5(115-129)Online publication date: 31-May-2024
https://doi.org/10.14801/jkiit.2024.22.5.115
Yu WLiu RChen DHu Q(2024)Explainability Enhanced Object Detection Transformer With Feature DisentanglementIEEE Transactions on Image Processing10.1109/TIP.2024.349273333(6439-6454)Online publication date: 2024
https://doi.org/10.1109/TIP.2024.3492733
Gong YZhong YHuang H(2024)Offline Data-Driven Optimization at Scale: A Cooperative Coevolutionary ApproachIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.333869328:6(1809-1823)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3338693
Guo TMei YTang KDu W(2024)Cooperative Co-Evolution for Large-Scale Multiobjective Air Traffic Flow ManagementIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.332888628:6(1644-1658)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3328886
Liu XZhan ZZhang J(2024)Transfer-Based Particle Swarm Optimization for Large-Scale Dynamic Optimization With Changing Variable InteractionsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.332632728:6(1633-1643)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3326327
Kumar ADas SMallipeddi R(2024)An Efficient Differential Grouping Algorithm for Large-Scale Global OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.323007028:1(32-46)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TEVC.2022.3230070
He CCheng RLi LTan KJin Y(2024)Large-Scale Multiobjective Optimization via Reformulated Decision Variable AnalysisIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321300628:1(47-61)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TEVC.2022.3213006
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents