
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.HillClimbing
public class HillClimbing
Hillclimbing search. An heuristic search algorithm and local optimizer.
(One variant
of hillclimbing)
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 hillclimbing 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 randomrestart hillclimbing with a sufficient number of iterations. Randomrestart hillclimbing requires that ties break randomly. Which is the cause for hillclimbing to be a simple probabilistic algorithm.
Note that randomrestart hillclimbing 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 hillclimbing approximates gradient descent. If the state space is spanned by a system of linear unequalities, and the evaluation function is linear, then hillclimbing equals the simplex algorithm of linear programming. Local optimization guarantees that local optimum is global optimum if the statespace as well as the evaluation function are convex, then.
Hillclimbing "resembles trying to find the top of Mount Everest in a thick fog while suffering from amnesia." (Russel&Norvig, Ch 4.4)
Greedy
,
Serialized FormSimulatedAnnealing
, specializes ThresholdAccepting
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 

public HillClimbing(Function heuristic, LocalOptimizerSearch.LocalSelection localSelection)
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.public HillClimbing(Function heuristic)
heuristic
 the heuristic cost function h:S→R to be used as evaluation function f(n) = h(n).Method Detail 

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 getEvaluation()
getEvaluation
in interface EvaluativeAlgorithm
getEvaluation
in interface HeuristicAlgorithm
public Function complexity()
complexity
in interface AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)
public Function spaceComplexity()
spaceComplexity
in interface AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)
public boolean isOptimal()
GeneralSearch
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.
isOptimal
in class GeneralSearch
public boolean isCorrect()
ProbabilisticAlgorithm
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

Orbital library 1.3.0: 11 Apr 2009 

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