soogo.acquisition module

Acquisition functions for surrogate optimization.

class soogo.acquisition.AcquisitionFunction(optimizer=None, mi_optimizer=None, rtol: float = 1e-06, termination: TerminationCondition | None = None) → None

Bases: ABC

Base class for acquisition functions.

This an abstract class. Subclasses must implement the method optimize().

Acquisition functions are strategies to propose new sample points to a surrogate. The acquisition functions here are modeled as objects with the goals of adding states to the learning process. Moreover, this design enables the definition of the optimize() method with a similar API when we compare different acquisition strategies.

Parameters:

• optimizer – Continuous optimizer to be used for the acquisition function. Default is Differential Evolution (DE) from pymoo. (default: None)

• mi_optimizer – Mixed-integer optimizer to be used for the acquisition function. Default is Genetic Algorithm (MixedVariableGA) from pymoo. (default: None)

• rtol (float) – Minimum distance between a candidate point and the previously selected points relative to the domain size. Default is 1e-6. (default: 1e-06)

optimizer

Continuous optimizer to be used for the acquisition function. This is used in optimize().

mi_optimizer

Mixed-integer optimizer to be used for the acquisition function. This is used in optimize().

rtol

Minimum distance between a candidate point and the previously selected points. This figures out as a constraint in the optimization problem solved in optimize().

has_converged() → bool

Check if the acquisition function has converged.

This method is used to check if the acquisition function has converged based on a termination criterion. The default implementation always returns False.

Return type:

bool

abstractmethod optimize(surrogateModel: Surrogate, bounds, n: int = 1, **kwargs) → ndarray

Propose a maximum of n new sample points to improve the surrogate.

Parameters:

• surrogateModel (Surrogate) – Surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Number of requested points. Mind that the number of points returned may be smaller than n, depending on the implementation. (default: 1)

Return type:

ndarray

Returns:

m-by-dim matrix with the selected points, where m <= n.

tol(bounds) → float

Compute tolerance used to eliminate points that are too close to previously selected ones.

The tolerance value is based on rtol and the diameter of the largest d-dimensional cube that can be inscribed whithin the bounds.

Parameters:

bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

Return type:

float

update(out: OptimizeResult, model: Surrogate) → None

Update the acquisition function knowledge about the optimization process.

Return type:

None

class soogo.acquisition.CoordinatePerturbationOverNondominated(acquisitionFunc: WeightedAcquisition, **kwargs) → None

Bases: AcquisitionFunction

Coordinate perturbation acquisition function over the nondominated set.

This acquisition method was proposed in [1]. It perturbs locally each of the non-dominated sample points to find new sample points. The perturbation is performed by acquisitionFunc.

Parameters:

acquisitionFunc (WeightedAcquisition) – Weighted acquisition function with a normal sampler. Stored in acquisitionFunc.

acquisitionFunc

Weighted acquisition function with a normal sampler.

References

[1]

Juliane Mueller. SOCEMO: Surrogate Optimization of Computationally Expensive Multiobjective Problems. INFORMS Journal on Computing, 29(4):581-783, 2017. https://doi.org/10.1287/ijoc.2017.0749

optimize(surrogateModel: Surrogate, bounds, n: int = 1, *, nondominated=(), paretoFront=(), **kwargs) → ndarray

Acquire k points, where k <= n.

Parameters:

• surrogateModel (Surrogate) – Multi-target surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Maximum number of points to be acquired. (default: 1)

• nondominated – Nondominated set in the objective space. (default: ())

• paretoFront – Pareto front in the objective space. (default: ())

Return type:

ndarray

class soogo.acquisition.EndPointsParetoFront(**kwargs) → None

Bases: AcquisitionFunction

Obtain endpoints of the Pareto front as described in [2].

For each component i in the target space, this algorithm solves a cheap auxiliary optimization problem to minimize the i-th component of the trained surrogate model. Points that are too close to each other and to training sample points are eliminated. If all points were to be eliminated, consider the whole variable domain and sample at the point that maximizes the minimum distance to training sample points.

References

[2]

Juliane Mueller. SOCEMO: Surrogate Optimization of Computationally Expensive Multiobjective Problems. INFORMS Journal on Computing, 29(4):581-783, 2017. https://doi.org/10.1287/ijoc.2017.0749

optimize(surrogateModel: Surrogate, bounds, n: int = 1, **kwargs) → ndarray

Acquire k points at most, where k <= n.

Parameters:

• surrogateModel (Surrogate) – Multi-target surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Maximum number of points to be acquired. (default: 1)

