net.sf.cpsolver.exam.heuristics
Class ExamSimulatedAnnealing

java.lang.Object
  net.sf.cpsolver.exam.heuristics.ExamSimulatedAnnealing

All Implemented Interfaces:

NeighbourSelection, SolutionListener

public class ExamSimulatedAnnealing
extends Object
implements NeighbourSelection, SolutionListener

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

• random move (ExamRandomMove)
• period swap (ExamTimeMove)
• room swap (ExamRoomMove)

, 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.1 (Examination Timetabling)
Copyright (C) 2008 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

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 2.1 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

Constructor Summary

ExamSimulatedAnnealing(DataProperties properties)
Constructor.

Method Summary

protected boolean	accept(Solution solution, Neighbour neighbour) True if the given neighboir is to be be accepted
void	bestCleared(Solution solution) Called by the solution when method Solution.clearBest() is called.
void	bestRestored(Solution solution) Called by the solution when method Solution.restoreBest() is called.
void	bestSaved(Solution solution) Memorize the iteration when the last best solution was found.
protected void	cool(Solution solution) Cool temperature
Neighbour	genMove(Solution solution) Generate neighbour -- select neighbourhood randomly, select neighbour
void	getInfo(Solution solution, Dictionary info) Called by the solution when it is asked to produce info table, see Solution.getInfo().
void	getInfo(Solution solution, Dictionary info, Vector variables) Called by the solution when it is asked to produce info table, see Solution.getInfo().
protected void	incIter(Solution solution) Increment iteration counter, cool/reheat/restoreBest if necessary
void	init(Solver solver) Initialization
protected double	prob(double value) Neighbour acceptance probability
protected void	reheat(Solution solution) Reheat temperature
protected void	restoreBest(Solution solution) restore best ever found solution
Neighbour	selectNeighbour(Solution 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 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:

• SimulatedAnnealing.InitialTemperature ... initial temperature (default 1.5)
• SimulatedAnnealing.TemperatureLength ... temperature length (number of iterations between temperature decrements, default 25000)
• SimulatedAnnealing.CoolingRate ... temperature cooling rate (default 0.95)
• SimulatedAnnealing.ReheatLengthCoef ... temperature re-heat length coefficient (multiple of temperature length, default 5)
• SimulatedAnnealing.ReheatRate ... temperature re-heating rate (default (1/coolingRate)^(reheatLengthCoef*1.7))
• SimulatedAnnealing.RestoreBestLengthCoef ... restore best length coefficient (multiple of re-heat length, default reheatLengthCoef^2)
• SimulatedAnnealing.StochasticHC ... true for stochastic search acceptance criterion, false for simulated annealing acceptance (default false)
• SimulatedAnnealing.RelativeAcceptance ... true for relative acceptance (different between the new and the current solutions, if the neighbour is accepted), false for absolute acceptance (difference between the new and the best solutions, if the neighbour is accepted)

Parameters:

properties - problem properties

Method Detail

init

public void init(Solver solver)

Initialization

Specified by:

init in interface NeighbourSelection

cool

protected void cool(Solution solution)

Cool temperature

reheat

protected void reheat(Solution solution)

Reheat temperature

restoreBest

protected void restoreBest(Solution solution)

restore best ever found solution

genMove

public Neighbour genMove(Solution 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 solution,
                         Neighbour 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)

incIter

protected void incIter(Solution solution)

Increment iteration counter, cool/reheat/restoreBest if necessary

selectNeighbour

public Neighbour selectNeighbour(Solution 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

Parameters:

solution - given solution

Returns:

a neighbour assignment

bestSaved

public void bestSaved(Solution solution)

Memorize the iteration when the last best solution was found.

Specified by:

bestSaved in interface SolutionListener

Parameters:

solution - source solution

solutionUpdated

public void solutionUpdated(Solution solution)

Description copied from interface: SolutionListener

Called by the solution when it is updated, see Solution.update(double).

Specified by:

solutionUpdated in interface SolutionListener

Parameters:

solution - source solution

getInfo

public void getInfo(Solution solution,
                    Dictionary 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

Parameters:

solution - source solution

info - produced info table

getInfo

public void getInfo(Solution solution,
                    Dictionary info,
                    Vector 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

Parameters:

solution - source solution

info - produced info table

variables - only variables from this set are included

bestCleared

public void bestCleared(Solution solution)

Description copied from interface: SolutionListener

Called by the solution when method Solution.clearBest() is called.

Specified by:

bestCleared in interface SolutionListener

Parameters:

solution - source solution

bestRestored

public void bestRestored(Solution solution)

Description copied from interface: SolutionListener

Called by the solution when method Solution.restoreBest() is called.

Specified by:

bestRestored in interface SolutionListener

Parameters:

solution - source solution