    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}