SimulatedAnnealingSearch.java

package aima.core.search.local;

import aima.core.search.framework.*;
import aima.core.search.framework.problem.Problem;
import aima.core.util.Tasks;
import aima.core.util.Util;

import java.util.List;
import java.util.Optional;
import java.util.function.Consumer;
import java.util.function.ToDoubleFunction;

/**
 * Artificial Intelligence A Modern Approach (3rd Edition): Figure 4.5, page
 * 126.<br>
 * <br>
 * 
 * <pre>
 * function SIMULATED-ANNEALING(problem, schedule) returns a solution state
 *                    
 *   current &lt;- MAKE-NODE(problem.INITIAL-STATE)
 *   for t = 1 to INFINITY do
 *     T &lt;- schedule(t)
 *     if T = 0 then return current
 *     next &lt;- a randomly selected successor of current
 *     /\E &lt;- next.VALUE - current.value
 *     if /\E &gt; 0 then current &lt;- next
 *     else current &lt;- next only with probability e&circ;(/\E/T)
 * </pre>
 * 
 * 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
 * @author Mike Stampone
 * @author Ruediger Lunde
 */
public class SimulatedAnnealingSearch<S, A> implements SearchForActions<S, A>, SearchForStates<S, A> {

    public static final String METRIC_NODES_EXPANDED = "nodesExpanded";
	public static final String METRIC_TEMPERATURE = "temp";
	public static final String METRIC_NODE_VALUE = "nodeValue";
	
	private final ToDoubleFunction<Node<S, A>> energyFn;
	private final Scheduler scheduler;
	private final NodeFactory<S, A> nodeFactory;

	private S lastState;
	private Metrics metrics = new Metrics();

	/**
	 * Constructs a simulated annealing search for the specified energy
	 * function and a default scheduler.
	 * 
	 * @param energyFn
	 *            a function mapping nodes to the energy of their state (the lower the better).
	 */
	public SimulatedAnnealingSearch(ToDoubleFunction<Node<S, A>> energyFn) {
		this(energyFn, new Scheduler());
	}

	/**
	 * Constructs a simulated annealing search for the specified energy
	 * function and scheduler.
	 *
	 * @param energyFn
	 *            a function mapping nodes to the energy of their state (the lower the better).
	 * @param scheduler
	 *            a mapping from time to "temperature"
	 */
	public SimulatedAnnealingSearch(ToDoubleFunction<Node<S, A>> energyFn, Scheduler scheduler) {
		this(energyFn, scheduler, new NodeFactory<>());
	}
	
	public SimulatedAnnealingSearch(ToDoubleFunction<Node<S, A>> energyFn, Scheduler scheduler, NodeFactory<S, A> nodeFactory) {
		this.energyFn = energyFn;
		this.scheduler = scheduler;
		this.nodeFactory = nodeFactory;
		nodeFactory.addNodeListener((node) -> metrics.incrementInt(METRIC_NODES_EXPANDED));
	}
	
	@Override
	public Optional<List<A>> findActions(Problem<S, A> p) {
		nodeFactory.useParentLinks(true);
		return SearchUtils.toActions(findNode(p));
	}
	
	@Override
	public Optional<S> findState(Problem<S, A> p) {
		nodeFactory.useParentLinks(false);
		return SearchUtils.toState(findNode(p));
	}

	/**
	 * Returns a node corresponding to a goal state or empty. Method {@link #getLastState()}
	 * provides the last explored state if result is empty. Note that in this version, a minimum
	 * is searched (two advantages: 1. The physical idea behind the algorithm becomes more visible.
	 * 2. Heuristic functions can directly be used as energy functions, no need to change the sign
	 * of the value).
	 */
	/// function SIMULATED-ANNEALING(problem, schedule) returns a solution state
	public Optional<Node<S, A>> findNode(Problem<S, A> p) {
		clearMetrics();
		/// current <- MAKE-NODE(problem.INITIAL-STATE)
		Node<S, A> current = nodeFactory.createNode(p.getInitialState());
		/// for t = 1 to INFINITY do
		int timeStep = 0;
		while (!Tasks.currIsCancelled()) {
			/// temperature <- schedule(t)
			double temperature = scheduler.getTemp(timeStep);
			timeStep++;
			lastState = current.getState();
			/// if temperature = 0 then return current
			if (temperature == 0.0) {
				lastState = current.getState();
				return Optional.ofNullable(p.testSolution(current) ? current : null);
			}

			updateMetrics(temperature, getEnergy(current));
			List<Node<S, A>> children = nodeFactory.getSuccessors(current, p);
			if (children.size() > 0) {
				/// next <- a randomly selected successor of current
				Node<S, A> next = Util.selectRandomlyFromList(children);
				/// dE <- next.VALUE - current.value
				double deltaE = getEnergy(next) - getEnergy(current);
				// if dE < 0 then current &lt;- next
				// else current <- next only with probability e&circ;(-dE/T)
				if (deltaE < 0.0 || Math.random() <= Math.exp(-deltaE / temperature))
					current = next;
			}
		}
		lastState = current.getState();
		return Optional.empty();
	}

	private double getEnergy(Node<S, A> n) {
		return energyFn.applyAsDouble(n);
	}

	/**
	 * Returns the last explored state.
	 */
	public S getLastState() {
		return lastState;
	}
	
	/**
	 * Returns all the search metrics.
	 */
	@Override
	public Metrics getMetrics() {
		return metrics;
	}
	
	private void updateMetrics(double temperature, double value) {
		metrics.set(METRIC_TEMPERATURE, temperature);
		metrics.set(METRIC_NODE_VALUE, value);
	}
	
	/**
	 * Sets all metrics to zero.
	 */
	private void clearMetrics() {
		metrics.set(METRIC_NODES_EXPANDED, 0);
		metrics.set(METRIC_TEMPERATURE, 0);
		metrics.set(METRIC_NODE_VALUE, 0);
	}

	@Override
	public void addNodeListener(Consumer<Node<S, A>> listener)  {
		nodeFactory.addNodeListener(listener);
	}

	@Override
	public boolean removeNodeListener(Consumer<Node<S, A>> listener) {
		return nodeFactory.removeNodeListener(listener);
	}
}