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    }