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