001package net.sf.cpsolver.exam.heuristics; 002 003import java.util.ArrayList; 004import java.util.HashSet; 005import java.util.List; 006import java.util.Set; 007import java.util.TreeSet; 008 009import net.sf.cpsolver.exam.model.Exam; 010import net.sf.cpsolver.exam.model.ExamModel; 011import net.sf.cpsolver.exam.model.ExamPeriodPlacement; 012import net.sf.cpsolver.exam.model.ExamPlacement; 013import net.sf.cpsolver.exam.model.ExamRoomPlacement; 014import net.sf.cpsolver.ifs.extension.ConflictStatistics; 015import net.sf.cpsolver.ifs.extension.Extension; 016import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 017import net.sf.cpsolver.ifs.heuristics.ValueSelection; 018import net.sf.cpsolver.ifs.model.Model; 019import net.sf.cpsolver.ifs.model.Neighbour; 020import net.sf.cpsolver.ifs.model.SimpleNeighbour; 021import net.sf.cpsolver.ifs.model.Value; 022import net.sf.cpsolver.ifs.solution.Solution; 023import net.sf.cpsolver.ifs.solver.Solver; 024import net.sf.cpsolver.ifs.util.DataProperties; 025import net.sf.cpsolver.ifs.util.ToolBox; 026 027import org.apache.log4j.Logger; 028 029/** 030 * Tabu search algorithm. <br> 031 * <br> 032 * If used as {@link NeighbourSelection}, the most improving (re)assignment of a 033 * value to a variable is returned (all variables and all their values are 034 * enumerated). If there are more than one of such assignments, one is selected 035 * randomly. A returned assignment can cause unassignment of other existing 036 * assignments. The search is stopped ( 037 * {@link ExamTabuSearch#selectNeighbour(Solution)} returns null) after 038 * TabuSearch.MaxIdle idle (not improving) iterations. <br> 039 * <br> 040 * If used as {@link ValueSelection}, the most improving (re)assignment of a 041 * value to a given variable is returned (all values of the given variable are 042 * enumerated). If there are more than one of such assignments, one is selected 043 * randomly. A returned assignment can cause unassignment of other existing 044 * assignments. <br> 045 * <br> 046 * To avoid cycling, a tabu is maintainded during the search. It is the list of 047 * the last n selected values. A selection of a value that is present in the 048 * tabu list is only allowed when it improves the best ever found solution. <br> 049 * <br> 050 * The minimum size of the tabu list is TabuSearch.MinSize, maximum size is 051 * TabuSearch.MaxSize (tabu list is not used when both sizes are zero). The 052 * current size of the tabu list starts at MinSize (and is reset to MinSize 053 * every time a new best solution is found), it is increased by one up to the 054 * MaxSize after TabuSearch.MaxIdle / (MaxSize - MinSize) non-improving 055 * iterations. <br> 056 * <br> 057 * Conflict-based Statistics {@link ConflictStatistics} (CBS) can be used 058 * instead of (or together with) tabu list, when CBS is used as a solver 059 * extension. 060 * 061 * @version ExamTT 1.2 (Examination Timetabling)<br> 062 * Copyright (C) 2008 - 2010 Tomáš Müller<br> 063 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 064 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 065 * <br> 066 * This library is free software; you can redistribute it and/or modify 067 * it under the terms of the GNU Lesser General Public License as 068 * published by the Free Software Foundation; either version 3 of the 069 * License, or (at your option) any later version. <br> 070 * <br> 071 * This library is distributed in the hope that it will be useful, but 072 * WITHOUT ANY WARRANTY; without even the implied warranty of 073 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 074 * Lesser General Public License for more details. <br> 075 * <br> 076 * You should have received a copy of the GNU Lesser General Public 077 * License along with this library; if not see 078 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 079 */ 080public class ExamTabuSearch implements NeighbourSelection<Exam, ExamPlacement>, ValueSelection<Exam, ExamPlacement> { 081 private static Logger sLog = Logger.getLogger(ExamTabuSearch.class); 082 private ConflictStatistics<Exam, ExamPlacement> iStat = null; 083 084 private long iFirstIteration = -1; 085 private long iMaxIdleIterations = 10000; 086 087 private int iTabuMinSize = 0; 088 private int iTabuMaxSize = 0; 089 private TabuList iTabu = null; 090 091 private double iConflictWeight = 1000000; 092 private double iValueWeight = 1; 093 094 /** 095 * <ul> 096 * <li>TabuSearch.MaxIdle ... maximum number of idle iterations (default is 097 * 10000) 098 * <li>TabuSearch.MinSize ... minimum size of the tabu list 099 * <li>TabuSearch.MaxSize ... maximum size of the tabu list 100 * <li>Value.ValueWeight ... weight of a value (i.e., 101 * {@link Value#toDouble()}) 102 * <li>Value.ConflictWeight ... weight of a conflicting value (see 103 * {@link Model#conflictValues(Value)}), it is also weighted by the past 104 * occurrences when conflict-based statistics is used 105 * </ul> 106 */ 107 public ExamTabuSearch(DataProperties properties) throws Exception { 108 iTabuMinSize = properties.getPropertyInt("TabuSearch.MinSize", iTabuMinSize); 109 iTabuMaxSize = properties.getPropertyInt("TabuSearch.MaxSize", iTabuMaxSize); 110 if (iTabuMaxSize > 0) 111 iTabu = new TabuList(iTabuMinSize); 112 iMaxIdleIterations = properties.getPropertyLong("TabuSearch.MaxIdle", iMaxIdleIterations); 113 iConflictWeight = properties.getPropertyDouble("Value.ConflictWeight", iConflictWeight); 114 iValueWeight = properties.getPropertyDouble("Value.ValueWeight", iValueWeight); 115 } 116 117 /** Initialization */ 118 @Override 119 public void init(Solver<Exam, ExamPlacement> solver) { 120 for (Extension<Exam, ExamPlacement> extension : solver.getExtensions()) { 121 if (ConflictStatistics.class.isInstance(extension)) 122 iStat = (ConflictStatistics<Exam, ExamPlacement>) extension; 123 } 124 } 125 126 /** 127 * Neighbor selection 128 */ 129 @Override 130 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 131 if (iFirstIteration < 0) 132 iFirstIteration = solution.getIteration(); 133 long idle = solution.getIteration() - Math.max(iFirstIteration, solution.getBestIteration()); 134 if (idle > iMaxIdleIterations) { 135 sLog.debug(" [tabu] max idle iterations reached"); 136 iFirstIteration = -1; 137 if (iTabu != null) 138 iTabu.clear(); 139 return null; 140 } 141 if (iTabu != null && iTabuMaxSize > iTabuMinSize) { 142 if (idle == 0) { 143 iTabu.resize(iTabuMinSize); 144 } else if (idle % (iMaxIdleIterations / (iTabuMaxSize - iTabuMinSize)) == 0) { 145 iTabu.resize(Math.min(iTabuMaxSize, iTabu.size() + 1)); 146 } 147 } 148 149 boolean acceptConflicts = solution.getModel().getBestUnassignedVariables() > 0; 150 ExamModel model = (ExamModel) solution.getModel(); 151 double bestEval = 0.0; 152 List<ExamPlacement> best = null; 153 for (Exam exam : model.variables()) { 154 ExamPlacement assigned = exam.getAssignment(); 155 double assignedVal = (assigned == null ? iConflictWeight : iValueWeight * assigned.toDouble()); 156 for (ExamPeriodPlacement period : exam.getPeriodPlacements()) { 157 Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(period); 158 if (rooms == null) 159 rooms = exam.findRoomsRandom(period, false); 160 if (rooms == null) 161 continue; 162 ExamPlacement value = new ExamPlacement(exam, period, rooms); 163 if (value.equals(assigned)) 164 continue; 165 double eval = iValueWeight * value.toDouble() - assignedVal; 166 if (acceptConflicts) { 167 Set<ExamPlacement> conflicts = model.conflictValues(value); 168 for (ExamPlacement conflict : conflicts) { 169 eval -= iValueWeight * conflict.toDouble(); 170 eval += iConflictWeight 171 * (1.0 + (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflict, 172 value))); 173 } 174 } else { 175 if (model.inConflict(value)) 176 continue; 177 } 178 if (iTabu != null && iTabu.contains(exam.getId() + ":" + value.getPeriod().getIndex())) { 179 int un = model.nrUnassignedVariables() - (assigned == null ? 0 : 1); 180 if (un > model.getBestUnassignedVariables()) 181 continue; 182 if (un == model.getBestUnassignedVariables() 183 && model.getTotalValue() + eval >= solution.getBestValue()) 184 continue; 185 } 186 if (best == null || bestEval > eval) { 187 if (best == null) 188 best = new ArrayList<ExamPlacement>(); 189 else 190 best.clear(); 191 best.add(value); 192 bestEval = eval; 193 } else if (bestEval == eval) { 194 best.add(value); 195 } 196 } 197 } 198 199 if (best == null) { 200 sLog.debug(" [tabu] --none--"); 201 iFirstIteration = -1; 202 if (iTabu != null) 203 iTabu.clear(); 204 return null; 205 } 206 ExamPlacement bestVal = ToolBox.random(best); 207 208 if (sLog.isDebugEnabled()) { 209 Set<ExamPlacement> conflicts = model.conflictValues(bestVal); 210 double wconf = (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflicts, bestVal)); 211 sLog.debug(" [tabu] " 212 + bestVal 213 + " (" 214 + (bestVal.variable().getAssignment() == null ? "" : "was=" + bestVal.variable().getAssignment() 215 + ", ") + "val=" + bestEval 216 + (conflicts.isEmpty() ? "" : ", conf=" + (wconf + conflicts.size()) + "/" + conflicts) + ")"); 217 } 218 219 if (iTabu != null) 220 iTabu.add(bestVal.variable().getId() + ":" + bestVal.getPeriod().getIndex()); 221 222 return new SimpleNeighbour<Exam, ExamPlacement>(bestVal.variable(), bestVal); 223 } 224 225 /** 226 * Value selection 227 */ 228 @Override 229 public ExamPlacement selectValue(Solution<Exam, ExamPlacement> solution, Exam exam) { 230 if (iFirstIteration < 0) 231 iFirstIteration = solution.getIteration(); 232 long idle = solution.getIteration() - Math.max(iFirstIteration, solution.getBestIteration()); 233 if (idle > iMaxIdleIterations) { 234 sLog.debug(" [tabu] max idle iterations reached"); 235 iFirstIteration = -1; 236 if (iTabu != null) 237 iTabu.clear(); 238 return null; 239 } 240 if (iTabu != null && iTabuMaxSize > iTabuMinSize) { 241 if (idle == 0) { 242 iTabu.resize(iTabuMinSize); 243 } else if (idle % (iMaxIdleIterations / (iTabuMaxSize - iTabuMinSize)) == 0) { 244 iTabu.resize(Math.min(iTabuMaxSize, iTabu.size() + 1)); 245 } 246 } 247 248 ExamModel model = (ExamModel) solution.getModel(); 249 double bestEval = 0.0; 250 List<ExamPlacement> best = null; 251 252 ExamPlacement assigned = exam.getAssignment(); 253 // double assignedVal = 254 // (assigned==null?-iConflictWeight:iValueWeight*assigned.toDouble()); 255 double assignedVal = (assigned == null ? iConflictWeight : iValueWeight * assigned.toDouble()); 256 for (ExamPeriodPlacement period : exam.getPeriodPlacements()) { 257 Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(period); 258 if (rooms == null) 259 rooms = exam.findRoomsRandom(period, false); 260 if (rooms == null) { 261 sLog.info("Exam " + exam.getName() + " has no rooms for period " + period); 262 continue; 263 } 264 ExamPlacement value = new ExamPlacement(exam, period, rooms); 265 if (value.equals(assigned)) 266 continue; 267 Set<ExamPlacement> conflicts = model.conflictValues(value); 268 double eval = iValueWeight * value.toDouble() - assignedVal; 269 for (ExamPlacement conflict : conflicts) { 270 eval -= iValueWeight * conflict.toDouble(); 271 eval += iConflictWeight 272 * (1.0 + (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflict, value))); 273 } 274 if (iTabu != null && iTabu.contains(exam.getId() + ":" + value.getPeriod().getIndex())) { 275 int un = model.nrUnassignedVariables() - (assigned == null ? 0 : 1); 276 if (un > model.getBestUnassignedVariables()) 277 continue; 278 if (un == model.getBestUnassignedVariables() && model.getTotalValue() + eval >= solution.getBestValue()) 279 continue; 280 } 281 if (best == null || bestEval > eval) { 282 if (best == null) 283 best = new ArrayList<ExamPlacement>(); 284 else 285 best.clear(); 286 best.add(value); 287 bestEval = eval; 288 } else if (bestEval == eval) { 289 best.add(value); 290 } 291 } 292 293 if (best == null) 294 return null; 295 ExamPlacement bestVal = ToolBox.random(best); 296 297 if (sLog.isDebugEnabled()) { 298 Set<ExamPlacement> conflicts = model.conflictValues(bestVal); 299 double wconf = (iStat == null ? 0.0 : iStat.countRemovals(solution.getIteration(), conflicts, bestVal)); 300 sLog.debug(" [tabu] " 301 + bestVal 302 + " (" 303 + (bestVal.variable().getAssignment() == null ? "" : "was=" + bestVal.variable().getAssignment() 304 + ", ") + "val=" + bestEval 305 + (conflicts.isEmpty() ? "" : ", conf=" + (wconf + conflicts.size()) + "/" + conflicts) + ")"); 306 } 307 308 if (iTabu != null) 309 iTabu.add(exam.getId() + ":" + bestVal.getPeriod().getIndex()); 310 311 return bestVal; 312 } 313 314 /** Tabu-list */ 315 private static class TabuList { 316 private HashSet<TabuItem> iList = new HashSet<TabuItem>(); 317 private int iSize; 318 private long iIteration = 0; 319 320 public TabuList(int size) { 321 iSize = size; 322 } 323 324 public Object add(Object object) { 325 if (iSize == 0) 326 return object; 327 if (contains(object)) { 328 iList.remove(new TabuItem(object, 0)); 329 iList.add(new TabuItem(object, iIteration++)); 330 return null; 331 } else { 332 Object oldest = null; 333 if (iList.size() >= iSize) 334 oldest = removeOldest(); 335 iList.add(new TabuItem(object, iIteration++)); 336 return oldest; 337 } 338 } 339 340 public void resize(int newSize) { 341 iSize = newSize; 342 while (iList.size() > newSize) 343 removeOldest(); 344 } 345 346 public boolean contains(Object object) { 347 return iList.contains(new TabuItem(object, 0)); 348 } 349 350 public void clear() { 351 iList.clear(); 352 } 353 354 public int size() { 355 return iSize; 356 } 357 358 public Object removeOldest() { 359 TabuItem oldest = null; 360 for (TabuItem element : iList) { 361 if (oldest == null || oldest.getIteration() > element.getIteration()) 362 oldest = element; 363 } 364 if (oldest == null) 365 return null; 366 iList.remove(oldest); 367 return oldest.getObject(); 368 } 369 370 @Override 371 public String toString() { 372 return new TreeSet<TabuItem>(iList).toString(); 373 } 374 } 375 376 /** Tabu item (an item in {@link TabuList}) */ 377 private static class TabuItem implements Comparable<TabuItem> { 378 private Object iObject; 379 private long iIteration; 380 381 public TabuItem(Object object, long iteration) { 382 iObject = object; 383 iIteration = iteration; 384 } 385 386 public Object getObject() { 387 return iObject; 388 } 389 390 public long getIteration() { 391 return iIteration; 392 } 393 394 @Override 395 public boolean equals(Object object) { 396 if (object == null || !(object instanceof TabuItem)) 397 return false; 398 return getObject().equals(((TabuItem) object).getObject()); 399 } 400 401 @Override 402 public int hashCode() { 403 return getObject().hashCode(); 404 } 405 406 @Override 407 public int compareTo(TabuItem o) { 408 return Double.compare(getIteration(), o.getIteration()); 409 } 410 411 @Override 412 public String toString() { 413 return getObject().toString(); 414 } 415 } 416}