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

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.algorithm.AbstractIterativeAlgorithm
          extended by gov.sandia.cognition.algorithm.AbstractAnytimeAlgorithm<ResultType>
              extended by gov.sandia.cognition.learning.algorithm.AbstractAnytimeBatchLearner<CostParametersType,AnnealedType>
                  extended by 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, Serializable, Cloneable

@CodeReviews(reviews={@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
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
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
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<Double> getPerformance()
          Gets the performance, which is the best score so far.
 Perturber<AnnealedType> getPerturber()
          Gets the perturber.
 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(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 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(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<Double> getPerformance()
Gets the performance, which is the best score so far.

Specified by:
getPerformance in interface MeasurablePerformanceAlgorithm
Returns:
The performance of the algorithm.