001package net.sf.cpsolver.coursett.heuristics; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.Iterator; 006import java.util.List; 007 008import net.sf.cpsolver.coursett.model.Lecture; 009import net.sf.cpsolver.coursett.model.Placement; 010import net.sf.cpsolver.coursett.model.TimetableModel; 011import net.sf.cpsolver.ifs.extension.Extension; 012import net.sf.cpsolver.ifs.extension.MacPropagation; 013import net.sf.cpsolver.ifs.heuristics.VariableSelection; 014import net.sf.cpsolver.ifs.solution.Solution; 015import net.sf.cpsolver.ifs.solver.Solver; 016import net.sf.cpsolver.ifs.util.DataProperties; 017import net.sf.cpsolver.ifs.util.ToolBox; 018 019/** 020 * Lecture (variable) selection. <br> 021 * <br> 022 * If there are one or more variables unassigned, the variable selection 023 * criterion picks one of them randomly. We have tried several approaches using 024 * domain sizes, number of previous assignments, numbers of constraints in which 025 * the variable participates, etc., but there was no significant improvement in 026 * this timetabling problem towards the random selection of an unassigned 027 * variable. The reason is, that it is easy to go back when a wrong variable is 028 * picked - such a variable is unassigned when there is a conflict with it in 029 * some of the subsequent iterations. <br> 030 * <br> 031 * When all variables are assigned, an evaluation is made for each variable 032 * according to the above described weights. The variable with the worst 033 * evaluation is selected. This variable promises the best improvement in 034 * optimization. <br> 035 * <br> 036 * Parameters (selection among unassigned lectures): 037 * <table border='1'> 038 * <tr> 039 * <th>Parameter</th> 040 * <th>Type</th> 041 * <th>Comment</th> 042 * </tr> 043 * <tr> 044 * <td>Lecture.RouletteWheelSelection</td> 045 * <td>{@link Boolean}</td> 046 * <td>Roulette wheel selection</td> 047 * </tr> 048 * <tr> 049 * <td>Lecture.RandomWalkProb</td> 050 * <td>{@link Double}</td> 051 * <td>Random walk probability</td> 052 * </tr> 053 * <tr> 054 * <td>Lecture.DomainSizeWeight</td> 055 * <td>{@link Double}</td> 056 * <td>Domain size weight</td> 057 * </tr> 058 * <tr> 059 * <td>Lecture.NrAssignmentsWeight</td> 060 * <td>{@link Double}</td> 061 * <td>Number of assignments weight</td> 062 * </tr> 063 * <tr> 064 * <td>Lecture.InitialAssignmentWeight</td> 065 * <td>{@link Double}</td> 066 * <td>Initial assignment weight</td> 067 * </tr> 068 * <tr> 069 * <td>Lecture.NrConstraintsWeight</td> 070 * <td>{@link Double}</td> 071 * <td>Number of constraint weight</td> 072 * </tr> 073 * </table> 074 * <br> 075 * Parameters (selection among assigned lectures, when the solution is 076 * complete): 077 * <table border='1'> 078 * <tr> 079 * <th>Parameter</th> 080 * <th>Type</th> 081 * <th>Comment</th> 082 * </tr> 083 * <tr> 084 * <td>Comparator.HardStudentConflictWeight</td> 085 * <td>{@link Double}</td> 086 * <td>Hard student conflict weight</td> 087 * </tr> 088 * <tr> 089 * <td>Comparator.StudentConflictWeight</td> 090 * <td>{@link Double}</td> 091 * <td>Student conflict weight</td> 092 * </tr> 093 * <tr> 094 * <td>Comparator.TimePreferenceWeight</td> 095 * <td>{@link Double}</td> 096 * <td>Time preference weight</td> 097 * </tr> 098 * <tr> 099 * <td>Comparator.ContrPreferenceWeight</td> 100 * <td>{@link Double}</td> 101 * <td>Group constraint preference weight</td> 102 * </tr> 103 * <tr> 104 * <td>Comparator.RoomPreferenceWeight</td> 105 * <td>{@link Double}</td> 106 * <td>Room preference weight</td> 107 * </tr> 108 * <tr> 109 * <td>Comparator.UselessSlotWeight</td> 110 * <td>{@link Double}</td> 111 * <td>Useless slot weight</td> 112 * </tr> 113 * <tr> 114 * <td>Comparator.TooBigRoomWeight</td> 115 * <td>{@link Double}</td> 116 * <td>Too big room weight</td> 117 * </tr> 118 * <tr> 119 * <td>Comparator.DistanceInstructorPreferenceWeight</td> 120 * <td>{@link Double}</td> 121 * <td>Distance (of the rooms of the back-to-back classes) based instructor 122 * preferences weight</td> 123 * </tr> 124 * <tr> 125 * <td>Comparator.DeptSpreadPenaltyWeight</td> 126 * <td>{@link Double}</td> 127 * <td>Department balancing penalty (see 128 * {@link net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint})</td> 129 * </tr> 130 * </table> 131 * <br> 132 * Parameters (selection among subset of lectures (faster)): 133 * <table border='1'> 134 * <tr> 135 * <th>Parameter</th> 136 * <th>Type</th> 137 * <th>Comment</th> 138 * </tr> 139 * <tr> 140 * <td>Lecture.SelectionSubSet</td> 141 * <td>{@link Boolean}</td> 142 * <td>Selection among subset of lectures (faster)</td> 143 * </tr> 144 * <tr> 145 * <td>Lecture.SelectionSubSetMinSize</td> 146 * <td>{@link Double}</td> 147 * <td>Minimal subset size</td> 148 * </tr> 149 * <tr> 150 * <td>Lecture.SelectionSubSetPart</td> 151 * <td>{@link Double}</td> 152 * <td>Subset size in percentage of all lectures available for selection</td> 153 * </tr> 154 * </table> 155 * 156 * @see PlacementSelection 157 * @version CourseTT 1.2 (University Course Timetabling)<br> 158 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 159 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 160 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 161 * <br> 162 * This library is free software; you can redistribute it and/or modify 163 * it under the terms of the GNU Lesser General Public License as 164 * published by the Free Software Foundation; either version 3 of the 165 * License, or (at your option) any later version. <br> 166 * <br> 167 * This library is distributed in the hope that it will be useful, but 168 * WITHOUT ANY WARRANTY; without even the implied warranty of 169 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 170 * Lesser General Public License for more details. <br> 171 * <br> 172 * You should have received a copy of the GNU Lesser General Public 173 * License along with this library; if not see 174 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 175 */ 176public class LectureSelection implements VariableSelection<Lecture, Placement> { 177 private double iRandomWalkProb; 178 private double iDomainSizeWeight; 179 private double iGoodValuesWeight; 180 private double iNrAssignmentsWeight; 181 private double iConstraintsWeight; 182 private double iInitialAssignmentWeight; 183 private boolean iRouletteWheelSelection; 184 private boolean iUnassignWhenNotGood; 185 186 private boolean iSubSetSelection; 187 private double iSelectionSubSetPart; 188 private int iSelectionSubSetMinSize; 189 private boolean iInteractiveMode; 190 191 private boolean iRW = false; 192 private boolean iMPP = false; 193 194 private MacPropagation<Lecture, Placement> iProp = null; 195 196 private int iTabuSize = 0; 197 private ArrayList<Lecture> iTabu = null; 198 private int iTabuPos = 0; 199 200 private int iVariableChanceIteration = 1000; 201 private double iVariableChanceProb = 0.05; 202 203 public LectureSelection(DataProperties properties) { 204 iRouletteWheelSelection = properties.getPropertyBoolean("Lecture.RouletteWheelSelection", true); 205 iUnassignWhenNotGood = properties.getPropertyBoolean("Lecture.UnassignWhenNotGood", false); 206 iRW = properties.getPropertyBoolean("General.RandomWalk", true); 207 iRandomWalkProb = (!iRW ? 0.0 : properties.getPropertyDouble("Lecture.RandomWalkProb", 1.00)); 208 iGoodValuesWeight = properties.getPropertyDouble("Lecture.GoodValueProb", 1.0); 209 iDomainSizeWeight = properties.getPropertyDouble("Lecture.DomainSizeWeight", 30.0); 210 211 iInteractiveMode = properties.getPropertyBoolean("General.InteractiveMode", false); 212 213 iNrAssignmentsWeight = properties.getPropertyDouble("Lecture.NrAssignmentsWeight", 10.0); 214 iConstraintsWeight = properties.getPropertyDouble("Lecture.NrConstraintsWeight", 0.0); 215 iMPP = properties.getPropertyBoolean("General.MPP", false); 216 iInitialAssignmentWeight = (!iMPP ? 0.0 : properties.getPropertyDouble("Lecture.InitialAssignmentWeight", 20.0)); 217 218 iSubSetSelection = properties.getPropertyBoolean("Lecture.SelectionSubSet", true); 219 iSelectionSubSetMinSize = properties.getPropertyInt("Lecture.SelectionSubSetMinSize", 10); 220 iSelectionSubSetPart = properties.getPropertyDouble("Lecture.SelectionSubSetPart", 0.2); 221 222 iTabuSize = properties.getPropertyInt("Lecture.TabuSize", 20); 223 if (iTabuSize > 0) 224 iTabu = new ArrayList<Lecture>(iTabuSize); 225 226 iVariableChanceIteration = properties.getPropertyInt("Lecture.VariableChanceIteration", 1000); 227 iVariableChanceProb = properties.getPropertyDouble("Lecture.VariableChanceProb", 0.05); 228 } 229 230 @Override 231 public void init(Solver<Lecture, Placement> solver) { 232 for (Extension<Lecture, Placement> extension : solver.getExtensions()) { 233 if (MacPropagation.class.isInstance(extension)) 234 iProp = (MacPropagation<Lecture, Placement>) extension; 235 } 236 } 237 238 @Override 239 public Lecture selectVariable(Solution<Lecture, Placement> solution) { 240 TimetableModel model = (TimetableModel) solution.getModel(); 241 Collection<Lecture> unassignedVariables = model.unassignedVariables(); 242 if (iInteractiveMode) { 243 // remove variables that have no values 244 unassignedVariables = new ArrayList<Lecture>(unassignedVariables.size()); 245 for (Lecture variable : model.unassignedVariables()) { 246 if (!variable.values().isEmpty()) 247 unassignedVariables.add(variable); 248 } 249 } 250 251 if (unassignedVariables.isEmpty()) { 252 Collection<Lecture> variables = model.perturbVariables(); 253 if (variables.isEmpty()) 254 variables = model.assignedVariables(); 255 256 if (iRW && ToolBox.random() <= iRandomWalkProb) 257 return ToolBox.random(variables); 258 259 List<Lecture> selectionVariables = new ArrayList<Lecture>(); 260 double worstValue = 0.0; 261 262 for (Iterator<Lecture> i1 = (iSubSetSelection ? ToolBox.subSet(variables, iSelectionSubSetPart, 263 iSelectionSubSetMinSize) : variables).iterator(); i1.hasNext();) { 264 Lecture selectedVariable = i1.next(); 265 266 if (iTabu != null && iTabu.contains(selectedVariable)) 267 continue; 268 269 double value = selectedVariable.getAssignment().toDouble(); 270 271 if (selectionVariables.isEmpty() || value > worstValue) { 272 selectionVariables.clear(); 273 selectionVariables.add(selectedVariable); 274 worstValue = value; 275 } else if (worstValue == value) { 276 selectionVariables.add(selectedVariable); 277 } 278 } 279 280 Lecture selectedVariable = ToolBox.random(selectionVariables); 281 282 if (selectedVariable == null) 283 selectedVariable = ToolBox.random(variables); 284 285 if (selectedVariable != null && iTabu != null) { 286 if (iTabu.size() == iTabuPos) 287 iTabu.add(selectedVariable); 288 else 289 iTabu.set(iTabuPos, selectedVariable); 290 iTabuPos = (iTabuPos + 1) % iTabuSize; 291 } 292 293 return selectedVariable; 294 } else { 295 if (iVariableChanceIteration > 0) { 296 List<Lecture> variablesWithChance = new ArrayList<Lecture>(unassignedVariables.size()); 297 for (Lecture v : unassignedVariables) { 298 if (v.countAssignments() > iVariableChanceIteration) 299 continue; 300 variablesWithChance.add(v); 301 } 302 303 if (variablesWithChance.isEmpty() && ToolBox.random() <= iVariableChanceProb 304 && !model.assignedVariables().isEmpty()) 305 return ToolBox.random(model.assignedVariables()); 306 307 if (ToolBox.random() <= iRandomWalkProb) { 308 if (!variablesWithChance.isEmpty()) 309 return ToolBox.random(variablesWithChance); 310 else 311 return ToolBox.random(unassignedVariables); 312 } 313 } else { 314 if (ToolBox.random() <= iRandomWalkProb) 315 return ToolBox.random(unassignedVariables); 316 } 317 318 if (iProp != null && iUnassignWhenNotGood) { 319 List<Lecture> noGoodVariables = new ArrayList<Lecture>(); 320 for (Iterator<Lecture> i1 = ToolBox.subSet(unassignedVariables, iSelectionSubSetPart, 321 iSelectionSubSetMinSize).iterator(); i1.hasNext();) { 322 Lecture variable = i1.next(); 323 if (iProp.goodValues(variable).isEmpty()) 324 noGoodVariables.add(variable); 325 } 326 if (!noGoodVariables.isEmpty()) { 327 if (ToolBox.random() < 0.02) 328 return ToolBox.random(model.assignedVariables()); 329 for (int attempt = 0; attempt < 10; attempt++) { 330 Lecture noGoodVariable = ToolBox.random(noGoodVariables); 331 Placement noGoodValue = ToolBox.random(noGoodVariable.values()); 332 if (!iProp.noGood(noGoodValue).isEmpty()) 333 return ToolBox.random(iProp.noGood(noGoodValue)).variable(); 334 } 335 } 336 } 337 338 if (iRouletteWheelSelection) { 339 int iMaxDomainSize = 0; 340 int iMaxGoodDomainSize = 0; 341 int iMaxConstraints = 0; 342 long iMaxNrAssignments = 0; 343 Collection<Lecture> variables = (iSubSetSelection ? ToolBox.subSet(unassignedVariables, 344 iSelectionSubSetPart, iSelectionSubSetMinSize) : unassignedVariables); 345 for (Lecture variable : variables) { 346 347 if (iTabu != null && iTabu.contains(variable)) 348 continue; 349 350 iMaxDomainSize = Math.max(iMaxDomainSize, variable.values().size()); 351 iMaxGoodDomainSize = (iProp == null ? 0 : Math.max(iMaxGoodDomainSize, iProp.goodValues(variable) 352 .size())); 353 iMaxConstraints = Math.max(iMaxConstraints, variable.constraints().size()); 354 iMaxNrAssignments = Math.max(iMaxNrAssignments, variable.countAssignments()); 355 } 356 357 List<Integer> points = new ArrayList<Integer>(); 358 int totalPoints = 0; 359 360 for (Lecture variable : variables) { 361 362 long pointsThisVariable = Math 363 .round(iDomainSizeWeight 364 * (((double) (iMaxDomainSize - variable.values().size())) / ((double) iMaxDomainSize)) 365 + (iProp == null ? 0.0 366 : iGoodValuesWeight 367 * (((double) (iMaxGoodDomainSize - iProp.goodValues(variable) 368 .size())) / ((double) iMaxGoodDomainSize))) 369 + iNrAssignmentsWeight 370 * (((double) variable.countAssignments()) / ((double) iMaxNrAssignments)) 371 + iConstraintsWeight 372 * (((double) (iMaxConstraints - variable.constraints().size())) / ((double) iMaxConstraints)) 373 + iInitialAssignmentWeight 374 * (variable.getInitialAssignment() != null ? model.conflictValues( 375 variable.getInitialAssignment()).size() : 0.0)); 376 if (pointsThisVariable > 0) { 377 totalPoints += pointsThisVariable; 378 points.add(totalPoints); 379 } 380 } 381 382 if (totalPoints > 0) { 383 int rndPoints = ToolBox.random(totalPoints); 384 Iterator<Lecture> x = variables.iterator(); 385 for (int i = 0; x.hasNext() && i < points.size(); i++) { 386 Lecture variable = x.next(); 387 int tp = points.get(i); 388 if (tp > rndPoints) { 389 if (variable != null && iTabu != null) { 390 if (iTabu.size() == iTabuPos) 391 iTabu.add(variable); 392 else 393 iTabu.set(iTabuPos, variable); 394 iTabuPos = (iTabuPos + 1) % iTabuSize; 395 } 396 return variable; 397 } 398 } 399 } 400 401 } else { 402 403 List<Lecture> selectionVariables = null; 404 long bestGood = 0; 405 for (Iterator<Lecture> i = ToolBox.subSet(unassignedVariables, iSelectionSubSetPart, 406 iSelectionSubSetMinSize).iterator(); i.hasNext();) { 407 Lecture variable = i.next(); 408 409 if (iTabu != null && iTabu.contains(variable)) 410 continue; 411 412 long good = (long) (iDomainSizeWeight * variable.values().size() + iGoodValuesWeight 413 * (iProp == null ? 0 : iProp.goodValues(variable).size()) + iNrAssignmentsWeight 414 * variable.countAssignments() + iConstraintsWeight * variable.constraints().size() + iInitialAssignmentWeight 415 * (variable.getInitialAssignment() != null ? model.conflictValues( 416 variable.getInitialAssignment()).size() : 0.0)); 417 if (selectionVariables == null || bestGood > good) { 418 if (selectionVariables == null) 419 selectionVariables = new ArrayList<Lecture>(); 420 else 421 selectionVariables.clear(); 422 bestGood = good; 423 selectionVariables.add(variable); 424 } else if (good == bestGood) { 425 selectionVariables.add(variable); 426 } 427 } 428 429 if (!selectionVariables.isEmpty()) { 430 Lecture selectedVariable = ToolBox.random(selectionVariables); 431 432 if (selectedVariable != null && iTabu != null) { 433 if (iTabu.size() == iTabuPos) 434 iTabu.add(selectedVariable); 435 else 436 iTabu.set(iTabuPos, selectedVariable); 437 iTabuPos = (iTabuPos + 1) % iTabuSize; 438 } 439 440 return selectedVariable; 441 } 442 } 443 444 Lecture selectedVariable = ToolBox.random(unassignedVariables); 445 446 if (selectedVariable != null && iTabu != null) { 447 if (iTabu.size() == iTabuPos) 448 iTabu.add(selectedVariable); 449 else 450 iTabu.set(iTabuPos, selectedVariable); 451 iTabuPos = (iTabuPos + 1) % iTabuSize; 452 } 453 454 return selectedVariable; 455 } 456 } 457 458}