001package net.sf.cpsolver.ifs.algorithms; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.Iterator; 007import java.util.List; 008import java.util.Map; 009 010import org.apache.log4j.Logger; 011 012import net.sf.cpsolver.ifs.algorithms.neighbourhoods.HillClimberSelection; 013import net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomMove; 014import net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove; 015import net.sf.cpsolver.ifs.algorithms.neighbourhoods.SuggestionMove; 016import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 017import net.sf.cpsolver.ifs.model.LazyNeighbour; 018import net.sf.cpsolver.ifs.model.Model; 019import net.sf.cpsolver.ifs.model.Neighbour; 020import net.sf.cpsolver.ifs.model.Value; 021import net.sf.cpsolver.ifs.model.Variable; 022import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion; 023import net.sf.cpsolver.ifs.solution.Solution; 024import net.sf.cpsolver.ifs.solution.SolutionListener; 025import net.sf.cpsolver.ifs.solver.Solver; 026import net.sf.cpsolver.ifs.util.DataProperties; 027import net.sf.cpsolver.ifs.util.JProf; 028import net.sf.cpsolver.ifs.util.Progress; 029import net.sf.cpsolver.ifs.util.ToolBox; 030 031/** 032 * Base class for the search techniques like hill climber, great deluge, or simulated annealing. 033 * It implements the {@link SolutionListener} and the variable neighbourhood selection. 034 * 035 * <br> 036 * 037 * @version IFS 1.2 (Iterative Forward Search)<br> 038 * Copyright (C) 2014 Tomáš Müller<br> 039 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 040 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 041 * <br> 042 * This library is free software; you can redistribute it and/or modify 043 * it under the terms of the GNU Lesser General Public License as 044 * published by the Free Software Foundation; either version 3 of the 045 * License, or (at your option) any later version. <br> 046 * <br> 047 * This library is distributed in the hope that it will be useful, but 048 * WITHOUT ANY WARRANTY; without even the implied warranty of 049 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 050 * Lesser General Public License for more details. <br> 051 * <br> 052 * You should have received a copy of the GNU Lesser General Public 053 * License along with this library; if not see 054 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 055 **/ 056public abstract class NeighbourSearch<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, SolutionListener<V, T>, LazyNeighbourAcceptanceCriterion<V, T> { 057 protected Logger iLog; 058 protected DecimalFormat iDF2 = new DecimalFormat("0.00"); 059 060 protected long iT0 = -1; 061 protected int iIter = 0; 062 protected String iPhase = null; 063 protected Progress iProgress = null; 064 065 private List<NeighbourSelector<V, T>> iNeighbours = null; 066 private boolean iRandomSelection = false; 067 private boolean iUpdatePoints = false; 068 private double iTotalBonus; 069 070 @SuppressWarnings("unchecked") 071 public NeighbourSearch(DataProperties properties) { 072 iPhase = getClass().getSimpleName().replaceAll("(?<=[^A-Z])([A-Z])"," $1"); 073 iLog = Logger.getLogger(getClass()); 074 iRandomSelection = properties.getPropertyBoolean(getParameterBaseName() + ".Random", iRandomSelection); 075 iUpdatePoints = properties.getPropertyBoolean(getParameterBaseName() + ".Update", iUpdatePoints); 076 String neighbours = properties.getProperty(getParameterBaseName() + ".Neighbours", 077 RandomMove.class.getName() + ";" + RandomSwapMove.class.getName() + "@0.01;" + SuggestionMove.class.getName() + "@0.01"); 078 neighbours += ";" + properties.getProperty(getParameterBaseName() + ".AdditionalNeighbours", ""); 079 iNeighbours = new ArrayList<NeighbourSelector<V,T>>(); 080 for (String neighbour: neighbours.split("\\;")) { 081 if (neighbour == null || neighbour.isEmpty()) continue; 082 try { 083 double bonus = 1.0; 084 if (neighbour.indexOf('@')>=0) { 085 bonus = Double.parseDouble(neighbour.substring(neighbour.indexOf('@') + 1)); 086 neighbour = neighbour.substring(0, neighbour.indexOf('@')); 087 } 088 Class<NeighbourSelection<V, T>> clazz = (Class<NeighbourSelection<V, T>>)Class.forName(neighbour); 089 NeighbourSelection<V, T> selection = clazz.getConstructor(DataProperties.class).newInstance(properties); 090 addNeighbourSelection(selection, bonus); 091 } catch (Exception e) { 092 iLog.error("Unable to use " + neighbour + ": " + e.getMessage()); 093 } 094 } 095 } 096 097 /** 098 * Add neighbour selection 099 * @param bonus execution bonus (more bonus means more executions of this neighbour selection, see {@link NeighbourSelector}) 100 */ 101 protected void addNeighbourSelection(NeighbourSelection<V,T> ns, double bonus) { 102 iNeighbours.add(new NeighbourSelector<V,T>(ns, bonus, iUpdatePoints)); 103 } 104 105 private double totalPoints() { 106 if (!iUpdatePoints) return iTotalBonus; 107 double total = 0; 108 for (NeighbourSelector<V,T> ns: iNeighbours) 109 total += ns.getPoints(); 110 return total; 111 } 112 113 /** 114 * Set HC mode for all the neighbour selections that support the {@link HillClimberSelection} interface. 115 */ 116 protected void setHCMode(boolean hcMode) { 117 for (NeighbourSelector<V,T> s: iNeighbours) { 118 if (s.selection() instanceof HillClimberSelection) 119 ((HillClimberSelection)s.selection()).setHcMode(hcMode); 120 } 121 } 122 123 /** 124 * Return list of neighbour selections 125 * @return 126 */ 127 protected List<? extends NeighbourSelection<V, T>> getNeighbours() { 128 return iNeighbours; 129 } 130 131 @Override 132 public void init(Solver<V, T> solver) { 133 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 134 iT0 = -1; 135 solver.currentSolution().addSolutionListener(this); 136 solver.setUpdateProgress(false); 137 for (NeighbourSelection<V, T> neighbour: iNeighbours) 138 neighbour.init(solver); 139 solver.setUpdateProgress(false); 140 iTotalBonus = 0; 141 for (NeighbourSelector<V,T> s: iNeighbours) { 142 s.init(solver); 143 iTotalBonus += s.getBonus(); 144 } 145 } 146 147 /** 148 * Generate and return next neighbour selection 149 */ 150 protected NeighbourSelection<V,T> nextNeighbourSelection() { 151 NeighbourSelector<V,T> ns = null; 152 if (iRandomSelection) { 153 ns = ToolBox.random(iNeighbours); 154 } else { 155 double points = (ToolBox.random() * totalPoints()); 156 for (Iterator<NeighbourSelector<V,T>> i = iNeighbours.iterator(); i.hasNext(); ) { 157 ns = i.next(); 158 points -= (iUpdatePoints ? ns.getPoints() : ns.getBonus()); 159 if (points <= 0) break; 160 } 161 } 162 return ns; 163 } 164 165 /** 166 * Log some information about neigbour selections once in a while 167 */ 168 protected void logNeibourStatus() { 169 if (iUpdatePoints) 170 for (NeighbourSelector<V,T> ns: iNeighbours) 171 iLog.info(" "+ns+" ("+iDF2.format(ns.getPoints())+" pts, "+iDF2.format(100.0*(iUpdatePoints?ns.getPoints():ns.getBonus())/totalPoints())+"%)"); 172 } 173 174 /** 175 * Generate a random move 176 */ 177 public Neighbour<V, T> generateMove(Solution<V, T> solution) { 178 return nextNeighbourSelection().selectNeighbour(solution); 179 } 180 181 @Override 182 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 183 if (iT0 < 0) activate(solution); 184 while (canContinue(solution)) { 185 incIteration(solution); 186 Neighbour<V,T> n = generateMove(solution); 187 if (n != null && accept(solution, n)) 188 return n; 189 } 190 deactivate(solution); 191 return null; 192 } 193 194 /** 195 * Return false if the search is to be stopped. Null neighbour is returned when this method returns false. 196 */ 197 protected boolean canContinue(Solution<V, T> solution) { 198 return true; 199 } 200 201 /** 202 * Increment iteration counters etc. 203 */ 204 protected void incIteration(Solution<V, T> solution) { 205 iIter++; 206 } 207 208 /** 209 * Running time in milliseconds (since the last call of activate) 210 */ 211 protected long getTimeMillis() { return JProf.currentTimeMillis() - iT0; } 212 213 /** 214 * True if the generated move is to be accepted. 215 */ 216 protected boolean accept(Solution<V, T> solution, Neighbour<V, T> neighbour) { 217 if (neighbour instanceof LazyNeighbour) { 218 ((LazyNeighbour<V, T>)neighbour).setAcceptanceCriterion(this); 219 return true; 220 } 221 return accept(solution.getModel(), neighbour, neighbour.value(), false); 222 } 223 224 /** Accept lazy neighbour -- calling the acceptance criterion with lazy = true. */ 225 @Override 226 public boolean accept(LazyNeighbour<V, T> neighbour, double value) { 227 return accept(neighbour.getModel(), neighbour, value, true); 228 } 229 230 /** Acceptance criterion. If lazy, current assignment already contains the given neighbour. */ 231 protected abstract boolean accept(Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy); 232 233 /** Called just before the neighbourhood search is called for the first time. */ 234 protected void activate(Solution<V, T> solution) { 235 iT0 = JProf.currentTimeMillis(); 236 iIter = 0; 237 iProgress.setPhase(iPhase + "..."); 238 } 239 240 /** Called when the search cannot continue, just before a null neighbour is returned */ 241 protected void deactivate(Solution<V, T> solution) { 242 iT0 = -1; 243 } 244 245 /** 246 * Parameter base name. This can be used to distinguish between parameters of different search algorithms. 247 */ 248 public abstract String getParameterBaseName(); 249 250 @Override 251 public void bestSaved(Solution<V, T> solution) { 252 } 253 254 @Override 255 public void solutionUpdated(Solution<V, T> solution) { 256 } 257 258 @Override 259 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 260 } 261 262 @Override 263 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 264 } 265 266 @Override 267 public void bestCleared(Solution<V, T> solution) { 268 } 269 270 @Override 271 public void bestRestored(Solution<V, T> solution) { 272 } 273 274}