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