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