net.sf.cpsolver.exam.heuristics
Class ExamGreatDeluge

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

All Implemented Interfaces:

NeighbourSelection, SolutionListener

public class ExamGreatDeluge
extends Object
implements NeighbourSelection, SolutionListener

Greate deluge. 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 if the value of the new solution is below certain bound. This bound is initialized to the GreatDeluge.UpperBoundRate × value of the best solution ever found. After each iteration, the bound is decreased by GreatDeluge.CoolRate (new bound equals to old bound × GreatDeluge.CoolRate). If the bound gets bellow GreatDeluge.LowerBoundRate × value of the best solution ever found, it is changed back to GreatDeluge.UpperBoundRate × value of the best solution ever found. If there was no improvement found between the bounds, the new bounds are changed to GreatDeluge.UpperBoundRate^2 and GreatDeluge.LowerBoundRate^2, GreatDeluge.UpperBoundRate^3 and GreatDeluge.LowerBoundRate^3, etc. till there is an improvement found.

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

ExamGreatDeluge(DataProperties properties)
Constructor.

Method Summary

protected boolean	accept(Solution solution, Neighbour neighbour) Accept neighbour
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) Update last improving iteration count
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 count, update bound
protected void	info(Solution solution) Print some information
void	init(Solver solver) Initialization
Neighbour	selectNeighbour(Solution solution) A neighbour is generated randomly untill an acceptable one is found.
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

ExamGreatDeluge

public ExamGreatDeluge(DataProperties properties)

Constructor. Following problem properties are considered:

• GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995)
• GreatDeluge.UpperBoundRate ... bound upper bound relative to best solution ever found (default 1.05)
• GreatDeluge.LowerBoundRate ... bound lower bound relative to best solution ever found (default 0.95)

Parameters:

properties - problem properties

Method Detail

init

public void init(Solver solver)

Initialization

Specified by:

init in interface NeighbourSelection

info

protected void info(Solution solution)

Print some information

genMove

public Neighbour genMove(Solution solution)

Generate neighbour -- select neighbourhood randomly, select neighbour

accept

protected boolean accept(Solution solution,
                         Neighbour neighbour)

Accept neighbour

incIter

protected void incIter(Solution solution)

Increment iteration count, update bound

selectNeighbour

public Neighbour selectNeighbour(Solution solution)

A neighbour is generated randomly untill an acceptable one is found.

Specified by:

selectNeighbour in interface NeighbourSelection

Parameters:

solution - given solution

Returns:

a neighbour assignment

bestSaved

public void bestSaved(Solution solution)

Update last improving iteration count

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