001package org.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; 011import org.cpsolver.ifs.algorithms.neighbourhoods.HillClimberSelection; 012import org.cpsolver.ifs.algorithms.neighbourhoods.RandomMove; 013import org.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove; 014import org.cpsolver.ifs.algorithms.neighbourhoods.SuggestionMove; 015import org.cpsolver.ifs.assignment.Assignment; 016import org.cpsolver.ifs.assignment.context.AssignmentContext; 017import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext; 018import org.cpsolver.ifs.heuristics.NeighbourSelection; 019import org.cpsolver.ifs.model.LazyNeighbour; 020import org.cpsolver.ifs.model.Model; 021import org.cpsolver.ifs.model.Neighbour; 022import org.cpsolver.ifs.model.Value; 023import org.cpsolver.ifs.model.Variable; 024import org.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion; 025import org.cpsolver.ifs.solution.Solution; 026import org.cpsolver.ifs.solution.SolutionListener; 027import org.cpsolver.ifs.solver.Solver; 028import org.cpsolver.ifs.util.DataProperties; 029import org.cpsolver.ifs.util.JProf; 030import org.cpsolver.ifs.util.Progress; 031import org.cpsolver.ifs.util.ToolBox; 032 033 034/** 035 * Base class for the search techniques like hill climber, great deluge, or simulated annealing. 036 * It implements the {@link SolutionListener} and the variable neighbourhood selection. 037 * 038 * <br> 039 * 040 * @version IFS 1.3 (Iterative Forward Search)<br> 041 * Copyright (C) 2014 Tomáš Müller<br> 042 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 043 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 044 * <br> 045 * This library is free software; you can redistribute it and/or modify 046 * it under the terms of the GNU Lesser General Public License as 047 * published by the Free Software Foundation; either version 3 of the 048 * License, or (at your option) any later version. <br> 049 * <br> 050 * This library is distributed in the hope that it will be useful, but 051 * WITHOUT ANY WARRANTY; without even the implied warranty of 052 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 053 * Lesser General Public License for more details. <br> 054 * <br> 055 * You should have received a copy of the GNU Lesser General Public 056 * License along with this library; if not see 057 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 058 * @param <V> Variable 059 * @param <T> Value 060 **/ 061public abstract class NeighbourSearch<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V, T, NeighbourSearch<V, T>.NeighbourSearchContext> implements LazyNeighbourAcceptanceCriterion<V, T>, SolutionListener<V, T> { 062 private Logger iLog; 063 protected DecimalFormat iDF2 = new DecimalFormat("0.00"); 064 065 private Progress iProgress = null; 066 protected String iPhase = null; 067 068 private List<NeighbourSelector<V, T>> iNeighbours = null; 069 private boolean iRandomSelection = false; 070 private boolean iUpdatePoints = false; 071 private double iTotalBonus; 072 private Solver<V, T> iSolver = null; 073 074 @SuppressWarnings("unchecked") 075 public NeighbourSearch(DataProperties properties) { 076 iPhase = getClass().getSimpleName().replaceAll("(?<=[^A-Z])([A-Z])"," $1"); 077 iLog = Logger.getLogger(getClass()); 078 iRandomSelection = properties.getPropertyBoolean(getParameterBaseName() + ".Random", iRandomSelection); 079 iUpdatePoints = properties.getPropertyBoolean(getParameterBaseName() + ".Update", iUpdatePoints); 080 String neighbours = properties.getProperty(getParameterBaseName() + ".Neighbours", 081 RandomMove.class.getName() + ";" + RandomSwapMove.class.getName() + "@0.01;" + SuggestionMove.class.getName() + "@0.01"); 082 neighbours += ";" + properties.getProperty(getParameterBaseName() + ".AdditionalNeighbours", ""); 083 iNeighbours = new ArrayList<NeighbourSelector<V,T>>(); 084 for (String neighbour: neighbours.split("\\;")) { 085 if (neighbour == null || neighbour.isEmpty()) continue; 086 try { 087 double bonus = 1.0; 088 if (neighbour.indexOf('@')>=0) { 089 bonus = Double.parseDouble(neighbour.substring(neighbour.indexOf('@') + 1)); 090 neighbour = neighbour.substring(0, neighbour.indexOf('@')); 091 } 092 Class<NeighbourSelection<V, T>> clazz = (Class<NeighbourSelection<V, T>>)Class.forName(neighbour); 093 NeighbourSelection<V, T> selection = clazz.getConstructor(DataProperties.class).newInstance(properties); 094 addNeighbourSelection(selection, bonus); 095 } catch (Exception e) { 096 iLog.error("Unable to use " + neighbour + ": " + e.getMessage()); 097 } 098 } 099 } 100 101 /** 102 * Prints a message into the log 103 * @param message a message to log 104 */ 105 protected void info(String message) { 106 iProgress.debug("[" + Thread.currentThread().getName() + "] " + iPhase + "> " + message); 107 } 108 109 /** 110 * Set search progress 111 * @param progress between 0 and 100 112 */ 113 protected void setProgress(long progress) { 114 // iProgress.setProgress(progress); 115 } 116 117 /** 118 * Set search progress phase 119 * @param phase a progress phase to set 120 */ 121 protected void setProgressPhase(String phase) { 122 iProgress.info("[" + Thread.currentThread().getName() + "] " + phase); 123 // iProgress.setPhase(phase); 124 } 125 126 /** 127 * Add neighbour selection 128 * @param ns a selection 129 * @param bonus execution bonus (more bonus means more executions of this neighbour selection, see {@link NeighbourSelector}) 130 */ 131 protected void addNeighbourSelection(NeighbourSelection<V,T> ns, double bonus) { 132 iNeighbours.add(new NeighbourSelector<V,T>(ns, bonus, iUpdatePoints)); 133 } 134 135 private double totalPoints() { 136 if (!iUpdatePoints) return iTotalBonus; 137 double total = 0; 138 for (NeighbourSelector<V,T> ns: iNeighbours) 139 total += ns.getPoints(); 140 return total; 141 } 142 143 /** 144 * Set HC mode for all the neighbour selections that support the {@link HillClimberSelection} interface. 145 * @param hcMode true if the search is a hill climber (worsening moves are always rejected) 146 */ 147 protected void setHCMode(boolean hcMode) { 148 for (NeighbourSelector<V,T> s: iNeighbours) { 149 if (s.selection() instanceof HillClimberSelection) 150 ((HillClimberSelection)s.selection()).setHcMode(hcMode); 151 } 152 } 153 154 /** 155 * Return list of neighbour selections 156 * @return list of neighbour selections 157 */ 158 protected List<? extends NeighbourSelection<V, T>> getNeighbours() { 159 return iNeighbours; 160 } 161 162 @Override 163 public void init(Solver<V, T> solver) { 164 super.init(solver); 165 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 166 iSolver = solver; 167 solver.currentSolution().addSolutionListener(this); 168 // solver.setUpdateProgress(false); 169 for (NeighbourSelection<V, T> neighbour: iNeighbours) 170 neighbour.init(solver); 171 iTotalBonus = 0; 172 for (NeighbourSelector<V,T> s: iNeighbours) { 173 s.init(solver); 174 iTotalBonus += s.getBonus(); 175 } 176 } 177 178 /** 179 * Generate and return next neighbour selection 180 * @return next neighbour selection to use 181 */ 182 protected NeighbourSelection<V,T> nextNeighbourSelection() { 183 NeighbourSelector<V,T> ns = null; 184 if (iRandomSelection) { 185 ns = ToolBox.random(iNeighbours); 186 } else { 187 double points = (ToolBox.random() * totalPoints()); 188 for (Iterator<NeighbourSelector<V,T>> i = iNeighbours.iterator(); i.hasNext(); ) { 189 ns = i.next(); 190 points -= (iUpdatePoints ? ns.getPoints() : ns.getBonus()); 191 if (points <= 0) break; 192 } 193 } 194 return ns; 195 } 196 197 /** 198 * Log some information about neigbour selections once in a while 199 */ 200 protected void logNeibourStatus() { 201 if (iUpdatePoints) 202 for (NeighbourSelector<V,T> ns: iNeighbours) 203 iLog.info(" "+ns+" ("+iDF2.format(ns.getPoints())+" pts, "+iDF2.format(100.0*(iUpdatePoints?ns.getPoints():ns.getBonus())/totalPoints())+"%)"); 204 } 205 206 /** 207 * Generate a random move 208 * @param solution current solution 209 * @return generated neighbour 210 */ 211 public Neighbour<V, T> generateMove(Solution<V, T> solution) { 212 return nextNeighbourSelection().selectNeighbour(solution); 213 } 214 215 @Override 216 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 217 NeighbourSearchContext context = getContext(solution.getAssignment()); 218 context.activateIfNeeded(solution); 219 while (context.canContinue(solution)) { 220 if (iSolver != null && iSolver.isStop()) return null; 221 context.incIteration(solution); 222 Neighbour<V,T> n = generateMove(solution); 223 if (n != null && accept(context, solution, n)) 224 return n; 225 } 226 context.deactivateIfNeeded(solution); 227 return null; 228 } 229 230 /** 231 * True if the generated move is to be accepted. 232 * @param context search context 233 * @param solution current solution 234 * @param neighbour a generated move 235 * @return true if the generated move should be assigned 236 */ 237 protected boolean accept(NeighbourSearchContext context, Solution<V, T> solution, Neighbour<V, T> neighbour) { 238 if (neighbour instanceof LazyNeighbour) { 239 ((LazyNeighbour<V, T>)neighbour).setAcceptanceCriterion(this); 240 return true; 241 } 242 return context.accept(solution.getAssignment(), solution.getModel(), neighbour, neighbour.value(solution.getAssignment()), false); 243 } 244 245 /** Accept lazy neighbour -- calling the acceptance criterion with lazy = true. */ 246 @Override 247 public boolean accept(Assignment<V, T> assignment, LazyNeighbour<V, T> neighbour, double value) { 248 return getContext(assignment).accept(assignment, neighbour.getModel(), neighbour, value, true); 249 } 250 251 /** 252 * Parameter base name. This can be used to distinguish between parameters of different search algorithms. 253 * @return solver parameter base name for this search technique 254 */ 255 public abstract String getParameterBaseName(); 256 257 @Override 258 public void bestSaved(Solution<V, T> solution) { 259 getContext(solution.getAssignment()).bestSaved(solution); 260 } 261 262 @Override 263 public void solutionUpdated(Solution<V, T> solution) { 264 getContext(solution.getAssignment()).solutionUpdated(solution); 265 } 266 267 @Override 268 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 269 getContext(solution.getAssignment()).getInfo(solution, info); 270 } 271 272 @Override 273 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 274 getContext(solution.getAssignment()).getInfo(solution, info, variables); 275 } 276 277 @Override 278 public void bestCleared(Solution<V, T> solution) { 279 getContext(solution.getAssignment()).bestCleared(solution); 280 } 281 282 @Override 283 public void bestRestored(Solution<V, T> solution) { 284 getContext(solution.getAssignment()).bestRestored(solution); 285 } 286 287 /** 288 * In single solution multiple threads environments return true if the given solution is of the first thread 289 * @param solution current solution 290 * @return if the current thread is master (can alter bound etc.) 291 */ 292 public boolean isMaster(Solution<V, T> solution) { 293 return !hasContextOverride() || solution.getAssignment().getIndex() <= 1; 294 } 295 296 /** 297 * Search context 298 */ 299 public abstract class NeighbourSearchContext implements AssignmentContext, SolutionListener<V, T> { 300 protected long iT0 = -1; 301 protected int iIter = 0; 302 303 /** Called just before the neighbourhood search is called for the first time. 304 * @param solution current solution 305 **/ 306 protected void activate(Solution<V, T> solution) { 307 iT0 = JProf.currentTimeMillis(); 308 iIter = 0; 309 setProgressPhase(iPhase + "..."); 310 } 311 312 private synchronized void activateIfNeeded(Solution<V, T> solution) { 313 if (iT0 < 0) activate(solution); 314 } 315 316 /** Called when the search cannot continue, just before a null neighbour is returned 317 * @param solution current solution 318 **/ 319 protected void deactivate(Solution<V, T> solution) { 320 iT0 = -1; 321 } 322 323 private synchronized void deactivateIfNeeded(Solution<V, T> solution) { 324 if (isMaster(solution)) deactivate(solution); 325 } 326 327 /** 328 * Increment iteration counters etc. 329 * @param solution current solution 330 */ 331 protected void incIteration(Solution<V, T> solution) { 332 iIter++; 333 } 334 335 /** 336 * Running time in milliseconds (since the last call of activate) 337 * @return running time 338 */ 339 protected long getTimeMillis() { return JProf.currentTimeMillis() - iT0; } 340 341 /** 342 * Return false if the search is to be stopped. Null neighbour is returned when this method returns false. 343 * @param solution current solution 344 * @return true if can continue 345 */ 346 protected boolean canContinue(Solution<V, T> solution) { 347 return true; 348 } 349 350 /** Acceptance criterion. If lazy, current assignment already contains the given neighbour. 351 * @param assignment current assignment 352 * @param model problem model 353 * @param neighbour a generated move 354 * @param value value of the generated move (i.e., its impact on the solution value) 355 * @param lazy true if lazy move 356 * @return true if the generated move is to be assigned 357 **/ 358 protected abstract boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy); 359 360 @Override 361 public void bestSaved(Solution<V, T> solution) { 362 } 363 364 @Override 365 public void solutionUpdated(Solution<V, T> solution) { 366 } 367 368 @Override 369 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 370 } 371 372 @Override 373 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 374 } 375 376 @Override 377 public void bestCleared(Solution<V, T> solution) { 378 } 379 380 @Override 381 public void bestRestored(Solution<V, T> solution) { 382 } 383 } 384}