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 Tomas Muller<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 073 @SuppressWarnings("unchecked") 074 public NeighbourSearch(DataProperties properties) { 075 iPhase = getClass().getSimpleName().replaceAll("(?<=[^A-Z])([A-Z])"," $1"); 076 iLog = Logger.getLogger(getClass()); 077 iRandomSelection = properties.getPropertyBoolean(getParameterBaseName() + ".Random", iRandomSelection); 078 iUpdatePoints = properties.getPropertyBoolean(getParameterBaseName() + ".Update", iUpdatePoints); 079 String neighbours = properties.getProperty(getParameterBaseName() + ".Neighbours", 080 RandomMove.class.getName() + ";" + RandomSwapMove.class.getName() + "@0.01;" + SuggestionMove.class.getName() + "@0.01"); 081 neighbours += ";" + properties.getProperty(getParameterBaseName() + ".AdditionalNeighbours", ""); 082 iNeighbours = new ArrayList<NeighbourSelector<V,T>>(); 083 for (String neighbour: neighbours.split("\\;")) { 084 if (neighbour == null || neighbour.isEmpty()) continue; 085 try { 086 double bonus = 1.0; 087 if (neighbour.indexOf('@')>=0) { 088 bonus = Double.parseDouble(neighbour.substring(neighbour.indexOf('@') + 1)); 089 neighbour = neighbour.substring(0, neighbour.indexOf('@')); 090 } 091 Class<NeighbourSelection<V, T>> clazz = (Class<NeighbourSelection<V, T>>)Class.forName(neighbour); 092 NeighbourSelection<V, T> selection = clazz.getConstructor(DataProperties.class).newInstance(properties); 093 addNeighbourSelection(selection, bonus); 094 } catch (Exception e) { 095 iLog.error("Unable to use " + neighbour + ": " + e.getMessage()); 096 } 097 } 098 } 099 100 /** 101 * Prints a message into the log 102 * @param message a message to log 103 */ 104 protected void info(String message) { 105 iProgress.debug("[" + Thread.currentThread().getName() + "] " + iPhase + "> " + message); 106 } 107 108 /** 109 * Set search progress 110 * @param progress between 0 and 100 111 */ 112 protected void setProgress(long progress) { 113 // iProgress.setProgress(progress); 114 } 115 116 /** 117 * Set search progress phase 118 * @param phase a progress phase to set 119 */ 120 protected void setProgressPhase(String phase) { 121 iProgress.info("[" + Thread.currentThread().getName() + "] " + phase); 122 // iProgress.setPhase(phase); 123 } 124 125 /** 126 * Add neighbour selection 127 * @param ns a selection 128 * @param bonus execution bonus (more bonus means more executions of this neighbour selection, see {@link NeighbourSelector}) 129 */ 130 protected void addNeighbourSelection(NeighbourSelection<V,T> ns, double bonus) { 131 iNeighbours.add(new NeighbourSelector<V,T>(ns, bonus, iUpdatePoints)); 132 } 133 134 private double totalPoints() { 135 if (!iUpdatePoints) return iTotalBonus; 136 double total = 0; 137 for (NeighbourSelector<V,T> ns: iNeighbours) 138 total += ns.getPoints(); 139 return total; 140 } 141 142 /** 143 * Set HC mode for all the neighbour selections that support the {@link HillClimberSelection} interface. 144 * @param hcMode true if the search is a hill climber (worsening moves are always rejected) 145 */ 146 protected void setHCMode(boolean hcMode) { 147 for (NeighbourSelector<V,T> s: iNeighbours) { 148 if (s.selection() instanceof HillClimberSelection) 149 ((HillClimberSelection)s.selection()).setHcMode(hcMode); 150 } 151 } 152 153 /** 154 * Return list of neighbour selections 155 * @return list of neighbour selections 156 */ 157 protected List<? extends NeighbourSelection<V, T>> getNeighbours() { 158 return iNeighbours; 159 } 160 161 @Override 162 public void init(Solver<V, T> solver) { 163 super.init(solver); 164 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 165 solver.currentSolution().addSolutionListener(this); 166 // solver.setUpdateProgress(false); 167 for (NeighbourSelection<V, T> neighbour: iNeighbours) 168 neighbour.init(solver); 169 iTotalBonus = 0; 170 for (NeighbourSelector<V,T> s: iNeighbours) { 171 s.init(solver); 172 iTotalBonus += s.getBonus(); 173 } 174 } 175 176 /** 177 * Generate and return next neighbour selection 178 * @return next neighbour selection to use 179 */ 180 protected NeighbourSelection<V,T> nextNeighbourSelection() { 181 NeighbourSelector<V,T> ns = null; 182 if (iRandomSelection) { 183 ns = ToolBox.random(iNeighbours); 184 } else { 185 double points = (ToolBox.random() * totalPoints()); 186 for (Iterator<NeighbourSelector<V,T>> i = iNeighbours.iterator(); i.hasNext(); ) { 187 ns = i.next(); 188 points -= (iUpdatePoints ? ns.getPoints() : ns.getBonus()); 189 if (points <= 0) break; 190 } 191 } 192 return ns; 193 } 194 195 /** 196 * Log some information about neigbour selections once in a while 197 */ 198 protected void logNeibourStatus() { 199 if (iUpdatePoints) 200 for (NeighbourSelector<V,T> ns: iNeighbours) 201 iLog.info(" "+ns+" ("+iDF2.format(ns.getPoints())+" pts, "+iDF2.format(100.0*(iUpdatePoints?ns.getPoints():ns.getBonus())/totalPoints())+"%)"); 202 } 203 204 /** 205 * Generate a random move 206 * @param solution current solution 207 * @return generated neighbour 208 */ 209 public Neighbour<V, T> generateMove(Solution<V, T> solution) { 210 return nextNeighbourSelection().selectNeighbour(solution); 211 } 212 213 @Override 214 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 215 NeighbourSearchContext context = getContext(solution.getAssignment()); 216 context.activateIfNeeded(solution); 217 while (context.canContinue(solution)) { 218 context.incIteration(solution); 219 Neighbour<V,T> n = generateMove(solution); 220 if (n != null && accept(context, solution, n)) 221 return n; 222 } 223 context.deactivate(solution); 224 return null; 225 } 226 227 /** 228 * True if the generated move is to be accepted. 229 * @param context search context 230 * @param solution current solution 231 * @param neighbour a generated move 232 * @return true if the generated move should be assigned 233 */ 234 protected boolean accept(NeighbourSearchContext context, Solution<V, T> solution, Neighbour<V, T> neighbour) { 235 if (neighbour instanceof LazyNeighbour) { 236 ((LazyNeighbour<V, T>)neighbour).setAcceptanceCriterion(this); 237 return true; 238 } 239 return context.accept(solution.getAssignment(), solution.getModel(), neighbour, neighbour.value(solution.getAssignment()), false); 240 } 241 242 /** Accept lazy neighbour -- calling the acceptance criterion with lazy = true. */ 243 @Override 244 public boolean accept(Assignment<V, T> assignment, LazyNeighbour<V, T> neighbour, double value) { 245 return getContext(assignment).accept(assignment, neighbour.getModel(), neighbour, value, true); 246 } 247 248 /** 249 * Parameter base name. This can be used to distinguish between parameters of different search algorithms. 250 * @return solver parameter base name for this search technique 251 */ 252 public abstract String getParameterBaseName(); 253 254 @Override 255 public void bestSaved(Solution<V, T> solution) { 256 getContext(solution.getAssignment()).bestSaved(solution); 257 } 258 259 @Override 260 public void solutionUpdated(Solution<V, T> solution) { 261 getContext(solution.getAssignment()).solutionUpdated(solution); 262 } 263 264 @Override 265 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 266 getContext(solution.getAssignment()).getInfo(solution, info); 267 } 268 269 @Override 270 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 271 getContext(solution.getAssignment()).getInfo(solution, info, variables); 272 } 273 274 @Override 275 public void bestCleared(Solution<V, T> solution) { 276 getContext(solution.getAssignment()).bestCleared(solution); 277 } 278 279 @Override 280 public void bestRestored(Solution<V, T> solution) { 281 getContext(solution.getAssignment()).bestRestored(solution); 282 } 283 284 /** 285 * Search context 286 */ 287 public abstract class NeighbourSearchContext implements AssignmentContext, SolutionListener<V, T> { 288 protected long iT0 = -1; 289 protected int iIter = 0; 290 291 /** Called just before the neighbourhood search is called for the first time. 292 * @param solution current solution 293 **/ 294 protected void activate(Solution<V, T> solution) { 295 iT0 = JProf.currentTimeMillis(); 296 iIter = 0; 297 setProgressPhase(iPhase + "..."); 298 } 299 300 private void activateIfNeeded(Solution<V, T> solution) { 301 if (iT0 < 0) activate(solution); 302 } 303 304 /** Called when the search cannot continue, just before a null neighbour is returned 305 * @param solution current solution 306 **/ 307 protected void deactivate(Solution<V, T> solution) { 308 iT0 = -1; 309 } 310 311 /** 312 * Increment iteration counters etc. 313 * @param solution current solution 314 */ 315 protected void incIteration(Solution<V, T> solution) { 316 iIter++; 317 } 318 319 /** 320 * Running time in milliseconds (since the last call of activate) 321 * @return running time 322 */ 323 protected long getTimeMillis() { return JProf.currentTimeMillis() - iT0; } 324 325 /** 326 * Return false if the search is to be stopped. Null neighbour is returned when this method returns false. 327 * @param solution current solution 328 * @return true if can continue 329 */ 330 protected boolean canContinue(Solution<V, T> solution) { 331 return true; 332 } 333 334 /** Acceptance criterion. If lazy, current assignment already contains the given neighbour. 335 * @param assignment current assignment 336 * @param model problem model 337 * @param neighbour a generated move 338 * @param value value of the generated move (i.e., its impact on the solution value) 339 * @param lazy true if lazy move 340 * @return true if the generated move is to be assigned 341 **/ 342 protected abstract boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy); 343 344 @Override 345 public void bestSaved(Solution<V, T> solution) { 346 } 347 348 @Override 349 public void solutionUpdated(Solution<V, T> solution) { 350 } 351 352 @Override 353 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 354 } 355 356 @Override 357 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 358 } 359 360 @Override 361 public void bestCleared(Solution<V, T> solution) { 362 } 363 364 @Override 365 public void bestRestored(Solution<V, T> solution) { 366 } 367 } 368}