View Javadoc

1   /*
2    * Copyright 2006 - 2012 Christina Bohk and Roland Ewald
3    *  
4    * Licensed under the Apache License, Version 2.0 (the "License"); 
5    * you may not use this file except in compliance with the License. 
6    * You may obtain a copy of the License at 
7    *  
8    *  http://www.apache.org/licenses/LICENSE-2.0
9    *  
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
13   * See the License for the specific language governing permissions and 
14   * limitations under the License. 
15   */
16  package p3j.simulation.assignments.exhaustive;
17  
18  import java.util.ArrayList;
19  import java.util.HashMap;
20  import java.util.HashSet;
21  import java.util.List;
22  import java.util.Map;
23  
24  import org.jamesii.core.math.random.generators.IRandom;
25  import org.jamesii.core.util.misc.Pair;
26  
27  import p3j.misc.errors.GeneratorError;
28  import p3j.pppm.IProjectionModel;
29  import p3j.pppm.ProjectionModel;
30  import p3j.pppm.parameters.ParameterAssignment;
31  import p3j.pppm.parameters.ParameterInstance;
32  import p3j.pppm.sets.Set;
33  import p3j.pppm.sets.SetType;
34  import p3j.simulation.assignments.plugintype.IParamAssignmentGenerator;
35  
36  /**
37   * Generator that analyses probabilities to select the most probable
38   * combinations first (and also avoid re-trying existing combinations). This
39   * leads to an exhaustive enumeration of all assignments, ordered by their
40   * probability.
41   * 
42   * Created: August 21, 2008
43   * 
44   * @author Christina Bohk
45   * @author Roland Ewald
46   */
47  public class ExhaustiveAssignmentGenerator implements IParamAssignmentGenerator {
48  
49  	/** Simulation parameters to use. */
50  	private ExhaustiveSimParameters parameters;
51  
52  	/** Overall number of configurations. */
53  	private long overallCombinations;
54  
55  	/** Number of current run. */
56  	private int currentRun;
57  
58  	/**
59  	 * Flag that determines if the stopping criterion with respect for assignment
60  	 * probabilities are fulfilled.
61  	 */
62  	private boolean probStopCriterionFulfilled;
63  
64  	/**
65  	 * Overall sum of probabilities of the parameter assignments generated so far.
66  	 */
67  	private double overallProbabilitySum;
68  
69  	/**
70  	 * List of {@link SetTypeManager}. Positions in this list are used in
71  	 * {@link SetTypeAssignment} instances.
72  	 */
73  	private List<SetTypeManager> stManagers = new ArrayList<SetTypeManager>();
74  
75  	/** Helps enumerating the assignments. */
76  	private AssignmentEnumerator assignmentEnumerator;
77  
78  	@Override
79  	public void init(IProjectionModel proj) {
80  		overallCombinations = calculateNumOfCombinations(proj);
81  
82  		// Initialize Settype managers
83  		List<Integer> maxProbIndices = new ArrayList<Integer>();
84  		for (SetType setType : proj.getAllSetTypes()) {
85  			stManagers.add(new SetTypeManager(setType));
86  			maxProbIndices.add(0);
87  		}
88  
89  		// Add first Settype assignment to queue
90  		assignmentEnumerator = new AssignmentEnumerator(new Assignment(
91  		    maxProbIndices, calcAssignmentProbability(maxProbIndices)));
92  	}
93  
94  	@Override
95  	public Pair<Map<ParameterInstance, ParameterAssignment>, List<GeneratorError>> chooseParamAssignments(
96  	    IRandom random) {
97  
98  		List<GeneratorError> errorLog = new ArrayList<GeneratorError>();
99  		Pair<Map<ParameterInstance, ParameterAssignment>, Double> assignment = nextAssignment();
100 		double assignmentProb = assignment.getSecondValue();
101 
102 		currentRun++;
103 
104 		// Check probabilistic stopping criteria
105 		overallProbabilitySum += assignmentProb;
106 		if ((parameters.getDesiredOverallProbability() > 0 && overallProbabilitySum >= parameters
107 		    .getDesiredOverallProbability())
108 		    || (assignmentProb < parameters.getCutOffProbability())) {
109 			probStopCriterionFulfilled = true;
110 		}
111 
112 		return new Pair<Map<ParameterInstance, ParameterAssignment>, List<GeneratorError>>(
113 		    assignment.getFirstValue(), errorLog);
114 	}
115 
116 	/**
117 	 * Generates next assignment.
118 	 * 
119 	 * @return tuple (assignment, probability) containing the next most probable
120 	 *         assignment and its corresponding probability, null if there is none
121 	 *         left
122 	 */
123 	protected Pair<Map<ParameterInstance, ParameterAssignment>, Double> nextAssignment() {
124 
125 		if (assignmentEnumerator.isEmpty()) {
126 			return null;
127 		}
128 
129 		// Add children to queue
130 		Assignment top = assignmentEnumerator.removeMostProbable();
131 		assignmentEnumerator.add(getChildren(top));
132 
133 		// Retrieve result
134 		Map<ParameterInstance, ParameterAssignment> overallAssignment = createMapping(top
135 		    .getAssignmentIndices());
136 		return new Pair<Map<ParameterInstance, ParameterAssignment>, Double>(
137 		    overallAssignment, top.getProbability());
138 	}
139 
140 	/**
141 	 * Peeks for the next Settype assignment to choose.
142 	 * 
143 	 * @return the sets the type assignment
144 	 */
145 	protected Assignment peek() {
146 		return assignmentEnumerator.isEmpty() ? null : assignmentEnumerator
147 		    .getMostProbable();
148 	}
149 
150 	/**
151 	 * Retrieves all possible children for given {@link SetTypeAssignment}.
152 	 * 
153 	 * @param assignment
154 	 *          the given assignment
155 	 * 
156 	 * @return set containing all possible children
157 	 */
158 	protected java.util.Set<Assignment> getChildren(Assignment assignment) {
159 		java.util.Set<Assignment> childs = new HashSet<Assignment>();
160 		final List<Integer> indices = assignment.getAssignmentIndices();
161 		for (int i = 0; i < stManagers.size(); i++) {
162 			int currentIndex = indices.get(i);
163 			if (!stManagers.get(i).hasAssignment(currentIndex + 1)) {
164 				continue;
165 			}
166 			List<Integer> childIndices = new ArrayList<Integer>(indices);
167 			childIndices.set(i, currentIndex + 1);
168 			childs.add(new Assignment(childIndices,
169 			    calcAssignmentProbability(childIndices)));
170 		}
171 		return childs;
172 	}
173 
174 	@Override
175 	public long assignmentsLeft() {
176 
177 		if (probStopCriterionFulfilled) {
178 			return 0;
179 		}
180 
181 		if (parameters.getMaxNumRuns() > 0) {
182 			if (currentRun >= parameters.getMaxNumRuns()) {
183 				return 0;
184 			}
185 			return (long) parameters.getMaxNumRuns() - currentRun;
186 		}
187 
188 		return (long) Math.ceil(overallCombinations
189 		    * parameters.getMaxRunFraction())
190 		    - currentRun;
191 	}
192 
193 	/**
194 	 * Calculates number of different combinations.
195 	 * 
196 	 * @param proj
197 	 *          the given projection setup
198 	 * 
199 	 * @return the number of possible matrix assignments
200 	 */
201 	protected long calculateNumOfCombinations(IProjectionModel proj) {
202 
203 		long num = 1;
204 		for (SetType defType : proj.getAllSetTypes()) {
205 			long numSetTypeCombinations = 0;
206 			for (Set set : defType.getSets()) {
207 				long numSetCombinations = 1;
208 				for (ParameterInstance instance : defType.getDefinedParameters()) {
209 					numSetCombinations *= set.getNumberOfAssignments(instance);
210 				}
211 				numSetTypeCombinations += numSetCombinations;
212 			}
213 			num *= numSetTypeCombinations;
214 		}
215 
216 		return num;
217 	}
218 
219 	/**
220 	 * Calculates number of distinct sets.
221 	 * 
222 	 * @param proj
223 	 *          the projection setup
224 	 * 
225 	 * @return number of possible set combinations
226 	 */
227 	protected long calculateNumOfSetCombinations(ProjectionModel proj) {
228 		long num = 1;
229 		int setTypes = proj.getNumOfSetTypes();
230 		for (int i = 0; i < setTypes; i++) {
231 			num *= proj.getSetType(i).getNumOfSets();
232 		}
233 		return num;
234 	}
235 
236 	/**
237 	 * Calculates the assignment probability for a given list of assignment
238 	 * indices.
239 	 * 
240 	 * @param indices
241 	 *          list of assignment indices
242 	 * 
243 	 * @return calculated probability
244 	 */
245 	protected double calcAssignmentProbability(List<Integer> indices) {
246 		double prob = 1;
247 		for (int i = 0; i < indices.size(); i++) {
248 			prob *= stManagers.get(i).getProbability(indices.get(i));
249 		}
250 		return prob;
251 	}
252 
253 	/**
254 	 * Puts all assignments for the given index list into one map.
255 	 * 
256 	 * @param indices
257 	 *          indices of Settype manager assignments
258 	 * 
259 	 * @return complete parameter map
260 	 */
261 	protected Map<ParameterInstance, ParameterAssignment> createMapping(
262 	    List<Integer> indices) {
263 		Map<ParameterInstance, ParameterAssignment> overallMap = new HashMap<ParameterInstance, ParameterAssignment>();
264 		for (int i = 0; i < indices.size(); i++) {
265 			overallMap.putAll(stManagers.get(i).getAssignment(indices.get(i)));
266 		}
267 		return overallMap;
268 	}
269 
270 	/**
271 	 * Gets the parameters.
272 	 * 
273 	 * @return the parameters
274 	 */
275 	public ExhaustiveSimParameters getParameters() {
276 		return parameters;
277 	}
278 
279 	/**
280 	 * Sets the parameters.
281 	 * 
282 	 * @param parameters
283 	 *          the new parameters
284 	 */
285 	public void setParameters(ExhaustiveSimParameters parameters) {
286 		this.parameters = parameters;
287 	}
288 
289 }