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