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