SimulatedAnnealing

public abstract class SimulatedAnnealing<S extends HeuristicSolution<?>> extends HeuristicAbstract<S>

A base class for implementation of Simulated Annealing algorithms used to find a suboptimal solution for a problem defined by sub-classes of this one. The Simulated Annealing is a heuristic that starts with a random solution and iteratively generates a random neighbor solution that its fitness is assessed in order to reach a sub-optimal result. The algorithm try to avoid local maximums, randomly selecting worse solutions to get away from being stuck in these locals.

The algorithm basically works as follows:

  1. Starts generating a random solution as you wish;
  2. Computes its fitness using some function (defined by the developer implementing the heuristic);
  3. Generates a neighbor random solution from the current solution and computes its fitness;
  4. Assesses the neighbor and current solution (the conditions below are ensured by the getAcceptanceProbability() method):
    • if neighbor.getFitness() > current.getFitness() then move to the new solution;
    • if neighbor.getFitness() < current.getFitness() then randomly decide if move to the new solution;
  5. Repeat steps 3 to 4 until an aceptable solution is found or some number of iterations or time is reached. These conditions are defined by the developer implementing the heuristic.
Author:

Manoel Campos da Silva Filho

Parameters:
  • <S> – the class of solutions the heuristic will deal with, starting with a random solution and execute the solution search in order to achieve a satisfying solution (defined by a stop criteria)

See also: [1] R. A. Rutenbar, “Simulated Annealing Algorithms: An overview,” IEEE Circuits Devices Mag., vol. 1, no. 5, pp. 19–26, 1989.

Constructors

SimulatedAnnealing

SimulatedAnnealing(ContinuousDistribution random, Class<S> solutionClass)

Instantiates a simulated annealing heuristic.

Parameters:
  • random – a pseudo random number generator
  • solutionClass – reference to the generic class that will be used to instantiate heuristic solutions

Methods

getAcceptanceProbability

public double getAcceptanceProbability()

{@inheritDoc}

It is used the Boltzmann distribution to define the probability of a worse solution (considering its cost) to be accepted or not in order to avoid local minima. The computed Boltzmann factor also ensures that better solutions are always accepted. The Boltzmann Constant has different values depending of the used unit. In this case, it was used the natural unit of information.

Returns:{@inheritDoc}

See also: Boltzmann distribution, Boltzmann constant

getColdTemperature

public double getColdTemperature()
Returns:the temperature that defines the system is cold enough and solution search may be stopped.

getCoolingRate

public double getCoolingRate()
Returns:percentage rate in which the system will be cooled, in scale from [0 to 1[.

getCurrentTemperature

public double getCurrentTemperature()

Gets the current system temperature that represents the system state at the time of the method call.

Returns:the current system temperature

isToStopSearch

public boolean isToStopSearch()

{@inheritDoc}

Returns:true if the system is cold enough and solution search can be stopped, false otherwise

setColdTemperature

public void setColdTemperature(double coldTemperature)

Sets the temperature that defines the system is cold enough and solution search may be stopped.

Parameters:
  • coldTemperature – the cold temperature to set

setCoolingRate

public void setCoolingRate(double coolingRate)

Sets the percentage rate in which the system will be cooled, in scale from [0 to 1[.

Parameters:
  • coolingRate – the rate to set

setCurrentTemperature

protected void setCurrentTemperature(double currentTemperature)

Sets the current system temperature.

Parameters:
  • currentTemperature – the temperature to set

updateSystemState

public void updateSystemState()

{@inheritDoc} Cools the system at a the defined cooling rate.

See also: .getCurrentTemperature()()