    001package org.cpsolver.ifs.algorithms;
    002
    003import org.cpsolver.ifs.assignment.Assignment;
    004import org.cpsolver.ifs.heuristics.NeighbourSelection;
    005import org.cpsolver.ifs.model.Model;
    006import org.cpsolver.ifs.model.Neighbour;
    007import org.cpsolver.ifs.model.Value;
    008import org.cpsolver.ifs.model.Variable;
    009import org.cpsolver.ifs.solution.Solution;
    010import org.cpsolver.ifs.solver.Solver;
    011import org.cpsolver.ifs.util.DataProperties;
    012
    013/**
    014 * Hill climber. In each iteration, one of the given neighbourhoods is selected first,
    015 * then a neighbour is generated and it is accepted if its value
    016 * {@link Neighbour#value(Assignment)} is below or equal to zero. The search is
    017 * stopped after a given amount of idle iterations ( can be defined by problem
    018 * property HillClimber.MaxIdle). <br>
    019 * <br>
    020 * Custom neighbours can be set using HillClimber.Neighbours property that should
    021 * contain semicolon separated list of {@link NeighbourSelection}. By default,
    022 * each neighbour selection is selected with the same probability (each has 1 point in
    023 * a roulette wheel selection). It can be changed by adding &nbsp;@n at the end
    024 * of the name of the class, for example:
    025 * <pre><code>
    026 * HillClimber.Neighbours=org.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;org.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1
    027 * </code></pre>
    028 * Selector RandomSwapMove is 10&times; less probable to be selected than other selectors.
    029 * When HillClimber.Random is true, all selectors are selected with the same probability, ignoring these weights.
    030 * <br><br>
    031 * When HillClimber.Update is true, {@link NeighbourSelector#update(Assignment, Neighbour, long)} is called
    032 * after each iteration (on the selector that was used) and roulette wheel selection
    033 * that is using {@link NeighbourSelector#getPoints()} is used to pick a selector in each iteration.
    034 * See {@link NeighbourSelector} for more details.
    035 * <br>
    036 *
    037 * @author  Tomáš Müller
    038 * @version IFS 1.3 (Iterative Forward Search)<br>
    039 *          Copyright (C) 2014 Tomáš Müller<br>
    040 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    041 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    042 * <br>
    043 *          This library is free software; you can redistribute it and/or modify
    044 *          it under the terms of the GNU Lesser General Public License as
    045 *          published by the Free Software Foundation; either version 3 of the
    046 *          License, or (at your option) any later version. <br>
    047 * <br>
    048 *          This library is distributed in the hope that it will be useful, but
    049 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    050 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    051 *          Lesser General Public License for more details. <br>
    052 * <br>
    053 *          You should have received a copy of the GNU Lesser General Public
    054 *          License along with this library; if not see
    055 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    056 * @param <V> Variable
    057 * @param <T> Value
    058 */
    059public class HillClimber<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSearch<V, T> {
    060    protected int iMaxIdleIters = 10000;
    061    protected boolean iSetHCMode = false;
    062    protected static double sEPS = 0.00001;
    063
    064    /**
    065     * Constructor
    066     * <ul>
    067     * <li>HillClimber.MaxIdle ... maximum number of idle iterations (default is 200000)
    068     * <li>HillClimber.Neighbours ... semicolon separated list of classes implementing {@link NeighbourSelection}
    069     * <li>HillClimber.AdditionalNeighbours ... semicolon separated list of classes implementing {@link NeighbourSelection}
    070     * <li>HillClimber.Random ... when true, a neighbour selector is selected randomly
    071     * <li>HillClimber.Update ... when true, a neighbour selector is selected using {@link NeighbourSelector#getPoints()} weights (roulette wheel selection)
    072     * </ul>
    073     * @param properties solver configuration
    074     */
    075    public HillClimber(DataProperties properties) {
    076        super(properties);
    077        iMaxIdleIters = properties.getPropertyInt(getParameterBaseName() + ".MaxIdle", iMaxIdleIters);
    078        iSetHCMode = properties.getPropertyBoolean(getParameterBaseName() + ".SetHCMode", iSetHCMode);
    079    }
    080
    081    /**
    082     * Set progress phase name
    083     * @param phase name of the phase in which the hill climber is used (for logging purposes)
    084     */
    085    public void setPhase(String phase) {
    086        iPhase = phase;
    087    }
    088
    089    /**
    090     * Initialization
    091     */
    092    @Override
    093    public void init(Solver<V, T> solver) {
    094        super.init(solver);
    095        if (iSetHCMode)
    096            setHCMode(true);
    097    }
    098
    099    /**
    100     * All parameters start with HillClimber base name, e.g., HillClimber.MaxIdle
    101     */
    102    @Override
    103    public String getParameterBaseName() { return "HillClimber"; }
    104
    105    @Override
    106    public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) {
    107        return new HillClimberContext();
    108    }
    109
    110    public class HillClimberContext extends NeighbourSearchContext {
    111        protected int iLastImprovingIter = 0;
    112
    113        /**
    114         * Increase iteration counter
    115         */
    116        @Override
    117        protected void incIteration(Solution<V, T> solution) {
    118            super.incIteration(solution);
    119            if (iIter % 10000 == 0) {
    120                info("Iter=" + (iIter / 1000)+"k, NonImpIter=" + iDF2.format((iIter-iLastImprovingIter)/1000.0)+"k, Speed="+iDF2.format(1000.0*iIter/getTimeMillis())+" it/s");
    121                logNeibourStatus();
    122            }
    123            setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters));
    124        }
    125
    126        /**
    127         * Stop the search after a given number of idle (not improving) iterations
    128         */
    129        @Override
    130        protected boolean canContinue(Solution<V, T> solution) {
    131            return iIter - iLastImprovingIter < iMaxIdleIters;
    132        }
    133
    134        /**
    135         * Reset the idle iterations counter
    136         */
    137        @Override
    138        protected void activate(Solution<V, T> solution) {
    139            super.activate(solution);
    140            iLastImprovingIter = iIter;
    141        }
    142
    143        /**
    144         * Accept any move that does not worsen the solution (value &lt;= 0)
    145         */
    146        @Override
    147        protected boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) {
    148            if (value < -sEPS) iLastImprovingIter = iIter;
    149            return value <= 0;
    150        }
    151    }
    152}