10 Sequential Parameter Optimization for Mixed-Discrete Problems
345
With respect to mixed or discrete problems, Kriging is actually very flexible. By
changing the kernel (or correlation) function, any search space may be modeled
with Kriging [8, 59]. The flexibility of this modeling method renders Kriging one
of the most promising mixed-variable models. Take for example a typical problem
characterization from algorithm tuning: Parameters like mutation rates may be realvalued, and the choice between different mutation operators may be a categorical
parameter. Hence, if x i (the i-th dimension of a parameter configuration
x) is a factor
variable, Hamming distance can be used, otherwise the absolute deviation may be
used for real-valued variables. The reader is referred to the discussion in [8].
10.4.3 Optimization Algorithms for the Metamodel
As shown in Algorithm 1, the next step in the SPOT methodology, after constructing
a model, consists in the employment of optimizers that search for promising
candidate solutions. Standard techniques from mathematical programming [56], the
so-called mixed-integer nonlinear programming methods [17], are commonly not
applicable to deterministic optimization of real-world application problems. These
methods, such as outer approximation [15], branch and bound [11], and generalized
Benders decomposition [20], have difficulties with the mixed design space, multimodality, uncertainty in the observations and unknown black-box properties. A
consolidated alternative consists in the employment of metaheuristics for mixeddiscrete optimization [31]. These strategies propose to heuristically determine
solutions that improve the objective function value.
In cases where mathematical programming techniques are not flexible enough
to yield satisfying results, heuristic search for solutions that improve the objective
function value can lead to interesting results. Metaheuristics for mixed-discrete
optimization are generally categorized in two classes:
• Hierarchical approaches solve problems with continuous variables together and
discrete variables by considering the original optimization as a bi-level problem.
The discrete variables are optimized by the upper level optimization process and
the continuous parameters are optimized in the lower level [33, 53].
• Simultaneous approaches optimize discrete and continuous parameters simultaneously. In this approach, we consider that a similarity of parameter vectors
due to an appropriate metric is equivalent to being positively correlated to the
similarity in function values [31, 44].
In the following we will highlight the peculiarities of an algorithm from the
class of simultaneous approaches. These algorithms are a better choice for our
purposes. They need fewer observations and consider correlations between discrete
and continuous variables. This is in contrast to the hierarchical approaches where
variables of different type are strictly separated from each other. Particularly, we
will discuss the mixed-integer evolution strategy (MIES) proposed in [31].
345
With respect to mixed or discrete problems, Kriging is actually very flexible. By
changing the kernel (or correlation) function, any search space may be modeled
with Kriging [8, 59]. The flexibility of this modeling method renders Kriging one
of the most promising mixed-variable models. Take for example a typical problem
characterization from algorithm tuning: Parameters like mutation rates may be realvalued, and the choice between different mutation operators may be a categorical
parameter. Hence, if x i (the i-th dimension of a parameter configuration
x) is a factor
variable, Hamming distance can be used, otherwise the absolute deviation may be
used for real-valued variables. The reader is referred to the discussion in [8].
10.4.3 Optimization Algorithms for the Metamodel
As shown in Algorithm 1, the next step in the SPOT methodology, after constructing
a model, consists in the employment of optimizers that search for promising
candidate solutions. Standard techniques from mathematical programming [56], the
so-called mixed-integer nonlinear programming methods [17], are commonly not
applicable to deterministic optimization of real-world application problems. These
methods, such as outer approximation [15], branch and bound [11], and generalized
Benders decomposition [20], have difficulties with the mixed design space, multimodality, uncertainty in the observations and unknown black-box properties. A
consolidated alternative consists in the employment of metaheuristics for mixeddiscrete optimization [31]. These strategies propose to heuristically determine
solutions that improve the objective function value.
In cases where mathematical programming techniques are not flexible enough
to yield satisfying results, heuristic search for solutions that improve the objective
function value can lead to interesting results. Metaheuristics for mixed-discrete
optimization are generally categorized in two classes:
• Hierarchical approaches solve problems with continuous variables together and
discrete variables by considering the original optimization as a bi-level problem.
The discrete variables are optimized by the upper level optimization process and
the continuous parameters are optimized in the lower level [33, 53].
• Simultaneous approaches optimize discrete and continuous parameters simultaneously. In this approach, we consider that a similarity of parameter vectors
due to an appropriate metric is equivalent to being positively correlated to the
similarity in function values [31, 44].
In the following we will highlight the peculiarities of an algorithm from the
class of simultaneous approaches. These algorithms are a better choice for our
purposes. They need fewer observations and consider correlations between discrete
and continuous variables. This is in contrast to the hierarchical approaches where
variables of different type are strictly separated from each other. Particularly, we
will discuss the mixed-integer evolution strategy (MIES) proposed in [31].