REPOSITORY > RESULTS

Abstract

In optimization, it is well known that algorithm performance is dependent on the problem
being solved. As a consequence of this, achieving good optimization results requires correctly
matching an optimization problem to a specific optimization algorithm that performs
well on that problem. For this to be possible, knowledge of both optimization algorithms
and optimization problems is required. However, while a large amount of work has been
dedicated to analyzing and creating optimization algorithms, there is a relatively limited
amount of research available that analyzes optimization problems. In this thesis, we focus
on the analysis of numerical optimization problems using a popular state-of-the-art
method called exploratory landscape analysis, which transforms samples collected from an
optimization problem into numerical descriptors called landscape features.
First, we perform an analysis of the problem sets from two most popular single-objective
numerical optimization benchmarks events. We show that the performance of optimization
algorithms differs on the problems used at these events, which we assume is caused by the
differences in the problems. We show that these differences are also present among the
different years of a single benchmarking event, meaning that an algorithm that achieves
the best performance on the most recent version of the event might not necessarily be the
best-performing algorithm if problems from an older version of the same event are taken
into account. Then, we further examine these two problem sets by calculating exploratory
landscape analysis features on these problems. We particularly focus on examining the
generalizability of exploratory landscape analysis, and show that some landscape features
used for our experiments are highly sensitive to problem transformations of shifting and
scaling.
Finally, we evaluate the suitability of exploratory landscape analysis for the task of selecting
the best-performing optimization algorithm for a specific problem, called algorithm
selection. Prior work has shown that it can be used for this task when the algorithm selection
model is both trained and tested on the problems of a single benchmark set. In our
experiments, we instead examine the generalizability of such a meta-learning method. We
train an algorithm selection model on a set of algorithmically generated problems in order
to create a training set that has never been examined before. We use this set to predict the
best-performing algorithms on the problems of an existing optimization benchmark problem
set. This experiment produces low-quality results, indicating that the algorithmically
generated problems are not generalizable to the set of existing benchmark problems when
exploratory landscape analysis is used to describe the problems.
The main contribution of the thesis is an in-depth and systematic examination of
optimization problems, with a focus on exploratory landscape analysis. We show that while
exploratory landscape analysis can be used to describe optimization problem landscapes,
this must be done with caution and understanding that some landscape features can be
sensitive to even simple problem transformations. Additionally, when used for algorithm
selection, we show that these features might be unable to generalize among different sets
of problems.