public class

AnnealingSearch

extends Algorithm<A, S, N extends Node<A, S, N>>
java.lang.Object
   ↳ es.usc.citius.hipster.algorithm.Algorithm<A, S, N extends es.usc.citius.hipster.model.Node<A, S, N>>
     ↳ es.usc.citius.hipster.algorithm.localsearch.AnnealingSearch<A, S, N extends es.usc.citius.hipster.model.HeuristicNode<A, S, java.lang.Double, N>>

Class Overview

Implementation of the simulated annealing search that is a probabilistic technique for approximating the global optimum of a given function. It starts the exploration from a random point as a global optimum and selects one of its neighbors with a neighboring function. The neighbor will become the new optimum if its associated cost is lower or if the acceptance probability function returns a probability greater than a random number. The probability function takes as an input the cost of the current selected node, the cost of its randomly selected neighbour and the current temperature. The higher the cost of the neighbour is or the lower the temperature is, the more unlikely it is that the neighbour becomes the new optimum. The process continues until the temperature is below a given threshold. The temperature decreases at each iteration according to a geometric cooling schedule that has two parameters alpha and temperature min. The main idea of this algorithm is to avoid to be "trapped" in a bad local optimum by exploring more deeply the state space by looking at states whose cost is not optimum but that may have interesting neighbours. A user can adjusted the algorithm by tuning the alpha coefficient (default 0.9) or the min temperature (0.00001) or by providing his own implementation of the acceptance probability function (default: exp((old score - new score) / current temperature)) or the neighbouring function (random selection by default). Note: costs are Double in this implementation and have no type parameters. see in Wikipedia and in annealing search for more details.

Summary

Nested Classes
class AnnealingSearch.ASIterator  
interface AnnealingSearch.AcceptanceProbability Interface to compute the acceptance probability. 
interface AnnealingSearch.SuccessorFinder<A, S, N extends Node<A, S, N>> Interface to find the successor of a node. 
Public Constructors
AnnealingSearch(N initialNode, NodeExpander<A, S, N> nodeExpander, Double alpha, Double minTemp, AnnealingSearch.AcceptanceProbability acceptanceProbability, SuccessorFinder<A, S, N> successorFinder)
Public Methods
ASIterator iterator()
[Expand]
Inherited Methods
From class es.usc.citius.hipster.algorithm.Algorithm
From class java.lang.Object
From interface java.lang.Iterable

Public Constructors

public AnnealingSearch (N initialNode, NodeExpander<A, S, N> nodeExpander, Double alpha, Double minTemp, AnnealingSearch.AcceptanceProbability acceptanceProbability, SuccessorFinder<A, S, N> successorFinder)

Public Methods

public ASIterator iterator ()