orbital.algorithm.template
Class LocalOptimizerSearch

java.lang.Object
  orbital.algorithm.template.GeneralSearch
      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.

Author:

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

EvaluativeAlgorithm.EvaluationComparator

Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate

AlgorithmicTemplate.Configuration

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

isCorrect

Methods inherited from interface orbital.algorithm.template.EvaluativeAlgorithm

getEvaluation

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

complexity, solve, spaceComplexity

Field Detail

BEST_LOCAL_SELECTION

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:

BestFirstSearch

FIRST_LOCAL_SELECTION

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

LocalOptimizerSearch

public LocalOptimizerSearch(java.util.Random random,
                            LocalOptimizerSearch.LocalSelection localSelection)

Parameters:

random - the random generator source.

localSelection - the variant of local selection used.

See Also:

BEST_LOCAL_SELECTION, FIRST_LOCAL_SELECTION

LocalOptimizerSearch

public LocalOptimizerSearch(LocalOptimizerSearch.LocalSelection localSelection)

Method Detail

getRandom

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

Returns:

the random generator used for producing probabilistic effects.

setRandom

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

search

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.

Overrides:

search in class GeneralSearch

Parameters:

nodes - is the iterator over the nodes to visit (sometimes called open set) which determines the traversal order.

Returns:

the solution found searching the state space via nodes.

See Also:

Template Method

Postconditions:

¬super