orbital.algorithm.template
Class HillClimbing

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

All Implemented Interfaces:

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

public class HillClimbing
extends LocalOptimizerSearch
implements HeuristicAlgorithm

Hill-climbing search. An heuristic search algorithm and local optimizer.

(One variant of hill-climbing) Expands best nodes first, i.e. those that have min h(n) and forgets about the alternatives.

Hill climbing is neither complete nor optimal, has a time complexity of O(∞) but a space complexity of O(b).

No special implementation data structure since hill climbing discards old nodes. Because of this "amnesy", hill climbing is a suboptimal search strategy and hill climbing is not complete. Due to its concept hill-climbing may get caught at local extrema, will only perform a random walk on "plateaux", and may have difficulties passing ridges when no "sloping" step actions exist. However, these problems can be solved probabilistically by using an iterative random-restart hill-climbing with a sufficient number of iterations. Random-restart hill-climbing requires that ties break randomly. Which is the cause for hill-climbing to be a simple probabilistic algorithm.

Note that random-restart hill-climbing could be implemented by a Decorator decorating GeneralSearchProblem with a broad range of equally cheap initial actions prepended, that branch to several random locations.

Note that hill-climbing approximates gradient descent. If the state space is spanned by a system of linear unequalities, and the evaluation function is linear, then hill-climbing equals the simplex algorithm of linear programming. Local optimization guarantees that local optimum is global optimum if the state-space as well as the evaluation function are convex, then.

Hill-climbing "resembles trying to find the top of Mount Everest in a thick fog while suffering from amnesia." (Russel&Norvig, Ch 4.4)

Author:

André Platzer

See Also:

Greedy, Serialized Form

Attributes:

specializes SimulatedAnnealing, specializes ThresholdAccepting

Note:

is a basic aspect of local optimization, only., the father of local optimizers, also the most simple version

Nested Class Summary

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

LocalOptimizerSearch.LocalSelection, LocalOptimizerSearch.OptionIterator

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

HillClimbing(Function heuristic)
Create a new instance of hill climbing search.

HillClimbing(Function heuristic, LocalOptimizerSearch.LocalSelection localSelection)
Create a new instance of hill climbing 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.
boolean	isCorrect() Whether this algorithm is correct.
boolean	isOptimal() Whether this search algorithm is optimal.
void	setHeuristic(Function heuristic) Set the heuristic function to use.
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

HillClimbing

public HillClimbing(Function heuristic,
                    LocalOptimizerSearch.LocalSelection localSelection)

Create a new instance of hill climbing search.

Parameters:

heuristic - the heuristic cost function h:S→R to be used as evaluation function f(n) = h(n).

localSelection - the variant of local selection used.

HillClimbing

public HillClimbing(Function heuristic)

Create a new instance of hill climbing search.

Parameters:

heuristic - the heuristic cost function h:S→R to be used as evaluation function f(n) = h(n).

Method Detail

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

getEvaluation

public Function getEvaluation()

f(n) = h(n).

Specified by:

getEvaluation in interface EvaluativeAlgorithm

Specified by:

getEvaluation in interface HeuristicAlgorithm

Returns:

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

complexity

public Function complexity()

O(∞).

Specified by:

complexity in interface AlgorithmicTemplate

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.

Specified by:

spaceComplexity in interface AlgorithmicTemplate

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

Description copied from class: GeneralSearch

Whether this search algorithm is optimal.

If a search algorithm is not optimal, i.e. it might be content with solutions that are sub optimal only, then it can at most reliably find solutions, not best solutions. However, those solutions found still provide an upper bound to the optimal solution.

Specified by:

isOptimal in class GeneralSearch

Returns:

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

isCorrect

public boolean isCorrect()

Description copied from interface: ProbabilisticAlgorithm

Whether this algorithm is correct.

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