Characteristic feature analysis of continuous optimization problems based on Variability Map of objective function for optimization algorithm configuration

Abstract

Advanced optimization algorithms with a variety of configurable parameters become increasingly difficult to apply effectively to solving optimization problems. Appropriate algorithm configuration becomes highly relevant, still remaining a computationally expensive operation. Development of machine learning methods allows to model and predict the efficiency of different solving strategies and algorithm configurations depending on properties of optimization problem to be solved. The paper suggests the Dependency Decomposition approach to reduce computational complexity of modeling the efficiency of optimization algorithm, also considering the amount of computational resources available for optimization problem solving. The approach requires development of explicit Exploratory Landscape Analysis methods to assess a variety of significant characteristic features of optimization problems. The results of feature assessment depend on the number of sample points analyzed and their location in the design space, on top of that some of methods require additional evaluations of objective function. The paper proposes new landscape analysis methods based on given points without the need of any additional objective function evaluations. An algorithm of building a so-called Full Variability Map is suggested based on informativeness criteria formulated for groups of sample points. The paper suggests Generalized Information Content method for analysis of Full Variability Map which allows to get accurate and stable estimations of objective function features. The Sectorization method of Variability Map analysis is proposed to assess characteristic features reflecting such properties of objective function that are critical for optimization algorithm efficiency. The resulting features are invariant to the scale of objective function gradients which positively affects the generalizing ability of problems classification algorithm. The procedure of the comparative study of effectiveness of landscape analysis algorithms is introduced. The results of computational experiments indicate reliability of applying the suggested landscape analysis methods to optimization problem characterization and classification.

Keywords

• global optimization
• continuous optimization problem
• meta-optimization
• algorithm configuration
• parameter tuning
• dependency decomposition approach
• characteristic features
• exploratory landscape analysis
• variability map
• generalized information content
• sectorization method