    001package net.sf.cpsolver.ifs.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.Iterator;
    006import java.util.List;
    007import java.util.Set;
    008
    009import net.sf.cpsolver.ifs.extension.ConflictStatistics;
    010import net.sf.cpsolver.ifs.extension.Extension;
    011import net.sf.cpsolver.ifs.extension.MacPropagation;
    012import net.sf.cpsolver.ifs.extension.ViolatedInitials;
    013import net.sf.cpsolver.ifs.model.Model;
    014import net.sf.cpsolver.ifs.model.Value;
    015import net.sf.cpsolver.ifs.model.Variable;
    016import net.sf.cpsolver.ifs.solution.Solution;
    017import net.sf.cpsolver.ifs.solver.Solver;
    018import net.sf.cpsolver.ifs.util.DataProperties;
    019import net.sf.cpsolver.ifs.util.ToolBox;
    020
    021/**
    022 * General implementation of value selection criterion. <br>
    023 * <br>
    024 * Value selection criterion is based on weighted sum of various criteria. It
    025 * also allows random walk technique and tabu search. <br>
    026 * Parameters: <br>
    027 * <table border='1'>
    028 * <tr>
    029 * <th>Parameter</th>
    030 * <th>Type</th>
    031 * <th>Comment</th>
    032 * </tr>
    033 * <tr>
    034 * <td>General.MPP</td>
    035 * <td>{@link Boolean}</td>
    036 * <td>if true, MPP is being solved</td>
    037 * </tr>
    038 * <tr>
    039 * <td>Value.MPPLimit</td>
    040 * <td>{@link Integer}</td>
    041 * <td>MPP: limitation of the number of allowed perturbations. If a solution
    042 * within this limit is gound, it is decreased.</td>
    043 * </tr>
    044 * <tr>
    045 * <td>Value.InitialSelectionProb</td>
    046 * <td>{@link Double}</td>
    047 * <td>MPP: probability of selection of the initial value</td>
    048 * </tr>
    049 * <tr>
    050 * <td>Value.RandomWalkProb</td>
    051 * <td>{@link Double}</td>
    052 * <td>Random Walk: probability of selection of a value randomly among all the
    053 * values</td>
    054 * </tr>
    055 * <tr>
    056 * <td>Value.Tabu</td>
    057 * <td>{@link Integer}</td>
    058 * <td>Tabu Search: length of the tabu-list</td>
    059 * </tr>
    060 * <tr>
    061 * <td>Value.GoodSelectionProb</td>
    062 * <td>{@link Double}</td>
    063 * <td>In case of {@link MacPropagation}, with this probability (1.0 means
    064 * always), the selection is made only among good values (not removed from the
    065 * domain).</td>
    066 * </tr>
    067 * </table>
    068 * <br>
    069 * Following weights are used in the weighted sum (computed for all values). The
    070 * value with the lowest weighted sum is selected. If there are more than one of
    071 * such values, one of them is selected randomly. <br>
    072 * <table border='1'>
    073 * <tr>
    074 * <th>Parameter</th>
    075 * <th>Type</th>
    076 * <th>Comment</th>
    077 * </tr>
    078 * <tr>
    079 * <td>Value.WeightDeltaInitialAssignments</td>
    080 * <td>{@link Double}</td>
    081 * <td>MPP: Difference in the number of assigned initial values if the value is
    082 * assigned to the variable (weighted by this
    083 * Value.WeightDeltaInitialAssignments): -1 if the value is initial, 0
    084 * otherwise, increased by the number of initial values assigned to variables
    085 * with hard conflicts with the value</td>
    086 * </tr>
    087 * <tr>
    088 * <td>Value.WeightWeightedConflicts</td>
    089 * <td>{@link Double}</td>
    090 * <td>When {@link ConflictStatistics} is used: weighted number of conflicting
    091 * variables</td>
    092 * </tr>
    093 * <tr>
    094 * <td>Value.WeightPotentialConflicts</td>
    095 * <td>{@link Double}</td>
    096 * <td>When {@link ConflictStatistics} is used: weighted number of potentially
    097 * conflicting variables</td>
    098 * </tr>
    099 * <tr>
    100 * <td>Value.WeightConflicts</td>
    101 * <td>{@link Double}</td>
    102 * <td>Number of conflicting variables {@link Model#conflictValues(Value)}.</td>
    103 * </tr>
    104 * <tr>
    105 * <td>Value.WeightNrAssignments</td>
    106 * <td>{@link Double}</td>
    107 * <td>Number of previous assignments of the value</td>
    108 * </tr>
    109 * <tr>
    110 * <td>Value.WeightValue</td>
    111 * <td>{@link Double}</td>
    112 * <td>Value {@link Value#toDouble()}</td>
    113 * </tr>
    114 * </table>
    115 *
    116 * @see VariableSelection
    117 * @see Solver
    118 *
    119 * @version IFS 1.2 (Iterative Forward Search)<br>
    120 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    121 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    122 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    123 * <br>
    124 *          This library is free software; you can redistribute it and/or modify
    125 *          it under the terms of the GNU Lesser General Public License as
    126 *          published by the Free Software Foundation; either version 3 of the
    127 *          License, or (at your option) any later version. <br>
    128 * <br>
    129 *          This library is distributed in the hope that it will be useful, but
    130 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    131 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    132 *          Lesser General Public License for more details. <br>
    133 * <br>
    134 *          You should have received a copy of the GNU Lesser General Public
    135 *          License along with this library; if not see <http://www.gnu.org/licenses/>.
    136 **/
    137
    138public class GeneralValueSelection<V extends Variable<V, T>, T extends Value<V, T>> implements ValueSelection<V, T> {
    139    private double iRandomWalkProb = 0.0;
    140    private double iInitialSelectionProb = 0.0;
    141    private double iGoodSelectionProb = 0.0;
    142    private int iMPPLimit = -1;
    143
    144    private double iWeightDeltaInitialAssignment = 0.0;
    145    private double iWeightPotentialConflicts = 0.0;
    146    private double iWeightWeightedCoflicts = 0.0;
    147    private double iWeightCoflicts = 1.0;
    148    private double iWeightNrAssignments = 0.5;
    149    private double iWeightValue = 0.0;
    150
    151    protected int iTabuSize = 0;
    152    protected ArrayList<T> iTabu = null;
    153    protected int iTabuPos = 0;
    154
    155    private boolean iMPP = false;
    156    private ConflictStatistics<V, T> iStat = null;
    157    private MacPropagation<V, T> iProp = null;
    158    private ViolatedInitials<V, T> iViolatedInitials = null;
    159
    160    public GeneralValueSelection() {
    161    }
    162
    163    /**
    164     * Constructor
    165     *
    166     * @param properties
    167     *            input configuration
    168     */
    169    public GeneralValueSelection(DataProperties properties) {
    170        iMPP = properties.getPropertyBoolean("General.MPP", false);
    171        if (iMPP) {
    172            iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
    173            iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
    174            iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
    175        }
    176        iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00);
    177        iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 1.0);
    178        iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0);
    179
    180        iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
    181        iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0);
    182        iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments", 0.5);
    183        iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
    184        iTabuSize = properties.getPropertyInt("Value.Tabu", 0);
    185        if (iTabuSize > 0)
    186            iTabu = new ArrayList<T>(iTabuSize);
    187    }
    188
    189    /** Initialization */
    190    @Override
    191    public void init(Solver<V, T> solver) {
    192        for (Extension<V, T> extension : solver.getExtensions()) {
    193            if (ConflictStatistics.class.isInstance(extension))
    194                iStat = (ConflictStatistics<V, T>) extension;
    195            if (MacPropagation.class.isInstance(extension))
    196                iProp = (MacPropagation<V, T>) extension;
    197            if (ViolatedInitials.class.isInstance(extension))
    198                iViolatedInitials = (ViolatedInitials<V, T>) extension;
    199        }
    200    }
    201
    202    /** Value selection */
    203    @Override
    204    public T selectValue(Solution<V, T> solution, V selectedVariable) {
    205        if (iMPP) {
    206            if (selectedVariable.getInitialAssignment() != null) {
    207                if (solution.getModel().nrUnassignedVariables() == 0) {
    208                    if (solution.getModel().perturbVariables().size() <= iMPPLimit)
    209                        iMPPLimit = solution.getModel().perturbVariables().size() - 1;
    210                }
    211                if (iMPPLimit >= 0 && solution.getModel().perturbVariables().size() > iMPPLimit)
    212                    return selectedVariable.getInitialAssignment();
    213                if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb)
    214                    return selectedVariable.getInitialAssignment();
    215            }
    216        }
    217
    218        List<T> values = selectedVariable.values();
    219        if (ToolBox.random() <= iRandomWalkProb)
    220            return ToolBox.random(values);
    221        if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
    222            Collection<T> goodValues = iProp.goodValues(selectedVariable);
    223            if (!goodValues.isEmpty())
    224                values = new ArrayList<T>(goodValues);
    225        }
    226        if (values.size() == 1)
    227            return values.get(0);
    228
    229        List<T> bestValues = null;
    230        double bestWeightedSum = 0;
    231
    232        for (T value : values) {
    233            if (iTabu != null && iTabu.contains(value))
    234                continue;
    235            if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
    236                continue;
    237
    238            Collection<T> conf = solution.getModel().conflictValues(value);
    239            if (conf.contains(value))
    240                continue;
    241
    242            double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(
    243                    solution.getIteration(), conf, value));
    244            double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat
    245                    .countPotentialConflicts(solution.getIteration(), value, 3));
    246
    247            long deltaInitialAssignments = 0;
    248            if (iMPP && iWeightDeltaInitialAssignment != 0.0) {
    249                if (iViolatedInitials != null) {
    250                    Set<T> violations = iViolatedInitials.getViolatedInitials(value);
    251                    if (violations != null) {
    252                        for (T aValue : violations) {
    253                            if (aValue.variable().getAssignment() == null
    254                                    || aValue.variable().getAssignment().equals(aValue))
    255                                deltaInitialAssignments += 2;
    256                        }
    257                    }
    258                }
    259                for (Iterator<T> it1 = conf.iterator(); it1.hasNext();) {
    260                    T aValue = it1.next();
    261                    if (aValue.variable().getInitialAssignment() != null)
    262                        deltaInitialAssignments--;
    263                }
    264                if (selectedVariable.getInitialAssignment() != null
    265                        && !selectedVariable.getInitialAssignment().equals(value)) {
    266                    deltaInitialAssignments++;
    267                }
    268                if (iMPPLimit >= 0
    269                        && (solution.getModel().perturbVariables().size() + deltaInitialAssignments) > iMPPLimit)
    270                    continue;
    271            }
    272
    273            double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments)
    274                    + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts)
    275                    + (iWeightCoflicts * conf.size()) + (iWeightNrAssignments * value.countAssignments())
    276                    + (iWeightValue * value.toDouble());
    277
    278            if (bestValues == null || bestWeightedSum > weightedSum) {
    279                bestWeightedSum = weightedSum;
    280                if (bestValues == null)
    281                    bestValues = new ArrayList<T>();
    282                else
    283                    bestValues.clear();
    284                bestValues.add(value);
    285            } else {
    286                if (bestWeightedSum == weightedSum)
    287                    bestValues.add(value);
    288            }
    289        }
    290
    291        T selectedValue = (bestValues == null ? null : ToolBox.random(bestValues));
    292        if (selectedValue == null)
    293            selectedValue = ToolBox.random(values);
    294        if (iTabu != null) {
    295            if (iTabu.size() == iTabuPos)
    296                iTabu.add(selectedValue);
    297            else
    298                iTabu.set(iTabuPos, selectedValue);
    299            iTabuPos = (iTabuPos + 1) % iTabuSize;
    300        }
    301        return (bestValues == null ? null : selectedValue);
    302    }
    303
    304}