    001package net.sf.cpsolver.exam.heuristics;
    002
    003import java.text.DecimalFormat;
    004import java.util.ArrayList;
    005import java.util.Collection;
    006import java.util.List;
    007import java.util.Map;
    008
    009import net.sf.cpsolver.exam.model.Exam;
    010import net.sf.cpsolver.exam.model.ExamPlacement;
    011import net.sf.cpsolver.exam.neighbours.ExamRandomMove;
    012import net.sf.cpsolver.exam.neighbours.ExamRoomMove;
    013import net.sf.cpsolver.exam.neighbours.ExamTimeMove;
    014import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    015import net.sf.cpsolver.ifs.model.LazyNeighbour;
    016import net.sf.cpsolver.ifs.model.Neighbour;
    017import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
    018import net.sf.cpsolver.ifs.solution.Solution;
    019import net.sf.cpsolver.ifs.solution.SolutionListener;
    020import net.sf.cpsolver.ifs.solver.Solver;
    021import net.sf.cpsolver.ifs.util.DataProperties;
    022import net.sf.cpsolver.ifs.util.JProf;
    023import net.sf.cpsolver.ifs.util.Progress;
    024import net.sf.cpsolver.ifs.util.ToolBox;
    025
    026import org.apache.log4j.Logger;
    027
    028/**
    029 * Greate deluge. In each iteration, one of the following three neighbourhoods
    030 * is selected first
    031 * <ul>
    032 * <li>random move ({@link ExamRandomMove})
    033 * <li>period swap ({@link ExamTimeMove})
    034 * <li>room swap ({@link ExamRoomMove})
    035 * </ul>
    036 * , then a neighbour is generated and it is accepted if the value of the new
    037 * solution is below certain bound. This bound is initialized to the
    038 * GreatDeluge.UpperBoundRate &times; value of the best solution ever found.
    039 * After each iteration, the bound is decreased by GreatDeluge.CoolRate (new
    040 * bound equals to old bound &times; GreatDeluge.CoolRate). If the bound gets
    041 * bellow GreatDeluge.LowerBoundRate &times; value of the best solution ever
    042 * found, it is changed back to GreatDeluge.UpperBoundRate &times; value of the
    043 * best solution ever found.
    044 *
    045 * If there was no improvement found between the bounds, the new bounds are
    046 * changed to GreatDeluge.UpperBoundRate^2 and GreatDeluge.LowerBoundRate^2,
    047 * GreatDeluge.UpperBoundRate^3 and GreatDeluge.LowerBoundRate^3, etc. till
    048 * there is an improvement found. <br>
    049 * <br>
    050 *
    051 * @version ExamTT 1.2 (Examination Timetabling)<br>
    052 *          Copyright (C) 2008 - 2010 Tomáš Müller<br>
    053 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    054 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    055 * <br>
    056 *          This library is free software; you can redistribute it and/or modify
    057 *          it under the terms of the GNU Lesser General Public License as
    058 *          published by the Free Software Foundation; either version 3 of the
    059 *          License, or (at your option) any later version. <br>
    060 * <br>
    061 *          This library is distributed in the hope that it will be useful, but
    062 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    063 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    064 *          Lesser General Public License for more details. <br>
    065 * <br>
    066 *          You should have received a copy of the GNU Lesser General Public
    067 *          License along with this library; if not see
    068 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    069 */
    070public class ExamGreatDeluge implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> {
    071    private static Logger sLog = Logger.getLogger(ExamGreatDeluge.class);
    072    private static DecimalFormat sDF2 = new DecimalFormat("0.00");
    073    private static DecimalFormat sDF5 = new DecimalFormat("0.00000");
    074    private double iBound = 0.0;
    075    private double iCoolRate = 0.99999995;
    076    private long iIter;
    077    private double iUpperBound;
    078    private double iUpperBoundRate = 1.05;
    079    private double iLowerBoundRate = 0.95;
    080    private int iMoves = 0;
    081    private int iAcceptedMoves = 0;
    082    private int iNrIdle = 0;
    083    private long iT0 = -1;
    084    private long iLastImprovingIter = 0;
    085    private double iBestValue = 0;
    086    private Progress iProgress = null;
    087
    088    private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null;
    089
    090    /**
    091     * Constructor. Following problem properties are considered:
    092     * <ul>
    093     * <li>GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995)
    094     * <li>GreatDeluge.UpperBoundRate ... bound upper bound relative to best
    095     * solution ever found (default 1.05)
    096     * <li>GreatDeluge.LowerBoundRate ... bound lower bound relative to best
    097     * solution ever found (default 0.95)
    098     * </ul>
    099     *
    100     * @param properties
    101     *            problem properties
    102     */
    103    @SuppressWarnings("unchecked")
    104    public ExamGreatDeluge(DataProperties properties) {
    105        iCoolRate = properties.getPropertyDouble("GreatDeluge.CoolRate", iCoolRate);
    106        iUpperBoundRate = properties.getPropertyDouble("GreatDeluge.UpperBoundRate", iUpperBoundRate);
    107        iLowerBoundRate = properties.getPropertyDouble("GreatDeluge.LowerBoundRate", iLowerBoundRate);
    108        String neighbours = properties.getProperty("GreatDeluge.Neighbours",
    109                ExamRandomMove.class.getName() + ";" +
    110                ExamRoomMove.class.getName() + ";" +
    111                ExamTimeMove.class.getName());
    112        neighbours += ";" + properties.getProperty("GreatDeluge.AdditionalNeighbours", "");
    113        iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>();
    114        for (String neighbour: neighbours.split("\\;")) {
    115            if (neighbour == null || neighbour.isEmpty()) continue;
    116            try {
    117                Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour);
    118                iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties));
    119            } catch (Exception e) {
    120                sLog.error("Unable to use " + neighbour + ": " + e.getMessage());
    121            }
    122        }
    123    }
    124
    125    /** Initialization */
    126    @Override
    127    public void init(Solver<Exam, ExamPlacement> solver) {
    128        iIter = -1;
    129        solver.currentSolution().addSolutionListener(this);
    130        for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours)
    131            neighbour.init(solver);
    132        solver.setUpdateProgress(false);
    133        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    134    }
    135
    136    /** Print some information */
    137    protected void info(Solution<Exam, ExamPlacement> solution) {
    138        sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
    139                + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
    140        sLog.info("Bound is " + sDF2.format(iBound) + ", " + "best value is " + sDF2.format(solution.getBestValue())
    141                + " (" + sDF2.format(100.0 * iBound / solution.getBestValue()) + "%), " + "current value is "
    142                + sDF2.format(solution.getModel().getTotalValue()) + " ("
    143                + sDF2.format(100.0 * iBound / solution.getModel().getTotalValue()) + "%), " + "#idle=" + iNrIdle
    144                + ", " + "Pacc=" + sDF5.format(100.0 * iAcceptedMoves / iMoves) + "%");
    145        iAcceptedMoves = iMoves = 0;
    146    }
    147
    148    /**
    149     * Generate neighbour -- select neighbourhood randomly, select neighbour
    150     */
    151    public Neighbour<Exam, ExamPlacement> genMove(Solution<Exam, ExamPlacement> solution) {
    152        while (true) {
    153            incIter(solution);
    154            NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size()));
    155            Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
    156            if (n != null)
    157                return n;
    158        }
    159    }
    160
    161    /** Accept neighbour */
    162    protected boolean accept(Solution<Exam, ExamPlacement> solution, Neighbour<Exam, ExamPlacement> neighbour) {
    163        if (neighbour instanceof LazyNeighbour) {
    164            ((LazyNeighbour<Exam, ExamPlacement>)neighbour).setAcceptanceCriterion(this);
    165            return true;
    166        }
    167        return (neighbour.value() <= 0 || solution.getModel().getTotalValue() + neighbour.value() <= iBound);
    168    }
    169
    170    /** Accept lazy neighbour */
    171    @Override
    172    public boolean accept(LazyNeighbour<Exam, ExamPlacement> neighbour, double value) {
    173        return (value <= 0.0 || neighbour.getModel().getTotalValue() <= iBound);
    174    }
    175
    176    /** Increment iteration count, update bound */
    177    protected void incIter(Solution<Exam, ExamPlacement> solution) {
    178        if (iIter < 0) {
    179            iIter = 0;
    180            iLastImprovingIter = 0;
    181            iT0 = JProf.currentTimeMillis();
    182            iBound = (solution.getBestValue() > 0.0 ? iUpperBoundRate * solution.getBestValue() : solution
    183                    .getBestValue()
    184                    / iUpperBoundRate);
    185            iUpperBound = iBound;
    186            iNrIdle = 0;
    187            iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]...");
    188        } else {
    189            iIter++;
    190            if (solution.getBestValue() >= 0.0)
    191                iBound *= iCoolRate;
    192            else
    193                iBound /= iCoolRate;
    194        }
    195        if (iIter % 100000 == 0) {
    196            info(solution);
    197        }
    198        double lowerBound = (solution.getBestValue() >= 0.0 ? Math.pow(iLowerBoundRate, 1 + iNrIdle)
    199                * solution.getBestValue() : solution.getBestValue() / Math.pow(iLowerBoundRate, 1 + iNrIdle));
    200        if (iBound < lowerBound) {
    201            iNrIdle++;
    202            sLog.info(" -<[" + iNrIdle + "]>- ");
    203            iBound = Math.max(solution.getBestValue() + 2.0, (solution.getBestValue() >= 0.0 ? Math.pow(
    204                    iUpperBoundRate, iNrIdle)
    205                    * solution.getBestValue() : solution.getBestValue() / Math.pow(iUpperBoundRate, iNrIdle)));
    206            iUpperBound = iBound;
    207            iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]...");
    208        }
    209        iProgress.setProgress(100 - Math.round(100.0 * (iBound - lowerBound) / (iUpperBound - lowerBound)));
    210    }
    211
    212    /**
    213     * A neighbour is generated randomly untill an acceptable one is found.
    214     */
    215    @Override
    216    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
    217        Neighbour<Exam, ExamPlacement> neighbour = null;
    218        while ((neighbour = genMove(solution)) != null) {
    219            iMoves++;
    220            if (accept(solution, neighbour)) {
    221                iAcceptedMoves++;
    222                break;
    223            }
    224        }
    225        return (neighbour == null ? null : neighbour);
    226    }
    227
    228    /** Update last improving iteration count */
    229    @Override
    230    public void bestSaved(Solution<Exam, ExamPlacement> solution) {
    231        if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) {
    232            iLastImprovingIter = iIter;
    233            iNrIdle = 0;
    234            iBestValue = solution.getBestValue();
    235        }
    236    }
    237
    238    @Override
    239    public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
    240    }
    241
    242    @Override
    243    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
    244    }
    245
    246    @Override
    247    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
    248    }
    249
    250    @Override
    251    public void bestCleared(Solution<Exam, ExamPlacement> solution) {
    252    }
    253
    254    @Override
    255    public void bestRestored(Solution<Exam, ExamPlacement> solution) {
    256    }
    257}