001 package net.sf.cpsolver.ifs.heuristics;
002
003
004 import java.util.*;
005
006 import net.sf.cpsolver.ifs.extension.*;
007 import net.sf.cpsolver.ifs.model.*;
008 import net.sf.cpsolver.ifs.solution.*;
009 import net.sf.cpsolver.ifs.solver.*;
010 import net.sf.cpsolver.ifs.util.*;
011
012 /**
013 * General implementation of value selection criterion.
014 * <br><br>
015 * Value selection criterion is based on weighted sum of various criteria. It also allows random walk technique and
016 * tabu search.
017 * <br>
018 * Parameters:
019 * <br>
020 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
021 * <tr><td>General.MPP</td><td>{@link Boolean}</td><td>if true, MPP is being solved</td></tr>
022 * <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>
023 * <tr><td>Value.InitialSelectionProb</td><td>{@link Double}</td><td>MPP: probability of selection of the initial value</td></tr>
024 * <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>
025 * <tr><td>Value.Tabu</td><td>{@link Integer}</td><td>Tabu Search: length of the tabu-list</td></tr>
026 * <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>
027 * </table>
028 * <br>
029 * Following weights are used in the weighted sum (computed for all values). The value with the lowest weighted sum is selected.
030 * If there are more than one of such values, one of them is selected randomly.
031 * <br>
032 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
033 * <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>
034 * <tr><td>Value.WeightWeightedConflicts</td><td>{@link Double}</td><td>When {@link ConflictStatistics} is used: weighted number of conflicting variables</td></tr>
035 * <tr><td>Value.WeightPotentialConflicts</td><td>{@link Double}</td><td>When {@link ConflictStatistics} is used: weighted number of potentially conflicting variables</td></tr>
036 * <tr><td>Value.WeightConflicts</td><td>{@link Double}</td><td>Number of conflicting variables {@link Model#conflictValues(Value)}.</td></tr>
037 * <tr><td>Value.WeightNrAssignments</td><td>{@link Double}</td><td>Number of previous assignments of the value</td></tr>
038 * <tr><td>Value.WeightValue</td><td>{@link Double}</td><td>Value {@link Value#toDouble()}</td></tr>
039 * </table>
040 *
041 * @see VariableSelection
042 * @see Solver
043 *
044 * @version
045 * IFS 1.1 (Iterative Forward Search)<br>
046 * Copyright (C) 2006 Tomáš Müller<br>
047 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
048 * Lazenska 391, 76314 Zlin, Czech Republic<br>
049 * <br>
050 * This library is free software; you can redistribute it and/or
051 * modify it under the terms of the GNU Lesser General Public
052 * License as published by the Free Software Foundation; either
053 * version 2.1 of the License, or (at your option) any later version.
054 * <br><br>
055 * This library is distributed in the hope that it will be useful,
056 * but WITHOUT ANY WARRANTY; without even the implied warranty of
057 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
058 * Lesser General Public License for more details.
059 * <br><br>
060 * You should have received a copy of the GNU Lesser General Public
061 * License along with this library; if not, write to the Free Software
062 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
063 **/
064
065 public class GeneralValueSelection implements ValueSelection {
066 private double iRandomWalkProb = 0.0;
067 private double iInitialSelectionProb = 0.0;
068 private double iGoodSelectionProb = 0.0;
069 private int iMPPLimit = -1;
070
071 private double iWeightDeltaInitialAssignment = 0.0;
072 private double iWeightPotentialConflicts = 0.0;
073 private double iWeightWeightedCoflicts = 0.0;
074 private double iWeightCoflicts = 1.0;
075 private double iWeightNrAssignments = 0.5;
076 private double iWeightValue = 0.0;
077
078 protected int iTabuSize = 0;
079 protected ArrayList iTabu = null;
080 protected int iTabuPos = 0;
081
082 private boolean iMPP = false;
083 private ConflictStatistics iStat = null;
084 private MacPropagation iProp = null;
085 private ViolatedInitials iViolatedInitials = null;
086
087 public GeneralValueSelection() {}
088
089 /** Constructor
090 * @param properties input configuration
091 */
092 public GeneralValueSelection(DataProperties properties) {
093 iMPP = properties.getPropertyBoolean("General.MPP", false);
094 if (iMPP) {
095 iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
096 iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
097 iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
098 }
099 iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00);
100 iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 1.0);
101 iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0);
102
103 iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
104 iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0);
105 iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments", 0.5);
106 iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
107 iTabuSize = properties.getPropertyInt("Value.Tabu", 0);
108 if (iTabuSize > 0)
109 iTabu = new ArrayList(iTabuSize);
110 }
111
112 /** Initialization */
113 public void init(Solver solver) {
114 for (Enumeration i = solver.getExtensions().elements(); i.hasMoreElements();) {
115 Extension extension = (Extension)i.nextElement();
116 if (extension instanceof ConflictStatistics)
117 iStat = (ConflictStatistics)extension;
118 if (extension instanceof MacPropagation)
119 iProp = (MacPropagation)extension;
120 if (extension instanceof ViolatedInitials)
121 iViolatedInitials = (ViolatedInitials)extension;
122 }
123 }
124
125 /** Value selecion */
126 public Value selectValue(Solution solution, Variable selectedVariable) {
127 if (iMPP) {
128 if (selectedVariable.getInitialAssignment() != null) {
129 if (solution.getModel().nrUnassignedVariables()==0) {
130 if (solution.getModel().perturbVariables().size() <= iMPPLimit)
131 iMPPLimit = solution.getModel().perturbVariables().size() - 1;
132 }
133 if (iMPPLimit >= 0 && solution.getModel().perturbVariables().size() > iMPPLimit)
134 return selectedVariable.getInitialAssignment();
135 if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb)
136 return selectedVariable.getInitialAssignment();
137 }
138 }
139
140 Vector values = selectedVariable.values();
141 if (ToolBox.random() <= iRandomWalkProb) return (Value)ToolBox.random(values);
142 if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
143 Collection goodValues = iProp.goodValues(selectedVariable);
144 if (!goodValues.isEmpty()) values = new FastVector(goodValues);
145 }
146 if (values.size() == 1)
147 return (Value)values.firstElement();
148
149 Vector bestValues = null;
150 double bestWeightedSum = 0;
151
152 for (Enumeration i1 = values.elements(); i1.hasMoreElements();) {
153 Value value = (Value)i1.nextElement();
154 if (iTabu != null && iTabu.contains(value)) continue;
155 if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
156 continue;
157
158 Collection conf = solution.getModel().conflictValues(value);
159 if (conf.contains(value)) continue;
160
161 double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(solution.getIteration(), conf, value));
162 double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat.countPotentialConflicts(solution.getIteration(), value, 3));
163
164 long deltaInitialAssignments = 0;
165 if (iMPP && iWeightDeltaInitialAssignment != 0.0) {
166 if (iViolatedInitials != null) {
167 Set violations = iViolatedInitials.getViolatedInitials(value);
168 if (violations != null) {
169 for (Iterator it1 = violations.iterator(); it1.hasNext();) {
170 Value aValue = (Value)it1.next();
171 if (aValue.variable().getAssignment() == null || aValue.variable().getAssignment().equals( aValue))
172 deltaInitialAssignments += 2;
173 }
174 }
175 }
176 for (Iterator it1 = conf.iterator(); it1.hasNext();) {
177 Value aValue = (Value)it1.next();
178 if (aValue.variable().getInitialAssignment() != null)
179 deltaInitialAssignments--;
180 }
181 if (selectedVariable.getInitialAssignment() != null && !selectedVariable.getInitialAssignment().equals(value)) {
182 deltaInitialAssignments++;
183 }
184 if (iMPPLimit >= 0 && (solution.getModel().perturbVariables().size() + deltaInitialAssignments) > iMPPLimit)
185 continue;
186 }
187
188 double weightedSum =
189 (iWeightDeltaInitialAssignment * deltaInitialAssignments)
190 + (iWeightPotentialConflicts * potentialConflicts)
191 + (iWeightWeightedCoflicts * weightedConflicts)
192 + (iWeightCoflicts * conf.size())
193 + (iWeightNrAssignments * value.countAssignments())
194 + (iWeightValue * value.toDouble());
195
196 if (bestValues == null || bestWeightedSum > weightedSum) {
197 bestWeightedSum = weightedSum;
198 if (bestValues == null) bestValues = new FastVector();
199 else bestValues.clear();
200 bestValues.addElement(value);
201 } else {
202 if (bestWeightedSum == weightedSum)
203 bestValues.addElement(value);
204 }
205 }
206
207 Value selectedValue = (Value)(bestValues==null?null:ToolBox.random(bestValues));
208 if (selectedValue == null) selectedValue = (Value)ToolBox.random(values);
209 if (iTabu != null) {
210 if (iTabu.size() == iTabuPos)
211 iTabu.add(selectedValue);
212 else
213 iTabu.set(iTabuPos, selectedValue);
214 iTabuPos = (iTabuPos + 1) % iTabuSize;
215 }
216 return (bestValues == null ? null : selectedValue);
217 }
218
219 }