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