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