    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}