001package net.sf.cpsolver.exam.heuristics; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.List; 007import java.util.Map; 008 009import net.sf.cpsolver.exam.model.Exam; 010import net.sf.cpsolver.exam.model.ExamPlacement; 011import net.sf.cpsolver.exam.neighbours.ExamRandomMove; 012import net.sf.cpsolver.exam.neighbours.ExamRoomMove; 013import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour; 014import net.sf.cpsolver.exam.neighbours.ExamTimeMove; 015import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 016import net.sf.cpsolver.ifs.model.LazyNeighbour; 017import net.sf.cpsolver.ifs.model.Neighbour; 018import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion; 019import net.sf.cpsolver.ifs.solution.Solution; 020import net.sf.cpsolver.ifs.solution.SolutionListener; 021import net.sf.cpsolver.ifs.solver.Solver; 022import net.sf.cpsolver.ifs.util.DataProperties; 023import net.sf.cpsolver.ifs.util.JProf; 024import net.sf.cpsolver.ifs.util.Progress; 025import net.sf.cpsolver.ifs.util.ToolBox; 026 027import 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 Tomáš Müller<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 */ 081public 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}