gov.sandia.cognition.learning.algorithm.annealing

Class SimulatedAnnealer<CostParametersType,AnnealedType>

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>

gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<CostParametersType,AnnealedType>

gov.sandia.cognition.learning.algorithm.annealing.SimulatedAnnealer<CostParametersType,AnnealedType>

Type Parameters:

AnnealedType - Class returned from the learn() method, such as a FeedforwardNeuralNetwork, for example

CostParametersType - Cost parameters given to the learn() method, such as Collection<InputOutputPair>, for example

All Implemented Interfaces:

AnytimeAlgorithm<AnnealedType>, IterativeAlgorithm, MeasurablePerformanceAlgorithm, StoppableAlgorithm, AnytimeBatchLearner<CostParametersType,AnnealedType>, BatchCostMinimizationLearner<CostParametersType,AnnealedType>, BatchLearner<CostParametersType,AnnealedType>, CloneableSerializable, java.io.Serializable, java.lang.Cloneable

@CodeReview(reviewer="Kevin R. Dixon",date="2008-07-22",changesNeeded=false,comments={"Moved previous code review to annotation.","Added HTML tags to javadoc.","Fixed a few typos in javadoc.","Code looks fine."}) @CodeReview(reviewer="Justin Basilico",date="2006-10-02",changesNeeded=false,comments={"Did some reformatting of the code.","Added missing documentation.","Cleaned up the use of default parameter values."})
public class SimulatedAnnealer<CostParametersType,AnnealedType>
extends AbstractAnytimeBatchLearner<CostParametersType,AnnealedType>
implements BatchCostMinimizationLearner<CostParametersType,AnnealedType>, MeasurablePerformanceAlgorithm

The SimulatedAnnealer class implements the simulated annealing algorithm using the provided cost function and perturbation function.

Simulated annealing is attempts to find the minimum-cost parameters of a function using a stochastic hill climbing (descent, actually). A lower-cost parameter tweak is always taken, but a higher-cost tweak is taken with a probability dictated by an "annealing" schedule. This stochastic step toward badness is an attempt to find global minima, instead of your vanilla-flavored local minima. Thus, SA only relies on function evaluations, not needed the gradient.

Here's my opinion on simulated annealing: it is a method of absolute last resort, and I have trouble thinking of a more general, brain-dead approach. Use SA only when you are stranded on a desolate glacier, one arm trapped under a boulder, and your pocket knife is out of reach.

If you are still reading this, then I assume you still think you need SA because you can only evaluate a function against a cost function and, oh my goodness, you have a huge search space. At least, you should be using Genetic Algorithms. Even better, try Powell's method, which is a powerful minimization technique that only relies on function evaluations. Think of it as SA, but smart. Generally better than Powell's method is Conjugate Gradient with automated gradient approximation, which only relies on function evaluations and automatically estimates the gradient for you. If you can store the (approximated) Jacobian in memory, then the best technique is usually BFGS with automated gradient approximation (sometimes Levenberg-Marquardt Estimation is as good as BFGS, but usually not).

If you're still going to use SA, then may the optimization gods have mercy on your soul.

Since:

1.0

Author:

Jonathan McClain, Justin Basilico, Kevin R. Dixon

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static double	DEFAULT_COOLING_FACTOR The default cooling factor for learning, 0.1.
static int	DEFAULT_MAX_ITERATIONS The default number of maximum iterations, 1000.
static double	DEFAULT_STARTING_TEMPERATURE The default starting temperature for the algorithm, 1.0.

Fields inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner

data, keepGoing

Fields inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm

maxIterations

Fields inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

DEFAULT_ITERATION, iteration

Constructor Summary

Constructors

