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