001 package net.sf.cpsolver.exam.heuristics;
002
003 import net.sf.cpsolver.exam.neighbours.ExamRandomMove;
004 import net.sf.cpsolver.exam.neighbours.ExamRoomMove;
005 import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour;
006 import net.sf.cpsolver.exam.neighbours.ExamTimeMove;
007 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
008 import net.sf.cpsolver.ifs.model.Neighbour;
009 import net.sf.cpsolver.ifs.solution.Solution;
010 import net.sf.cpsolver.ifs.solution.SolutionListener;
011 import net.sf.cpsolver.ifs.solver.Solver;
012 import net.sf.cpsolver.ifs.util.DataProperties;
013 import net.sf.cpsolver.ifs.util.Progress;
014 import net.sf.cpsolver.ifs.util.ToolBox;
015
016 /**
017 * Hill climber. In each iteration, one of the following three neighbourhoods is selected first
018 * <ul>
019 * <li>random move ({@link ExamRandomMove})
020 * <li>period swap ({@link ExamTimeMove})
021 * <li>room swap ({@link ExamRoomMove})
022 * </ul>,
023 * then a neighbour is generated and it is accepted if its value {@link ExamSimpleNeighbour#value()} is
024 * below or equal to zero. The search is stopped after a given amount of idle iterations (
025 * can be defined by problem property HillClimber.MaxIdle).
026 * <br><br>
027 *
028 * @version
029 * ExamTT 1.1 (Examination Timetabling)<br>
030 * Copyright (C) 2008 Tomáš Müller<br>
031 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
032 * Lazenska 391, 76314 Zlin, Czech Republic<br>
033 * <br>
034 * This library is free software; you can redistribute it and/or
035 * modify it under the terms of the GNU Lesser General Public
036 * License as published by the Free Software Foundation; either
037 * version 2.1 of the License, or (at your option) any later version.
038 * <br><br>
039 * This library is distributed in the hope that it will be useful,
040 * but WITHOUT ANY WARRANTY; without even the implied warranty of
041 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
042 * Lesser General Public License for more details.
043 * <br><br>
044 * You should have received a copy of the GNU Lesser General Public
045 * License along with this library; if not, write to the Free Software
046 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
047 */
048 public class ExamHillClimbing implements NeighbourSelection, SolutionListener {
049 private NeighbourSelection[] iNeighbours = null;
050 private int iMaxIdleIters = 25000;
051 private int iLastImprovingIter = 0;
052 private double iBestValue = 0;
053 private int iIter = 0;
054 private Progress iProgress = null;
055 private boolean iActive;
056 private String iName = "Hill climbing";
057
058 /**
059 * Constructor
060 * @param properties problem properties (use HillClimber.MaxIdle to set maximum number of idle iterations)
061 */
062 public ExamHillClimbing(DataProperties properties) {
063 this(properties, "Hill Climbing");
064 }
065
066 /**
067 * Constructor
068 * @param properties problem properties (use HillClimber.MaxIdle to set maximum number of idle iterations)
069 */
070 public ExamHillClimbing(DataProperties properties, String name) {
071 iMaxIdleIters = properties.getPropertyInt("HillClimber.MaxIdle", iMaxIdleIters);
072 iNeighbours = new NeighbourSelection[] {
073 new ExamRandomMove(properties),
074 new ExamRoomMove(properties),
075 new ExamTimeMove(properties)
076 };
077 iName = name;
078 }
079
080 /**
081 * Initialization
082 */
083 public void init(Solver solver) {
084 solver.currentSolution().addSolutionListener(this);
085 for (int i=0;i<iNeighbours.length;i++)
086 iNeighbours[i].init(solver);
087 solver.setUpdateProgress(false);
088 iProgress = Progress.getInstance(solver.currentSolution().getModel());
089 iActive = false;
090 }
091
092 /**
093 * Select one of the given neighbourhoods randomly, select neighbour, return it if
094 * its value is below or equal to zero (continue with the next selection otherwise).
095 * Return null when the given number of idle iterations is reached.
096 */
097 public Neighbour selectNeighbour(Solution solution) {
098 if (!iActive) {
099 iProgress.setPhase(iName+"...");
100 iActive = true;
101 }
102 while (true) {
103 iIter ++;
104 iProgress.setProgress(Math.round(100.0*(iIter-iLastImprovingIter)/iMaxIdleIters));
105 if (iIter-iLastImprovingIter>=iMaxIdleIters) break;
106 NeighbourSelection ns = iNeighbours[ToolBox.random(iNeighbours.length)];
107 Neighbour n = ns.selectNeighbour(solution);
108 if (n!=null && n.value()<=0) return n;
109 }
110 iIter = 0; iLastImprovingIter = 0;
111 iActive=false;
112 return null;
113 }
114
115 /**
116 * Memorize the iteration when the last best solution was found.
117 */
118 public void bestSaved(Solution solution) {
119 if (Math.abs(iBestValue-solution.getBestValue())>=1.0) {
120 iLastImprovingIter = iIter;
121 iBestValue = solution.getBestValue();
122 }
123 }
124 public void solutionUpdated(Solution solution) {}
125 public void getInfo(Solution solution, java.util.Dictionary info) {}
126 public void getInfo(Solution solution, java.util.Dictionary info, java.util.Vector variables) {}
127 public void bestCleared(Solution solution) {}
128 public void bestRestored(Solution solution){} }