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