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 @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)} < 0) 137 * @return number of improving moves (value < 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}