    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}