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 * @version IFS 1.3 (Iterative Forward Search)<br>
038 *          Copyright (C) 2014 Tomáš Müller<br>
039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 *          This library is free software; you can redistribute it and/or modify
043 *          it under the terms of the GNU Lesser General Public License as
044 *          published by the Free Software Foundation; either version 3 of the
045 *          License, or (at your option) any later version. <br>
046 * <br>
047 *          This library is distributed in the hope that it will be useful, but
048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
050 *          Lesser General Public License for more details. <br>
051 * <br>
052 *          You should have received a copy of the GNU Lesser General Public
053 *          License along with this library; if not see
054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
055 * @param <V> Variable
056 * @param <T> Value
057 */
058public class HillClimber<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSearch<V, T> {
059    protected int iMaxIdleIters = 10000;
060    protected boolean iSetHCMode = false;
061    protected static double sEPS = 0.00001;
062
063    /**
064     * Constructor
065     * <ul>
066     * <li>HillClimber.MaxIdle ... maximum number of idle iterations (default is 200000)
067     * <li>HillClimber.Neighbours ... semicolon separated list of classes implementing {@link NeighbourSelection}
068     * <li>HillClimber.AdditionalNeighbours ... semicolon separated list of classes implementing {@link NeighbourSelection}
069     * <li>HillClimber.Random ... when true, a neighbour selector is selected randomly
070     * <li>HillClimber.Update ... when true, a neighbour selector is selected using {@link NeighbourSelector#getPoints()} weights (roulette wheel selection)
071     * </ul>
072     * @param properties solver configuration
073     */
074    public HillClimber(DataProperties properties) {
075        super(properties);
076        iMaxIdleIters = properties.getPropertyInt(getParameterBaseName() + ".MaxIdle", iMaxIdleIters);
077        iSetHCMode = properties.getPropertyBoolean(getParameterBaseName() + ".SetHCMode", iSetHCMode);
078    }
079    
080    /**
081     * Set progress phase name
082     * @param phase name of the phase in which the hill climber is used (for logging purposes)
083     */
084    public void setPhase(String phase) {
085        iPhase = phase;
086    }
087
088    /**
089     * Initialization
090     */
091    @Override
092    public void init(Solver<V, T> solver) {
093        super.init(solver);
094        if (iSetHCMode)
095            setHCMode(true);
096    }
097    
098    /**
099     * All parameters start with HillClimber base name, e.g., HillClimber.MaxIdle 
100     */
101    @Override
102    public String getParameterBaseName() { return "HillClimber"; }
103    
104    @Override
105    public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) {
106        return new HillClimberContext();
107    }
108    
109    public class HillClimberContext extends NeighbourSearchContext {
110        protected int iLastImprovingIter = 0;
111
112        /**
113         * Increase iteration counter
114         */
115        @Override
116        protected void incIteration(Solution<V, T> solution) {
117            super.incIteration(solution);
118            if (iIter % 10000 == 0) {
119                info("Iter=" + (iIter / 1000)+"k, NonImpIter=" + iDF2.format((iIter-iLastImprovingIter)/1000.0)+"k, Speed="+iDF2.format(1000.0*iIter/getTimeMillis())+" it/s");
120                logNeibourStatus();
121            }
122            setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters));
123        }
124        
125        /**
126         * Stop the search after a given number of idle (not improving) iterations
127         */
128        @Override
129        protected boolean canContinue(Solution<V, T> solution) {
130            return iIter - iLastImprovingIter < iMaxIdleIters;
131        }
132        
133        /**
134         * Reset the idle iterations counter
135         */
136        @Override
137        protected void activate(Solution<V, T> solution) {
138            super.activate(solution);
139            iLastImprovingIter = iIter;
140        }
141        
142        /**
143         * Accept any move that does not worsen the solution (value &lt;= 0)
144         */
145        @Override
146        protected boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) {
147            if (value < -sEPS) iLastImprovingIter = iIter;
148            return value <= 0;
149        }
150    }
151}