Orbital library

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 HillClimbingextends LocalOptimizerSearchimplements 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
`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`.
"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).
`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).
`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.
Factory Method, `GeneralSearch.OptionIterator`