    001package net.sf.cpsolver.ifs.algorithms;
    002
    003import java.text.DecimalFormat;
    004
    005import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    006import net.sf.cpsolver.ifs.model.Neighbour;
    007import net.sf.cpsolver.ifs.model.Value;
    008import net.sf.cpsolver.ifs.model.Variable;
    009import net.sf.cpsolver.ifs.solution.Solution;
    010import net.sf.cpsolver.ifs.solver.Solver;
    011
    012/**
    013 * A wrapper for {@link NeighbourSelection} that keeps some stats about the
    014 * given neighbour selector.
    015 *
    016 * @version IFS 1.2 (Iterative Forward Search)<br>
    017 *          Copyright (C) 2014 Tomáš Müller<br>
    018 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    019 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    020 * <br>
    021 *          This library is free software; you can redistribute it and/or modify
    022 *          it under the terms of the GNU Lesser General Public License as
    023 *          published by the Free Software Foundation; either version 3 of the
    024 *          License, or (at your option) any later version. <br>
    025 * <br>
    026 *          This library is distributed in the hope that it will be useful, but
    027 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    028 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    029 *          Lesser General Public License for more details. <br>
    030 * <br>
    031 *          You should have received a copy of the GNU Lesser General Public
    032 *          License along with this library; if not see
    033 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    034 */
    035public class NeighbourSelector<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T> {
    036    protected static DecimalFormat sDF = new DecimalFormat("0.00");
    037    private boolean iUpdate = false;
    038    private NeighbourSelection<V,T> iSelection;
    039    private int iNrCalls = 0;
    040    private int iNrNotNull = 0;
    041    private int iNrSideMoves = 0;
    042    private int iNrImprovingMoves = 0;
    043    private double iBonus = 1.0;
    044    private double iPoints = 0;
    045    private long iTime = 0;
    046
    047    /**
    048     * Constructor
    049     * @param sel neighbour selector
    050     * @param bonus initial bonus (default is 1, can be changed by &nbsp;@n parameter after
    051     * the name of the selector in Xxx.Neigbours, e.g., net.sf.cpsolver.itc.tim.neighbours.TimPrecedenceMove@0.1
    052     * for initial bonus 0.1
    053     * @param update update selector bonus after each iteration
    054     */
    055    public NeighbourSelector(NeighbourSelection<V,T> sel, double bonus, boolean update) {
    056        iSelection = sel;
    057        iBonus = bonus;
    058        iUpdate = update;
    059    }
    060
    061    /** Initialization */
    062    @Override
    063    public void init(Solver<V,T> solver) {
    064        iSelection.init(solver);
    065    }
    066
    067    /** Neighbour selection -- use {@link NeighbourSelection#selectNeighbour(Solution)}
    068     * update stats if desired.
    069     */
    070    @Override
    071    public Neighbour<V,T> selectNeighbour(Solution<V,T> solution) {
    072        if (iUpdate) {
    073            long t0 = System.currentTimeMillis();
    074            Neighbour<V,T> n = iSelection.selectNeighbour(solution);
    075            long t1 = System.currentTimeMillis();
    076            update(n, t1-t0);
    077            return n;
    078        } else
    079            return iSelection.selectNeighbour(solution);
    080    }
    081
    082    /**
    083     * Update stats
    084     * @param n generated move
    085     * @param time time needed to generate the move (in milliseconds)
    086     */
    087    public void update(Neighbour<V,T> n, long time) {
    088        iNrCalls ++;
    089        iTime += time;
    090        if (n!=null) {
    091            iNrNotNull++;
    092            if (n.value()==0) {
    093                iNrSideMoves++;
    094                iPoints += 0.1;
    095            } else if (n.value()<0) {
    096                iNrImprovingMoves++;
    097                iPoints -= n.value();
    098            } else {
    099                iPoints *= 0.9999;
    100            }
    101        } else {
    102            iPoints *= 0.999;
    103        }
    104    }
    105
    106    /** Weight of the selector in the roulette wheel selection of neighbour selectors */
    107    public double getPoints() { return iBonus * Math.min(100.0, 0.1+iPoints); }
    108    /** Initial bonus */
    109    public double getBonus() { return iBonus; }
    110    /** Given neighbour selection */
    111    public NeighbourSelection<V,T> selection() { return iSelection; }
    112    /** Number of calls of {@link NeighbourSelection#selectNeighbour(Solution)} */
    113    public int nrCalls() { return iNrCalls; }
    114    /** Number of returned not-null moves */
    115    public int nrNotNull() { return iNrNotNull; }
    116    /** Number of returned moves with zero improvement of the solution (i.e., {@link Neighbour#value()} = 0)*/
    117    public int nrSideMoves() { return iNrSideMoves; }
    118    /** Number of returned improving moves (i.e., {@link Neighbour#value()} < 0)*/
    119    public int nrImprovingMoves() { return iNrImprovingMoves; }
    120    /** Total time spend in {@link NeighbourSelection#selectNeighbour(Solution)} (in milliseconds) */
    121    public long time() { return iTime; }
    122    /** Average number of iterations per second (calls of {@link NeighbourSelection#selectNeighbour(Solution)}) */
    123    public double speed() { return 1000.0*nrCalls()/time(); }
    124    /** String representation */
    125    @Override
    126    public String toString() {
    127        return iSelection.getClass().getName().substring(iSelection.getClass().getName().lastIndexOf('.')+1)+" "+
    128            nrCalls()+"x, "+
    129            sDF.format(100.0*(nrCalls()-nrNotNull())/nrCalls())+"% null, "+
    130            sDF.format(100.0*nrSideMoves()/nrCalls())+"% side, "+
    131            sDF.format(100.0*nrImprovingMoves()/nrCalls())+"% imp, "+
    132            sDF.format(speed())+" it/s";
    133    }
    134}