    001package org.cpsolver.exam.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.List;
    006import java.util.Map;
    007
    008import org.apache.logging.log4j.Logger;
    009import org.cpsolver.exam.model.Exam;
    010import org.cpsolver.exam.model.ExamPlacement;
    011import org.cpsolver.exam.neighbours.ExamRandomMove;
    012import org.cpsolver.exam.neighbours.ExamRoomMove;
    013import org.cpsolver.exam.neighbours.ExamSimpleNeighbour;
    014import org.cpsolver.exam.neighbours.ExamTimeMove;
    015import org.cpsolver.ifs.assignment.Assignment;
    016import org.cpsolver.ifs.assignment.context.AssignmentContext;
    017import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
    018import org.cpsolver.ifs.heuristics.NeighbourSelection;
    019import org.cpsolver.ifs.model.LazyNeighbour;
    020import org.cpsolver.ifs.model.Model;
    021import org.cpsolver.ifs.model.Neighbour;
    022import org.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
    023import org.cpsolver.ifs.solution.Solution;
    024import org.cpsolver.ifs.solution.SolutionListener;
    025import org.cpsolver.ifs.solver.Solver;
    026import org.cpsolver.ifs.util.DataProperties;
    027import org.cpsolver.ifs.util.Progress;
    028import org.cpsolver.ifs.util.ToolBox;
    029
    030
    031/**
    032 * Hill climber. In each iteration, one of the following three neighbourhoods is
    033 * selected first
    034 * <ul>
    035 * <li>random move ({@link ExamRandomMove})
    036 * <li>period swap ({@link ExamTimeMove})
    037 * <li>room swap ({@link ExamRoomMove})
    038 * </ul>
    039 * , then a neighbour is generated and it is accepted if its value
    040 * {@link ExamSimpleNeighbour#value(Assignment)} is below or equal to zero. The search is
    041 * stopped after a given amount of idle iterations ( can be defined by problem
    042 * property HillClimber.MaxIdle). <br>
    043 * <br>
    044 *
    045 * @author  Tomáš Müller
    046 * @version ExamTT 1.3 (Examination Timetabling)<br>
    047 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
    048 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    049 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    050 * <br>
    051 *          This library is free software; you can redistribute it and/or modify
    052 *          it under the terms of the GNU Lesser General Public License as
    053 *          published by the Free Software Foundation; either version 3 of the
    054 *          License, or (at your option) any later version. <br>
    055 * <br>
    056 *          This library is distributed in the hope that it will be useful, but
    057 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    058 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    059 *          Lesser General Public License for more details. <br>
    060 * <br>
    061 *          You should have received a copy of the GNU Lesser General Public
    062 *          License along with this library; if not see
    063 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    064 */
    065@Deprecated
    066public class ExamHillClimbing extends NeighbourSelectionWithContext<Exam, ExamPlacement, ExamHillClimbing.Context> implements SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> {
    067    private static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(ExamHillClimbing.class);
    068    private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null;
    069    private int iMaxIdleIters = 25000;
    070    private Progress iProgress = null;
    071    private String iName = "Hill climbing";
    072
    073    /**
    074     * Constructor
    075     *
    076     * @param properties
    077     *            problem properties (use HillClimber.MaxIdle to set maximum
    078     *            number of idle iterations)
    079     */
    080    public ExamHillClimbing(DataProperties properties) {
    081        this(properties, "Hill Climbing");
    082    }
    083
    084    /**
    085     * Constructor
    086     *
    087     * @param properties
    088     *            problem properties (use HillClimber.MaxIdle to set maximum
    089     *            number of idle iterations)
    090     * @param name solver search phase name
    091     */
    092    @SuppressWarnings("unchecked")
    093    public ExamHillClimbing(DataProperties properties, String name) {
    094        iMaxIdleIters = properties.getPropertyInt("HillClimber.MaxIdle", iMaxIdleIters);
    095        String neighbours = properties.getProperty("HillClimber.Neighbours",
    096                ExamRandomMove.class.getName() + ";" +
    097                ExamRoomMove.class.getName() + ";" +
    098                ExamTimeMove.class.getName());
    099        neighbours += ";" + properties.getProperty("HillClimber.AdditionalNeighbours", "");
    100        iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>();
    101        for (String neighbour: neighbours.split("\\;")) {
    102            if (neighbour == null || neighbour.isEmpty()) continue;
    103            try {
    104                Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour);
    105                iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties));
    106            } catch (Exception e) {
    107                sLog.error("Unable to use " + neighbour + ": " + e.getMessage());
    108            }
    109        }
    110        iName = name;
    111    }
    112
    113    /**
    114     * Initialization
    115     */
    116    @Override
    117    public void init(Solver<Exam, ExamPlacement> solver) {
    118        super.init(solver);
    119        solver.currentSolution().addSolutionListener(this);
    120        for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours)
    121            neighbour.init(solver);
    122        solver.setUpdateProgress(false);
    123        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    124        getContext(solver.currentSolution().getAssignment()).reset();
    125    }
    126
    127    /**
    128     * Select one of the given neighbourhoods randomly, select neighbour, return
    129     * it if its value is below or equal to zero (continue with the next
    130     * selection otherwise). Return null when the given number of idle
    131     * iterations is reached.
    132     */
    133    @Override
    134    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
    135        Context context = getContext(solution.getAssignment());
    136        context.activateIfNeeded();
    137        while (true) {
    138            if (context.incIter(solution)) break;
    139            NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size()));
    140            Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
    141            if (n != null) {
    142                if (n instanceof LazyNeighbour) {
    143                    ((LazyNeighbour<Exam,ExamPlacement>)n).setAcceptanceCriterion(this);
    144                    return n;
    145                } else if (n.value(solution.getAssignment()) <= 0.0) return n;
    146            }
    147        }
    148        context.reset();
    149        return null;
    150    }
    151
    152    /**
    153     * Memorize the iteration when the last best solution was found.
    154     */
    155    @Override
    156    public void bestSaved(Solution<Exam, ExamPlacement> solution) {
    157        getContext(solution.getAssignment()).bestSaved(solution.getModel());
    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
    180    /** Accept lazy neighbour */
    181    @Override
    182    public boolean accept(Assignment<Exam, ExamPlacement> assignment, LazyNeighbour<Exam, ExamPlacement> neighbour, double value) {
    183        return value <= 0.0;
    184    }
    185
    186    @Override
    187    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
    188        return new Context();
    189    }
    190
    191    public class Context implements AssignmentContext {
    192        private int iLastImprovingIter = 0;
    193        private double iBestValue = 0;
    194        private int iIter = 0;
    195        private boolean iActive;
    196
    197        protected void reset() {
    198            iIter = 0;
    199            iLastImprovingIter = 0;
    200            iActive = false;
    201        }
    202
    203        protected void activateIfNeeded() {
    204            if (!iActive) {
    205                iProgress.setPhase(iName + "...");
    206                iActive = true;
    207            }
    208        }
    209
    210        protected boolean incIter(Solution<Exam, ExamPlacement> solution) {
    211            iIter++;
    212            iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters));
    213            if (iIter - iLastImprovingIter >= iMaxIdleIters) return true;
    214            return false;
    215        }
    216
    217        protected void bestSaved(Model<Exam, ExamPlacement> model) {
    218            if (Math.abs(iBestValue - model.getBestValue()) >= 1.0) {
    219                iLastImprovingIter = iIter;
    220                iBestValue = model.getBestValue();
    221            }
    222        }
    223    }
    224}