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