Orbital library

Class LocalOptimizerSearch

  extended by orbital.algorithm.template.GeneralSearch
      extended by orbital.algorithm.template.LocalOptimizerSearch
All Implemented Interfaces:
java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm, ProbabilisticAlgorithm
Direct Known Subclasses:
HillClimbing, SimulatedAnnealing, ThresholdAccepting

public abstract class LocalOptimizerSearch
extends GeneralSearch
implements ProbabilisticAlgorithm, EvaluativeAlgorithm

General search scheme for local optimizing search.

Local optimizers will try state transitions and accept only improvements, or states that promise to lead to improvements. In order to achieve that, most of these local optimizers use some sort of randomization and a probability depending on the degree of improvement or decrease. In fact, most uses of local optimizers also depend more or less on a random initial state. Then, some of them may profit from random-restart.

Subclasses usually use the LocalOptimizerSearch.OptionIterator provided to implement the traversal policy. Then they only have to provide the abstract methods to implement the search algorithm.

André Platzer
See Also:
Greedy, Serialized Form

Nested Class Summary
static class LocalOptimizerSearch.LocalSelection
          The local selection mechanism used to evaluate states.
static class LocalOptimizerSearch.OptionIterator
          An iterator over a state space in "choosy" random order.
Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm
Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate
Field Summary
static LocalOptimizerSearch.LocalSelection BEST_LOCAL_SELECTION
          attempt the best local transition (default).
static LocalOptimizerSearch.LocalSelection FIRST_LOCAL_SELECTION
          + attempt a randomly chosen local transition.
Constructor Summary
LocalOptimizerSearch(LocalOptimizerSearch.LocalSelection localSelection)
LocalOptimizerSearch(java.util.Random random, LocalOptimizerSearch.LocalSelection localSelection)
Method Summary
 java.util.Random getRandom()
          Get the random-generator used as probabilistic random source.
protected  java.lang.Object search(java.util.Iterator nodes)
          A slight modification of GeneralSearch.search(Iterator).
 void setRandom(java.util.Random randomGenerator)
          Set the random-generator to use as probabilistic random source.
Methods inherited from class orbital.algorithm.template.GeneralSearch
createTraversal, getProblem, isOptimal, 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.ProbabilisticAlgorithm
Methods inherited from interface orbital.algorithm.template.EvaluativeAlgorithm
Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate
complexity, solve, spaceComplexity

Field Detail


public static final LocalOptimizerSearch.LocalSelection BEST_LOCAL_SELECTION
attempt the best local transition (default). Although we have a local convergence criterion then, that variant is no good for very high branching factors (or expensive expansions).

See Also:


public static final LocalOptimizerSearch.LocalSelection FIRST_LOCAL_SELECTION
+ attempt a randomly chosen local transition. In the usual case of accepting only improvements this becomes: accept the first (randomly chosen) local transition At least for local derivable evaluation functions, the expected number of random trials until finding an improvement is 2, anyway.

Constructor Detail


public LocalOptimizerSearch(java.util.Random random,
                            LocalOptimizerSearch.LocalSelection localSelection)
random - the random generator source.
localSelection - the variant of local selection used.
See Also:


public LocalOptimizerSearch(LocalOptimizerSearch.LocalSelection localSelection)
Method Detail


public java.util.Random getRandom()
Description copied from interface: ProbabilisticAlgorithm
Get the random-generator used as probabilistic random source.

Specified by:
getRandom in interface ProbabilisticAlgorithm
the random generator used for producing probabilistic effects.


public void setRandom(java.util.Random randomGenerator)
Description copied from interface: ProbabilisticAlgorithm
Set the random-generator to use as probabilistic random source.

Especially called to change the random source to a previous, more secure, or more realistic generator.

Specified by:
setRandom in interface ProbabilisticAlgorithm


protected java.lang.Object search(java.util.Iterator nodes)
A slight modification of GeneralSearch.search(Iterator). This method will finally return the most optimal node found, regardless of whether it is a solution, or not. This behaviour is especially useful if the isSolution test is omitted by categorically returning true there.

search in class GeneralSearch
nodes - is the iterator over the nodes to visit (sometimes called open set) which determines the traversal order.
the solution found searching the state space via nodes.
See Also:
Template Method

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.