001package org.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.3 (University Course Timetabling)<br> 042 * Copyright (C) 2006 - 2014 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 * @param <E> A class of the objects that are being selected from 060 */ 061public class HeuristicSelector<E> { 062 private double[] iThreshKoef; 063 private List<Element> iElements = new ArrayList<Element>(); 064 private double iBestValueZero = 0.0; 065 066 /** 067 * Constructor 068 * 069 * @param threshKoef 070 * limit for each level, e.g., new double[] {0.1, 0.1, 0.1} for 071 * three level selection with 10% limit on each level 072 */ 073 public HeuristicSelector(double[] threshKoef) { 074 iThreshKoef = threshKoef; 075 } 076 077 /** 078 * Adds an object to selection 079 * 080 * @param values 081 * weighted sum for each level 082 * @param object 083 * object to be returned if selected 084 * @return true if added (it is not added if it is obvious that it cannot be 085 * selected) 086 */ 087 public boolean add(double[] values, E object) { 088 if (iElements.isEmpty() || values[0] < iBestValueZero) { 089 iBestValueZero = values[0]; 090 iElements.add(new Element(values, object)); 091 return true; 092 } else if (values[0] <= iBestValueZero * (iBestValueZero < 0.0 ? 1.0 - iThreshKoef[0] : 1.0 + iThreshKoef[0])) { 093 iElements.add(new Element(values, object)); 094 return true; 095 } 096 return false; 097 } 098 099 public Double firstLevelThreshold() { 100 return (iElements.isEmpty() ? null : new Double(iBestValueZero 101 * (iBestValueZero < 0.0 ? 1.0 - iThreshKoef[0] : 1.0 + iThreshKoef[0]))); 102 } 103 104 /** 105 * Do the selection. 106 * 107 * @return inserted objects which met the criteria 108 */ 109 public List<Element> selection() { 110 List<Element> selection = iElements; 111 double bestValue = iBestValueZero; 112 for (int level = 0; level < iThreshKoef.length; level++) { 113 List<Element> x = new ArrayList<Element>(selection.size()); 114 double threshold = (bestValue < 0.0 ? 1.0 - iThreshKoef[level] : 1.0 + iThreshKoef[level]) * bestValue; 115 // System.out.println("B"+(level+1)+": "+bestValue); 116 // System.out.println("T"+(level+1)+": "+threshold); 117 double nextBestValue = 0.0; 118 boolean lastLevel = (level + 1 == iThreshKoef.length); 119 for (Element element : selection) { 120 if (element.getValue(level) <= threshold) { 121 if (!lastLevel && (x.isEmpty() || element.getValue(level + 1) < nextBestValue)) 122 nextBestValue = element.getValue(level + 1); 123 x.add(element); 124 } 125 } 126 selection = x; 127 bestValue = nextBestValue; 128 } 129 return selection; 130 } 131 132 /** An element in heuristical selection */ 133 public class Element { 134 private double[] iValues; 135 private E iObject; 136 137 private Element(double[] values, E object) { 138 iValues = values; 139 iObject = object; 140 } 141 142 /** weighted sum in each level 143 * @return weighted sum for each level 144 **/ 145 public double[] getValues() { 146 return iValues; 147 } 148 149 /** weighted sum in the given level 150 * @param level a level 151 * @return weighted sum for the given level 152 **/ 153 public double getValue(int level) { 154 return iValues[level]; 155 } 156 157 /** given object 158 * @return the object in the selection 159 **/ 160 public E getObject() { 161 return iObject; 162 } 163 164 @Override 165 public String toString() { 166 StringBuffer sb = new StringBuffer(); 167 for (int i = 0; i < iValues.length; i++) 168 sb.append(i == 0 ? "" : ",").append(iValues[i]); 169 return "[" + sb + "]:" + iObject; 170 } 171 } 172}