aima.core.search.local

Class SimulatedAnnealingSearch

java.lang.Object

aima.core.search.local.SimulatedAnnealingSearch

All Implemented Interfaces:

SearchForActions, SearchForStates

public class SimulatedAnnealingSearch
extends java.lang.Object
implements SearchForActions, SearchForStates

Artificial Intelligence A Modern Approach (3rd Edition): Figure 4.5, page 126.

 function SIMULATED-ANNEALING(problem, schedule) returns a solution state
                    
   current <- MAKE-NODE(problem.INITIAL-STATE)
   for t = 1 to INFINITY do
     T <- schedule(t)
     if T = 0 then return current
     next <- a randomly selected successor of current
     /\E <- next.VALUE - current.value
     if /\E > 0 then current <- next
     else current <- next only with probability eˆ(/\E/T)
 

Figure 4.5 The simulated annealing search algorithm, a version of stochastic hill climbing where some downhill moves are allowed. Downhill moves are accepted readily early in the annealing schedule and then less often as time goes on. The schedule input determines the value of the temperature T as a function of time.

Author:

Ravi Mohan, Mike Stampone, Ruediger Lunde

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SimulatedAnnealingSearch.SearchOutcome

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	METRIC_NODE_VALUE
static java.lang.String	METRIC_NODES_EXPANDED
static java.lang.String	METRIC_TEMPERATURE

Constructor Summary

Constructors

Constructor and Description
SimulatedAnnealingSearch(HeuristicFunction hf) Constructs a simulated annealing search from the specified heuristic function and a default scheduler.
SimulatedAnnealingSearch(HeuristicFunction hf, Scheduler scheduler) Constructs a simulated annealing search from the specified heuristic function and scheduler.
SimulatedAnnealingSearch(HeuristicFunction hf, Scheduler scheduler, NodeExpander nodeExpander)

Method Summary

Modifier and Type	Method and Description
java.util.List<Action>	findActions(Problem p) Returns a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.
Node	findNode(Problem p)
java.lang.Object	findState(Problem p) Returns a state which is might be but not necessary is a goal state of the problem.
java.lang.Object	getLastSearchState() Returns the last state from which the simulated annealing search found a solution state.
Metrics	getMetrics() Returns all the search metrics.
NodeExpander	getNodeExpander() Returns the node expander used by the search.
SimulatedAnnealingSearch.SearchOutcome	getOutcome()
double	probabilityOfAcceptance(double temperature, double deltaE) Returns e&deltaE / T

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

METRIC_NODES_EXPANDED

public static final java.lang.String METRIC_NODES_EXPANDED

See Also:

Constant Field Values

METRIC_TEMPERATURE

public static final java.lang.String METRIC_TEMPERATURE

See Also:

Constant Field Values

METRIC_NODE_VALUE

public static final java.lang.String METRIC_NODE_VALUE

See Also:

Constant Field Values

Constructor Detail

SimulatedAnnealingSearch

public SimulatedAnnealingSearch(HeuristicFunction hf)

Constructs a simulated annealing search from the specified heuristic function and a default scheduler.

Parameters:

hf - a heuristic function

SimulatedAnnealingSearch

public SimulatedAnnealingSearch(HeuristicFunction hf,
                                Scheduler scheduler)

Constructs a simulated annealing search from the specified heuristic function and scheduler.

Parameters:

hf - a heuristic function

scheduler - a mapping from time to "temperature"

SimulatedAnnealingSearch

public SimulatedAnnealingSearch(HeuristicFunction hf,
                                Scheduler scheduler,
                                NodeExpander nodeExpander)

Method Detail

findActions

public java.util.List<Action> findActions(Problem p)

Description copied from interface: SearchForActions

Returns a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.

Specified by:

findActions in interface SearchForActions

Parameters:

p - the search problem

Returns:

a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.

findState

public java.lang.Object findState(Problem p)

Description copied from interface: SearchForStates

Returns a state which is might be but not necessary is a goal state of the problem.

Specified by:

findState in interface SearchForStates

Parameters:

p - the search problem

Returns:

a state.

findNode

public Node findNode(Problem p)

probabilityOfAcceptance

public double probabilityOfAcceptance(double temperature,
                                      double deltaE)

Returns e^{&deltaE / T}

Parameters:

temperature - T, a "temperature" controlling the probability of downward steps

deltaE - VALUE[next] - VALUE[current]

Returns:

e^{&deltaE / T}

getOutcome

public SimulatedAnnealingSearch.SearchOutcome getOutcome()

getLastSearchState

public java.lang.Object getLastSearchState()

Returns the last state from which the simulated annealing search found a solution state.

Returns:

the last state from which the simulated annealing search found a solution state.

getNodeExpander

public NodeExpander getNodeExpander()

Description copied from interface: SearchForActions

Returns the node expander used by the search. Useful for progress tracing.

Specified by:

getNodeExpander in interface SearchForActions

Specified by:

getNodeExpander in interface SearchForStates

getMetrics

public Metrics getMetrics()

Returns all the search metrics.

Specified by:

getMetrics in interface SearchForActions

Specified by:

getMetrics in interface SearchForStates