001 package net.sf.cpsolver.exam.heuristics;
002
003 import java.text.DecimalFormat;
004 import java.util.ArrayList;
005 import java.util.Collection;
006 import java.util.List;
007 import java.util.Map;
008
009 import net.sf.cpsolver.exam.model.Exam;
010 import net.sf.cpsolver.exam.model.ExamPlacement;
011 import net.sf.cpsolver.exam.neighbours.ExamRandomMove;
012 import net.sf.cpsolver.exam.neighbours.ExamRoomMove;
013 import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour;
014 import net.sf.cpsolver.exam.neighbours.ExamTimeMove;
015 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
016 import net.sf.cpsolver.ifs.model.LazyNeighbour;
017 import net.sf.cpsolver.ifs.model.Neighbour;
018 import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
019 import net.sf.cpsolver.ifs.solution.Solution;
020 import net.sf.cpsolver.ifs.solution.SolutionListener;
021 import net.sf.cpsolver.ifs.solver.Solver;
022 import net.sf.cpsolver.ifs.util.DataProperties;
023 import net.sf.cpsolver.ifs.util.JProf;
024 import net.sf.cpsolver.ifs.util.Progress;
025 import net.sf.cpsolver.ifs.util.ToolBox;
026
027 import org.apache.log4j.Logger;
028
029 /**
030 * Simulated annealing. In each iteration, one of the following three
031 * neighbourhoods is selected first
032 * <ul>
033 * <li>random move ({@link ExamRandomMove})
034 * <li>period swap ({@link ExamTimeMove})
035 * <li>room swap ({@link ExamRoomMove})
036 * </ul>
037 * , then a neighbour is generated and it is accepted with probability
038 * {@link ExamSimulatedAnnealing#prob(double)}. The search is guided by the
039 * temperature, which starts at <i>SimulatedAnnealing.InitialTemperature</i>.
040 * After each <i>SimulatedAnnealing.TemperatureLength</i> iterations, the
041 * temperature is reduced by <i>SimulatedAnnealing.CoolingRate</i>. If there was
042 * no improvement in the past <i>SimulatedAnnealing.ReheatLengthCoef *
043 * SimulatedAnnealing.TemperatureLength</i> iterations, the temperature is
044 * increased by <i>SimulatedAnnealing.ReheatRate</i>. If there was no
045 * improvement in the past <i>SimulatedAnnealing.RestoreBestLengthCoef *
046 * SimulatedAnnealing.TemperatureLength</i> iterations, the best ever found
047 * solution is restored. <br>
048 * <br>
049 * If <i>SimulatedAnnealing.StochasticHC</i> is true, the acceptance probability
050 * is computed using stochastic hill climbing criterion, i.e.,
051 * <code>1.0 / (1.0 + Math.exp(value/temperature))</code>, otherwise it is
052 * cumputed using simlated annealing criterion, i.e.,
053 * <code>(value<=0.0?1.0:Math.exp(-value/temperature))</code>. If
054 * <i>SimulatedAnnealing.RelativeAcceptance</i> neighbour value
055 * {@link ExamSimpleNeighbour#value()} is taken as the value of the selected
056 * neighbour (difference between the new and the current solution, if the
057 * neighbour is accepted), otherwise the value is computed as the difference
058 * between the value of the current solution if the neighbour is accepted and
059 * the best ever found solution. <br>
060 * <br>
061 *
062 * @version ExamTT 1.2 (Examination Timetabling)<br>
063 * Copyright (C) 2008 - 2010 Tomas Muller<br>
064 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
065 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
066 * <br>
067 * This library is free software; you can redistribute it and/or modify
068 * it under the terms of the GNU Lesser General Public License as
069 * published by the Free Software Foundation; either version 3 of the
070 * License, or (at your option) any later version. <br>
071 * <br>
072 * This library is distributed in the hope that it will be useful, but
073 * WITHOUT ANY WARRANTY; without even the implied warranty of
074 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
075 * Lesser General Public License for more details. <br>
076 * <br>
077 * You should have received a copy of the GNU Lesser General Public
078 * License along with this library; if not see
079 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
080 */
081 public class ExamSimulatedAnnealing implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> {
082 private static Logger sLog = Logger.getLogger(ExamSimulatedAnnealing.class);
083 private static DecimalFormat sDF2 = new DecimalFormat("0.00");
084 private static DecimalFormat sDF5 = new DecimalFormat("0.00000");
085 private static DecimalFormat sDF10 = new DecimalFormat("0.0000000000");
086 private double iInitialTemperature = 1.5;
087 private double iCoolingRate = 0.95;
088 private double iReheatRate = -1;
089 private long iTemperatureLength = 250000;
090 private long iReheatLength = 0;
091 private long iRestoreBestLength = 0;
092 private double iTemperature = 0.0;
093 private double iReheatLengthCoef = 5.0;
094 private double iRestoreBestLengthCoef = -1;
095 private long iIter = 0;
096 private long iLastImprovingIter = 0;
097 private long iLastReheatIter = 0;
098 private long iLastCoolingIter = 0;
099 private int iAcceptIter[] = new int[] { 0, 0, 0 };
100 private boolean iStochasticHC = false;
101 private int iMoves = 0;
102 private double iAbsValue = 0;
103 private long iT0 = -1;
104 private double iBestValue = 0;
105 private Progress iProgress = null;
106 private boolean iActive;
107
108 private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null;
109
110 private boolean iRelativeAcceptance = true;
111
112 /**
113 * Constructor. Following problem properties are considered:
114 * <ul>
115 * <li>SimulatedAnnealing.InitialTemperature ... initial temperature
116 * (default 1.5)
117 * <li>SimulatedAnnealing.TemperatureLength ... temperature length (number
118 * of iterations between temperature decrements, default 25000)
119 * <li>SimulatedAnnealing.CoolingRate ... temperature cooling rate (default
120 * 0.95)
121 * <li>SimulatedAnnealing.ReheatLengthCoef ... temperature re-heat length
122 * coefficient (multiple of temperature length, default 5)
123 * <li>SimulatedAnnealing.ReheatRate ... temperature re-heating rate
124 * (default (1/coolingRate)^(reheatLengthCoef*1.7))
125 * <li>SimulatedAnnealing.RestoreBestLengthCoef ... restore best length
126 * coefficient (multiple of re-heat length, default reheatLengthCoef^2)
127 * <li>SimulatedAnnealing.StochasticHC ... true for stochastic search
128 * acceptance criterion, false for simulated annealing acceptance (default
129 * false)
130 * <li>SimulatedAnnealing.RelativeAcceptance ... true for relative
131 * acceptance (different between the new and the current solutions, if the
132 * neighbour is accepted), false for absolute acceptance (difference between
133 * the new and the best solutions, if the neighbour is accepted)
134 * </ul>
135 *
136 * @param properties
137 * problem properties
138 */
139 @SuppressWarnings("unchecked")
140 public ExamSimulatedAnnealing(DataProperties properties) {
141 iInitialTemperature = properties
142 .getPropertyDouble("SimulatedAnnealing.InitialTemperature", iInitialTemperature);
143 iReheatRate = properties.getPropertyDouble("SimulatedAnnealing.ReheatRate", iReheatRate);
144 iCoolingRate = properties.getPropertyDouble("SimulatedAnnealing.CoolingRate", iCoolingRate);
145 iRelativeAcceptance = properties.getPropertyBoolean("SimulatedAnnealing.RelativeAcceptance",
146 iRelativeAcceptance);
147 iStochasticHC = properties.getPropertyBoolean("SimulatedAnnealing.StochasticHC", iStochasticHC);
148 iTemperatureLength = properties.getPropertyLong("SimulatedAnnealing.TemperatureLength", iTemperatureLength);
149 iReheatLengthCoef = properties.getPropertyDouble("SimulatedAnnealing.ReheatLengthCoef", iReheatLengthCoef);
150 iRestoreBestLengthCoef = properties.getPropertyDouble("SimulatedAnnealing.RestoreBestLengthCoef",
151 iRestoreBestLengthCoef);
152 if (iReheatRate < 0)
153 iReheatRate = Math.pow(1 / iCoolingRate, iReheatLengthCoef * 1.7);
154 if (iRestoreBestLengthCoef < 0)
155 iRestoreBestLengthCoef = iReheatLengthCoef * iReheatLengthCoef;
156 String neighbours = properties.getProperty("SimulatedAnnealing.Neighbours",
157 ExamRandomMove.class.getName() + ";" +
158 ExamRoomMove.class.getName() + ";" +
159 ExamTimeMove.class.getName());
160 neighbours += ";" + properties.getProperty("SimulatedAnnealing.AdditionalNeighbours", "");
161 iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>();
162 for (String neighbour: neighbours.split("\\;")) {
163 if (neighbour == null || neighbour.isEmpty()) continue;
164 try {
165 Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour);
166 iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties));
167 } catch (Exception e) {
168 sLog.error("Unable to use " + neighbour + ": " + e.getMessage());
169 }
170 }
171 }
172
173 /**
174 * Initialization
175 */
176 @Override
177 public void init(Solver<Exam, ExamPlacement> solver) {
178 iTemperature = iInitialTemperature;
179 iReheatLength = Math.round(iReheatLengthCoef * iTemperatureLength);
180 iRestoreBestLength = Math.round(iRestoreBestLengthCoef * iTemperatureLength);
181 solver.currentSolution().addSolutionListener(this);
182 for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours)
183 neighbour.init(solver);
184 solver.setUpdateProgress(false);
185 iProgress = Progress.getInstance(solver.currentSolution().getModel());
186 iActive = false;
187 }
188
189 /**
190 * Cool temperature
191 */
192 protected void cool(Solution<Exam, ExamPlacement> solution) {
193 iTemperature *= iCoolingRate;
194 sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
195 + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
196 sLog.info("Temperature decreased to " + sDF5.format(iTemperature) + " " + "(#moves=" + iMoves + ", rms(value)="
197 + sDF2.format(Math.sqrt(iAbsValue / iMoves)) + ", " + "accept=-"
198 + sDF2.format(100.0 * iAcceptIter[0] / iTemperatureLength) + "/"
199 + sDF2.format(100.0 * iAcceptIter[1] / iTemperatureLength) + "/+"
200 + sDF2.format(100.0 * iAcceptIter[2] / iTemperatureLength) + "%, "
201 + (prob(-1) < 1.0 ? "p(-1)=" + sDF2.format(100.0 * prob(-1)) + "%, " : "") + "p(+1)="
202 + sDF2.format(100.0 * prob(1)) + "%, " + "p(+10)=" + sDF5.format(100.0 * prob(10)) + "%)");
203 iLastCoolingIter = iIter;
204 iAcceptIter = new int[] { 0, 0, 0 };
205 iMoves = 0;
206 iAbsValue = 0;
207 }
208
209 /**
210 * Reheat temperature
211 */
212 protected void reheat(Solution<Exam, ExamPlacement> solution) {
213 iTemperature *= iReheatRate;
214 sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
215 + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
216 sLog.info("Temperature increased to " + sDF5.format(iTemperature) + " "
217 + (prob(-1) < 1.0 ? "p(-1)=" + sDF2.format(100.0 * prob(-1)) + "%, " : "") + "p(+1)="
218 + sDF2.format(100.0 * prob(1)) + "%, " + "p(+10)=" + sDF5.format(100.0 * prob(10)) + "%, " + "p(+100)="
219 + sDF10.format(100.0 * prob(100)) + "%)");
220 iLastReheatIter = iIter;
221 iProgress.setPhase("Simulated Annealing [" + sDF2.format(iTemperature) + "]...");
222 }
223
224 /**
225 * restore best ever found solution
226 */
227 protected void restoreBest(Solution<Exam, ExamPlacement> solution) {
228 sLog.info("Best restored");
229 iLastImprovingIter = iIter;
230 }
231
232 /**
233 * Generate neighbour -- select neighbourhood randomly, select neighbour
234 */
235 public Neighbour<Exam, ExamPlacement> genMove(Solution<Exam, ExamPlacement> solution) {
236 while (true) {
237 incIter(solution);
238 NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size()));
239 Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
240 if (n != null)
241 return n;
242 }
243 }
244
245 /**
246 * Neighbour acceptance probability
247 *
248 * @param value
249 * absolute or relative value of the proposed change (neighbour)
250 * @return probability of acceptance of a change (neighbour)
251 */
252 protected double prob(double value) {
253 if (iStochasticHC)
254 return 1.0 / (1.0 + Math.exp(value / iTemperature));
255 else
256 return (value <= 0.0 ? 1.0 : Math.exp(-value / iTemperature));
257 }
258
259 /**
260 * True if the given neighboir is to be be accepted
261 *
262 * @param solution
263 * current solution
264 * @param neighbour
265 * proposed move
266 * @return true if generated random number is below
267 * {@link ExamSimulatedAnnealing#prob(double)}
268 */
269 protected boolean accept(Solution<Exam, ExamPlacement> solution, Neighbour<Exam, ExamPlacement> neighbour) {
270 if (neighbour instanceof LazyNeighbour) {
271 ((LazyNeighbour<Exam, ExamPlacement>)neighbour).setAcceptanceCriterion(this);
272 return true;
273 }
274 double value = (iRelativeAcceptance ? neighbour.value() : solution.getModel().getTotalValue() + neighbour.value() - solution.getBestValue());
275 double prob = prob(value);
276 if (prob >= 1.0 || ToolBox.random() < prob) {
277 iAcceptIter[neighbour.value() < 0.0 ? 0 : neighbour.value() > 0.0 ? 2 : 1]++;
278 return true;
279 }
280 return false;
281 }
282
283 /** Accept lazy neighbour */
284 @Override
285 public boolean accept(LazyNeighbour<Exam, ExamPlacement> neighbour, double value) {
286 double prob = prob(value);
287 if (prob >= 1.0 || ToolBox.random() < prob) {
288 iAcceptIter[value < 0.0 ? 0 : value > 0.0 ? 2 : 1]++;
289 return true;
290 }
291 return false;
292 }
293
294 /**
295 * Increment iteration counter, cool/reheat/restoreBest if necessary
296 */
297 protected void incIter(Solution<Exam, ExamPlacement> solution) {
298 if (iT0 < 0)
299 iT0 = JProf.currentTimeMillis();
300 iIter++;
301 if (iIter > iLastImprovingIter + iRestoreBestLength)
302 restoreBest(solution);
303 if (iIter > Math.max(iLastReheatIter, iLastImprovingIter) + iReheatLength)
304 reheat(solution);
305 if (iIter > iLastCoolingIter + iTemperatureLength)
306 cool(solution);
307 iProgress.setProgress(Math.round(100.0 * (iIter - Math.max(iLastReheatIter, iLastImprovingIter))
308 / iReheatLength));
309 }
310
311 /**
312 * Select neighbour -- generate a move
313 * {@link ExamSimulatedAnnealing#genMove(Solution)} until an acceptable
314 * neighbour is found
315 * {@link ExamSimulatedAnnealing#accept(Solution, Neighbour)}, keep
316 * increasing iteration {@link ExamSimulatedAnnealing#incIter(Solution)}.
317 */
318 @Override
319 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
320 if (!iActive) {
321 iProgress.setPhase("Simulated Annealing [" + sDF2.format(iTemperature) + "]...");
322 iActive = true;
323 }
324 Neighbour<Exam, ExamPlacement> neighbour = null;
325 while ((neighbour = genMove(solution)) != null) {
326 iMoves++;
327 iAbsValue += neighbour.value() * neighbour.value();
328 if (accept(solution, neighbour))
329 break;
330 }
331 if (neighbour == null)
332 iActive = false;
333 return (neighbour == null ? null : neighbour);
334 }
335
336 /**
337 * Memorize the iteration when the last best solution was found.
338 */
339 @Override
340 public void bestSaved(Solution<Exam, ExamPlacement> solution) {
341 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) {
342 iLastImprovingIter = iIter;
343 iBestValue = solution.getBestValue();
344 }
345 iLastImprovingIter = iIter;
346 }
347
348 @Override
349 public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
350 }
351
352 @Override
353 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
354 }
355
356 @Override
357 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
358 }
359
360 @Override
361 public void bestCleared(Solution<Exam, ExamPlacement> solution) {
362 }
363
364 @Override
365 public void bestRestored(Solution<Exam, ExamPlacement> solution) {
366 }
367 }