Return type:

ndarray

Returns:

k-by-dim matrix with the selected points.

class soogo.acquisition.GosacSample(fun, **kwargs) → None

Bases: AcquisitionFunction

GOSAC acquisition function as described in [3].

Minimize the objective function with surrogate constraints. If a feasible solution is found and is different from previous sample points, return it as the new sample. Otherwise, the new sample is the point that is farthest from previously selected sample points.

This acquisition function is only able to acquire 1 point at a time.

Parameters:

fun – Objective function. Stored in fun.

fun

Objective function.

References

[3]

Juliane Mueller and Joshua D. Woodbury. GOSAC: global optimization with surrogate approximation of constraints. J Glob Optim, 69:117-136, 2017. https://doi.org/10.1007/s10898-017-0496-y

optimize(surrogateModel: Surrogate, bounds, n: int = 1, **kwargs) → ndarray

Acquire 1 point.

Parameters:

• surrogateModel (Surrogate) – Multi-target surrogate model for the constraints.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Unused. (default: 1)

Return type:

ndarray

Returns:

1-by-dim matrix with the selected points.

class soogo.acquisition.MaximizeEI(sampler=None, avoid_clusters: bool = True, **kwargs) → None

Bases: AcquisitionFunction

Acquisition by maximization of the expected improvement of a Gaussian Process.

It starts by running a global optimization algorithm to find a point xs that maximizes the EI. If this point is found and the sample size is 1, return this point. Else, creates a pool of candidates using sampler and xs. From this pool, select the set of points with that maximize the expected improvement. If avoid_clusters is True avoid points that are too close to already chosen ones inspired in the strategy from [4]. Mind that the latter strategy can slow down considerably the acquisition process, although is advisable for a sample of good quality.

Parameters:

• sampler – Sampler to generate candidate points. Stored in sampler. (default: None)

• avoid_clusters (bool) – When True, use a strategy that avoids points too close to already chosen ones. Stored in avoid_clusters. (default: True)

sampler

Sampler to generate candidate points.

avoid_clusters

When True, use a strategy that avoids points too close to already chosen ones.

References

[4]

Che Y, Müller J, Cheng C. Dispersion-enhanced sequential batch sampling for adaptive contour estimation. Qual Reliab Eng Int. 2024; 40: 131–144. https://doi.org/10.1002/qre.3245

optimize(surrogateModel: GaussianProcess, bounds, n: int = 1, *, ybest=None) → ndarray

Acquire n points.

Run a global optimization procedure to try to find a point that has the highest expected improvement for the Gaussian Process. Moreover, if ybest isn’t provided, run a global optimization procedure to find the minimum value of the surrogate model. Use the minimum point as a candidate for this acquisition.

This implementation only works for continuous design variables.

Parameters:

• surrogateModel (GaussianProcess) – Surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Number of points to be acquired. (default: 1)

• ybest – Best point so far. If not provided, find the minimum value for the surrogate. Use it as a possible candidate. (default: None)

Return type:

ndarray

class soogo.acquisition.MinimizeMOSurrogate(**kwargs) → None

Bases: AcquisitionFunction

Obtain pareto-optimal sample points for the multi-objective surrogate model.

Parameters:

• optimizer – Continuous multi-objective optimizer. If None, use NSGA2 from pymoo.

• mi_optimizer – Mixed-integer multi-objective optimizer. If None, use MixedVariableGA from pymoo with RankAndCrowding survival strategy.

optimize(surrogateModel: Surrogate, bounds, n: int = 1, **kwargs) → ndarray

Acquire k points, where k <= n.

Parameters:

• surrogateModel (Surrogate) – Multi-target surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Maximum number of points to be acquired. If n is zero, use all points in the Pareto front. (default: 1)

Return type:

ndarray

Returns:

k-by-dim matrix with the selected points.

class soogo.acquisition.MinimizeSurrogate(nCand: int, rtol: float = 0.001, **kwargs) → None

Bases: AcquisitionFunction

Obtain sample points that are local minima of the surrogate model.

This implementation is based on the one of MISO-MS used in the paper [5]. The original method, Multi-level Single-Linkage, was described in [6]. In each iteration, the algorithm generates a pool of candidates and select the best candidates (lowest predicted value) that are far enough from each other. The number of candidates chosen as well as the distance threshold vary with each iteration. The hypothesis is that the successful candidates each belong to a different region in the space, which may contain a local minimum, and those regions cover the whole search space. In the sequence, the algorithm runs multiple local minimization procedures using the successful candidates as local guesses. The results of the minimization are collected for the new sample.

