001 package net.sf.cpsolver.ifs.heuristics;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.Iterator;
006 import java.util.List;
007 import java.util.Set;
008
009 import net.sf.cpsolver.ifs.extension.ConflictStatistics;
010 import net.sf.cpsolver.ifs.extension.Extension;
011 import net.sf.cpsolver.ifs.extension.MacPropagation;
012 import net.sf.cpsolver.ifs.extension.ViolatedInitials;
013 import net.sf.cpsolver.ifs.model.Model;
014 import net.sf.cpsolver.ifs.model.Value;
015 import net.sf.cpsolver.ifs.model.Variable;
016 import net.sf.cpsolver.ifs.solution.Solution;
017 import net.sf.cpsolver.ifs.solver.Solver;
018 import net.sf.cpsolver.ifs.util.DataProperties;
019 import 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 Tomas Muller<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
138 public 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 }