    001    package ttsolver.heuristics;
    002
    003    import ifs.util.*;
    004    import java.util.*;
    005
    006    /**
    007     * General hierarchical selection.
    008     * <br><br>
    009     * We have implemented a hierarchical handling of the value selection criteria. There are three levels of comparison. At
    010     * each level a weighted sum of the criteria described below is computed.  Only solutions with the smallest sum are
    011     * considered in the next level. The weights express how quickly a complete solution should be found.  Only hard
    012     * constraints are satisfied in the first level sum. Distance from the initial solution (MPP), and a weighting of
    013     * major preferences (including time, classroom requirements and student conflicts), are considered in the next level.
    014     * In the third level, other minor criteria are considered. In general, a criterion can be used in more than one level,
    015     * e.g., with different weights.
    016     * <br><br>
    017     * The above sums order the values lexicographically: the best value having the smallest first level sum, the smallest
    018     * second level sum among values with the smallest first level sum, and the smallest third level sum among these values.
    019     * As mentioned above, this allows diversification between the importance of individual criteria.
    020     * <br><br>
    021     * Furthermore, the value selection heuristics also support some limits (e.g., that all values with a first level sum
    022     * smaller than a given percentage Pth above the best value [typically 10%] will go to the second level comparison
    023     * and so on). This allows for the continued feasibility of a value near to the best that may yet be much better in the
    024     * next level of comparison.  If there is more than one solution after these three levels of comparison, one is
    025     * selected randomly. This approach helped us to significantly improve the quality of the resultant solutions.
    026     * <br><br>
    027     * In general, there can be more than three levels of these weighted sums, however three of them seem to be sufficient for
    028     * spreading weights of various criteria for our problem.
    029     *
    030     * @see PlacementSelection
    031     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    032     * @version 1.0
    033     */
    034    public class HeuristicSelector {
    035        private double[] iThreshKoef;
    036        private Vector iElements = new FastVector();
    037        private double iBestValueZero = 0.0;
    038
    039        /** Constructor
    040         * @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
    041         */
    042        public HeuristicSelector(double[] threshKoef) {
    043            iThreshKoef = threshKoef;
    044        }
    045
    046        /** Adds an object to selection
    047         *  @param values weighted sum for each level
    048         *  @param object object to be returned if selected
    049         *  @return true if added (it is not added if it is obvious that it cannot be selected)
    050         */
    051        public boolean add(double[] values, Object object) {
    052            if (iElements.isEmpty() || values[0] < iBestValueZero) {
    053                iBestValueZero = values[0];
    054                iElements.addElement(new Element(values, object));
    055                return true;
    056            } else if (values[0] <= iBestValueZero * (iBestValueZero<0.0?1.0-iThreshKoef[0]:1.0+iThreshKoef[0])) {
    057                iElements.addElement(new Element(values, object));
    058                return true;
    059            }
    060            return false;
    061        }
    062
    063        /** Do the selection.
    064         * @return inserted objects which met the criteria
    065         */
    066        public Vector selection() {
    067            Vector selection = iElements;
    068            double bestValue = iBestValueZero;
    069            for (int level=0; level<iThreshKoef.length; level++) {
    070                Vector x = new FastVector(selection.size());
    071                double threshold = (bestValue<0.0?1.0-iThreshKoef[level]:1.0+iThreshKoef[level]) * bestValue;
    072                //System.out.println("B"+(level+1)+": "+bestValue);
    073                //System.out.println("T"+(level+1)+": "+threshold);
    074                double nextBestValue = 0.0;
    075                boolean lastLevel = (level+1==iThreshKoef.length);
    076                for (Enumeration e=selection.elements();e.hasMoreElements();) {
    077                    Element element = (Element)e.nextElement();
    078                    if (element.getValue(level)<=threshold) {
    079                        if (!lastLevel && (x.isEmpty() || element.getValue(level+1)<nextBestValue))
    080                            nextBestValue=element.getValue(level+1);
    081                        x.addElement(element);
    082                    }
    083                }
    084                selection = x;
    085                bestValue = nextBestValue;
    086            }
    087            return selection;
    088        }
    089
    090        /** An element in heuristical selection*/
    091        public class Element {
    092            private double[] iValues;
    093            private Object iObject;
    094            private Element(double[] values, Object object) {
    095                iValues = values; iObject = object;
    096            }
    097            /** weighted sum in each level*/
    098            public double[] getValues() { return iValues; }
    099            /** weighted sum in the given level*/
    100            public double getValue(int level) { return iValues[level]; }
    101            /** given object */
    102            public Object getObject() { return iObject; }
    103            public String toString() {
    104                StringBuffer sb = new StringBuffer();
    105                for (int i=0;i<iValues.length;i++) sb.append(i==0?"":",").append(iValues[i]);
    106                return "["+sb+"]:"+iObject;
    107            }
    108        }
    109    }