001    package net.sf.cpsolver.exam.heuristics;
002    
003    import java.util.Collection;
004    import java.util.Map;
005    
006    import net.sf.cpsolver.exam.model.Exam;
007    import net.sf.cpsolver.exam.model.ExamPlacement;
008    import net.sf.cpsolver.exam.neighbours.ExamRandomMove;
009    import net.sf.cpsolver.exam.neighbours.ExamRoomMove;
010    import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour;
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.Progress;
019    import net.sf.cpsolver.ifs.util.ToolBox;
020    
021    /**
022     * Hill climber. In each iteration, one of the following three neighbourhoods is
023     * selected first
024     * <ul>
025     * <li>random move ({@link ExamRandomMove})
026     * <li>period swap ({@link ExamTimeMove})
027     * <li>room swap ({@link ExamRoomMove})
028     * </ul>
029     * , then a neighbour is generated and it is accepted if its value
030     * {@link ExamSimpleNeighbour#value()} is below or equal to zero. The search is
031     * stopped after a given amount of idle iterations ( can be defined by problem
032     * property HillClimber.MaxIdle). <br>
033     * <br>
034     * 
035     * @version ExamTT 1.2 (Examination Timetabling)<br>
036     *          Copyright (C) 2008 - 2010 Tomas Muller<br>
037     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
038     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
039     * <br>
040     *          This library is free software; you can redistribute it and/or modify
041     *          it under the terms of the GNU Lesser General Public License as
042     *          published by the Free Software Foundation; either version 3 of the
043     *          License, or (at your option) any later version. <br>
044     * <br>
045     *          This library is distributed in the hope that it will be useful, but
046     *          WITHOUT ANY WARRANTY; without even the implied warranty of
047     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
048     *          Lesser General Public License for more details. <br>
049     * <br>
050     *          You should have received a copy of the GNU Lesser General Public
051     *          License along with this library; if not see
052     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
053     */
054    public class ExamHillClimbing implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement> {
055        private NeighbourSelection<Exam, ExamPlacement>[] iNeighbours = null;
056        private int iMaxIdleIters = 25000;
057        private int iLastImprovingIter = 0;
058        private double iBestValue = 0;
059        private int iIter = 0;
060        private Progress iProgress = null;
061        private boolean iActive;
062        private String iName = "Hill climbing";
063    
064        /**
065         * Constructor
066         * 
067         * @param properties
068         *            problem properties (use HillClimber.MaxIdle to set maximum
069         *            number of idle iterations)
070         */
071        public ExamHillClimbing(DataProperties properties) {
072            this(properties, "Hill Climbing");
073        }
074    
075        /**
076         * Constructor
077         * 
078         * @param properties
079         *            problem properties (use HillClimber.MaxIdle to set maximum
080         *            number of idle iterations)
081         */
082        @SuppressWarnings("unchecked")
083        public ExamHillClimbing(DataProperties properties, String name) {
084            iMaxIdleIters = properties.getPropertyInt("HillClimber.MaxIdle", iMaxIdleIters);
085            iNeighbours = new NeighbourSelection[] { new ExamRandomMove(properties), new ExamRoomMove(properties),
086                    new ExamTimeMove(properties) };
087            iName = name;
088        }
089    
090        /**
091         * Initialization
092         */
093        @Override
094        public void init(Solver<Exam, ExamPlacement> solver) {
095            solver.currentSolution().addSolutionListener(this);
096            for (int i = 0; i < iNeighbours.length; i++)
097                iNeighbours[i].init(solver);
098            solver.setUpdateProgress(false);
099            iProgress = Progress.getInstance(solver.currentSolution().getModel());
100            iActive = false;
101        }
102    
103        /**
104         * Select one of the given neighbourhoods randomly, select neighbour, return
105         * it if its value is below or equal to zero (continue with the next
106         * selection otherwise). Return null when the given number of idle
107         * iterations is reached.
108         */
109        @Override
110        public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
111            if (!iActive) {
112                iProgress.setPhase(iName + "...");
113                iActive = true;
114            }
115            while (true) {
116                iIter++;
117                iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters));
118                if (iIter - iLastImprovingIter >= iMaxIdleIters)
119                    break;
120                NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours[ToolBox.random(iNeighbours.length)];
121                Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
122                if (n != null && n.value() <= 0)
123                    return n;
124            }
125            iIter = 0;
126            iLastImprovingIter = 0;
127            iActive = false;
128            return null;
129        }
130    
131        /**
132         * Memorize the iteration when the last best solution was found.
133         */
134        @Override
135        public void bestSaved(Solution<Exam, ExamPlacement> solution) {
136            if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) {
137                iLastImprovingIter = iIter;
138                iBestValue = solution.getBestValue();
139            }
140        }
141    
142        @Override
143        public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
144        }
145    
146        @Override
147        public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
148        }
149    
150        @Override
151        public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
152        }
153    
154        @Override
155        public void bestCleared(Solution<Exam, ExamPlacement> solution) {
156        }
157    
158        @Override
159        public void bestRestored(Solution<Exam, ExamPlacement> solution) {
160        }
161    }