Yi Mei
Skip Abstract Section
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.
- D. Andrews and Y. Whang. 1990. Additive interactive regression models: Circumvention of the curse of dimensionality. Econometric Theory 6, 4, 466--479.Google Scholar
Cross Ref
- D. Azulay and J. Pique. 2001. A revised simplex method with integer Q-matrices. ACM Transactions on Mathematical Software 27, 3, 350--360. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- M. Blondel, K. Seki, and K. Uehara. 2013. Block coordinate descent algorithms for large-scale sparse multiclass classification. Machine Learning 93, 1, 31--52. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- G. B. Dantzig and M. N. Thapa. 1997. Linear Programming: 1: Introduction. Vol. 1. Springer. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- J. H. Friedman and B.W. Silverman. 1989. Flexible parsimonious smoothing and additive modeling. Technometrics 31, 1, 3--21.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- N. Hansen. 2011. The CMA Evolution Strategy: A Tutorial. Technical Report, Machine Learning and Optimization group (TAO), Inria, France.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- R. Hooke and T. A. Jeeves. 1961. “Direct search” solution of numerical and statistical problems. Journal of the ACM 8, 2, 212--229. Google ScholarDigital Library
- J. E. Hopcroft and R. E. Tarjan. 1973. Efficient algorithms for graph manipulation. Communications of the ACM 16, 6, 372--378. Google ScholarDigital Library
- P. Larrañaga and J.A. Lozano. 2002. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Vol. 2. Springer.Google Scholar
- G. Li, C. Rosenthal, and H. Rabitz. 2001. High dimensional model representations. The Journal of Physical Chemistry A 105, 33, 7765--7777.Google ScholarCross Ref
- X. Li and X. Yao. 2012. Cooperatively coevolving particle swarms for large scale optimization. IEEE Transactions on Evolutionary Computation 16, 2, 210--224. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- J. A. Nelder and R. Mead. 1965. A simplex method for function minimization. The Computer Journal 7, 4, 308--313.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- M. A. Potter and K. De Jong. 1994. A cooperative coevolutionary approach to function optimization. Parallel Problem Solving from Nature (PPSN) 249--257. Google ScholarDigital Library
- P. Richtárik and M. Takáč. 2012. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming 1--38.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- H. H. Rosenbrock. 1960. An automatic method for finding the greatest or least value of a function. Computer Journal 3, 3, 175--184.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- D. J. Sheskin. 2003. Handbook of Parametric and Nonparametric Statistical Procedures. CRC Press, Boca Raton, FL. Google Scholar
- 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. Google ScholarDigital Library
- J. Smith and T. C. Fogarty. 1995. An adaptive poly-parental recombination strategy. In Evolutionary Computing. Springer, 48--61. Google ScholarDigital Library
- C. J. Stone. 1985. Additive regression and other nonparametric models. The Annals of Statistics 689--705.Google ScholarCross Ref
- 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.Google Scholar
- P. Tseng. 2001. Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of Optimization Theory and Applications 109, 3, 475--494. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- F. Wilcoxon. 1945. Individual comparisons by ranking methods. Biometrics Bulletin 1, 6, 80--83.Google ScholarCross Ref
- Z. Yang, K. Tang, and X. Yao. 2008. Large scale evolutionary optimization using cooperative coevolution. Information Sciences 178, 15, 2985--2999. Google ScholarDigital Library
- X. Yao, Y. Liu, and G. Lin. 1999. Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation 3, 2, 82--102. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- A Competitive Divide-and-Conquer Algorithm for Unconstrained Large-Scale Black-Box Optimization
Recommendations
Large-scale optimization using immune algorithm
GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary ComputationImmune-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 ...
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 ...
Black-box optimization benchmarking of IPOP-saACM-ES and BIPOP-saACM-ES on the BBOB-2012 noiseless testbed
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationIn this paper, we study the performance of IPOP-saACM-ES and BIPOP-saACM-ES, recently proposed self-adaptive surrogate-assisted Covariance Matrix Adaptation Evolution Strategies. Both algorithms were tested using restarts till a total number of function ...
Comments