001    package net.sf.cpsolver.coursett.heuristics;
002    
003    import java.util.ArrayList;
004    import 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 Tomas Muller<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     */
060    public 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    }