Constructor and Description
SimulatedAnnealer(AnnealedType initial, Perturber<AnnealedType> perturber, CostFunction<? super AnnealedType,? super CostParametersType> cost) Creates a new instance of SimulatedAnnealer.
SimulatedAnnealer(AnnealedType initial, Perturber<AnnealedType> perturber, CostFunction<? super AnnealedType,? super CostParametersType> cost, int maxIterations) Creates a new instance of SimulatedAnnealer.
SimulatedAnnealer(AnnealedType initial, Perturber<AnnealedType> perturber, CostFunction<? super AnnealedType,? super CostParametersType> cost, int maxIterations, int maxIterationsWithoutImprovement) Creates a new instance of SimulatedAnnealer.

Method Summary

Modifier and Type	Method and Description
protected void	cleanupAlgorithm() Called to clean up the learning algorithm's state after learning has finished.
SimulatedAnnealer<CostParametersType,AnnealedType>	clone() This makes public the clone method on the Object class and removes the exception that it throws.
protected AnnealedType	getBestSoFar() Gets the best state found so far.
protected double	getBestSoFarScore() Gets the score for the best state found so far.
double	getCoolingFactor() Gets the cooling factor.
CostFunction<? super AnnealedType,? super CostParametersType>	getCostFunction() Gets the cost function that the learner is minimizing.
protected AnnealedType	getCurrent() Gets the current state of the system.
protected double	getCurrentScore() Gets the score of the current state.
protected int	getIterationsWithoutImprovement() Gets the current number of iterations without improvement.
int	getMaxIterationsWithoutImprovement() Gets the maximum number of iterations to go without improvement before stopping.
NamedValue<java.lang.Double>	getPerformance() Gets the performance, which is the best score so far.
Perturber<AnnealedType>	getPerturber() Gets the perturber.
java.util.Random	getRandom() Gets the random number generator.
AnnealedType	getResult() Gets the current result of the algorithm.
protected double	getTemperature() Gets the current temperature of the system.
protected boolean	initializeAlgorithm() Called to initialize the learning algorithm's state based on the data that is stored in the data field.
protected void	setBestSoFar(AnnealedType bestSoFar) Sets the best state found so far.
protected void	setBestSoFarScore(double bestSoFarScore) Sets the score for the best state found so far.
void	setCoolingFactor(double coolingFactor) Sets the cooling factor.
void	setCostFunction(CostFunction<? super AnnealedType,? super CostParametersType> cost) Sets the cost function.
protected void	setCurrent(AnnealedType current) Sets the current state of the system.
protected void	setCurrentScore(double currentScore) Sets the score of the current state.
protected void	setIterationsWithoutImprovement(int iterationsWithoutImprovement) Sets the current number of iterations without improvement.
void	setMaxIterationsWithoutImprovement(int maxIterationsWithoutImprovement) Sets the maximum number of iterations to go without improvement before stopping.
void	setPerturber(Perturber<AnnealedType> perturber) Sets the perturber.
void	setRandom(java.util.Random random) Sets the random number generator.
protected void	setTemperature(double temperature) Sets the current temperature of the system.
protected boolean	step() Takes one step in the Simulated Annealing process.

Methods inherited from class gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner

getData, getKeepGoing, learn, setData, setKeepGoing, stop

Methods inherited from class gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm

getMaxIterations, isResultValid, setMaxIterations

Methods inherited from class gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm

addIterativeAlgorithmListener, fireAlgorithmEnded, fireAlgorithmStarted, fireStepEnded, fireStepStarted, getIteration, getListeners, removeIterativeAlgorithmListener, setIteration, setListeners

Methods inherited from class java.lang.Object

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

Methods inherited from interface gov.sandia.cognition.learning.algorithm.BatchCostMinimizationLearner

learn

Methods inherited from interface gov.sandia.cognition.algorithm.AnytimeAlgorithm

getMaxIterations, setMaxIterations

Methods inherited from interface gov.sandia.cognition.algorithm.IterativeAlgorithm

addIterativeAlgorithmListener, getIteration, removeIterativeAlgorithmListener

Methods inherited from interface gov.sandia.cognition.algorithm.StoppableAlgorithm

