|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object net.sf.cpsolver.coursett.heuristics.HeuristicSelector
public class HeuristicSelector
General hierarchical selection.
We have implemented a hierarchical handling of the value selection criteria. There are three levels of comparison. At
each level a weighted sum of the criteria described below is computed. Only solutions with the smallest sum are
considered in the next level. The weights express how quickly a complete solution should be found. Only hard
constraints are satisfied in the first level sum. Distance from the initial solution (MPP), and a weighting of
major preferences (including time, classroom requirements and student conflicts), are considered in the next level.
In the third level, other minor criteria are considered. In general, a criterion can be used in more than one level,
e.g., with different weights.
The above sums order the values lexicographically: the best value having the smallest first level sum, the smallest
second level sum among values with the smallest first level sum, and the smallest third level sum among these values.
As mentioned above, this allows diversification between the importance of individual criteria.
Furthermore, the value selection heuristics also support some limits (e.g., that all values with a first level sum
smaller than a given percentage Pth above the best value [typically 10%] will go to the second level comparison
and so on). This allows for the continued feasibility of a value near to the best that may yet be much better in the
next level of comparison. If there is more than one solution after these three levels of comparison, one is
selected randomly. This approach helped us to significantly improve the quality of the resultant solutions.
In general, there can be more than three levels of these weighted sums, however three of them seem to be sufficient for
spreading weights of various criteria for our problem.
PlacementSelection
Nested Class Summary | |
---|---|
class |
HeuristicSelector.Element
An element in heuristical selection |
Constructor Summary | |
---|---|
HeuristicSelector(double[] threshKoef)
Constructor |
Method Summary | |
---|---|
boolean |
add(double[] values,
Object object)
Adds an object to selection |
Double |
firstLevelThreshold()
|
Vector |
selection()
Do the selection. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public HeuristicSelector(double[] threshKoef)
threshKoef
- limit for each level, e.g., new double[] {0.1, 0.1, 0.1} for three level selection with 10% limit on each levelMethod Detail |
---|
public boolean add(double[] values, Object object)
values
- weighted sum for each levelobject
- object to be returned if selected
public Double firstLevelThreshold()
public Vector selection()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |