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