Main Content

How Simulated Annealing Works

Outline of the Algorithm

The simulated annealing algorithm performs the following steps:

  1. The algorithm generates a random trial point. The algorithm chooses the distance of the trial point from the current point by a probability distribution with a scale depending on the current temperature. You set the trial point distance distribution as a function with theAnnealingFcnoption. Choices:

    • @annealingfast(default) — Step length equals the current temperature, and direction is uniformly random.

    • @annealingboltz— Step length equals the square root of temperature, and direction is uniformly random.

    • @myfun— Custom annealing algorithm,myfun. For custom annealing function syntax, seeAlgorithm Settings.

    After generating the trial point, the algorithm shifts it, if necessary, to stay within bounds. The algorithm shifts each infeasible component of the trial point to a value chosen uniformly at random between the violated bound and the (feasible) value at the previous iteration.

  2. The algorithm determines whether the new point is better or worse than the current point. If the new point is better than the current point, it becomes the next point. If the new point is worse than the current point, the algorithm can still make it the next point. The algorithm accepts a worse point based on an acceptance function. Choose the acceptance function with theAcceptanceFcnoption. Choices:

    • @acceptancesa(default) — Simulated annealing acceptance function. The probability of acceptance is

      1 1 + exp ( Δ max ( T ) ) ,

      where

      Δ = new objective – old objective.
      T0= initial temperature of componenti
      T= the current temperature.

      Since both Δ andTare positive, the probability of acceptance is between 0 and 1/2. Smaller temperature leads to smaller acceptance probability. Also, larger Δ leads to smaller acceptance probability.

    • @myfun— Custom acceptance function,myfun. For custom acceptance function syntax, seeAlgorithm Settings.

  3. The algorithm systematically lowers the temperature, storing the best point found so far. TheTemperatureFcnoption specifies the function the algorithm uses to update the temperature. Letkdenote the annealing parameter. (The annealing parameter is the same as the iteration number until reannealing.) Options:

    • @temperatureexp(default) —T=T0* 0.95^k.

    • @temperaturefast—T=T0/k.

    • @temperatureboltz—T=T0/ log(k).

    • @myfun— Custom temperature function,myfun. For custom temperature function syntax, seeTemperature Options.

  4. simulannealbndreanneals after it acceptsReannealIntervalpoints. Reannealing sets the annealing parameters to lower values than the iteration number, thus raising the temperature in each dimension. The annealing parameters depend on the values of estimated gradients of the objective function in each dimension. The basic formula is

    k i = log ( T 0 T i max j ( s j ) s i ) ,

    where

    ki= annealing parameter for componenti.
    T0= initial temperature of componenti.
    Ti= current temperature of componenti.
    si= gradient of objective in directionitimes difference of bounds in directioni.

    simulannealbndsafeguards the annealing parameter values againstInfand other improper values.

  5. The algorithm stops when the average change in the objective function is small relative toFunctionTolerance, or when it reaches any other stopping criterion. SeeStopping Conditions for the Algorithm.

For more information on the algorithm, see Ingber[1].

Stopping Conditions for the Algorithm

The simulated annealing algorithm uses the following conditions to determine when to stop:

  • FunctionTolerance— The algorithm runs until the average change in value of the objective function inStallIterLimiterations is less than the value ofFunctionTolerance. The default value is1e-6.

  • MaxIterations— The algorithm stops when the number of iterations exceeds this maximum number of iterations. You can specify the maximum number of iterations as a positive integer orInf. The default value isInf.

  • MaxFunctionEvaluationsspecifies the maximum number of evaluations of the objective function. The algorithm stops if the number of function evaluations exceeds the value ofMaxFunctionEvaluations. The default value is3000*numberofvariables.

  • MaxTimespecifies the maximum time in seconds the algorithm runs before stopping. The default value isInf.

  • ObjectiveLimit— The algorithm stops when the best objective function value is less than the value ofObjectiveLimit. The default value is-Inf.

Bibliography

[1] Ingber, L.Adaptive simulated annealing (ASA): Lessons learned. Invited paper to a special issue of thePolish Journal Control and Cyberneticson “Simulated Annealing Applied to Combinatorial Optimization.” 1995. Available fromhttps://www.ingber.com/asa96_lessons.ps.gz

See Also

Related Topics