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