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