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}