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 @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}