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