Skip to main content
`Ctrl`+`K`
scipy.optimize.

# dual_annealing

scipy.optimize.dual_annealing(func, bounds, args=(), maxiter=1000, minimizer_kwargs=None, initial_temp=5230.0, restart_temp_ratio=2e-05, visit=2.62, accept=-5.0, maxfun=10000000.0, rng=None, no_local_search=False, callback=None, x0=None)

  Find the global minimum of a function using Dual Annealing.

  Parameters:
    func callable

      The objective function to be minimized. Must be in the form `f(x, *args)`, where `x` is the argument in the form of a 1-D array and `args` is a tuple of any additional fixed parameters needed to completely specify the function.

    bounds sequence or `Bounds`

      Bounds for variables. There are two ways to specify the bounds:

      1. Instance of `Bounds` class.

      2. Sequence of `(min, max)` pairs for each element in x.

    args tuple, optional

      Any additional fixed parameters needed to completely specify the objective function.

    maxiter int, optional

      The maximum number of global search iterations. Default value is 1000.

    minimizer_kwargs dict, optional

      Keyword arguments to be passed to the local minimizer (`minimize`). An important option could be `method` for the minimizer method to use. If no keyword arguments are provided, the local minimizer defaults to ‘L-BFGS-B’ and uses the already supplied bounds. If minimizer_kwargs is specified, then the dict must contain all parameters required to control the local minimization. args is ignored in this dict, as it is passed automatically. bounds is not automatically passed on to the local minimizer as the method may not support them.

    initial_temp float, optional

      The initial temperature, use higher values to facilitates a wider search of the energy landscape, allowing dual_annealing to escape local minima that it is trapped in. Default value is 5230. Range is (0.01, 5.e4].

    restart_temp_ratio float, optional

      During the annealing process, temperature is decreasing, when it reaches `initial_temp * restart_temp_ratio`, the reannealing process is triggered. Default value of the ratio is 2e-5. Range is (0, 1).

    visit float, optional

      Parameter for visiting distribution. Default value is 2.62. Higher values give the visiting distribution a heavier tail, this makes the algorithm jump to a more distant region. The value range is (1, 3].

    accept float, optional

      Parameter for acceptance distribution. It is used to control the probability of acceptance. The lower the acceptance parameter, the smaller the probability of acceptance. Default value is -5.0 with a range (-1e4, -5].

    maxfun int, optional

      Soft limit for the number of objective function calls. If the algorithm is in the middle of a local search, this number will be exceeded, the algorithm will stop just after the local search is done. Default value is 1e7.

    rng{None, int, `numpy.random.Generator`}, optional

      If rng is passed by keyword, types other than `numpy.random.Generator` are passed to `numpy.random.default_rng` to instantiate a `Generator`. If rng is already a `Generator` instance, then the provided instance is used. Specify rng for repeatable function behavior.

      If this argument is passed by position or seed is passed by keyword, legacy behavior for the argument seed applies:

      - If seed is None (or `numpy.random`), the `numpy.random.RandomState` singleton is used.

      - If seed is an int, a new `RandomState` instance is used, seeded with seed.

      - If seed is already a `Generator` or `RandomState` instance then that instance is used.

      Changed in version 1.15.0: As part of the SPEC-007 transition from use of `numpy.random.RandomState` to `numpy.random.Generator`, this keyword was changed from seed to rng. For an interim period, both keywords will continue to work, although only one may be specified at a time. After the interim period, function calls using the seed keyword will emit warnings. The behavior of both seed and rng are outlined above, but only the rng keyword should be used in new code.

      Specify rng for repeatable minimizations. The random numbers generated only affect the visiting distribution function and new coordinates generation.

    no_local_search bool, optional

      If no_local_search is set to True, a traditional Generalized Simulated Annealing will be performed with no local search strategy applied.

    callback callable, optional

      A callback function with signature `callback(x, f, context)`, which will be called for all minima found. `x` and `f` are the coordinates and function value of the latest minimum found, and `context` has one of the following values:

      - `0`: minimum detected in the annealing process.

      - `1`: detection occurred in the local search process.

      - `2`: detection done in the dual annealing process.

      If the callback implementation returns True, the algorithm will stop.

    x0 ndarray, shape(n,), optional

      Coordinates of a single N-D starting point.

  Returns:
    res OptimizeResult

      The optimization result represented as a `OptimizeResult` object. Important attributes are: `x` the solution array, `fun` the value of the function at the solution, and `message` which describes the cause of the termination. See `OptimizeResult` for a description of other attributes.

  Notes

  This function implements the Dual Annealing optimization. This stochastic approach derived from [3] combines the generalization of CSA (Classical Simulated Annealing) and FSA (Fast Simulated Annealing) [1] [2] coupled to a strategy for applying a local search on accepted locations [4]. An alternative implementation of this same algorithm is described in [5] and benchmarks are presented in [6]. This approach introduces an advanced method to refine the solution found by the generalized annealing process. This algorithm uses a distorted Cauchy-Lorentz visiting distribution, with its shape controlled by the parameter \(q_{v}\)

  \[g_{q_{v}}(\Delta x(t)) \propto \frac{ \ \left[T_{q_{v}}(t) \right]^{-\frac{D}{3-q_{v}}}}{ \ \left[{1+(q_{v}-1)\frac{(\Delta x(t))^{2}} { \ \left[T_{q_{v}}(t)\right]^{\frac{2}{3-q_{v}}}}}\right]^{ \ \frac{1}{q_{v}-1}+\frac{D-1}{2}}}\]

  Where \(t\) is the artificial time. This visiting distribution is used to generate a trial jump distance \(\Delta x(t)\) of variable \(x(t)\) under artificial temperature \(T_{q_{v}}(t)\).

  From the starting point, after calling the visiting distribution function, the acceptance probability is computed as follows:

  \[p_{q_{a}} = \min{\{1,\left[1-(1-q_{a}) \beta \Delta E \right]^{ \ \frac{1}{1-q_{a}}}\}}\]

  Where \(q_{a}\) is a acceptance parameter. For \(q_{a}<1\), zero acceptance probability is assigned to the cases where

  \[[1-(1-q_{a}) \beta \Delta E] < 0\]

  The artificial temperature \(T_{q_{v}}(t)\) is decreased according to

  \[T_{q_{v}}(t) = T_{q_{v}}(1) \frac{2^{q_{v}-1}-1}{\left( \ 1 + t\right)^{q_{v}-1}-1}\]

  Where \(q_{v}\) is the visiting parameter.

  Added in version 1.2.0.

  References

  [1]

  Tsallis C. Possible generalization of Boltzmann-Gibbs statistics. Journal of Statistical Physics, 52, 479-487 (1998).

  [2]

  Tsallis C, Stariolo DA. Generalized Simulated Annealing. Physica A, 233, 395-406 (1996).

  [3]

  Xiang Y, Sun DY, Fan W, Gong XG. Generalized Simulated Annealing Algorithm and Its Application to the Thomson Model. Physics Letters A, 233, 216-220 (1997).

  [4]

  Xiang Y, Gong XG. Efficiency of Generalized Simulated Annealing. Physical Review E, 62, 4473 (2000).

  [5]

  Xiang Y, Gubian S, Suomela B, Hoeng J. Generalized Simulated Annealing for Efficient Global Optimization: the GenSA Package for R. The R Journal, Volume 5/1 (2013).

  [6]

  Mullen, K. Continuous Global Optimization in R. Journal of Statistical Software, 60(6), 1 - 45, (2014). DOI:10.18637/jss.v060.i06

  Examples

  The following example is a 10-D problem, with many local minima. The function involved is called Rastrigin (https://en.wikipedia.org/wiki/Rastrigin_function)

      >>> import numpy as np
      >>> from scipy.optimize import dual_annealing
      >>> func = lambda x: np.sum(x*x - 10*np.cos(2*np.pi*x)) + 10*np.size(x)
      >>> lw = [-5.12] * 10
      >>> up = [5.12] * 10
      >>> ret = dual_annealing(func, bounds=list(zip(lw, up)))
      >>> ret.x
      array([-4.26437714e-09, -3.91699361e-09, -1.86149218e-09, -3.97165720e-09,
             -6.29151648e-09, -6.53145322e-09, -3.93616815e-09, -6.55623025e-09,
             -6.05775280e-09, -5.00668935e-09]) # random
      >>> ret.fun
      0.000000