Landscape characterization of numerical optimization problems using biased scattered data

The characterization of optimization problems over continuous parameter spaces plays an important role in optimization. A form of “fitness landscape” analysis is often carried out to describe the problem space in terms of modality, smoothness and variable separability. The outcomes of this analysis can then be used as a measure of problem difficulty and to predict the behaviour of a given algorithm. However, the metric value estimates of the landscape characterization are dependent upon the representation scheme adopted and the sampling method used. Consequently, the development of a complete classification of problem structure and complexity has proven to be challenging. In this paper, we continue this line of research. We present a methodology for the characterization of two dimensional numerical optimization problems. In our approach, data extracted during the search process is analyzed and the dependency of the results to the nominated sampling method are corrected. We show via computational simulations that the calculated metric values using our approach are consistent with the results from random experiments. As such, this study provides a first step towards the on-line calculation of fitness landscape characterization metrics and the development of empirical performance models of search algorithms. Advances in these areas would provide answers to the algorithm selection and portfolio configuration problems.