001package org.cpsolver.ifs.algorithms;
002
003import org.cpsolver.ifs.assignment.Assignment;
004import org.cpsolver.ifs.model.Model;
005import org.cpsolver.ifs.model.Neighbour;
006import org.cpsolver.ifs.model.Value;
007import org.cpsolver.ifs.model.Variable;
008import org.cpsolver.ifs.solution.Solution;
009import org.cpsolver.ifs.util.DataProperties;
010
011/**
012 * Step counting hill climber. Unlike with the ordinary hill climber, there is a bound.
013 * The bound is updated (to the value of the current solution) after a given number of
014 * moves. Based on the given mode, either all moves, only accepted moves, or only improving
015 * moves are counted. 
016 * <br>
017 * 
018 * @version IFS 1.3 (Iterative Forward Search)<br>
019 *          Copyright (C) 2014 Tomáš Müller<br>
020 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
021 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
022 * <br>
023 *          This library is free software; you can redistribute it and/or modify
024 *          it under the terms of the GNU Lesser General Public License as
025 *          published by the Free Software Foundation; either version 3 of the
026 *          License, or (at your option) any later version. <br>
027 * <br>
028 *          This library is distributed in the hope that it will be useful, but
029 *          WITHOUT ANY WARRANTY; without even the implied warranty of
030 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
031 *          Lesser General Public License for more details. <br>
032 * <br>
033 *          You should have received a copy of the GNU Lesser General Public
034 *          License along with this library; if not see
035 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
036 * @param <V> Variable
037 * @param <T> Value
038 */
039public class StepCountingHillClimber<V extends Variable<V, T>, T extends Value<V, T>> extends HillClimber<V, T> {
040    public static enum Mode {
041        ALL,
042        ACCEPTED,
043        IMPROVING
044    }
045    protected int iCounterLimit = 100;
046    protected Mode iCounterMode = Mode.ACCEPTED;
047    protected Double[] iCounterLimitAdjusts = null;
048
049    /**
050     * Constructor
051     * <ul>
052     * <li>HillClimber.CounterLimit ... number of moves after which the bound is reset (defaults to 1000)
053     * <li>HillClimber.CounterMode ... counter mode (all: count all moves, accepted: count accepted moves, improving: count improving moves)
054     * </ul>
055     * @param properties solver configuration
056     */
057    public StepCountingHillClimber(DataProperties properties) {
058        super(properties);
059        iSetHCMode = false;
060        iCounterLimit = properties.getPropertyInt(getParameterBaseName() + ".CounterLimit", iCounterLimit);
061        iCounterMode = Mode.valueOf(properties.getProperty(getParameterBaseName() + ".CounterMode", iCounterMode.name()).toUpperCase());
062        iCounterLimitAdjusts = properties.getPropertyDoubleArry(getParameterBaseName() + ".CounterLimitAdjustments", null);
063    }
064
065    @Override
066    public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) {
067        return new StepCountingHillClimberContext();
068    }
069    
070    public class StepCountingHillClimberContext extends HillClimberContext {
071        protected Double iBound = null;
072        protected int iCounter = 0;
073
074        /**
075         * Reset the bound and the steps counter.
076         */
077        @Override
078        public void activate(Solution<V, T> solution) {
079            super.activate(solution);
080            iBound = solution.getModel().getTotalValue(solution.getAssignment());
081            iCounter = 0;
082        }
083        
084        protected int getCounterLimit(int idx) {
085            if (idx < 0 || iCounterLimitAdjusts == null || idx >= iCounterLimitAdjusts.length || iCounterLimitAdjusts[idx] == null) return iCounterLimit;
086            return (int) Math.round(iCounterLimit * iCounterLimitAdjusts[idx]);
087        }
088        
089        /**
090         * Increase iteration number, also update bound when the given number of steps is reached.
091         */
092        @Override
093        public void incIteration(Solution<V, T> solution) {
094            iIter++;
095            if (iIter % 10000 == 0) {
096                info("Iter=" + (iIter / 1000)+"k, NonImpIter=" + iDF2.format((iIter-iLastImprovingIter)/1000.0)+"k, Speed="+iDF2.format(1000.0*iIter/getTimeMillis())+" it/s, Bound=" + iDF2.format(iBound));
097                logNeibourStatus();
098            }
099            // iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters));
100            if (iCounter >= getCounterLimit(solution.getAssignment().getIndex() - 1)) {
101                iBound = solution.getModel().getTotalValue(solution.getAssignment()); 
102                iCounter = 0;
103            }
104        }
105
106        /**
107         * Accept any move that does not worsen the solution (value &lt;= 0) or that is below the bound. Also increase the step counter.
108         */
109        @Override
110        protected boolean accept(Assignment<V, T> assignment, Model<V,T> model, Neighbour<V, T> neighbour, double value, boolean lazy) {
111            boolean accept = (value <= 0.0 || (lazy ? model.getTotalValue(assignment) : value + model.getTotalValue(assignment)) < iBound);
112            switch (iCounterMode) {
113                case ALL:
114                    iCounter ++;
115                    break;
116                case ACCEPTED:
117                    if (accept) iCounter ++;
118                    break;
119                case IMPROVING:
120                    if (value < 0) iCounter ++;
121                    break;
122            }
123            return accept;
124        }
125        
126        /**
127         * Stop the search when the number of idle iterations is reached and the bound is no longer decreasing
128         */
129        @Override
130        protected boolean canContinue(Solution<V, T> solution) {
131            return super.canContinue(solution) || iCounter < getCounterLimit(solution.getAssignment().getIndex() - 1) || solution.getModel().getTotalValue(solution.getAssignment()) < iBound;
132        }
133    }
134}