isResultValid

Field Detail

DEFAULT_STARTING_TEMPERATURE

public static final double DEFAULT_STARTING_TEMPERATURE

The default starting temperature for the algorithm, 1.0.

See Also:

Constant Field Values

DEFAULT_COOLING_FACTOR

public static final double DEFAULT_COOLING_FACTOR

The default cooling factor for learning, 0.1.

See Also:

Constant Field Values

DEFAULT_MAX_ITERATIONS

public static final int DEFAULT_MAX_ITERATIONS

The default number of maximum iterations, 1000.

See Also:

Constant Field Values

Constructor Detail

SimulatedAnnealer

public SimulatedAnnealer(AnnealedType initial,
                         Perturber<AnnealedType> perturber,
                         CostFunction<? super AnnealedType,? super CostParametersType> cost)

Creates a new instance of SimulatedAnnealer.

Parameters:

initial - Initial candidate to consider

perturber - The perturbing function to use.

cost - The cost function to minimize.

SimulatedAnnealer

public SimulatedAnnealer(AnnealedType initial,
                         Perturber<AnnealedType> perturber,
                         CostFunction<? super AnnealedType,? super CostParametersType> cost,
                         int maxIterations)

Creates a new instance of SimulatedAnnealer.

Parameters:

initial - Initial candidate to consider

perturber - The perturbing function to use.

cost - The cost function to minimize.

maxIterations - The maximum number of iterations to perform.

SimulatedAnnealer

public SimulatedAnnealer(AnnealedType initial,
                         Perturber<AnnealedType> perturber,
                         CostFunction<? super AnnealedType,? super CostParametersType> cost,
                         int maxIterations,
                         int maxIterationsWithoutImprovement)

Creates a new instance of SimulatedAnnealer.

Parameters:

initial - Initial candidate to consider

perturber - The perturbing function to use.

cost - The cost function to minimize.

maxIterations - The maximum number of iterations to perform.

maxIterationsWithoutImprovement - The maximum number of iterations to go without improvement before stopping.

Method Detail

clone

public SimulatedAnnealer<CostParametersType,AnnealedType> clone()

Description copied from class: AbstractCloneableSerializable

