001 package net.sf.cpsolver.coursett.heuristics;
002
003 import java.util.Enumeration;
004 import java.util.Vector;
005
006 import net.sf.cpsolver.ifs.util.FastVector;
007
008 /**
009 * General hierarchical selection.
010 * <br><br>
011 * We have implemented a hierarchical handling of the value selection criteria. There are three levels of comparison. At
012 * each level a weighted sum of the criteria described below is computed. Only solutions with the smallest sum are
013 * considered in the next level. The weights express how quickly a complete solution should be found. Only hard
014 * constraints are satisfied in the first level sum. Distance from the initial solution (MPP), and a weighting of
015 * major preferences (including time, classroom requirements and student conflicts), are considered in the next level.
016 * In the third level, other minor criteria are considered. In general, a criterion can be used in more than one level,
017 * e.g., with different weights.
018 * <br><br>
019 * The above sums order the values lexicographically: the best value having the smallest first level sum, the smallest
020 * second level sum among values with the smallest first level sum, and the smallest third level sum among these values.
021 * As mentioned above, this allows diversification between the importance of individual criteria.
022 * <br><br>
023 * Furthermore, the value selection heuristics also support some limits (e.g., that all values with a first level sum
024 * smaller than a given percentage Pth above the best value [typically 10%] will go to the second level comparison
025 * and so on). This allows for the continued feasibility of a value near to the best that may yet be much better in the
026 * next level of comparison. If there is more than one solution after these three levels of comparison, one is
027 * selected randomly. This approach helped us to significantly improve the quality of the resultant solutions.
028 * <br><br>
029 * In general, there can be more than three levels of these weighted sums, however three of them seem to be sufficient for
030 * spreading weights of various criteria for our problem.
031 *
032 * @see PlacementSelection
033 * @version
034 * CourseTT 1.1 (University Course Timetabling)<br>
035 * Copyright (C) 2006 Tomáš Müller<br>
036 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
037 * Lazenska 391, 76314 Zlin, Czech Republic<br>
038 * <br>
039 * This library is free software; you can redistribute it and/or
040 * modify it under the terms of the GNU Lesser General Public
041 * License as published by the Free Software Foundation; either
042 * version 2.1 of the License, or (at your option) any later version.
043 * <br><br>
044 * This library is distributed in the hope that it will be useful,
045 * but WITHOUT ANY WARRANTY; without even the implied warranty of
046 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
047 * Lesser General Public License for more details.
048 * <br><br>
049 * You should have received a copy of the GNU Lesser General Public
050 * License along with this library; if not, write to the Free Software
051 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
052 */
053 public class HeuristicSelector {
054 private double[] iThreshKoef;
055 private Vector iElements = new FastVector();
056 private double iBestValueZero = 0.0;
057
058 /** Constructor
059 * @param threshKoef limit for each level, e.g., new double[] {0.1, 0.1, 0.1} for three level selection with 10% limit on each level
060 */
061 public HeuristicSelector(double[] threshKoef) {
062 iThreshKoef = threshKoef;
063 }
064
065 /** Adds an object to selection
066 * @param values weighted sum for each level
067 * @param object object to be returned if selected
068 * @return true if added (it is not added if it is obvious that it cannot be selected)
069 */
070 public boolean add(double[] values, Object object) {
071 if (iElements.isEmpty() || values[0] < iBestValueZero) {
072 iBestValueZero = values[0];
073 iElements.addElement(new Element(values, object));
074 return true;
075 } else if (values[0] <= iBestValueZero * (iBestValueZero<0.0?1.0-iThreshKoef[0]:1.0+iThreshKoef[0])) {
076 iElements.addElement(new Element(values, object));
077 return true;
078 }
079 return false;
080 }
081
082 public Double firstLevelThreshold() {
083 return (iElements.isEmpty()?null:new Double(iBestValueZero * (iBestValueZero<0.0?1.0-iThreshKoef[0]:1.0+iThreshKoef[0])));
084 }
085
086 /** Do the selection.
087 * @return inserted objects which met the criteria
088 */
089 public Vector selection() {
090 Vector selection = iElements;
091 double bestValue = iBestValueZero;
092 for (int level=0; level<iThreshKoef.length; level++) {
093 Vector x = new FastVector(selection.size());
094 double threshold = (bestValue<0.0?1.0-iThreshKoef[level]:1.0+iThreshKoef[level]) * bestValue;
095 //System.out.println("B"+(level+1)+": "+bestValue);
096 //System.out.println("T"+(level+1)+": "+threshold);
097 double nextBestValue = 0.0;
098 boolean lastLevel = (level+1==iThreshKoef.length);
099 for (Enumeration e=selection.elements();e.hasMoreElements();) {
100 Element element = (Element)e.nextElement();
101 if (element.getValue(level)<=threshold) {
102 if (!lastLevel && (x.isEmpty() || element.getValue(level+1)<nextBestValue))
103 nextBestValue=element.getValue(level+1);
104 x.addElement(element);
105 }
106 }
107 selection = x;
108 bestValue = nextBestValue;
109 }
110 return selection;
111 }
112
113 /** An element in heuristical selection*/
114 public class Element {
115 private double[] iValues;
116 private Object iObject;
117 private Element(double[] values, Object object) {
118 iValues = values; iObject = object;
119 }
120 /** weighted sum in each level*/
121 public double[] getValues() { return iValues; }
122 /** weighted sum in the given level*/
123 public double getValue(int level) { return iValues[level]; }
124 /** given object */
125 public Object getObject() { return iObject; }
126 public String toString() {
127 StringBuffer sb = new StringBuffer();
128 for (int i=0;i<iValues.length;i++) sb.append(i==0?"":",").append(iValues[i]);
129 return "["+sb+"]:"+iObject;
130 }
131 }
132 }