Package es.urjc.etsii.grafo.improve.sa

Class SimulatedAnnealing<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance>

java.lang.Object

es.urjc.etsii.grafo.improve.Improver<S,I>

es.urjc.etsii.grafo.improve.sa.SimulatedAnnealing<M,S,I>

Type Parameters:

M - Move type

S - Solution type

I - Instance type

public class SimulatedAnnealing<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance>
extends Improver<S,I>

Simulated annealing (SA) is a metaheuristic whose name comes from annealing in metallurgy. This metaheuristic considers some neighboring state s* of the current state s, and probabilistically decides between moving the system to state s* or staying in-state s. The transition is always performed if it improves the current solution, while it depends on the current temperature if not. The decision to transition is controlled by the AcceptanceCriteria. These probabilities ultimately lead the system to move to lower energy states. After each possible transition, the current temperature is lowered, using the CoolDownControl. The process is repeated until the TerminationCriteria is met. The initial temperature is configured using InitialTemperatureCalculator, which usually defaults to something like the Max diff between the moves in the neighborhood, as implemented in MaxDifferenceInitialTemperature.

See Also:

• SimulatedAnnealingBuilder

Nested Class Summary

Nested classes/interfaces inherited from class es.urjc.etsii.grafo.improve.Improver

Improver.NullImprover<S extends Solution<S,I>,I extends Instance>, Improver.SequentialImprover<S extends Solution<S,I>,I extends Instance>

Field Summary

Fields

Modifier and Type	Field	Description
protected final AcceptanceCriteria<M,S,I>	acceptanceCriteria
protected final CoolDownControl<M,S,I>	coolDownControl
protected final int	cycleLength
protected final InitialTemperatureCalculator<M,S,I>	initialTemperatureCalculator
protected final RandomizableNeighborhood<M,S,I>	neighborhood
protected final Objective<M,S,I>	objective
protected final TerminationCriteria<M,S,I>	terminationCriteria

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	SimulatedAnnealing(Objective<M,S,I> objective, AcceptanceCriteria<M,S,I> acceptanceCriteria, RandomizableNeighborhood<M,S,I> ps, InitialTemperatureCalculator<M,S,I> initialTemperatureCalculator, TerminationCriteria<M,S,I> terminationCriteria, CoolDownControl<M,S,I> coolDownControl, int cycleLength)	Internal constructor, use SimulatedAnnealingBuilder.

Method Summary

Modifier and Type	Method	Description
protected es.urjc.etsii.grafo.improve.sa.SimulatedAnnealing.CycleResult<S>	doCycle(RandomizableNeighborhood<M,S,I> neighborhood, S solution, S best, double currentTemperature, int currentIteration)	Does a cycle with the same temperature.
S	improve(S solution)	Improves a model.Solution Iterates until we run out of time, or we cannot improve the current es.urjc.etsii.grafo.solution any further
protected boolean	shouldEnd(S best, double currentTemperature, int currentIteration)

Methods inherited from class es.urjc.etsii.grafo.improve.Improver

getObjective, nul, serial, serial

Methods inherited from class java.lang.Object

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

Field Details

objective

protected final Objective<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> objective

acceptanceCriteria

protected final AcceptanceCriteria<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> acceptanceCriteria

neighborhood

protected final RandomizableNeighborhood<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> neighborhood

terminationCriteria

protected final TerminationCriteria<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> terminationCriteria

coolDownControl

protected final CoolDownControl<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> coolDownControl

initialTemperatureCalculator

protected final InitialTemperatureCalculator<M extends Move<S,I>,S extends Solution<S,I>,I extends Instance> initialTemperatureCalculator

cycleLength

protected final int cycleLength

Constructor Details

SimulatedAnnealing

protected SimulatedAnnealing(Objective<M,S,I> objective,
 AcceptanceCriteria<M,S,I> acceptanceCriteria,
 RandomizableNeighborhood<M,S,I> ps,
 InitialTemperatureCalculator<M,S,I> initialTemperatureCalculator,
 TerminationCriteria<M,S,I> terminationCriteria,
 CoolDownControl<M,S,I> coolDownControl,
 int cycleLength)

Internal constructor, use SimulatedAnnealingBuilder.

Parameters:

acceptanceCriteria -

ps -

initialTemperatureCalculator -

terminationCriteria -

coolDownControl -

cycleLength -

Method Details

shouldEnd

protected boolean shouldEnd(S best,
 double currentTemperature,
 int currentIteration)

improve

public S improve(S solution)

Description copied from class: Improver

Improves a model.Solution Iterates until we run out of time, or we cannot improve the current es.urjc.etsii.grafo.solution any further

Specified by:

improve in class Improver<S extends Solution<S,I>,I extends Instance>

Parameters:

solution - model.Solution to improve

Returns:

Improved s

doCycle

protected es.urjc.etsii.grafo.improve.sa.SimulatedAnnealing.CycleResult<S> doCycle(RandomizableNeighborhood<M,S,I> neighborhood,
 S solution,
 S best,
 double currentTemperature,
 int currentIteration)

Does a cycle with the same temperature. Always works on the same solution. Fast implementation that can only be used if the Neighborhood implements RandomizableNeighborhood.

Parameters:

solution - current working solution

best - best solution found until now

currentTemperature - current temperature

currentIteration - current iteration

Returns:

best solution found, remember that you should NOT use the returned solution