Variability Map of Objective Function for Analysis of Global Optimization Problem Characteristic Features

Authors: Agasiev T.A. Published: 17.04.2019
Published in issue: #2(125)/2019  
DOI: 10.18698/0236-3933-2019-2-4-21

Category: Informatics, Computer Engineering and Control | Chapter: System Analysis, Control, and Information Processing  
Keywords: global optimization, objective function, characteristic features of optimization problem, landscape analysis, landscape sample, information content, variability map

Methods of landscape analysis are developed to estimate various characteristic features of the objective function in the optimization problem. The accuracy of the estimates largely depends on the chosen method of experiment design for the landscape sampling, i.e. on the number and location of points in the search space forming a discrete representation of the objective function landscape. The method of information content is the most resistant to changes in the experiment design but requires route building to bypass the obtained points of landscape sampling. A method of characterization of the optimization problem objective function is proposed on the base of landscape sampling without building a route to bypass its points. The notion of a variability map of objective function is introduced. The informativeness criteria are formulated for groups of points of a landscape sample. A method of constructing the so-called full variability map is proposed as well as the function of generalized information content for the analysis of the characteristic features of the objective function. The method allows obtaining more accurate estimates of target function characteristics which are resistant to variations of the experiment design


[1] Shan S., Wang G.G. Survey of modeling and optimization strategies to solve high-dimensional design problems with computationally-expensive black-box functions. Struct. Multidisc. Optim., 2010, vol. 41, no. 2, pp. 219--241. DOI: 10.1007/s00158-009-0420-2

[2] Kerschke P. Comprehensive feature-based landscape analysis of continuous and constrained optimization problems using the R-Package flacco. arXiv.org: website. Available at: https://arxiv.org/abs/1708.05258v1 (accessed: 28.12.2018).

[3] Agasiev T.A., Karpenko A.P. Modern techniques of global optimization. Review. Informatsionnye tekhnologii [Information Technologies], 2018, vol. 6, no. 24, pp. 363--370 (in Russ.). DOI: 10.17587/it.24.370-386

[4] Cavazzuti M. Design of experiments. Optimization methods. Springer, 2013, pp. 13--42.

[5] Li G., Aute V., Azarm S. An accumulative error based adaptive design of experiments for offline metamodeling. Struct. Multidisc. Optim., 2010, vol. 40, no. 1, pp. 137--155. DOI: 10.1007/s00158-009-0395-z

[6] Forrester A.I.J., Keane A.J. Recent advances in surrogate-based optimization. Prog. Aerosp. Sci., 2009, vol. 45, no. 1-3, pp. 50--79. DOI: 10.1016/j.paerosci.2008.11.001

[7] Mersmann O., Bischl B., Trautmann H., et al. Exploratory landscape analysis. Proc. 13th Ann. Conf. Genetic and Evolutionary Comp. ACM, 2011, pp. 829--836. DOI: 10.1145/2001576.2001690

[8] Hoos H.H., Neumann F., Trautmann H. Automated algorithm selection and configuration (Dagstuhl Seminar 16412). Dagstuhl Reports, 2017, vol. 6, no. 10, pp. 34--74.

[9] Kerschke P., et al. Cell mapping techniques for exploratory landscape analysis. EVOLVE  ---  A bridge between probability, set oriented numerics, and evolutionary compu-tation. Springer, 2014, pp. 115--131.

[10] Flamm C., Hofacker I.L., Stadler P.F. Barrier trees of degenerate landscapes. Zeitschrift für Physikalische Chemie, 2002, vol. 216, no. 2, p. 155. DOI: 10.1524/zpch.2002.216.2.155

[11] Kerschke P., Preuss M., Wessing S., et al. Detecting funnel structures by means of exploratory landscape analysis. Proc. 2015 Ann. Conf. Genetic and Evolutionary Comp. ACM, 2015, pp. 265--272. DOI: 10.1145/2739480.2754642

[12] Munoz M.A., Kirley M., Halgamuge S.K. Exploratory landscape analysis of continuous space optimization problems using information content. IEEE Trans. Evol. Comput., 2015, vol. 19, no. 1, pp. 74--87. DOI: 10.1109/TEVC.2014.2302006

[13] Momin J., Yang X.S. A literature survey of benchmark functions for global optimization problems. IJMMNO, 2013, vol. 4, no. 2, pp. 150--194. DOI: 10.1504/IJMMNO.2013.055204

[14] Lawder J.K., King P.J.H. Using space-filling curves for multi-dimensional indexing. British National Conf. on Databases. Springer, 2000, pp. 20--35.