    001    package ifs.heuristics;
    002
    003    import ifs.extension.*;
    004    import ifs.model.*;
    005    import ifs.solution.*;
    006    import ifs.solver.*;
    007    import ifs.util.*;
    008
    009    import java.util.*;
    010
    011    /**
    012     * General implementation of value selection criterion.
    013     * <br><br>
    014     * Value selection criterion is based on weighted sum of various criteria. It also allows random walk technique and
    015     * tabu search.
    016     * <br>
    017     * Parameters:
    018     * <br>
    019     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    020     * <tr><td>General.MPP</td><td>{@link Boolean}</td><td>if true, MPP is being solved</td></tr>
    021     * <tr><td>Value.MPPLimit</td><td>{@link Integer}</td><td>MPP: limitation of the number of allowed perturbations. If a solution within this limit is gound, it is decreased.</td></tr>
    022     * <tr><td>Value.InitialSelectionProb</td><td>{@link Double}</td><td>MPP: probability of selection of the initial value</td></tr>
    023     * <tr><td>Value.RandomWalkProb</td><td>{@link Double}</td><td>Random Walk: probability of selection of a value randomly among all the values</td></tr>
    024     * <tr><td>Value.Tabu</td><td>{@link Integer}</td><td>Tabu Search: length of the tabu-list</td></tr>
    025     * <tr><td>Value.GoodSelectionProb</td><td>{@link Double}</td><td>In case of {@link MacPropagation}, with this probability (1.0 means always), the selection is made only among good values (not removed from the domain).</td></tr>
    026     * </table>
    027     * <br>
    028     * Following weights are used in the weighted sum (computed for all values). The value with the lowest weighted sum is selected.
    029     * If there are more than one of such values, one of them is selected randomly.
    030     * <br>
    031     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    032     * <tr><td>Value.WeightDeltaInitialAssignments</td><td>{@link Double}</td><td>MPP: Difference in the number of assigned initial values if the value is assigned to the variable (weighted by this Value.WeightDeltaInitialAssignments): -1 if the value is initial, 0 otherwise, increased by the number of initial values assigned to variables with hard conflicts with the value</td></tr>
    033     * <tr><td>Value.WeightWeightedConflicts</td><td>{@link Double}</td><td>When {@link ConflictStatistics} is used: weighted number of conflicting variables</td></tr>
    034     * <tr><td>Value.WeightPotentialConflicts</td><td>{@link Double}</td><td>When {@link ConflictStatistics} is used: weighted number of potentially conflicting variables</td></tr>
    035     * <tr><td>Value.WeightConflicts</td><td>{@link Double}</td><td>Number of conflicting variables {@link Model#conflictValues(Value)}.</td></tr>
    036     * <tr><td>Value.WeightNrAssignments</td><td>{@link Double}</td><td>Number of previous assignments of the value</td></tr>
    037     * <tr><td>Value.WeightValue</td><td>{@link Double}</td><td>Value {@link Value#toInt()}</td></tr>
    038     * </table>
    039     *
    040     * @see VariableSelection
    041     * @see Solver
    042     *
    043     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    044     * @version 1.0
    045     **/
    046
    047    public class GeneralValueSelection implements ValueSelection {
    048        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(GeneralValueSelection.class);
    049        private double iRandomWalkProb = 0.0;
    050        private double iInitialSelectionProb = 0.0;
    051        private double iGoodSelectionProb = 0.0;
    052        private int iMPPLimit = -1;
    053
    054        private double iWeightDeltaInitialAssignment = 0.0;
    055        private double iWeightPotentialConflicts = 0.0;
    056        private double iWeightWeightedCoflicts = 0.0;
    057        private double iWeightCoflicts = 1.0;
    058        private double iWeightNrAssignments = 0.5;
    059        private double iWeightValue = 0.0;
    060
    061        private int iTabuSize = 0;
    062        private ArrayList iTabu = null;
    063        private int iTabuPos = 0;
    064
    065        private boolean iMPP = false;
    066        private ConflictStatistics iStat = null;
    067        private MacPropagation iProp = null;
    068        private ViolatedInitials iViolatedInitials = null;
    069
    070        public GeneralValueSelection() {}
    071
    072        /** Constructor
    073         * @param properties input configuration
    074         */
    075        public GeneralValueSelection(DataProperties properties) {
    076            iMPP = properties.getPropertyBoolean("General.MPP", false);
    077            if (iMPP) {
    078                iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
    079                iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
    080                iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
    081            }
    082            iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00);
    083            iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 1.0);
    084            iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0);
    085
    086            iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
    087            iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0);
    088            iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments", 0.5);
    089            iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
    090            iTabuSize = properties.getPropertyInt("Value.Tabu", 0);
    091            if (iTabuSize > 0)
    092                iTabu = new ArrayList(iTabuSize);
    093        }
    094
    095        /** Initialization */
    096        public void init(Solver solver) {
    097            for (Enumeration i = solver.getExtensions().elements(); i.hasMoreElements();) {
    098                Extension extension = (Extension)i.nextElement();
    099                if (extension instanceof ConflictStatistics)
    100                    iStat = (ConflictStatistics)extension;
    101                if (extension instanceof MacPropagation)
    102                    iProp = (MacPropagation)extension;
    103                if (extension instanceof ViolatedInitials)
    104                    iViolatedInitials = (ViolatedInitials)extension;
    105            }
    106        }
    107
    108        /** Value selecion */
    109        public Value selectValue(Solution solution, Variable selectedVariable) {
    110            if (iMPP) {
    111                if (selectedVariable.getInitialAssignment() != null) {
    112                    if (solution.getModel().unassignedVariables().isEmpty()) {
    113                        if (solution.getModel().perturbVariables().size() <= iMPPLimit)
    114                            iMPPLimit = solution.getModel().perturbVariables().size() - 1;
    115                    }
    116                    if (iMPPLimit >= 0 && solution.getModel().perturbVariables().size() > iMPPLimit)
    117                        return selectedVariable.getInitialAssignment();
    118                    if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb)
    119                        return selectedVariable.getInitialAssignment();
    120                }
    121            }
    122
    123            Vector values = selectedVariable.values();
    124            if (ToolBox.random() <= iRandomWalkProb) return (Value)ToolBox.random(values);
    125            if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
    126                Collection goodValues = iProp.goodValues(selectedVariable);
    127                if (!goodValues.isEmpty()) values = new FastVector(goodValues);
    128            }
    129            if (values.size() == 1)
    130                return (Value)values.firstElement();
    131
    132            Vector bestValues = null;
    133            double bestWeightedSum = 0;
    134
    135            for (Enumeration i1 = values.elements(); i1.hasMoreElements();) {
    136                Value value = (Value)i1.nextElement();
    137                if (iTabu != null && iTabu.contains(value)) continue;
    138                if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
    139                    continue;
    140
    141                Collection conf = solution.getModel().conflictValues(value);
    142                double weightedConflicts = (iStat == null || iWeightCoflicts == 0.0 ? 0.0 : iStat.countRemovals(solution.getIteration(), conf, value));
    143                double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat.countPotentialConflicts(solution.getIteration(), value, 3));
    144
    145                long deltaInitialAssignments = 0;
    146                if (iMPP && iWeightDeltaInitialAssignment != 0.0) {
    147                    if (iViolatedInitials != null) {
    148                        Set violations = iViolatedInitials.getViolatedInitials(value);
    149                        if (violations != null) {
    150                            for (Iterator it1 = violations.iterator(); it1.hasNext();) {
    151                                Value aValue = (Value)it1.next();
    152                                if (aValue.variable().getAssignment() == null || aValue.variable().getAssignment().equals( aValue))
    153                                    deltaInitialAssignments += 2;
    154                            }
    155                        }
    156                    }
    157                    for (Iterator it1 = conf.iterator(); it1.hasNext();) {
    158                        Value aValue = (Value)it1.next();
    159                        if (aValue.variable().getInitialAssignment() != null)
    160                            deltaInitialAssignments--;
    161                    }
    162                    if (selectedVariable.getInitialAssignment() != null && !selectedVariable.getInitialAssignment().equals(value)) {
    163                        deltaInitialAssignments++;
    164                    }
    165                    if (iMPPLimit >= 0 && (solution.getModel().perturbVariables().size() + deltaInitialAssignments) > iMPPLimit)
    166                        continue;
    167                }
    168
    169                double weightedSum =
    170                        (iWeightDeltaInitialAssignment * deltaInitialAssignments)
    171                        + (iWeightPotentialConflicts * potentialConflicts)
    172                        + (iWeightWeightedCoflicts * weightedConflicts)
    173                        + (iWeightCoflicts * conf.size())
    174                        + (iWeightNrAssignments * value.countAssignments())
    175                        + (iWeightValue * value.toInt());
    176
    177                if (bestValues == null || bestWeightedSum > weightedSum) {
    178                    bestWeightedSum = weightedSum;
    179                    if (bestValues == null) bestValues = new FastVector();
    180                    else bestValues.clear();
    181                    bestValues.addElement(value);
    182                } else {
    183                    if (bestWeightedSum == weightedSum)
    184                        bestValues.addElement(value);
    185                }
    186            }
    187
    188            Value selectedValue = (Value)(bestValues==null?null:ToolBox.random(bestValues));
    189            if (selectedValue == null) selectedValue = (Value)ToolBox.random(values);
    190            if (iTabu != null) {
    191                if (iTabu.size() == iTabuPos)
    192                    iTabu.add(selectedValue);
    193                else
    194                    iTabu.set(iTabuPos, selectedValue);
    195                iTabuPos = (iTabuPos + 1) % iTabuSize;
    196            }
    197            return (bestValues == null ? null : selectedValue);
    198        }
    199
    200    }