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