orbital.algorithm.template
Class ThresholdAccepting

java.lang.Object
  orbital.algorithm.template.GeneralSearch
      orbital.algorithm.template.LocalOptimizerSearch
          orbital.algorithm.template.ThresholdAccepting

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm, HeuristicAlgorithm, ProbabilisticAlgorithm

public class ThresholdAccepting
extends LocalOptimizerSearch

Threshold Accepting (TA) search. A probabilistic and heuristic search algorithm and local optimizer.

The behaviour in practical applications approximates that of simulated annealing, but this algorithm is a little faster.

At temperature 0 this algorithm equals ordinary hill-climbing.

Author:

André Platzer

See Also:

SimulatedAnnealing, HillClimbing, Serialized Form

Nested 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

ThresholdAccepting(Function heuristic, Function schedule)
Create a new instance of threshold accepting 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

ThresholdAccepting

public ThresholdAccepting(Function heuristic,
                          Function schedule)

Create a new instance of threshold accepting search.

Parameters:

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).

Preconditions:

lim_t→∞schedule(t) = 0 ∧ schedule decreases monotonically

Method Detail

getEvaluation

public Function getEvaluation()

f(n) = h(n).

Returns:

the evaluation function f:S→R used to evaluate (either utility or cost) value of states.

complexity

public Function complexity()

O(∞).

Returns:

the function f for which the solve() method of this algorithm runs in O(f(n)) assuming the algorithmic problem hook to run in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

spaceComplexity

public Function spaceComplexity()

O(b) where b is the branching factor and d the solution depth.

Returns:

the function f for which the solve() method of this algorithm consumes memory with an amount in O(f(n)) assuming the algorithmic problem hook uses space in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

isOptimal

public boolean isOptimal()

Local optimizers are not optimal (usually). Because the scheduling function may be too fast, such that the search cannot yet have reached the global optimum.

Returns:

whether this search algorithm is optimal, i.e. whether solutions found are guaranteed to be optimal.

isCorrect

public boolean isCorrect()

Local optimizers are usally not correct. Because the scheduling function is (usually) independent from the current state, and thus may be too fast, such that the search has not yet reached an optimum.

Specified by:

isCorrect in interface ProbabilisticAlgorithm

Returns:

whether all solutions found by this algorithms are correct despite the approximative nature of this algorithm. Monte Carlo algorithms are not correct, while Las Vegas algorithms usually are.

createTraversal

protected java.util.Iterator createTraversal(GeneralSearchProblem problem)

Description copied from class: GeneralSearch

Define a traversal order by creating an iterator for the problem's state space.

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.

Specified by:

createTraversal in class GeneralSearch

Parameters:

problem - the problem whose state space to create a traversal iterator for.

Returns:

an iterator over the options of the problem's state space thereby encapsulating and hiding the traversal order.

See Also:

Factory Method, GeneralSearch.OptionIterator

getHeuristic

public Function getHeuristic()

Description copied from interface: HeuristicAlgorithm

Get the heuristic function used.

Specified by:

getHeuristic in interface HeuristicAlgorithm

Returns:

the heuristic cost function h:S→R estimating h^*.

setHeuristic

public void setHeuristic(Function heuristic)

Description copied from interface: HeuristicAlgorithm

Set the heuristic function to use.

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

h ≤ h^* i.e. h is a lower bound for the effective cost function h^*. Then the pathmax heuristic f(s') := max {f(s), g(s') + h(s')} (for transitions s→s'=t(s,a) with a∈A(s)) is monotonic.

A heuristic cost function h is monotonic :⇔ the f-costs (with h) do not decrease in any path from the initial state ⇔ h obeys the triangular inequality

∀s∈S,a∈A(s) h(s) ≤ h(s') + c(s,a) with s' = t(s,a) i.e. the sum of the costs from A to C and from C to B must not be less than the cost from A to B.

A simple improvement for heuristic functions is using pathmax.

Specified by:

setHeuristic in interface HeuristicAlgorithm

Parameters:

heuristic - the heuristic cost function h:S→R estimating h^*. h will be embedded in the evaluation function f.

See Also:

"Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading, Massachusetts. 1984."

getSchedule

public Function getSchedule()

Get the scheduling function.

Returns:

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).

setSchedule

public void setSchedule(Function schedule)