
Orbital library  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object orbital.algorithm.template.GeneralSearch orbital.algorithm.template.LocalOptimizerSearch orbital.algorithm.template.SimulatedAnnealing
public class SimulatedAnnealing
Simulated Annealing (SA) search. A probabilistic and heuristic search algorithm and local optimizer.
No special implementation data structure since simulated annealing discards old nodes. Because of this "amnesy", simulated annealing is a suboptimal search strategy and simulated annealing is not complete (but see below). However, due to its Monte Carlo nature it has a certain probability of avoiding local optima and actually reaching a global optimum. In practical applications, it usually scores much better than randomrestart hillclimbing.
Simulated annealing problems can omit checking for solutions and simply wait until the temperature drops to zero.
Another possibility of using simulated annealing is to develop to a good stable balance of f at a high temperature, first, and then decrease the temperature. Monitoring acceptance probability ensuring to keep it at a medium rate might improve convergence. Also performing some optimization at temperature 0 still (equalling ordinary hillclimbing then), ensures that the solution is at least at a local optimum.
The Boltzman distribution specifies the probability of being at enery level E:=f(s) given the current temperature T
MDPs
P(sʹs) is the probability of reaching sʹ from s with one move.
lim_{n→∞} P(S_{n}=s) converges independent from the initial state s_{0} if the Markov system underlying the state transition is ergodic (the graph spanned by all transitions with probability >0 is connected i.e. from any s∈S to any t∈S the is a path from s to t with nonzero transition probability). At least, it also converges if the Markov system is homogenous (i.e. transition probabilities are independent from time) and aperiodic (i.e. ¬∃n∈N P^{n}=I, with P∈[0,1]^{S×S} being the matrix of transition probabilities). Also, for example, the condition with the acceptance probability is satisfied by simulated annealing, and thus metropolis search. (metropolis search is simulated annealing at a fixed temperature T).
HillClimbing
,
ThresholdAccepting
,
Serialized FormNested Class Summary 

Nested classes/interfaces inherited from class orbital.algorithm.template.LocalOptimizerSearch 

LocalOptimizerSearch.LocalSelection 
Nested classes/interfaces inherited from interface orbital.algorithm.template.HeuristicAlgorithm 

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic 
Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm 

EvaluativeAlgorithm.EvaluationComparator 
Field Summary 

Fields inherited from class orbital.algorithm.template.LocalOptimizerSearch 

BEST_LOCAL_SELECTION, FIRST_LOCAL_SELECTION 
Constructor Summary  

SimulatedAnnealing(Function heuristic,
Function schedule)
Create a new instance of simulated annealing search. 
Method Summary  

Function 
complexity()
O(∞). 
protected java.util.Iterator 
createTraversal(GeneralSearchProblem problem)
Define a traversal order by creating an iterator for the problem's state space. 
Function 
getEvaluation()
f(n) = h(n). 
Function 
getHeuristic()
Get the heuristic function used. 
Function 
getSchedule()
Get the scheduling function. 
boolean 
isCorrect()
Local optimizers are usally not correct. 
boolean 
isOptimal()
Local optimizers are not optimal (usually). 
void 
setHeuristic(Function heuristic)
Set the heuristic function to use. 
void 
setSchedule(Function schedule)

Function 
spaceComplexity()
O(b) where b is the branching factor and d the solution depth. 
Methods inherited from class orbital.algorithm.template.LocalOptimizerSearch 

getRandom, search, setRandom 
Methods inherited from class orbital.algorithm.template.GeneralSearch 

getProblem, solve, solveImpl 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate 

solve 
Constructor Detail 

public SimulatedAnnealing(Function heuristic, Function schedule)
heuristic
 the heuristic cost function h:S→R to be used as evaluation function f(n) = h(n).schedule
 a mapping N→R
from time to "temperature" controlling the cooling, and thus
the probability of downward steps.
Algorithm stops if the temperature drops to 0
(or isSolution is true,
or it fails due to a lack of alternative expansion nodes).Method Detail 

public Function getEvaluation()
public Function complexity()
AlgorithmicTemplate.solve(AlgorithmicProblem)
public Function spaceComplexity()
AlgorithmicTemplate.solve(AlgorithmicProblem)
public boolean isOptimal()
public boolean isCorrect()
isCorrect
in interface ProbabilisticAlgorithm
protected java.util.Iterator createTraversal(GeneralSearchProblem problem)
GeneralSearch
Lays a linear order through the state space which the search can simply follow sequentially. Thus a traversal policy effectively reduces a search problem through a graph to a search problem through a linear sequence of states. Of course, the mere notion of a traversal policy does not yet solve the task of finding a good order of states, but only encapsulate it. Complete search algorithms result from traversal policies that have a linear sequence through the whole state space.
createTraversal
in class GeneralSearch
problem
 the problem whose state space to create a traversal iterator for.
GeneralSearch.OptionIterator
public Function getHeuristic()
HeuristicAlgorithm
getHeuristic
in interface HeuristicAlgorithm
public void setHeuristic(Function heuristic)
HeuristicAlgorithm
An heuristic cost function h:S→R is estimating the cost to get from a node n to a goal G. For several heuristic algorithms this heuristic function needs to be admissible
A heuristic cost function h is monotonic :⇔ the fcosts (with h) do not decrease in any path from the initial state ⇔ h obeys the triangular inequality
A simple improvement for heuristic functions is using pathmax.
setHeuristic
in interface HeuristicAlgorithm
heuristic
 the heuristic cost function h:S→R estimating h^{*}.
h will be embedded in the evaluation function f
.public Function getSchedule()
public void setSchedule(Function schedule)

Orbital library 1.3.0: 11 Apr 2009 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 