    001package org.cpsolver.ifs.algorithms;
    002
    003import java.text.DecimalFormat;
    004
    005import org.cpsolver.ifs.assignment.Assignment;
    006import org.cpsolver.ifs.heuristics.NeighbourSelection;
    007import org.cpsolver.ifs.model.Model;
    008import org.cpsolver.ifs.model.Neighbour;
    009import org.cpsolver.ifs.model.Value;
    010import org.cpsolver.ifs.model.Variable;
    011import org.cpsolver.ifs.solution.Solution;
    012import org.cpsolver.ifs.util.DataProperties;
    013import org.cpsolver.ifs.util.JProf;
    014
    015
    016/**
    017 * Great deluge. In each iteration, one of the given neighbourhoods is selected first,
    018 * then a neighbour is generated and it is accepted if the value of the new
    019 * solution is below certain bound. This bound is initialized to the
    020 * GreatDeluge.UpperBoundRate &times; value of the best solution ever found.
    021 * After each iteration, the bound is decreased by GreatDeluge.CoolRate (new
    022 * bound equals to old bound &times; GreatDeluge.CoolRate). If the bound gets
    023 * bellow GreatDeluge.LowerBoundRate &times; value of the best solution ever
    024 * found, it is changed back to GreatDeluge.UpperBoundRate &times; value of the
    025 * best solution ever found.
    026 * <br><br>
    027 * If there was no improvement found between the bounds, the new bounds are
    028 * changed to GreatDeluge.UpperBoundRate^2 and GreatDeluge.LowerBoundRate^2,
    029 * GreatDeluge.UpperBoundRate^3 and GreatDeluge.LowerBoundRate^3, etc. till
    030 * there is an improvement found. <br>
    031 * <br>
    032 * Custom neighbours can be set using GreatDeluge.Neighbours property that should
    033 * contain semicolon separated list of {@link NeighbourSelection}. By default,
    034 * each neighbour selection is selected with the same probability (each has 1 point in
    035 * a roulette wheel selection). It can be changed by adding &nbsp;@n at the end
    036 * of the name of the class, for example:
    037 * <pre><code>
    038 * GreatDeluge.Neighbours=org.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;org.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1
    039 * </code></pre>
    040 * Selector RandomSwapMove is 10&times; less probable to be selected than other selectors.
    041 * When GreatDeluge.Random is true, all selectors are selected with the same probability, ignoring these weights.
    042 * <br><br>
    043 * When GreatDeluge.Update is true, {@link NeighbourSelector#update(Assignment, Neighbour, long)} is called
    044 * after each iteration (on the selector that was used) and roulette wheel selection
    045 * that is using {@link NeighbourSelector#getPoints()} is used to pick a selector in each iteration.
    046 * See {@link NeighbourSelector} for more details.
    047 * <br>
    048 *
    049 * @author  Tomáš Müller
    050 * @version IFS 1.3 (Iterative Forward Search)<br>
    051 *          Copyright (C) 2014 Tomáš Müller<br>
    052 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    053 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    054 * <br>
    055 *          This library is free software; you can redistribute it and/or modify
    056 *          it under the terms of the GNU Lesser General Public License as
    057 *          published by the Free Software Foundation; either version 3 of the
    058 *          License, or (at your option) any later version. <br>
    059 * <br>
    060 *          This library is distributed in the hope that it will be useful, but
    061 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    062 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    063 *          Lesser General Public License for more details. <br>
    064 * <br>
    065 *          You should have received a copy of the GNU Lesser General Public
    066 *          License along with this library; if not see
    067 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    068 * @param <V> Variable
    069 * @param <T> Value
    070 */
    071public class GreatDeluge<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSearch<V, T> {
    072    private DecimalFormat sDF2 = new DecimalFormat("0.00");
    073    private DecimalFormat sDF5 = new DecimalFormat("0.00000");
    074    private double iCoolRate = 0.9999999;
    075    private double iUpperBoundRate = 1.05;
    076    private double iLowerBoundRate = 0.95;
    077    private Double[] iCoolRateAdjusts = null;
    078
    079    /**
    080     * Constructor. Following problem properties are considered:
    081     * <ul>
    082     * <li>GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995)
    083     * <li>GreatDeluge.UpperBoundRate ... bound upper bound relative to best solution ever found (default 1.05)
    084     * <li>GreatDeluge.LowerBoundRate ... bound lower bound relative to best solution ever found (default 0.95)
    085     * <li>GreatDeluge.Neighbours ... semicolon separated list of classes implementing {@link NeighbourSelection}
    086     * <li>GreatDeluge.AdditionalNeighbours ... semicolon separated list of classes implementing {@link NeighbourSelection}
    087     * <li>GreatDeluge.Random ... when true, a neighbour selector is selected randomly
    088     * <li>GreatDeluge.Update ... when true, a neighbour selector is selected using {@link NeighbourSelector#getPoints()} weights (roulette wheel selection)
    089     * </ul>
    090     *
    091     * @param properties
    092     *            problem properties
    093     */
    094    public GreatDeluge(DataProperties properties) {
    095        super(properties);
    096        iCoolRate = properties.getPropertyDouble(getParameterBaseName() + ".CoolRate", iCoolRate);
    097        iUpperBoundRate = properties.getPropertyDouble(getParameterBaseName() + ".UpperBoundRate", iUpperBoundRate);
    098        iLowerBoundRate = properties.getPropertyDouble(getParameterBaseName() + ".LowerBoundRate", iLowerBoundRate);
    099        iCoolRateAdjusts = properties.getPropertyDoubleArry(getParameterBaseName() + ".CoolRateAdjustments", null);
    100    }
    101
    102    @Override
    103    public String getParameterBaseName() { return "GreatDeluge"; }
    104
    105    @Override
    106    public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) {
    107        return new GreatDelugeContext();
    108    }
    109
    110    public class GreatDelugeContext extends NeighbourSearchContext {
    111        private int iMoves = 0;
    112        private int iAcceptedMoves = 0;
    113        private int iNrIdle = 0;
    114        private long iLastImprovingIter = 0;
    115        private double iBestValue = 0;
    116        private double iBound = 0.0;
    117        private double iUpperBound;
    118
    119        /** Accept the given neighbour if it does not worsen the current solution or when the new solution is below the bound */
    120        @Override
    121        protected boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) {
    122            iMoves ++;
    123            if (value <= 0.0 || (lazy ? model.getTotalValue(assignment) : value + model.getTotalValue(assignment)) < iBound) {
    124                iAcceptedMoves ++;
    125                return true;
    126            }
    127            return false;
    128        }
    129
    130        /** Setup the bound */
    131        @Override
    132        protected void activate(Solution<V, T> solution) {
    133            super.activate(solution);
    134            iNrIdle = 0;
    135            iLastImprovingIter = 0;
    136            iBound = (solution.getBestValue() > 0.0 ? iUpperBoundRate * solution.getBestValue() : solution.getBestValue() / iUpperBoundRate);
    137            iUpperBound = iBound;
    138        }
    139
    140        protected double getCoolRate(int idx) {
    141            if (idx < 0 || iCoolRateAdjusts == null || idx >= iCoolRateAdjusts.length || iCoolRateAdjusts[idx] == null) return iCoolRate;
    142            return iCoolRate * iCoolRateAdjusts[idx];
    143        }
    144
    145        /** Increment iteration count, update bound */
    146        @Override
    147        protected void incIteration(Solution<V, T> solution) {
    148            super.incIteration(solution);
    149            if (solution.getBestValue() >= 0.0)
    150                iBound *= getCoolRate(solution.getAssignment().getIndex() - 1);
    151            else
    152                iBound /= getCoolRate(solution.getAssignment().getIndex() - 1);
    153            if (iIter % 10000 == 0) {
    154                info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
    155                        + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
    156                info("Bound is " + sDF2.format(iBound) + ", " + "best value is " + sDF2.format(solution.getBestValue())
    157                        + " (" + sDF2.format(100.0 * iBound / solution.getBestValue()) + "%), " + "current value is "
    158                        + sDF2.format(solution.getModel().getTotalValue(solution.getAssignment())) + " ("
    159                        + sDF2.format(100.0 * iBound / solution.getModel().getTotalValue(solution.getAssignment())) + "%), " + "#idle=" + iNrIdle
    160                        + ", " + "Pacc=" + sDF5.format(100.0 * iAcceptedMoves / iMoves) + "%");
    161                logNeibourStatus();
    162                iAcceptedMoves = iMoves = 0;
    163            }
    164            if (isMaster(solution)) {
    165                double upperBound = Math.max(solution.getBestValue() + 2.0,(solution.getBestValue() >= 0.0 ?
    166                        Math.pow(iUpperBoundRate, 1 + iNrIdle) * solution.getBestValue() :
    167                        solution.getBestValue() / Math.pow(iUpperBoundRate, 1 + iNrIdle)));
    168                double lowerBound = (solution.getBestValue() >= 0.0
    169                        ? Math.pow(iLowerBoundRate, 1 + iNrIdle) * solution.getBestValue()
    170                        : solution.getBestValue() / Math.pow(iLowerBoundRate, 1 + iNrIdle));
    171                if (iBound > upperBound) {
    172                    iBound = upperBound;
    173                } else if (iBound < lowerBound) {
    174                    iNrIdle++;
    175                    iBound = upperBound;
    176                    iUpperBound = iBound;
    177                    setProgressPhase("Great Deluge [" + (1 + iNrIdle) + "]...");
    178                }
    179                setProgress(100 - Math.round(100.0 * (iBound - lowerBound) / (iUpperBound - lowerBound)));
    180            }
    181            iMoves++;
    182        }
    183
    184        /** Update last improving iteration count */
    185        @Override
    186        public void bestSaved(Solution<V, T> solution) {
    187            super.bestSaved(solution);
    188            if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) {
    189                iLastImprovingIter = iIter;
    190                iNrIdle = 0;
    191                iBestValue = solution.getBestValue();
    192            }
    193        }
    194    }
    195}