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}