001package net.sf.cpsolver.exam.heuristics;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.List;
006import java.util.Map;
007
008import org.apache.log4j.Logger;
009
010import net.sf.cpsolver.exam.model.Exam;
011import net.sf.cpsolver.exam.model.ExamPlacement;
012import net.sf.cpsolver.exam.neighbours.ExamRandomMove;
013import net.sf.cpsolver.exam.neighbours.ExamRoomMove;
014import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour;
015import net.sf.cpsolver.exam.neighbours.ExamTimeMove;
016import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
017import net.sf.cpsolver.ifs.model.LazyNeighbour;
018import net.sf.cpsolver.ifs.model.Neighbour;
019import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
020import net.sf.cpsolver.ifs.solution.Solution;
021import net.sf.cpsolver.ifs.solution.SolutionListener;
022import net.sf.cpsolver.ifs.solver.Solver;
023import net.sf.cpsolver.ifs.util.DataProperties;
024import net.sf.cpsolver.ifs.util.Progress;
025import 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 Tomáš Müller<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 */
060public 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}