Parameters:

• nCand (int) – Number of candidates used on each iteration.

• rtol (float) – Minimum distance between a candidate point and the previously selected points relative to the domain size. Default is 1e-3. (default: 0.001)

sampler

Sampler to generate candidate points.

References

[5]

Müller, J. MISO: mixed-integer surrogate optimization framework. Optim Eng 17, 177–203 (2016). https://doi.org/10.1007/s11081-015-9281-2

[6]

Rinnooy Kan, A.H.G., Timmer, G.T. Stochastic global optimization methods part II: Multi level methods. Mathematical Programming 39, 57–78 (1987). https://doi.org/10.1007/BF02592071

optimize(surrogateModel: Surrogate, bounds, n: int = 1, **kwargs) → ndarray

Acquire n points based on MISO-MS from Müller (2016).

The critical distance is the same used in the seminal work from Rinnooy Kan and Timmer (1987).

Parameters:

• surrogateModel (Surrogate) – Surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Max number of points to be acquired. (default: 1)

Return type:

ndarray

Returns:

n-by-dim matrix with the selected points.

class soogo.acquisition.ParetoFront(oldTV=(), **kwargs) → None

Bases: AcquisitionFunction

Obtain sample points that fill gaps in the Pareto front from [7].

The algorithm proceeds as follows to find each new point:

1. Find a target value \(\tau\) that should fill a gap in the Pareto front. Make sure to use a target value that wasn’t used before.

2. Solve a multi-objective optimization problem that minimizes \(\|s_i(x)-\tau\|\) for all \(x\) in the search space, where \(s_i(x)\) is the i-th target value predicted by the surrogate for \(x\).

3. If a Pareto-optimal solution was found for the problem above, chooses the point that minimizes the L1 distance to \(\tau\) to be part of the new sample.

Parameters:

• optimizer – Continuous multi-objective optimizer. If None, use NSGA2 from pymoo.

• mi_optimizer – Mixed-integer multi-objective optimizer. If None, use MixedVariableGA from pymoo with RankAndCrowding survival strategy.

• oldTV – Old target values to be avoided in the acquisition. Copied to oldTV. (default: ())

oldTV

Old target values to be avoided in the acquisition of step 1.

References

[7]

Juliane Mueller. SOCEMO: Surrogate Optimization of Computationally Expensive Multiobjective Problems. INFORMS Journal on Computing, 29(4):581-783, 2017. https://doi.org/10.1287/ijoc.2017.0749

optimize(surrogateModel: Surrogate, bounds, n: int = 1, *, nondominated=(), paretoFront=(), **kwargs) → ndarray

Acquire k points, where k <= n.

Perform n attempts to find n points to fill gaps in the Pareto front.

Parameters:

• surrogateModel (Surrogate) – Multi-target surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Number of points to be acquired. (default: 1)

• nondominated – Nondominated set in the objective space. (default: ())

• paretoFront – Pareto front in the objective space. If not provided, use the surrogate to compute it. (default: ())

Return type:

ndarray

Returns:

k-by-dim matrix with the selected points.

pareto_front_target(paretoFront: ndarray) → ndarray

Find a target value that should fill a gap in the Pareto front.

As suggested by Mueller (2017), the algorithm fits a linear RBF model with the points in the Pareto front. This will represent the (d-1)-dimensional Pareto front surface. Then, the algorithm searches the a value in the surface that maximizes the distances to previously selected target values and to the training points of the RBF model. This value is projected in the d-dimensional space to obtain \(\tau\).

Parameters:

paretoFront (ndarray) – Pareto front in the objective space.

Return type:

ndarray

Returns:

The target value \(\tau\).

class soogo.acquisition.TargetValueAcquisition(cycleLength: int = 6, **kwargs) → None

Bases: AcquisitionFunction

Target value acquisition function for the RBF model based on [8], [9], and [10].

Every iteration of the algorithm sequentially chooses a number from 0 to cycleLength + 1 (inclusive) and runs one of the procedures:

• Inf-step (0): Selects a sample point that minimizes the \(\mu\) measure, i.e., mu_measure(). The point selected is the farthest from the current sample using the kernel measure.

• Global search (1 to cycleLength): Minimizes the product of \(\mu\) measure by the distance to a target value. The target value is based on the distance to the current minimum of the surrogate. The described measure is known as the ‘bumpiness measure’.

• Local search (cycleLength + 1): Minimizes the bumpiness measure with a target value equal to the current minimum of the surrogate. If the current minimum is already represented by the training points of the surrogate, do a global search with a target value slightly smaller than the current minimum.

