Detecting funnel structures of continuous single-objective optimization problems by means of exploratory landscape analysis

5:20 pm - 5:45 pm 24 Thursday

Track

Theory

In single-objective optimization, the performance of an optimization algorithm strongly relies on the structure and characteristics of the optimization problem at hand. The knowledge of its structure allows to choose between algorithms, which aim at exploring the entire search space, and algorithms that focus on exploiting the function’s global structure. The latter is advisable, if the underlying structure represents a so-called funnel, i.e. a function whose local optima lead towards the global optimum as exemplarily shown in the second panel of Figure 1. In recent years, the concept of Exploratory Landscape Analysis has evolved [1, 2, 3]. It automatically identifies problem characteristics based on a moderately small initial sample of the objective function. Furthermore, in combination with efficient machine learning techniques,it has proven to be a very effective approach for algorithm selection problems in continuous black-box optimization.

In this work, specific features for detecting funnel structures are introduced and then combined with already existing ones. The entire set is used for fitting different classification models on specifically generated multimodal test instances. All classifiers are binary, i.e. they classify whether the underlying structure of an optimization problem is a funnel or a random structure. The quality of those models is then validated on standard benchmark problems.The ability to detect, whether an unknown black-box optimization problem has the funnel property, can be considered as the first, necessary step for algorithm selection. Therefore, we suggest a two-stage approach when creating the algorithm selection model. First, the unknown optimization instance should be classified into funnel / random. In a second step, this binary feature will be included in the feature set and used for selecting the best optimization algorithm (out of a portfolio of algorithms) for that specific instance.

References

[1] B. Bischl, O. Mersmann, H. Trautmann, and M. Preuss. Algorithm selection based on exploratory landscape analysis and cost-sensitive learning.Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO ’12), 313–320, 2012.

[2] P. Kerschke, M. Preuss, C. Hernández, O. Schütze, J. Sun, C. Grimme, G. Rudolph, B. Bischl, andH. Trautmann. Cell Mapping Techniques for Exploratory Landscape Analysis.EVOLVE – A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V, 288:115–131, 2014.

[3] P. Kerschke, M. Preuss, S. Wessing, and H. Trautmann. Detecting Funnel Structures by Means of Exploratory Landscape Analysis.Proceedings of the 17th Annual Conference on Genetic and EvolutionaryComputation (GECCO ’15), 265–272, 2015.

Speaker:
Pascal Kerschke