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