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:
- Starts generating a random solution as you wish;
- Computes its fitness using some function (defined by the developer implementing the heuristic);
- Generates a neighbor random solution from the current solution and computes its fitness;
- Assesses the neighbor and current solution (the conditions below are ensured by the
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;
- 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.
Manoel Campos da Silva Filho
- <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)
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: the temperature that defines the system is cold enough and solution search may be stopped.
Returns: percentage rate in which the system will be cooled, in scale from [0 to 1[.
Gets the current system temperature that represents the system state at the time of the method call.
Returns: the current system temperature
Sets the temperature that defines the system is cold enough and solution search may be stopped.
- coldTemperature – the cold temperature to set
Sets the percentage rate in which the system will be cooled, in scale from [0 to 1[.
- coolingRate – the rate to set
Sets the current system temperature.
- currentTemperature – the temperature to set