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.ExamTimeMove;
012    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
013    import net.sf.cpsolver.ifs.model.Neighbour;
014    import net.sf.cpsolver.ifs.solution.Solution;
015    import net.sf.cpsolver.ifs.solution.SolutionListener;
016    import net.sf.cpsolver.ifs.solver.Solver;
017    import net.sf.cpsolver.ifs.util.DataProperties;
018    import net.sf.cpsolver.ifs.util.JProf;
019    import net.sf.cpsolver.ifs.util.Progress;
020    import net.sf.cpsolver.ifs.util.ToolBox;
021    
022    import org.apache.log4j.Logger;
023    
024    /**
025     * Greate deluge. In each iteration, one of the following three neighbourhoods
026     * is selected first
027     * <ul>
028     * <li>random move ({@link ExamRandomMove})
029     * <li>period swap ({@link ExamTimeMove})
030     * <li>room swap ({@link ExamRoomMove})
031     * </ul>
032     * , then a neighbour is generated and it is accepted if the value of the new
033     * solution is below certain bound. This bound is initialized to the
034     * GreatDeluge.UpperBoundRate &times; value of the best solution ever found.
035     * After each iteration, the bound is decreased by GreatDeluge.CoolRate (new
036     * bound equals to old bound &times; GreatDeluge.CoolRate). If the bound gets
037     * bellow GreatDeluge.LowerBoundRate &times; value of the best solution ever
038     * found, it is changed back to GreatDeluge.UpperBoundRate &times; value of the
039     * best solution ever found.
040     * 
041     * If there was no improvement found between the bounds, the new bounds are
042     * changed to GreatDeluge.UpperBoundRate^2 and GreatDeluge.LowerBoundRate^2,
043     * GreatDeluge.UpperBoundRate^3 and GreatDeluge.LowerBoundRate^3, etc. till
044     * there is an improvement found. <br>
045     * <br>
046     * 
047     * @version ExamTT 1.2 (Examination Timetabling)<br>
048     *          Copyright (C) 2008 - 2010 Tomas Muller<br>
049     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
050     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
051     * <br>
052     *          This library is free software; you can redistribute it and/or modify
053     *          it under the terms of the GNU Lesser General Public License as
054     *          published by the Free Software Foundation; either version 3 of the
055     *          License, or (at your option) any later version. <br>
056     * <br>
057     *          This library is distributed in the hope that it will be useful, but
058     *          WITHOUT ANY WARRANTY; without even the implied warranty of
059     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
060     *          Lesser General Public License for more details. <br>
061     * <br>
062     *          You should have received a copy of the GNU Lesser General Public
063     *          License along with this library; if not see
064     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
065     */
066    public class ExamGreatDeluge implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement> {
067        private static Logger sLog = Logger.getLogger(ExamGreatDeluge.class);
068        private static DecimalFormat sDF2 = new DecimalFormat("0.00");
069        private static DecimalFormat sDF5 = new DecimalFormat("0.00000");
070        private double iBound = 0.0;
071        private double iCoolRate = 0.99999995;
072        private long iIter;
073        private double iUpperBound;
074        private double iUpperBoundRate = 1.05;
075        private double iLowerBoundRate = 0.95;
076        private int iMoves = 0;
077        private int iAcceptedMoves = 0;
078        private int iNrIdle = 0;
079        private long iT0 = -1;
080        private long iLastImprovingIter = 0;
081        private double iBestValue = 0;
082        private Progress iProgress = null;
083    
084        private NeighbourSelection<Exam, ExamPlacement>[] iNeighbours = null;
085    
086        /**
087         * Constructor. Following problem properties are considered:
088         * <ul>
089         * <li>GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995)
090         * <li>GreatDeluge.UpperBoundRate ... bound upper bound relative to best
091         * solution ever found (default 1.05)
092         * <li>GreatDeluge.LowerBoundRate ... bound lower bound relative to best
093         * solution ever found (default 0.95)
094         * </ul>
095         * 
096         * @param properties
097         *            problem properties
098         */
099        @SuppressWarnings("unchecked")
100        public ExamGreatDeluge(DataProperties properties) {
101            iCoolRate = properties.getPropertyDouble("GreatDeluge.CoolRate", iCoolRate);
102            iUpperBoundRate = properties.getPropertyDouble("GreatDeluge.UpperBoundRate", iUpperBoundRate);
103            iLowerBoundRate = properties.getPropertyDouble("GreatDeluge.LowerBoundRate", iLowerBoundRate);
104            iNeighbours = new NeighbourSelection[] { new ExamRandomMove(properties), new ExamRoomMove(properties),
105                    new ExamTimeMove(properties) };
106        }
107    
108        /** Initialization */
109        @Override
110        public void init(Solver<Exam, ExamPlacement> solver) {
111            iIter = -1;
112            solver.currentSolution().addSolutionListener(this);
113            for (int i = 0; i < iNeighbours.length; i++)
114                iNeighbours[i].init(solver);
115            solver.setUpdateProgress(false);
116            iProgress = Progress.getInstance(solver.currentSolution().getModel());
117        }
118    
119        /** Print some information */
120        protected void info(Solution<Exam, ExamPlacement> solution) {
121            sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
122                    + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
123            sLog.info("Bound is " + sDF2.format(iBound) + ", " + "best value is " + sDF2.format(solution.getBestValue())
124                    + " (" + sDF2.format(100.0 * iBound / solution.getBestValue()) + "%), " + "current value is "
125                    + sDF2.format(solution.getModel().getTotalValue()) + " ("
126                    + sDF2.format(100.0 * iBound / solution.getModel().getTotalValue()) + "%), " + "#idle=" + iNrIdle
127                    + ", " + "Pacc=" + sDF5.format(100.0 * iAcceptedMoves / iMoves) + "%");
128            iAcceptedMoves = iMoves = 0;
129        }
130    
131        /**
132         * Generate neighbour -- select neighbourhood randomly, select neighbour
133         */
134        public Neighbour<Exam, ExamPlacement> genMove(Solution<Exam, ExamPlacement> solution) {
135            while (true) {
136                incIter(solution);
137                NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours[ToolBox.random(iNeighbours.length)];
138                Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
139                if (n != null)
140                    return n;
141            }
142        }
143    
144        /** Accept neighbour */
145        protected boolean accept(Solution<Exam, ExamPlacement> solution, Neighbour<Exam, ExamPlacement> neighbour) {
146            return (neighbour.value() <= 0 || solution.getModel().getTotalValue() + neighbour.value() <= iBound);
147        }
148    
149        /** Increment iteration count, update bound */
150        protected void incIter(Solution<Exam, ExamPlacement> solution) {
151            if (iIter < 0) {
152                iIter = 0;
153                iLastImprovingIter = 0;
154                iT0 = JProf.currentTimeMillis();
155                iBound = (solution.getBestValue() > 0.0 ? iUpperBoundRate * solution.getBestValue() : solution
156                        .getBestValue()
157                        / iUpperBoundRate);
158                iUpperBound = iBound;
159                iNrIdle = 0;
160                iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]...");
161            } else {
162                iIter++;
163                if (solution.getBestValue() >= 0.0)
164                    iBound *= iCoolRate;
165                else
166                    iBound /= iCoolRate;
167            }
168            if (iIter % 100000 == 0) {
169                info(solution);
170            }
171            double lowerBound = (solution.getBestValue() >= 0.0 ? Math.pow(iLowerBoundRate, 1 + iNrIdle)
172                    * solution.getBestValue() : solution.getBestValue() / Math.pow(iLowerBoundRate, 1 + iNrIdle));
173            if (iBound < lowerBound) {
174                iNrIdle++;
175                sLog.info(" -<[" + iNrIdle + "]>- ");
176                iBound = Math.max(solution.getBestValue() + 2.0, (solution.getBestValue() >= 0.0 ? Math.pow(
177                        iUpperBoundRate, iNrIdle)
178                        * solution.getBestValue() : solution.getBestValue() / Math.pow(iUpperBoundRate, iNrIdle)));
179                iUpperBound = iBound;
180                iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]...");
181            }
182            iProgress.setProgress(100 - Math.round(100.0 * (iBound - lowerBound) / (iUpperBound - lowerBound)));
183        }
184    
185        /**
186         * A neighbour is generated randomly untill an acceptable one is found.
187         */
188        @Override
189        public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
190            Neighbour<Exam, ExamPlacement> neighbour = null;
191            while ((neighbour = genMove(solution)) != null) {
192                iMoves++;
193                if (accept(solution, neighbour)) {
194                    iAcceptedMoves++;
195                    break;
196                }
197            }
198            return (neighbour == null ? null : neighbour);
199        }
200    
201        /** Update last improving iteration count */
202        @Override
203        public void bestSaved(Solution<Exam, ExamPlacement> solution) {
204            if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) {
205                iLastImprovingIter = iIter;
206                iNrIdle = 0;
207                iBestValue = solution.getBestValue();
208            }
209        }
210    
211        @Override
212        public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
213        }
214    
215        @Override
216        public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
217        }
218    
219        @Override
220        public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
221        }
222    
223        @Override
224        public void bestCleared(Solution<Exam, ExamPlacement> solution) {
225        }
226    
227        @Override
228        public void bestRestored(Solution<Exam, ExamPlacement> solution) {
229        }
230    
231    }