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    }