public class ExamSimulatedAnnealing extends Object implements NeighbourSelection<Exam,ExamPlacement>, SolutionListener<Exam,ExamPlacement>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>
ExamRandomMove
)
ExamTimeMove
)
ExamRoomMove
)
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
ExamSimpleNeighbour.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. Constructor and Description |
---|
ExamSimulatedAnnealing(DataProperties properties)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
boolean |
accept(LazyNeighbour<Exam,ExamPlacement> neighbour,
double value)
Accept lazy neighbour
|
protected boolean |
accept(Solution<Exam,ExamPlacement> solution,
Neighbour<Exam,ExamPlacement> neighbour)
True if the given neighboir is to be be accepted
|
void |
bestCleared(Solution<Exam,ExamPlacement> solution)
Called by the solution when method
Solution.clearBest() is
called. |
void |
bestRestored(Solution<Exam,ExamPlacement> solution)
Called by the solution when method
Solution.restoreBest() is
called. |
void |
bestSaved(Solution<Exam,ExamPlacement> solution)
Memorize the iteration when the last best solution was found.
|
protected void |
cool(Solution<Exam,ExamPlacement> solution)
Cool temperature
|
Neighbour<Exam,ExamPlacement> |
genMove(Solution<Exam,ExamPlacement> solution)
Generate neighbour -- select neighbourhood randomly, select neighbour
|
void |
getInfo(Solution<Exam,ExamPlacement> solution,
Map<String,String> info)
Called by the solution when it is asked to produce info table, see
Solution.getInfo() . |
void |
getInfo(Solution<Exam,ExamPlacement> solution,
Map<String,String> info,
Collection<Exam> variables)
Called by the solution when it is asked to produce info table, see
Solution.getInfo() . |
protected void |
incIter(Solution<Exam,ExamPlacement> solution)
Increment iteration counter, cool/reheat/restoreBest if necessary
|
void |
init(Solver<Exam,ExamPlacement> solver)
Initialization
|
protected double |
prob(double value)
Neighbour acceptance probability
|
protected void |
reheat(Solution<Exam,ExamPlacement> solution)
Reheat temperature
|
protected void |
restoreBest(Solution<Exam,ExamPlacement> solution)
restore best ever found solution
|
Neighbour<Exam,ExamPlacement> |
selectNeighbour(Solution<Exam,ExamPlacement> solution)
Select neighbour -- generate a move
genMove(Solution) until an acceptable
neighbour is found
accept(Solution, Neighbour) , keep
increasing iteration incIter(Solution) . |
void |
solutionUpdated(Solution<Exam,ExamPlacement> solution)
Called by the solution when it is updated, see
Solution.update(double) . |
public ExamSimulatedAnnealing(DataProperties properties)
properties
- problem propertiespublic void init(Solver<Exam,ExamPlacement> solver)
init
in interface NeighbourSelection<Exam,ExamPlacement>
protected void cool(Solution<Exam,ExamPlacement> solution)
protected void reheat(Solution<Exam,ExamPlacement> solution)
protected void restoreBest(Solution<Exam,ExamPlacement> solution)
public Neighbour<Exam,ExamPlacement> genMove(Solution<Exam,ExamPlacement> solution)
protected double prob(double value)
value
- absolute or relative value of the proposed change (neighbour)protected boolean accept(Solution<Exam,ExamPlacement> solution, Neighbour<Exam,ExamPlacement> neighbour)
solution
- current solutionneighbour
- proposed moveprob(double)
public boolean accept(LazyNeighbour<Exam,ExamPlacement> neighbour, double value)
accept
in interface LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>
neighbour
- neighbour that was assignedvalue
- change in overall solution valueprotected void incIter(Solution<Exam,ExamPlacement> solution)
public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution)
genMove(Solution)
until an acceptable
neighbour is found
accept(Solution, Neighbour)
, keep
increasing iteration incIter(Solution)
.selectNeighbour
in interface NeighbourSelection<Exam,ExamPlacement>
solution
- given solutionpublic void bestSaved(Solution<Exam,ExamPlacement> solution)
bestSaved
in interface SolutionListener<Exam,ExamPlacement>
solution
- source solutionpublic void solutionUpdated(Solution<Exam,ExamPlacement> solution)
SolutionListener
Solution.update(double)
.solutionUpdated
in interface SolutionListener<Exam,ExamPlacement>
solution
- source solutionpublic void getInfo(Solution<Exam,ExamPlacement> solution, Map<String,String> info)
SolutionListener
Solution.getInfo()
. A listener can also add some its info into
this table.getInfo
in interface SolutionListener<Exam,ExamPlacement>
solution
- source solutioninfo
- produced info tablepublic void getInfo(Solution<Exam,ExamPlacement> solution, Map<String,String> info, Collection<Exam> variables)
SolutionListener
Solution.getInfo()
. A listener can also add some its info into
this table.getInfo
in interface SolutionListener<Exam,ExamPlacement>
solution
- source solutioninfo
- produced info tablevariables
- only variables from this set are includedpublic void bestCleared(Solution<Exam,ExamPlacement> solution)
SolutionListener
Solution.clearBest()
is
called.bestCleared
in interface SolutionListener<Exam,ExamPlacement>
solution
- source solutionpublic void bestRestored(Solution<Exam,ExamPlacement> solution)
SolutionListener
Solution.restoreBest()
is
called.bestRestored
in interface SolutionListener<Exam,ExamPlacement>
solution
- source solution