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