net.sf.cpsolver.exam.heuristics
Class ExamSimulatedAnnealing

java.lang.Object
  extended by net.sf.cpsolver.exam.heuristics.ExamSimulatedAnnealing
All Implemented Interfaces:
NeighbourSelection<Exam,ExamPlacement>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>, SolutionListener<Exam,ExamPlacement>

public class ExamSimulatedAnnealing
extends Object
implements NeighbourSelection<Exam,ExamPlacement>, SolutionListener<Exam,ExamPlacement>, LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>

Simulated annealing. In each iteration, one of the following three neighbourhoods is selected first

, then a neighbour is generated and it is accepted with probability 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.

If SimulatedAnnealing.StochasticHC is true, the acceptance probability is computed using stochastic hill climbing criterion, i.e., 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.

Version:
ExamTT 1.2 (Examination Timetabling)
Copyright (C) 2008 - 2010 Tomas Muller
muller@unitime.org
http://muller.unitime.org

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.

Constructor Summary
ExamSimulatedAnnealing(DataProperties properties)
          Constructor.
 
Method Summary
 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).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ExamSimulatedAnnealing

public ExamSimulatedAnnealing(DataProperties properties)
Constructor. Following problem properties are considered:

Parameters:
properties - problem properties
Method Detail

init

public void init(Solver<Exam,ExamPlacement> solver)
Initialization

Specified by:
init in interface NeighbourSelection<Exam,ExamPlacement>

cool

protected void cool(Solution<Exam,ExamPlacement> solution)
Cool temperature


reheat

protected void reheat(Solution<Exam,ExamPlacement> solution)
Reheat temperature


restoreBest

protected void restoreBest(Solution<Exam,ExamPlacement> solution)
restore best ever found solution


genMove

public Neighbour<Exam,ExamPlacement> genMove(Solution<Exam,ExamPlacement> solution)
Generate neighbour -- select neighbourhood randomly, select neighbour


prob

protected double prob(double value)
Neighbour acceptance probability

Parameters:
value - absolute or relative value of the proposed change (neighbour)
Returns:
probability of acceptance of a change (neighbour)

accept

protected boolean accept(Solution<Exam,ExamPlacement> solution,
                         Neighbour<Exam,ExamPlacement> neighbour)
True if the given neighboir is to be be accepted

Parameters:
solution - current solution
neighbour - proposed move
Returns:
true if generated random number is below prob(double)

accept

public boolean accept(LazyNeighbour<Exam,ExamPlacement> neighbour,
                      double value)
Accept lazy neighbour

Specified by:
accept in interface LazyNeighbour.LazyNeighbourAcceptanceCriterion<Exam,ExamPlacement>
Parameters:
neighbour - neighbour that was assigned
value - change in overall solution value
Returns:
true if the neighbour can be accepted (false to undo the assignment)

incIter

protected void incIter(Solution<Exam,ExamPlacement> solution)
Increment iteration counter, cool/reheat/restoreBest if necessary


selectNeighbour

public 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).

Specified by:
selectNeighbour in interface NeighbourSelection<Exam,ExamPlacement>
Parameters:
solution - given solution
Returns:
a neighbour assignment

bestSaved

public void bestSaved(Solution<Exam,ExamPlacement> solution)
Memorize the iteration when the last best solution was found.

Specified by:
bestSaved in interface SolutionListener<Exam,ExamPlacement>
Parameters:
solution - source solution

solutionUpdated

public void solutionUpdated(Solution<Exam,ExamPlacement> solution)
Description copied from interface: SolutionListener
Called by the solution when it is updated, see Solution.update(double).

Specified by:
solutionUpdated in interface SolutionListener<Exam,ExamPlacement>
Parameters:
solution - source solution

getInfo

public void getInfo(Solution<Exam,ExamPlacement> solution,
                    Map<String,String> info)
Description copied from interface: SolutionListener
Called by the solution when it is asked to produce info table, see Solution.getInfo(). A listener can also add some its info into this table.

Specified by:
getInfo in interface SolutionListener<Exam,ExamPlacement>
Parameters:
solution - source solution
info - produced info table

getInfo

public void getInfo(Solution<Exam,ExamPlacement> solution,
                    Map<String,String> info,
                    Collection<Exam> variables)
Description copied from interface: SolutionListener
Called by the solution when it is asked to produce info table, see Solution.getInfo(). A listener can also add some its info into this table.

Specified by:
getInfo in interface SolutionListener<Exam,ExamPlacement>
Parameters:
solution - source solution
info - produced info table
variables - only variables from this set are included

bestCleared

public void bestCleared(Solution<Exam,ExamPlacement> solution)
Description copied from interface: SolutionListener
Called by the solution when method Solution.clearBest() is called.

Specified by:
bestCleared in interface SolutionListener<Exam,ExamPlacement>
Parameters:
solution - source solution

bestRestored

public void bestRestored(Solution<Exam,ExamPlacement> solution)
Description copied from interface: SolutionListener
Called by the solution when method Solution.restoreBest() is called.

Specified by:
bestRestored in interface SolutionListener<Exam,ExamPlacement>
Parameters:
solution - source solution


Copyright © 2014 UniTime LLC. All Rights Reserved.