After each sample point is chosen we verify how close it is from the current sample. If it is too close, we replace it by a random point in the domain drawn from an uniform distribution. This is strategy was proposed in [11].

Parameters:

cycleLength (int) – Length of the global search cycle. Stored in cycleLength. (default: 6)

cycleLength

Length of the global search cycle to be used in optimize().

_cycle

Internal counter of cycles. The value to be used in the next call of optimize().

References

[8]

Gutmann, HM. A Radial Basis Function Method for Global Optimization. Journal of Global Optimization 19, 201–227 (2001). https://doi.org/10.1023/A:1011255519438

[9]

Björkman, M., Holmström, K. Global Optimization of Costly Nonconvex Functions Using Radial Basis Functions. Optimization and Engineering 1, 373–397 (2000). https://doi.org/10.1023/A:1011584207202

[10]

Holmström, K. An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. J Glob Optim 41, 447–464 (2008). https://doi.org/10.1007/s10898-007-9256-8

[11]

Müller, J. MISO: mixed-integer surrogate optimization framework. Optim Eng 17, 177–203 (2016). https://doi.org/10.1007/s11081-015-9281-2

static bumpiness_measure(surrogate: RbfModel, x: ndarray, target, target_range=1.0)

Compute the bumpiness of the surrogate model.

The bumpiness measure \(g_y\) was first defined by Gutmann (2001) with suggestions of usage for global optimization with RBF functions. Gutmann notes that \(g_y(x)\) tends to infinity when \(x\) tends to a training point of the surrogate, and so they use \(-1/g_y(x)\) for the minimization problem. Björkman and Holmström use \(-\log(1/g_y(x))\), which is the same as minimizing \(\log(g_y(x))\), to avoid a flat minimum. This option seems to slow down convergence rates for \(g_y(x)\) in [0,1] since it increases distances in that range.

The present implementation uses genetic algorithms by default, so there is no point in trying to make \(g_y\) smoother.

Parameters:

• surrogate (RbfModel) – RBF surrogate model.

• x (ndarray) – Possible point to be added to the surrogate model.

• target – Target value.

• target_range – Known range in the target space. Used to scale the function values to avoid overflow. (default: 1.0)

optimize(surrogateModel: RbfModel, bounds, n: int = 1, *, sampleStage: int = -1, **kwargs) → ndarray

Acquire n points following the algorithm from Holmström et al.(2008).

Parameters:

• surrogateModel (RbfModel) – Surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Number of points to be acquired. (default: 1)

• sampleStage (int) – Stage of the sampling process. The default is -1, which means that the stage is not specified. (default: -1)

Return type:

ndarray

Returns:

n-by-dim matrix with the selected points.

class soogo.acquisition.WeightedAcquisition(sampler, weightpattern=None, maxeval: int = 0, sigma_min: float = 0.0, sigma_max: float = 0.25, **kwargs) → None

Bases: AcquisitionFunction

Select candidates based on the minimization of an weighted average score.

The weighted average is \(w f_s(x) + (1-w) (-d_s(x))\), where \(f_s(x)\) is the surrogate value at \(x\) and \(d_s(x)\) is the distance of \(x\) to its closest neighbor in the current sample. Both values are scaled to the interval [0, 1], based on the maximum and minimum values for the pool of candidates. The sampler generates the candidate points to be scored and then selected.

This acquisition method is prepared deals with multi-objective optimization following the random perturbation strategy in [12] and [13]. More specificaly, the algorithm takes the average value among the predicted target values given by the surrogate. In other words, \(f_s(x)\) is the average value between the target components of the surrogate model evaluate at \(x\).

Parameters:

• sampler (Sampler) – Sampler to generate candidate points. Stored in sampler.

• weightpattern (float|sequence) – Weight(s) w to be used in the score. Stored in weightpattern. The default value is [0.2, 0.4, 0.6, 0.9, 0.95, 1].

• maxeval (int) – Description Stored in maxeval. (default: 0)

neval

Number of evaluations done so far. Used and updated in optimize().

sampler

Sampler to generate candidate points. Used in optimize().

weightpattern

Weight(s) w to be used in the score. This is a circular list that is rotated every time optimize() is called.

maxeval

Maximum number of evaluations. A value 0 means there is no maximum.

References

[12]

Regis, R. G., & Shoemaker, C. A. (2012). Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Engineering Optimization, 45(5), 529–555. https://doi.org/10.1080/0305215X.2012.687731

