The simulated annealing algorithm performs the following steps:
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 the AnnealingFcn
option.
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, see Algorithm 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.
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 the AcceptanceFcn
option. Choices:
@acceptancesa
(default) — Simulated annealing
acceptance function. The probability of acceptance is
where
Δ = new objective – old
objective.
T0 =
initial temperature of component
i
T = the current
temperature.
Since both Δ and T are 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, see Algorithm Settings.
The algorithm systematically lowers the temperature, storing the best point found so
far. The TemperatureFcn
option specifies the function the algorithm
uses to update the temperature. Let k denote 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, see Temperature Options.
simulannealbnd
reanneals after it accepts
ReannealInterval
points. 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
where
ki = annealing parameter for
component
i.
T0
= initial temperature of component
i.
Ti
= current temperature of component
i.
si
= gradient of objective in direction i times difference of bounds
in direction i.
simulannealbnd
safeguards the annealing parameter values
against Inf
and other improper values.
The algorithm stops when the average change in the objective function is small
relative to FunctionTolerance
, or when it reaches any other stopping
criterion. See Stopping Conditions for the Algorithm.
For more information on the algorithm, see Ingber [1].
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 in StallIterLim
iterations is less than
the value of FunctionTolerance
. The default value
is 1e-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 or Inf
. The default value is Inf
.
MaxFunctionEvaluations
specifies
the maximum number of evaluations of the objective function. The algorithm
stops if the number of function evaluations exceeds the value of MaxFunctionEvaluations
.
The default value is 3000*numberofvariables
.
MaxTime
specifies the maximum time
in seconds the algorithm runs before stopping. The default value is Inf
.
ObjectiveLimit
— The algorithm stops when the best
objective function value is less than the value of ObjectiveLimit
.
The default value is -Inf
.
[1] Ingber, L. Adaptive simulated annealing (ASA): Lessons
learned. Invited paper to a special issue of the Polish Journal
Control and Cybernetics on “Simulated Annealing Applied to
Combinatorial Optimization.” 1995. Available from https://www.ingber.com/asa96_lessons.ps.gz