This makes public the clone method on the Object class and removes the exception that it throws. Its default behavior is to automatically create a clone of the exact type of object that the clone is called on and to copy all primitives but to keep all references, which means it is a shallow copy. Extensions of this class may want to override this method (but call super.clone() to implement a "smart copy". That is, to target the most common use case for creating a copy of the object. Because of the default behavior being a shallow copy, extending classes only need to handle fields that need to have a deeper copy (or those that need to be reset). Some of the methods in ObjectUtil may be helpful in implementing a custom clone method. Note: The contract of this method is that you must use super.clone() as the basis for your implementation.

Specified by:

clone in interface CloneableSerializable

Overrides:

clone in class AbstractAnytimeBatchLearner<CostParametersType,AnnealedType>

Returns:

A clone of this object.

initializeAlgorithm

protected boolean initializeAlgorithm()

Description copied from class: AbstractAnytimeBatchLearner

Called to initialize the learning algorithm's state based on the data that is stored in the data field. The return value indicates if the algorithm can be run or not based on the initialization.

Specified by:

initializeAlgorithm in class AbstractAnytimeBatchLearner<CostParametersType,AnnealedType>

Returns:

True if the learning algorithm can be run and false if it cannot.

step

protected boolean step()

Takes one step in the Simulated Annealing process.

Specified by:

step in class AbstractAnytimeBatchLearner<CostParametersType,AnnealedType>

Returns:

Boolean indicating whether the SA process should continue (i.e. no stopping conditions have been met).

getCostFunction

public CostFunction<? super AnnealedType,? super CostParametersType> getCostFunction()

Description copied from interface: BatchCostMinimizationLearner

Gets the cost function that the learner is minimizing.

Specified by:

getCostFunction in interface BatchCostMinimizationLearner<CostParametersType,AnnealedType>

Returns:

The CostFunction that the learner's algorithm is minimizing.

getPerturber

public Perturber<AnnealedType> getPerturber()

Gets the perturber.

Returns:

The perturber.

getTemperature

protected double getTemperature()

Gets the current temperature of the system.

Returns:

The current temperature.

getMaxIterationsWithoutImprovement

public int getMaxIterationsWithoutImprovement()

Gets the maximum number of iterations to go without improvement before stopping.

Returns:

The current maximum.

getIterationsWithoutImprovement

protected int getIterationsWithoutImprovement()

Gets the current number of iterations without improvement.

Returns:

The current iteration.

getCoolingFactor

public double getCoolingFactor()

Gets the cooling factor.

Returns:

The cooling factor.

getRandom

public java.util.Random getRandom()

Gets the random number generator.

Returns:

The random number generator.

getBestSoFar

protected AnnealedType getBestSoFar()

Gets the best state found so far.

Returns:

The best state.

getBestSoFarScore

protected double getBestSoFarScore()

Gets the score for the best state found so far.

Returns:

The score.

getCurrent

protected AnnealedType getCurrent()

Gets the current state of the system.

Returns:

The current state.

getCurrentScore

protected double getCurrentScore()

Gets the score of the current state.

Returns:

The score.

setCostFunction

public void setCostFunction(CostFunction<? super AnnealedType,? super CostParametersType> cost)

Sets the cost function.

Parameters:

cost - The new cost function.

setPerturber

public void setPerturber(Perturber<AnnealedType> perturber)

Sets the perturber.

Parameters:

perturber - The new perturber.

setTemperature

protected void setTemperature(double temperature)

Sets the current temperature of the system.

Parameters:

temperature - The new temperature.

setMaxIterationsWithoutImprovement

public void setMaxIterationsWithoutImprovement(int maxIterationsWithoutImprovement)

Sets the maximum number of iterations to go without improvement before stopping.

Parameters:

maxIterationsWithoutImprovement - The new maximum.

setIterationsWithoutImprovement

protected void setIterationsWithoutImprovement(int iterationsWithoutImprovement)

Sets the current number of iterations without improvement.

Parameters:

iterationsWithoutImprovement - The new iteration.

setCoolingFactor

public void setCoolingFactor(double coolingFactor)

Sets the cooling factor.

Parameters:

coolingFactor - The new cooling factor.

setRandom

public void setRandom(java.util.Random random)

Sets the random number generator.

Parameters:

random - The new random number generator.

setBestSoFar

protected void setBestSoFar(AnnealedType bestSoFar)

Sets the best state found so far.

Parameters:

bestSoFar - The new best state.

setBestSoFarScore

protected void setBestSoFarScore(double bestSoFarScore)

Sets the score for the best state found so far.

Parameters:

bestSoFarScore - The new score.

setCurrent

protected void setCurrent(AnnealedType current)

Sets the current state of the system.

Parameters:

current - The new current state.

setCurrentScore

protected void setCurrentScore(double currentScore)

Sets the score of the current state.

Parameters:

currentScore - The new score.

cleanupAlgorithm

protected void cleanupAlgorithm()

Description copied from class: AbstractAnytimeBatchLearner

Called to clean up the learning algorithm's state after learning has finished.

Specified by:

cleanupAlgorithm in class AbstractAnytimeBatchLearner<CostParametersType,AnnealedType>

getResult

public AnnealedType getResult()

Description copied from interface: AnytimeAlgorithm

Gets the current result of the algorithm.

Specified by:

getResult in interface AnytimeAlgorithm<AnnealedType>

Returns:

Current result of the algorithm.

getPerformance

public NamedValue<java.lang.Double> getPerformance()

Gets the performance, which is the best score so far.

Specified by:

getPerformance in interface MeasurablePerformanceAlgorithm

Returns:

The performance of the algorithm.