public class SimulatedAnnealing<V extends Variable<V,T>,T extends Value<V,T>> extends NeighbourSearch<V,T>
prob(double)
. The search is guided by the
temperature, which starts at SimulatedAnnealing.InitialTemperature.
After each SimulatedAnnealing.TemperatureLength iterations, the
temperature is reduced by SimulatedAnnealing.CoolingRate. If there was
no improvement in the past SimulatedAnnealing.ReheatLengthCoef *
SimulatedAnnealing.TemperatureLength iterations, the temperature is
increased by SimulatedAnnealing.ReheatRate. If there was no
improvement in the past SimulatedAnnealing.RestoreBestLengthCoef *
SimulatedAnnealing.TemperatureLength iterations, the best ever found
solution is restored. 1.0 / (1.0 + Math.exp(value/temperature))
, otherwise it is
cumputed using simlated annealing criterion, i.e.,
(value<=0.0?1.0:Math.exp(-value/temperature))
. If
SimulatedAnnealing.RelativeAcceptance neighbour value
Neighbour.value()
is taken as the value of the selected
neighbour (difference between the new and the current solution, if the
neighbour is accepted), otherwise the value is computed as the difference
between the value of the current solution if the neighbour is accepted and
the best ever found solution. NeighbourSelection
. By default,
each neighbour selection is selected with the same probability (each has 1 point in
a roulette wheel selection). It can be changed by adding @n at the end
of the name of the class, for example:
SimulatedAnnealing.Neighbours=net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1
NeighbourSelector.update(Neighbour, long)
is called
after each iteration (on the selector that was used) and roulette wheel selection
that is using NeighbourSelector.getPoints()
is used to pick a selector in each iteration.
See NeighbourSelector
for more details.
Constructor and Description |
---|
SimulatedAnnealing(DataProperties properties)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
protected boolean |
accept(Model<V,T> model,
Neighbour<V,T> neighbour,
double value,
boolean lazy)
True if the given neighbour is to be be accepted
|
protected void |
activate(Solution<V,T> solution)
Setup the temperature
|
void |
bestSaved(Solution<V,T> solution)
Memorize the iteration when the last best solution was found.
|
protected void |
cool(Solution<V,T> solution)
Cool temperature
|
String |
getParameterBaseName()
Parameter base name.
|
protected void |
incIteration(Solution<V,T> solution)
Increment iteration counter, cool/reheat/restoreBest if necessary
|
protected double |
prob(double value)
Neighbour acceptance probability
|
protected void |
reheat(Solution<V,T> solution)
Reheat temperature
|
protected void |
restoreBest(Solution<V,T> solution)
restore best ever found solution
|
accept, accept, addNeighbourSelection, bestCleared, bestRestored, canContinue, deactivate, generateMove, getInfo, getInfo, getNeighbours, getTimeMillis, init, logNeibourStatus, nextNeighbourSelection, selectNeighbour, setHCMode, solutionUpdated
public SimulatedAnnealing(DataProperties properties)
NeighbourSelection
NeighbourSelection
NeighbourSelector.getPoints()
weights (roulette wheel selection)
properties
- problem propertiesprotected void restoreBest(Solution<V,T> solution)
protected double prob(double value)
value
- absolute or relative value of the proposed change (neighbour)protected boolean accept(Model<V,T> model, Neighbour<V,T> neighbour, double value, boolean lazy)
protected void incIteration(Solution<V,T> solution)
incIteration
in class NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>
public void bestSaved(Solution<V,T> solution)
public String getParameterBaseName()
NeighbourSearch
getParameterBaseName
in class NeighbourSearch<V extends Variable<V,T>,T extends Value<V,T>>