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