    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.ExamSimpleNeighbour;
    016import org.cpsolver.exam.neighbours.ExamTimeMove;
    017import org.cpsolver.ifs.assignment.Assignment;
    018import org.cpsolver.ifs.assignment.context.AssignmentContext;
    019import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
    020import org.cpsolver.ifs.heuristics.NeighbourSelection;
    021import org.cpsolver.ifs.model.LazyNeighbour;
    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 * Simulated annealing. In each iteration, one of the following three
    034 * neighbourhoods 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 with probability
    041 * {@link ExamSimulatedAnnealing.Context#prob(double)}. The search is guided by the
    042 * temperature, which starts at <i>SimulatedAnnealing.InitialTemperature</i>.
    043 * After each <i>SimulatedAnnealing.TemperatureLength</i> iterations, the
    044 * temperature is reduced by <i>SimulatedAnnealing.CoolingRate</i>. If there was
    045 * no improvement in the past <i>SimulatedAnnealing.ReheatLengthCoef *
    046 * SimulatedAnnealing.TemperatureLength</i> iterations, the temperature is
    047 * increased by <i>SimulatedAnnealing.ReheatRate</i>. If there was no
    048 * improvement in the past <i>SimulatedAnnealing.RestoreBestLengthCoef *
    049 * SimulatedAnnealing.TemperatureLength</i> iterations, the best ever found
    050 * solution is restored. <br>
    051 * <br>
    052 * If <i>SimulatedAnnealing.StochasticHC</i> is true, the acceptance probability
    053 * is computed using stochastic hill climbing criterion, i.e.,
    054 * <pre><code>1.0 / (1.0 + Math.exp(value/temperature))</code></pre>, otherwise it is
    055 * cumputed using simlated annealing criterion, i.e.,
    056 * <pre><code>(value&lt;=0.0?1.0:Math.exp(-value/temperature))</code></pre>. If
    057 * <i>SimulatedAnnealing.RelativeAcceptance</i> neighbour value
    058 * {@link ExamSimpleNeighbour#value(Assignment)} is taken as the value of the selected
    059 * neighbour (difference between the new and the current solution, if the
    060 * neighbour is accepted), otherwise the value is computed as the difference
    061 * between the value of the current solution if the neighbour is accepted and
    062 * the best ever found solution. <br>
    063 * <br>
    064 *
    065 * @author  Tomáš Müller
    066 * @version ExamTT 1.3 (Examination Timetabling)<br>
    067 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
    068 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    069 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    070 * <br>
    071 *          This library is free software; you can redistribute it and/or modify
    072 *          it under the terms of the GNU Lesser General Public License as
    073 *          published by the Free Software Foundation; either version 3 of the
    074 *          License, or (at your option) any later version. <br>
    075 * <br>
    076 *          This library is distributed in the hope that it will be useful, but
    077 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    078 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    079 *          Lesser General Public License for more details. <br>
    080 * <br>
    081 *          You should have received a copy of the GNU Lesser General Public
    082 *          License along with this library; if not see
    083 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    084 */
    085@Deprecated
    086public class ExamSimulatedAnnealing extends NeighbourSelectionWithContext<Exam, ExamPlacement, ExamSimulatedAnnealing.Context> implements SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> {
    087    private static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(ExamSimulatedAnnealing.class);
    088    private static DecimalFormat sDF2 = new DecimalFormat("0.00");
    089    private static DecimalFormat sDF5 = new DecimalFormat("0.00000");
    090    private static DecimalFormat sDF10 = new DecimalFormat("0.0000000000");
    091    private double iInitialTemperature = 1.5;
    092    private double iCoolingRate = 0.95;
    093    private double iReheatRate = -1;
    094    private long iTemperatureLength = 250000;
    095    private long iReheatLength = 0;
    096    private long iRestoreBestLength = 0;
    097    private double iReheatLengthCoef = 5.0;
    098    private double iRestoreBestLengthCoef = -1;
    099    private boolean iStochasticHC = false;
    100    private double iBestValue = 0;
    101    private Progress iProgress = null;
    102
    103    private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null;
    104
    105    private boolean iRelativeAcceptance = true;
    106
    107    /**
    108     * Constructor. Following problem properties are considered:
    109     * <ul>
    110     * <li>SimulatedAnnealing.InitialTemperature ... initial temperature
    111     * (default 1.5)
    112     * <li>SimulatedAnnealing.TemperatureLength ... temperature length (number
    113     * of iterations between temperature decrements, default 25000)
    114     * <li>SimulatedAnnealing.CoolingRate ... temperature cooling rate (default
    115     * 0.95)
    116     * <li>SimulatedAnnealing.ReheatLengthCoef ... temperature re-heat length
    117     * coefficient (multiple of temperature length, default 5)
    118     * <li>SimulatedAnnealing.ReheatRate ... temperature re-heating rate
    119     * (default (1/coolingRate)^(reheatLengthCoef*1.7))
    120     * <li>SimulatedAnnealing.RestoreBestLengthCoef ... restore best length
    121     * coefficient (multiple of re-heat length, default reheatLengthCoef^2)
    122     * <li>SimulatedAnnealing.StochasticHC ... true for stochastic search
    123     * acceptance criterion, false for simulated annealing acceptance (default
    124     * false)
    125     * <li>SimulatedAnnealing.RelativeAcceptance ... true for relative
    126     * acceptance (different between the new and the current solutions, if the
    127     * neighbour is accepted), false for absolute acceptance (difference between
    128     * the new and the best solutions, if the neighbour is accepted)
    129     * </ul>
    130     *
    131     * @param properties
    132     *            problem properties
    133     */
    134    @SuppressWarnings("unchecked")
    135    public ExamSimulatedAnnealing(DataProperties properties) {
    136        iInitialTemperature = properties
    137                .getPropertyDouble("SimulatedAnnealing.InitialTemperature", iInitialTemperature);
    138        iReheatRate = properties.getPropertyDouble("SimulatedAnnealing.ReheatRate", iReheatRate);
    139        iCoolingRate = properties.getPropertyDouble("SimulatedAnnealing.CoolingRate", iCoolingRate);
    140        iRelativeAcceptance = properties.getPropertyBoolean("SimulatedAnnealing.RelativeAcceptance",
    141                iRelativeAcceptance);
    142        iStochasticHC = properties.getPropertyBoolean("SimulatedAnnealing.StochasticHC", iStochasticHC);
    143        iTemperatureLength = properties.getPropertyLong("SimulatedAnnealing.TemperatureLength", iTemperatureLength);
    144        iReheatLengthCoef = properties.getPropertyDouble("SimulatedAnnealing.ReheatLengthCoef", iReheatLengthCoef);
    145        iRestoreBestLengthCoef = properties.getPropertyDouble("SimulatedAnnealing.RestoreBestLengthCoef",
    146                iRestoreBestLengthCoef);
    147        if (iReheatRate < 0)
    148            iReheatRate = Math.pow(1 / iCoolingRate, iReheatLengthCoef * 1.7);
    149        if (iRestoreBestLengthCoef < 0)
    150            iRestoreBestLengthCoef = iReheatLengthCoef * iReheatLengthCoef;
    151        String neighbours = properties.getProperty("SimulatedAnnealing.Neighbours",
    152                ExamRandomMove.class.getName() + ";" +
    153                ExamRoomMove.class.getName() + ";" +
    154                ExamTimeMove.class.getName());
    155        neighbours += ";" + properties.getProperty("SimulatedAnnealing.AdditionalNeighbours", "");
    156        iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>();
    157        for (String neighbour: neighbours.split("\\;")) {
    158            if (neighbour == null || neighbour.isEmpty()) continue;
    159            try {
    160                Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour);
    161                iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties));
    162            } catch (Exception e) {
    163                sLog.error("Unable to use " + neighbour + ": " + e.getMessage());
    164            }
    165        }
    166    }
    167
    168    /**
    169     * Initialization
    170     */
    171    @Override
    172    public void init(Solver<Exam, ExamPlacement> solver) {
    173        super.init(solver);
    174        iReheatLength = Math.round(iReheatLengthCoef * iTemperatureLength);
    175        iRestoreBestLength = Math.round(iRestoreBestLengthCoef * iTemperatureLength);
    176        solver.currentSolution().addSolutionListener(this);
    177        for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours)
    178            neighbour.init(solver);
    179        solver.setUpdateProgress(false);
    180        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    181    }
    182
    183
    184    /**
    185     * Generate neighbour -- select neighbourhood randomly, select neighbour
    186     * @param solution current solutoon
    187     * @return generated neighbour
    188     */
    189    public Neighbour<Exam, ExamPlacement> genMove(Solution<Exam, ExamPlacement> solution) {
    190        while (true) {
    191            getContext(solution.getAssignment()).incIter(solution);
    192            NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size()));
    193            Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
    194            if (n != null)
    195                return n;
    196        }
    197    }
    198
    199    /**
    200     * True if the given neighboir is to be be accepted
    201     *
    202     * @param solution
    203     *            current solution
    204     * @param neighbour
    205     *            proposed move
    206     * @return true if generated random number is below
    207     *         {@link ExamSimulatedAnnealing.Context#prob(double)}
    208     */
    209    protected boolean accept(Solution<Exam, ExamPlacement> solution, Neighbour<Exam, ExamPlacement> neighbour) {
    210        if (neighbour instanceof LazyNeighbour) {
    211            ((LazyNeighbour<Exam, ExamPlacement>)neighbour).setAcceptanceCriterion(this);
    212            return true;
    213        }
    214        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
    215        double value = (iRelativeAcceptance ? neighbour.value(assignment) : solution.getModel().getTotalValue(assignment) + neighbour.value(assignment) - solution.getBestValue());
    216        Context context = getContext(solution.getAssignment());
    217        double prob = context.prob(value);
    218        if (prob >= 1.0 || ToolBox.random() < prob) {
    219            context.accepted(neighbour.value(assignment));
    220            return true;
    221        }
    222        return false;
    223    }
    224
    225    /** Accept lazy neighbour */
    226    @Override
    227    public boolean accept(Assignment<Exam, ExamPlacement> assignment, LazyNeighbour<Exam, ExamPlacement> neighbour, double value) {
    228        Context context = getContext(assignment);
    229        double prob = context.prob(value);
    230        if (prob >= 1.0 || ToolBox.random() < prob) {
    231            context.accepted(value);
    232            return true;
    233        }
    234        return false;
    235    }
    236
    237    /**
    238     * Select neighbour -- generate a move
    239     * {@link ExamSimulatedAnnealing#genMove(Solution)} until an acceptable
    240     * neighbour is found
    241     * {@link ExamSimulatedAnnealing#accept(Solution, Neighbour)}, keep
    242     * increasing iteration {@link ExamSimulatedAnnealing.Context#incIter(Solution)}.
    243     */
    244    @Override
    245    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
    246        Context context = getContext(solution.getAssignment());
    247        context.activateIfNeeded();
    248        Neighbour<Exam, ExamPlacement> neighbour = null;
    249        while ((neighbour = genMove(solution)) != null) {
    250            context.incMoves(neighbour.value(solution.getAssignment()));
    251            if (accept(solution, neighbour))
    252                break;
    253        }
    254        if (neighbour == null)
    255            context.reset();
    256        return (neighbour == null ? null : neighbour);
    257    }
    258
    259    @Override
    260    public void bestSaved(Solution<Exam, ExamPlacement> solution) {
    261        getContext(solution.getAssignment()).bestSaved(solution);
    262    }
    263
    264    @Override
    265    public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
    266    }
    267
    268    @Override
    269    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
    270    }
    271
    272    @Override
    273    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
    274    }
    275
    276    @Override
    277    public void bestCleared(Solution<Exam, ExamPlacement> solution) {
    278    }
    279
    280    @Override
    281    public void bestRestored(Solution<Exam, ExamPlacement> solution) {
    282    }
    283
    284    public class Context implements AssignmentContext {
    285        private boolean iActive = false;
    286        private double iTemperature = 0.0;
    287        private long iIter = 0;
    288        private long iLastImprovingIter = 0;
    289        private long iLastReheatIter = 0;
    290        private long iLastCoolingIter = 0;
    291        private int iAcceptIter[] = new int[] { 0, 0, 0 };
    292        private int iMoves = 0;
    293        private long iT0 = -1;
    294        private double iAbsValue = 0;
    295
    296        /**
    297         * Increment iteration counter, cool/reheat/restoreBest if necessary
    298         * @param solution current solution
    299         */
    300        protected void incIter(Solution<Exam, ExamPlacement> solution) {
    301            if (iT0 < 0) {
    302                iT0 = JProf.currentTimeMillis();
    303                iTemperature = iInitialTemperature;
    304            }
    305            iIter++;
    306            if (iIter > iLastImprovingIter + iRestoreBestLength) {
    307                solution.restoreBest();
    308                iLastImprovingIter = iIter;
    309            }
    310            if (iIter > Math.max(iLastReheatIter, iLastImprovingIter) + iReheatLength)
    311                reheat(solution);
    312            if (iIter > iLastCoolingIter + iTemperatureLength)
    313                cool(solution);
    314            iProgress.setProgress(Math.round(100.0 * (iIter - Math.max(iLastReheatIter, iLastImprovingIter)) / iReheatLength));
    315        }
    316
    317        /**
    318         * Cool temperature
    319         * @param solution current solution
    320         */
    321        protected void cool(Solution<Exam, ExamPlacement> solution) {
    322            iTemperature *= iCoolingRate;
    323            sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
    324                    + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
    325            sLog.info("Temperature decreased to " + sDF5.format(iTemperature) + " " + "(#moves=" + iMoves + ", rms(value)="
    326                    + sDF2.format(Math.sqrt(iAbsValue / iMoves)) + ", " + "accept=-"
    327                    + sDF2.format(100.0 * iAcceptIter[0] / iTemperatureLength) + "/"
    328                    + sDF2.format(100.0 * iAcceptIter[1] / iTemperatureLength) + "/+"
    329                    + sDF2.format(100.0 * iAcceptIter[2] / iTemperatureLength) + "%, "
    330                    + (prob(-1) < 1.0 ? "p(-1)=" + sDF2.format(100.0 * prob(-1)) + "%, " : "") + "p(+1)="
    331                    + sDF2.format(100.0 * prob(1)) + "%, " + "p(+10)=" + sDF5.format(100.0 * prob(10)) + "%)");
    332            iLastCoolingIter = iIter;
    333            iAcceptIter = new int[] { 0, 0, 0 };
    334            iMoves = 0;
    335            iAbsValue = 0;
    336        }
    337
    338        /**
    339         * Reheat temperature
    340         * @param solution current solution
    341         */
    342        protected void reheat(Solution<Exam, ExamPlacement> solution) {
    343            iTemperature *= iReheatRate;
    344            sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
    345                    + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
    346            sLog.info("Temperature increased to " + sDF5.format(iTemperature) + " "
    347                    + (prob(-1) < 1.0 ? "p(-1)=" + sDF2.format(100.0 * prob(-1)) + "%, " : "") + "p(+1)="
    348                    + sDF2.format(100.0 * prob(1)) + "%, " + "p(+10)=" + sDF5.format(100.0 * prob(10)) + "%, " + "p(+100)="
    349                    + sDF10.format(100.0 * prob(100)) + "%)");
    350            iLastReheatIter = iIter;
    351            iProgress.setPhase("Simulated Annealing [" + sDF2.format(iTemperature) + "]...");
    352        }
    353
    354        /**
    355         * Memorize the iteration when the last best solution was found.
    356         * @param solution current solution
    357         */
    358        protected void bestSaved(Solution<Exam, ExamPlacement> solution) {
    359            if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) {
    360                iLastImprovingIter = iIter;
    361                iBestValue = solution.getBestValue();
    362            }
    363            iLastImprovingIter = iIter;
    364        }
    365
    366        /**
    367         * Neighbour acceptance probability
    368         *
    369         * @param value
    370         *            absolute or relative value of the proposed change (neighbour)
    371         * @return probability of acceptance of a change (neighbour)
    372         */
    373        protected double prob(double value) {
    374            if (iStochasticHC)
    375                return 1.0 / (1.0 + Math.exp(value / iTemperature));
    376            else
    377                return (value <= 0.0 ? 1.0 : Math.exp(-value / iTemperature));
    378        }
    379
    380        /** A neighbor with the given value was accepted.
    381         * @param value change in the solution value
    382         **/
    383        protected void accepted(double value) {
    384            iAcceptIter[value < 0.0 ? 0 : value > 0.0 ? 2 : 1]++;
    385        }
    386
    387        protected void activateIfNeeded() {
    388            if (!iActive) {
    389                iProgress.setPhase("Simulated Annealing [" + sDF2.format(iTemperature) + "]...");
    390                iActive = true;
    391            }
    392        }
    393
    394        protected void incMoves(double value) {
    395            iMoves ++;
    396            iAbsValue += value * value;
    397        }
    398
    399        protected void reset() {
    400            iActive = false;
    401        }
    402    }
    403
    404    @Override
    405    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
    406        return new Context();
    407    }
    408}