×

zbMATH — the first resource for mathematics

Efficient large scale global optimization through clustering-based population methods. (English) Zbl 07350550
Summary: Back in the 80’s clustering methods were considered state of the art for non-structured box constrained global optimization (GO). Their disappearance is mainly due to their increasing difficulties in solving even moderately sized GO problems, yet the basic idea was indeed a brilliant one. More recently population methods and Differential Evolution (DE) in particular has gained much attention in the GO heuristic world due to their easy implementation and good exploration capabilities. In order to improve the exploitation capability of DE, some memetic variants have been proposed with success. In this paper we revisit clustering methods and apply them both to standard low dimensional problems and to large scale ones; in particular we propose a novel approach to apply a clustering-type decision on when to start a local search to variants of memetic DE. The resulting algorithm, C-MDE (Clustering Memetic DE) outperforms the best-known methods both in quality of the returned solution and in the number of calls to the expensive local optimization phase, even in large dimension. For large dimensional problems, random projections are used in order to be able to decide on starting a local search on a limited number of features. The resulting GO method is a revisit of clustering techniques in which all of the defects which made those methods no more feasible are eliminated: in particular, the method is used within an adaptive population method and it efficiently runs also in large dimension. Thus we think the proposed approach will find a place in the top-performing modern GO algorithms.
MSC:
90Bxx Operations research and management science
Software:
SNOPT; Numba; AMPL; UMAP; t-SNE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achlioptas, D., Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J. Comput. Syst. Sci., 66, 4, 671-687 (2003) · Zbl 1054.68040
[2] Awad, N. H.; Ali, M. Z.; Suganthan, P. N., Ensemble sinusoidal differential covariance matrix adaptation with euclidean neighborhood for solving cec2017 benchmark problems, IEEE Congress on Evolutionary Computation (CEC), 2017, 372-379 (2017)
[3] Bäck, T.; Schwefel, H.-P., An overview of evolutionary algorithms for parameter optimization, Evol. Comput., 1, 1, 1-23 (1993)
[4] Bagattini, F.; Schoen, F.; Tigli, L., Clustering methods for the optimization of atomic cluster structure, J. Chem. Phys., 148, 14, Article 144102 pp. (2018)
[5] Bagattini, F.; Schoen, F.; Tigli, L., Clustering methods for large scale geometrical global optimization, Optimiz. Methods Software, 34, 5, 1099-1122 (2019) · Zbl 1429.90053
[6] Cabassi, F., Locatelli, M., 2016. Computational investigation of simple memetic approaches for continuous global optimization, Comput. Oper. Res. 72, 50-70. · Zbl 1349.90848
[7] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[8] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A Modeling Language for Mathematical Programming (2002), Duxbury Press
[9] Gill, P. E.; Murray, W.; Saunders, M. A., SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev., 47, 1, 99-131 (2005) · Zbl 1210.90176
[10] Hart, W. E., Adaptive global optimization with local search (1994), University of California at San Diego, (Ph.D. thesis)
[11] Johnson, W. B.; Lindenstrauss, J.; Schechtman, G., Extensions of Lipschitz maps into Banach spaces, Israel J. Math., 54, 2, 129-138 (1986) · Zbl 0626.46007
[12] Kumar, A.; Misra, R. K.; Singh, D., Improving the local search capability of effective butterfly optimizer using covariance matrix adapted retreat phase, IEEE Congress on Evolutionary Computation (CEC), 2017, 1835-1842 (2017)
[13] Lam, S.K., Pitrou, A., Seibert, S., 2015. Numba: A llvm-based python jit compiler, in: Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, LLVM ’15, pp. 7:1-7:6.
[14] Liang, J.; Qu, B.; Suganthan, P., Problem definitions and evaluation criteria for the cec, special session and competition on single objective real-parameter numerical optimization, 635 (2014), Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University: Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University Singapore
[15] Locatelli, M., Schoen, F., 2013. Global Optimization: theory, algorithms, and applications, Vol. MO15 of MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics and the Mathematical Optimization Society. · Zbl 1286.90003
[16] Locatelli, M.; Maischberger, M.; Schoen, F., Differential evolution methods based on local searches, Comput. Oper. Res., 43, 169-180 (2014) · Zbl 1348.90529
[17] Maaten, L. V.D.; Hinton, G., Visualizing data using t-sne, J. Mach. Learn. Res., 9, Nov, 2579-2605 (2008) · Zbl 1225.68219
[18] McInnes, L., Healy, J., Melville, J., 2018. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, ArXiv e-prints arXiv:1802.03426.
[19] Moré, J. J.; Wild, S. M., Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 1, 172-191 (2009) · Zbl 1187.90319
[20] Noman, N.; Iba, H., Accelerating differential evolution using an adaptive local search, IEEE Trans. Evol. Comput., 12, 1, 107-125 (2008)
[21] Rinnooy Kan, A. H.G.; Timmer, G. T., Stochastic global optimization methods. Part I: Clustering methods, Math. Program., 39, 27-56 (1987) · Zbl 0634.90066
[22] Rinnooy Kan, A. H.G.; Timmer, G. T., Stochastic global optimization methods. Part II: Multi level methods, Math. Program., 39, 57-78 (1987) · Zbl 0634.90067
[23] Schwefel, H.-P., Numerical Optimization of Computer Models (1981), John Wiley
[24] Storn, R., Price, K., 1995. Differential evolution: A simple and efficient adaptive scheme for global optimization over continuous spaces, J. Global Optim. 23. · Zbl 0888.90135
[25] Tanabe, R.; Fukunaga, A. S., Improving the search performance of shade using linear population size reduction, IEEE Congress on Evolutionary Computation (CEC), 2014, 1658-1665 (2014)
[26] Tenne, Y.; Armfield, S. W., A memetic algorithm using a trust-region derivative-free optimization with quadratic modelling for optimization of expensive and noisy black-box functions, (Yang, S.; Ong, Y.-S.; Jin, Y., Evolutionary Computation in Dynamic and Uncertain Environments (2007), Springer: Springer Berlin Heidelberg), 389-415
[27] Törn, A. A., Cluster analysis using seed points and density-determined hyperspheres as an aid to global optimization, IEEE Trans. Syst., Man, Cybern., 7, 8, 610-616 (1977) · Zbl 0361.62053
[28] Törn, A.; Žilinskas, A., Global optimization, vol. 350 (1989), Springer · Zbl 0752.90075
[29] Wu, G., Mallipeddi, R., Suganthan, P., 2017. Problem definitions and evaluation criteria for the cec 2017 competition on constrained real-parameter optimization, National University of Defense Technology, Changsha, Hunan, PR China and Kyungpook National University, Daegu, South Korea and Nanyang Technological University, Singapore, Technical Report.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.