001 package net.sf.cpsolver.exam.heuristics;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.List;
006 import java.util.Map;
007
008 import org.apache.log4j.Logger;
009
010 import net.sf.cpsolver.exam.model.Exam;
011 import net.sf.cpsolver.exam.model.ExamPlacement;
012 import net.sf.cpsolver.exam.neighbours.ExamRandomMove;
013 import net.sf.cpsolver.exam.neighbours.ExamRoomMove;
014 import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour;
015 import net.sf.cpsolver.exam.neighbours.ExamTimeMove;
016 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
017 import net.sf.cpsolver.ifs.model.LazyNeighbour;
018 import net.sf.cpsolver.ifs.model.Neighbour;
019 import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
020 import net.sf.cpsolver.ifs.solution.Solution;
021 import net.sf.cpsolver.ifs.solution.SolutionListener;
022 import net.sf.cpsolver.ifs.solver.Solver;
023 import net.sf.cpsolver.ifs.util.DataProperties;
024 import net.sf.cpsolver.ifs.util.Progress;
025 import net.sf.cpsolver.ifs.util.ToolBox;
026
027 /**
028 * Hill climber. In each iteration, one of the following three neighbourhoods is
029 * selected first
030 * <ul>
031 * <li>random move ({@link ExamRandomMove})
032 * <li>period swap ({@link ExamTimeMove})
033 * <li>room swap ({@link ExamRoomMove})
034 * </ul>
035 * , then a neighbour is generated and it is accepted if its value
036 * {@link ExamSimpleNeighbour#value()} is below or equal to zero. The search is
037 * stopped after a given amount of idle iterations ( can be defined by problem
038 * property HillClimber.MaxIdle). <br>
039 * <br>
040 *
041 * @version ExamTT 1.2 (Examination Timetabling)<br>
042 * Copyright (C) 2008 - 2010 Tomas Muller<br>
043 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
044 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
045 * <br>
046 * This library is free software; you can redistribute it and/or modify
047 * it under the terms of the GNU Lesser General Public License as
048 * published by the Free Software Foundation; either version 3 of the
049 * License, or (at your option) any later version. <br>
050 * <br>
051 * This library is distributed in the hope that it will be useful, but
052 * WITHOUT ANY WARRANTY; without even the implied warranty of
053 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
054 * Lesser General Public License for more details. <br>
055 * <br>
056 * You should have received a copy of the GNU Lesser General Public
057 * License along with this library; if not see
058 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
059 */
060 public class ExamHillClimbing implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> {
061 private static Logger sLog = Logger.getLogger(ExamHillClimbing.class);
062 private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null;
063 private int iMaxIdleIters = 25000;
064 private int iLastImprovingIter = 0;
065 private double iBestValue = 0;
066 private int iIter = 0;
067 private Progress iProgress = null;
068 private boolean iActive;
069 private String iName = "Hill climbing";
070
071 /**
072 * Constructor
073 *
074 * @param properties
075 * problem properties (use HillClimber.MaxIdle to set maximum
076 * number of idle iterations)
077 */
078 public ExamHillClimbing(DataProperties properties) {
079 this(properties, "Hill Climbing");
080 }
081
082 /**
083 * Constructor
084 *
085 * @param properties
086 * problem properties (use HillClimber.MaxIdle to set maximum
087 * number of idle iterations)
088 */
089 @SuppressWarnings("unchecked")
090 public ExamHillClimbing(DataProperties properties, String name) {
091 iMaxIdleIters = properties.getPropertyInt("HillClimber.MaxIdle", iMaxIdleIters);
092 String neighbours = properties.getProperty("HillClimber.Neighbours",
093 ExamRandomMove.class.getName() + ";" +
094 ExamRoomMove.class.getName() + ";" +
095 ExamTimeMove.class.getName());
096 neighbours += ";" + properties.getProperty("HillClimber.AdditionalNeighbours", "");
097 iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>();
098 for (String neighbour: neighbours.split("\\;")) {
099 if (neighbour == null || neighbour.isEmpty()) continue;
100 try {
101 Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour);
102 iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties));
103 } catch (Exception e) {
104 sLog.error("Unable to use " + neighbour + ": " + e.getMessage());
105 }
106 }
107 iName = name;
108 }
109
110 /**
111 * Initialization
112 */
113 @Override
114 public void init(Solver<Exam, ExamPlacement> solver) {
115 solver.currentSolution().addSolutionListener(this);
116 for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours)
117 neighbour.init(solver);
118 solver.setUpdateProgress(false);
119 iProgress = Progress.getInstance(solver.currentSolution().getModel());
120 iActive = false;
121 }
122
123 /**
124 * Select one of the given neighbourhoods randomly, select neighbour, return
125 * it if its value is below or equal to zero (continue with the next
126 * selection otherwise). Return null when the given number of idle
127 * iterations is reached.
128 */
129 @Override
130 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
131 if (!iActive) {
132 iProgress.setPhase(iName + "...");
133 iActive = true;
134 }
135 while (true) {
136 iIter++;
137 iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters));
138 if (iIter - iLastImprovingIter >= iMaxIdleIters)
139 break;
140 NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size()));
141 Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
142 if (n != null) {
143 if (n instanceof LazyNeighbour) {
144 ((LazyNeighbour<Exam,ExamPlacement>)n).setAcceptanceCriterion(this);
145 return n;
146 } else if (n.value() <= 0.0) return n;
147 }
148 }
149 iIter = 0;
150 iLastImprovingIter = 0;
151 iActive = false;
152 return null;
153 }
154
155 /**
156 * Memorize the iteration when the last best solution was found.
157 */
158 @Override
159 public void bestSaved(Solution<Exam, ExamPlacement> solution) {
160 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) {
161 iLastImprovingIter = iIter;
162 iBestValue = solution.getBestValue();
163 }
164 }
165
166 @Override
167 public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
168 }
169
170 @Override
171 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
172 }
173
174 @Override
175 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
176 }
177
178 @Override
179 public void bestCleared(Solution<Exam, ExamPlacement> solution) {
180 }
181
182 @Override
183 public void bestRestored(Solution<Exam, ExamPlacement> solution) {
184 }
185
186 /** Accept lazy neighbour */
187 @Override
188 public boolean accept(LazyNeighbour<Exam, ExamPlacement> neighbour, double value) {
189 return value <= 0.0;
190 }
191 }