001package net.sf.cpsolver.coursett.heuristics; 002 003import java.util.ArrayList; 004import 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 Tomáš Müller<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 */ 060public 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}