001package org.cpsolver.ifs.algorithms;
002
003import java.text.DecimalFormat;
004
005import org.cpsolver.ifs.assignment.Assignment;
006import org.cpsolver.ifs.heuristics.NeighbourSelection;
007import org.cpsolver.ifs.model.Neighbour;
008import org.cpsolver.ifs.model.Value;
009import org.cpsolver.ifs.model.Variable;
010import org.cpsolver.ifs.solution.Solution;
011import org.cpsolver.ifs.solver.Solver;
012
013
014/**
015 * A wrapper for {@link NeighbourSelection} that keeps some stats about the 
016 * given neighbour selector.
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 NeighbourSelector<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T> {
040    protected static DecimalFormat sDF = new DecimalFormat("0.00");
041    private boolean iUpdate = false;
042    private NeighbourSelection<V,T> iSelection;
043    private int iNrCalls = 0;
044    private int iNrNotNull = 0;
045    private int iNrSideMoves = 0;
046    private int iNrImprovingMoves = 0;
047    private double iBonus = 1.0;
048    private double iPoints = 0;
049    private long iTime = 0;
050    
051    /**
052     * Constructor 
053     * @param sel neighbour selector
054     * @param bonus initial bonus (default is 1, can be changed by &nbsp;@n parameter after 
055     * the name of the selector in Xxx.Neigbours, e.g., org.cpsolver.itc.tim.neighbours.TimPrecedenceMove@0.1
056     * for initial bonus 0.1 
057     * @param update update selector bonus after each iteration
058     */
059    public NeighbourSelector(NeighbourSelection<V,T> sel, double bonus, boolean update) {
060        iSelection = sel;
061        iBonus = bonus;
062        iUpdate = update;
063    }
064    
065    /** Initialization */
066    @Override
067    public void init(Solver<V,T> solver) {
068        iSelection.init(solver);
069    }
070    
071    /** Neighbour selection -- use {@link NeighbourSelection#selectNeighbour(Solution)} 
072     * update stats if desired.
073     */
074    @Override
075    public Neighbour<V,T> selectNeighbour(Solution<V,T> solution) {
076        if (iUpdate) {
077            long t0 = System.currentTimeMillis();
078            Neighbour<V,T> n = iSelection.selectNeighbour(solution);
079            long t1 = System.currentTimeMillis();
080            update(solution.getAssignment(), n, t1-t0);
081            return n;
082        } else
083            return iSelection.selectNeighbour(solution);
084    }
085
086    /**
087     * Update statistics
088     * @param a current assignment
089     * @param n generated move
090     * @param time time needed to generate the move (in milliseconds)
091     */
092    public void update(Assignment<V, T> a, Neighbour<V,T> n, long time) {
093        iNrCalls ++;
094        iTime += time;
095        if (n!=null) {
096            iNrNotNull++;
097            double val = n.value(a); 
098            if (val==0) {
099                iNrSideMoves++;
100                iPoints += 0.1;
101            } else if (val<0) {
102                iNrImprovingMoves++;
103                iPoints -= n.value(a);
104            } else {
105                iPoints *= 0.9999;
106            }
107        } else {
108            iPoints *= 0.999;
109        }
110    }
111    
112    /** Weight of the selector in the roulette wheel selection of neighbour selectors 
113     * @return weight of this selector
114     **/
115    public double getPoints() { return iBonus * Math.min(100.0, 0.1+iPoints); }
116    /** Initial bonus
117     * @return initial bonus
118     **/
119    public double getBonus() { return iBonus; }
120    /** Given neighbour selection
121     * @return given neighbour selection
122     **/
123    public NeighbourSelection<V,T> selection() { return iSelection; }
124    /** Number of calls of {@link NeighbourSelection#selectNeighbour(Solution)}
125     * @return number of calls
126     **/
127    public int nrCalls() { return iNrCalls; }
128    /** Number of returned not-null moves
129     * @return number of not-null moves
130     **/
131    public int nrNotNull() { return iNrNotNull; }
132    /** Number of returned moves with zero improvement of the solution (i.e., {@link Neighbour#value(Assignment)} = 0)
133     * @return number of side moves (value = 0) 
134     **/
135    public int nrSideMoves() { return iNrSideMoves; }
136    /** Number of returned improving moves (i.e., {@link Neighbour#value(Assignment)} &lt; 0)
137     * @return number of improving moves (value &lt; 0)
138     **/
139    public int nrImprovingMoves() { return iNrImprovingMoves; }
140    /** Total time spend in {@link NeighbourSelection#selectNeighbour(Solution)} (in milliseconds)
141     * @return total time spend in theis selector 
142     **/
143    public long time() { return iTime; }
144    /** Average number of iterations per second (calls of {@link NeighbourSelection#selectNeighbour(Solution)})
145     * @return number of calls per second
146     **/
147    public double speed() { return 1000.0*nrCalls()/time(); }
148    /** String representation */
149    @Override
150    public String toString() {
151        return iSelection.getClass().getName().substring(iSelection.getClass().getName().lastIndexOf('.')+1)+" "+
152            nrCalls()+"x, "+
153            sDF.format(100.0*(nrCalls()-nrNotNull())/nrCalls())+"% null, "+
154            sDF.format(100.0*nrSideMoves()/nrCalls())+"% side, "+
155            sDF.format(100.0*nrImprovingMoves()/nrCalls())+"% imp, "+
156            sDF.format(speed())+" it/s";
157    }
158}