dev.nm.solver.multivariate.unconstrained.annealing

Class SimulatedAnnealingMinimizer

java.lang.Object

dev.nm.solver.multivariate.unconstrained.annealing.SimulatedAnnealingMinimizer

All Implemented Interfaces:

Minimizer<OptimProblem,IterativeSolution<Vector>>, IterativeMinimizer<OptimProblem>, MultivariateMinimizer<OptimProblem,IterativeSolution<Vector>>, Optimizer<OptimProblem,IterativeSolution<Vector>>

Direct Known Subclasses:

GeneralizedSimulatedAnnealingMinimizer

public class SimulatedAnnealingMinimizer
extends Object
implements IterativeMinimizer<OptimProblem>

Simulated Annealing is a global optimization meta-heuristic that is inspired by annealing in metallurgy. Annealing involves heating materials to a high temperature and then letting them cool slowly. This allows the particles, which can move more freely at high temperatures, to align. The basic idea is to generate a proposed state from an AnnealingFunction and accept the state transition with a probability according to a TemperedAcceptanceProbabilityFunction. Both of these are subject to temperature, such that at high temperatures, the algorithm will move along the state space more freely (i.e. propose greater changes and be more likely to accept changes that do not offer an improvement on the current state), whereas the algorithm asymptotically tends towards a hill-climb as the temperature approaches 0.

See Also:

• Wikipedia: Simulated Annealing
• "Jun S. Liu. "p.209," Monte Carlo Strategies in Scientific Computing. 2002."
• Matlab: 'simulannealbnd' documentation

Constructor Summary

Constructors

Constructor and Description
SimulatedAnnealingMinimizer(int dim, double initialTemperature, StopCondition stopCondition, RandomLongGenerator uniform) Constructs a new instance to use BoltzTemperatureFunction, BoltzAnnealingFunction and MetropolisAcceptanceProbabilityFunction.
SimulatedAnnealingMinimizer(TemperatureFunction temperatureFunction, AnnealingFunction annealingFunction, TemperedAcceptanceProbabilityFunction probabilityFunction, int markovLength, StopCondition stopCondition, RandomLongGenerator uniform) Constructs a new instance.

Method Summary

Modifier and Type	Method and Description
IterativeSolution<Vector>	solve(OptimProblem problem) Solve an optimization problem, e.g., OptimProblem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SimulatedAnnealingMinimizer

public SimulatedAnnealingMinimizer(TemperatureFunction temperatureFunction,
                                   AnnealingFunction annealingFunction,
                                   TemperedAcceptanceProbabilityFunction probabilityFunction,
                                   int markovLength,
                                   StopCondition stopCondition,
                                   RandomLongGenerator uniform)

Constructs a new instance.

Parameters:

temperatureFunction - a function that for a given iteration i gives T_i, where 0 < i < temperature_levels. The function must be monotonically increasing with i

probabilityFunction - gives the acceptance probability for a state transition at a given temperature

annealingFunction - proposes next states

markovLength - the number of times we attempt a state change per iteration (per temperature)

stopCondition - the StopCondition

uniform - the rlg to be used to control the stochastic element of the algorithm

SimulatedAnnealingMinimizer

public SimulatedAnnealingMinimizer(int dim,
                                   double initialTemperature,
                                   StopCondition stopCondition,
                                   RandomLongGenerator uniform)

Constructs a new instance to use BoltzTemperatureFunction, BoltzAnnealingFunction and MetropolisAcceptanceProbabilityFunction.

Parameters:

dim - the dimension of the problem or solution

initialTemperature - the initial temperature

stopCondition - the StopCondition

uniform - the random number generator that is to be used

Method Detail

solve

public IterativeSolution<Vector> solve(OptimProblem problem)
                                throws Exception

Description copied from interface: Optimizer

Solve an optimization problem, e.g., OptimProblem.

Specified by:

solve in interface Optimizer<OptimProblem,IterativeSolution<Vector>>

Parameters:

problem - an optimization problem

Returns:

a solution to the optimization problem

Throws:

Exception - when there is an error solving the problem