[13]

Juliane Mueller. SOCEMO: Surrogate Optimization of Computationally Expensive Multiobjective Problems. INFORMS Journal on Computing, 29(4):581-783, 2017. https://doi.org/10.1287/ijoc.2017.0749

static argminscore(scaledvalue: ndarray, dist: ndarray, weight: float, tol: float) → int

Gets the index of the candidate point that minimizes the score.

The score is \(w f_s(x) + (1-w) (-d_s(x))\), where

• \(w\) is a weight.

• \(f_s(x)\) is the estimated value for the objective function on x, scaled to [0,1].

• \(d_s(x)\) is the minimum distance between x and the previously selected evaluation points, scaled to [-1,0].

Returns -1 if there is no feasible point.

Parameters:

• scaledvalue (ndarray) – Function values \(f_s(x)\) scaled to [0, 1].

• dist (ndarray) – Minimum distance between a candidate point and previously evaluated sampled points.

• weight (float) – Weight \(w\).

• tol (float) – Tolerance value for excluding candidates that are too close to current sample points.

Return type:

int

minimize_weightedavg_fx_distx(x: ndarray, distx: ndarray, fx: ndarray, n: int, tol: float) → tuple[ndarray, ndarray]

Select n points from a pool of candidates using argminscore() iteratively.

The score on the iteration i > 1 uses the distances to cadidates selected in the iterations 0 to i-1.

Parameters:

• x (ndarray) – Matrix with candidate points.

• distx (ndarray) – Matrix with the distances between the candidate points and the m number of rows of x.

• fx (ndarray) – Vector with the estimated values for the objective function on the candidate points.

• n (int) – Number of points to be selected for the next costly evaluation.

• tol (float) – Tolerance value for excluding candidates that are too close to current sample points.

Return type:

tuple[ndarray, ndarray]

Returns:

• n-by-dim matrix with the selected points.

• n-by-(n+m) matrix with the distances between the n selected points and the (n+m) sampled points (m is the number of points that have been sampled so far).

optimize(surrogateModel: Surrogate, bounds, n: int = 1, **kwargs) → ndarray

Generate a number of candidates using the sampler. Then, select up to n points that maximize the score.

When sampler.strategy is soogo.sampling.SamplingStrategy.DDS or soogo.sampling.SamplingStrategy.DDS_UNIFORM, the probability is computed based on the DYCORS method as proposed by Regis and Shoemaker (2012).

Parameters:

• surrogateModel (Surrogate) – Surrogate model.

• bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

• n (int) – Number of points requested. (default: 1)

• xbest – Best point so far. Used if sampler is an instance of soogo.sampling.NormalSampler. If not provided, compute it based on the training data for the surrogate.

Return type:

ndarray

Returns:

m-by-dim matrix with the selected points, where m <= n.

static score(sx, dx, weight: float, sx_min: float = 0.0, sx_max: float = 1.0, dx_max: float = 1.0) → float

Computes the score.

The score is

\[w \frac{s(x)-s_{min}}{s_{max}-s_{min}} + (1-w) \frac{d_{max}-d(x,X)}{d_{max}},\]

where:

• \(w\) is a weight.

• \(s(x)\) is the value for the surrogate model on x.

• \(d(x,X)\) is the minimum distance between x and the previously

  selected evaluation points.

• \(s_{min}\) is the minimum value of the surrogate model.

• \(s_{max}\) is the maximum value of the surrogate model.

• \(d_{max}\) is the maximum distance between a candidate point and

  the set X of previously selected evaluation points.

In case \(s_{max} = s_{min}\), the score is computed as

\[\frac{d_{max}-d(x,X)}{d_{max}}.\]

Parameters:

• sx – Function value(s) \(s(x)\).

• dx – Distance(s) between candidate(s) and the set X.

• weight (float) – Weight \(w\).

• sx_min (float) – Minimum value of the surrogate model. (default: 0.0)

• sx_max (float) – Maximum value of the surrogate model. (default: 1.0)

• dx_max (float) – Maximum distance between a candidate point and the set X. (default: 1.0)

Return type:

float

tol(bounds) → float

Compute tolerance used to eliminate points that are too close to previously selected ones.

The tolerance value is based on rtol and the diameter of the largest d-dimensional cube that can be inscribed whithin the bounds.

Parameters:

bounds (sequence) – List with the limits [x_min,x_max] of each direction x in the space.

Return type:

float

update(out: OptimizeResult, model: Surrogate) → None

Update the acquisition function knowledge about the optimization process.

Return type:

None