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