Seeks a global extremum (minimum or maximum) of a differentiable multidimensional object function using simulated annealing applied in conjunction with one of the following algorithms for finding the local extremum of differentiable object functions:
The general idea used here is that after each step within the selected algorithm for finding the local extremum, we perturb the point by a random jump corresponding to "temperature of the surface".
Indicates the type of extreme searched: in the case of a minimum, extremumType == ExtremumTypes.MINIMUM; and in the case of a maximum, extremumType == ExtremumTypes.MAXIMUM.
initialPoint
The initial point about which the iterative optimization procedure starts. The initial point is given as an array where the n-th term of the array corresponds to the value of the n coordinate value.
annealingSteps
The number of steps for the Simulated Annealing which is performed before the algorithm exists. Note that the number of iterations used effects the level at which the surface is vibrated before the algorithm exits. A reasonable value to take for this parameter in most case is 2.
initialTemperature
The initial temperature which corresponds to the amount which the "surface" of shaken during the first iteration. After which the "surface" cools resulting in decreased shaking until the surface come to rest.
alpha
A constant indicating the non-linearity of the annealing process. The more non-linear (i.e. the worst) the object function is in terms of trying to find a global extremum the lower the value of alpha which should be given. Since the lower alpha, the slower the "shaking of the surface" will decrease, as explicit describe within the formula (*) given above.
bracketingAlgorithm
The bracketing algorithm used within this method. We recommend in most cases that the AccelDerivBracketing bracketing algorithm is used. See the remarks given above, the PDF documentation or the examples for more information on selecting the most appropriate Bracketing Algorithm.
locateAlgorithm
The locate algorithm used within this method. We recommend in most cases that the CubicDerivLocate locate algorithms is used. See the remarks given above, the PDF documentation or the examples for more information on selecting the most appropriate Locate Algorithm.
minDistance
This parameter is required by all bracketing algorithms, and usually signifies the minimal distance between the end points of any bracketed interval in which the extremum lies. Therefore, the minDistance parameter should be approximately the same magnitude as tolerance parameter.
bracketingParameter
This parameter is required by some bracketing algorithms. For a detailed explanation as to its meaning and use for particular bracketing algorithms selected please see the documentation of the BracketingAlgorithm selected or the Mathematical Documentation chapter of the accompanying PDF documentation.
tolerance
The tolerance used when the exit condition of this iterative algorithm is checked. The smaller the tolerance used the more stable the convergence to the extremum within the iterative algorithm must be before the exit condition is trigger. Hence the smaller the tolerance generally the more accuracy the result, however it also has the draw back of making the algorithm more computationally demanding. A reasonable value to use for the tolerance is 0.1.
maxIterations
The maximum number of iterative steps taken before the algorithm exits and a TooManyMultiDimensionalIterationsException is thrown. A reasonable number to use for this parameter is 300.
fractionalTolerance
When the difference between the function values in two consecutive steps is less than fractionalTolerance, the point in the last step is considered a local extreme and returned. In most cases a reasonable value to take for this parameter is 0.00001, however if the object function in very oscillatory in a neighborhood of its extremum then a correspondingly larger value should be used.
algorithmUsed
The AnnealingAlgorithmTypes enumeration type which is used to select the multi-dimensional optimization algorithm to be used with Simulated annealing in the search of a global extremum. You are able to select from the following Algorithms:
Steepest-Descent (i.e. DerivSteepestDescent) - Given as AnnealingAlgorithmTypes.STEEPEST_DESCENT
Fletcher-Powell (i.e. DerivFletcherPowell) - Given as AnnealingAlgorithmTypes.FLETCHER_POWELL
Broyden-Fletcher-Goldfarb-Shanno (BFGS) (i.e. DerivBFGS) - Given as AnnealingAlgorithmTypes.BFGS
Polak-Riviere (i.e. DerivPolakRiviere) - Given as AnnealingAlgorithmTypes.POLAK_RIVIERE
Fletcher-Reeves (i.e. DerivFletcherReeves) - Given as AnnealingAlgorithmTypes.FLETCHER_REEVES
.
Remarks
The temperature of the surface starts from an initial value initialTemperature
and is decreases by a constant ratio after each iteration (that is, the surface is allowed to cool).
The rationale for this approach is that by "heating" the surface we vibrate it so that we are
knocked out by the shaking of local extremum allow the continued search for the global extremum.
When we are in the neighborhood of the global extremum (as long as the shaking is not to violent)
we will stay within the vicinity of the global extremum as the surface is allowed to cool.
The exit conditions used within the implementation of Simulated Annealing is that if the
previous 50 iterations is within the tolerance-neighborhood of the point
found then the algorithm will exit the point found will be returned. Note that when using
Simulated Annealing the jumps may force this condition to never be satisfied before the
number of iterations performed has exceeded maxIterations, and am exception
has been thrown.
Size of Jumps and the Rate of Cooling
The size of the random perturbations after each step and the rate at which the magnitude
of these jumps decreases is explicitly given as follows. If the initial temperature (given as
a parameter) is initialTemperature, then the initial size of the jump will be
initialTemperature. After the k-th iteration of the Simulated Annealing
the size of the random jump is given by:
(*) (1 - k / annealingSteps)alpha
where annealingSteps is the maximum number of simulated annealing steps used and
alpha is a parameters used in order to indicate the non-linearity, i.e how bad the
object function is in terms of being able to find its global extremum.
When should this approach be used
This method is one of the two algorithms along with GlobalAnnealing,
within this class which are specifically designed to find the global (rather than local)
extremum of the given object function. Both of these methods use the approach known as
Simulated annealing, however this method allow the Simulated Annealing the be applied to a
range of optimization algorithms using user selected locate and bracketing algorithms. This
method should be used if you wish fine tune a global optimization algorithm for your particular
problem at hand. By fine tuning this method you should be able to generate an algorithm which
is more efficient than GlobalAnnealing,
particularly in instances when the object function is differentiable. However, in should
be pointed out that this approach will take more effort than the alternative
GlobalAnnealing,