1 package net.sf.openrocket.optimization.general.multidim;
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.LinkedList;
8 import net.sf.openrocket.logging.LogHelper;
9 import net.sf.openrocket.optimization.general.FunctionCache;
10 import net.sf.openrocket.optimization.general.FunctionOptimizer;
11 import net.sf.openrocket.optimization.general.OptimizationController;
12 import net.sf.openrocket.optimization.general.OptimizationException;
13 import net.sf.openrocket.optimization.general.ParallelFunctionCache;
14 import net.sf.openrocket.optimization.general.Point;
15 import net.sf.openrocket.startup.Application;
16 import net.sf.openrocket.util.Statistics;
19 * A customized implementation of the parallel multidirectional search algorithm by Dennis and Torczon.
21 * This is a parallel pattern search optimization algorithm. The function evaluations are performed
22 * using an ExecutorService. By default a ThreadPoolExecutor is used that has as many thread defined
23 * as the system has processors.
25 public class MultidirectionalSearchOptimizer implements FunctionOptimizer, Statistics {
26 private static final LogHelper log = Application.getLogger();
28 private List<Point> simplex = new ArrayList<Point>();
30 private ParallelFunctionCache functionExecutor;
32 private boolean useExpansion = false;
34 private int stepCount = 0;
35 private int reflectionAcceptance = 0;
36 private int expansionAcceptance = 0;
37 private int coordinateAcceptance = 0;
38 private int reductionFallback = 0;
41 public MultidirectionalSearchOptimizer() {
45 public MultidirectionalSearchOptimizer(ParallelFunctionCache functionCache) {
46 this.functionExecutor = functionCache;
52 public void optimize(Point initial, OptimizationController control) throws OptimizationException {
53 FunctionCacheComparator comparator = new FunctionCacheComparator(functionExecutor);
55 final List<Point> pattern = SearchPattern.square(initial.dim());
56 log.info("Starting optimization at " + initial + " with pattern " + pattern);
60 boolean simplexComputed = false;
63 // Set up the current simplex
66 for (Point p : pattern) {
67 simplex.add(initial.add(p.mul(step)));
71 List<Point> reflection = new ArrayList<Point>(simplex.size());
72 List<Point> expansion = new ArrayList<Point>(simplex.size());
73 List<Point> coordinateSearch = new ArrayList<Point>(simplex.size());
78 log.debug("Starting optimization step with simplex " + simplex +
79 (simplexComputed ? "" : " (not computed)"));
82 if (!simplexComputed) {
83 // TODO: Could something be computed in parallel?
84 functionExecutor.compute(simplex);
85 functionExecutor.waitFor(simplex);
86 Collections.sort(simplex, comparator);
87 simplexComputed = true;
90 current = simplex.get(0);
91 currentValue = functionExecutor.getValue(current);
94 * Compute and queue the next points in likely order of usefulness.
95 * Expansion is unlikely as we're mainly dealing with bounded optimization.
97 createReflection(simplex, reflection);
98 createCoordinateSearch(current, step, coordinateSearch);
100 createExpansion(simplex, expansion);
102 functionExecutor.compute(reflection);
103 functionExecutor.compute(coordinateSearch);
105 functionExecutor.compute(expansion);
107 // Check reflection acceptance
108 log.debug("Computing reflection");
109 functionExecutor.waitFor(reflection);
111 if (accept(reflection, currentValue)) {
113 log.debug("Reflection was successful, aborting coordinate search, " +
114 (useExpansion ? "computing" : "skipping") + " expansion");
116 functionExecutor.abort(coordinateSearch);
119 simplex.add(current);
120 simplex.addAll(reflection);
121 Collections.sort(simplex, comparator);
126 * Assume expansion to be unsuccessful, queue next reflection while computing expansion.
128 createReflection(simplex, reflection);
130 functionExecutor.compute(reflection);
131 functionExecutor.waitFor(expansion);
133 if (accept(expansion, currentValue)) {
134 log.debug("Expansion was successful, aborting reflection");
135 functionExecutor.abort(reflection);
138 simplex.add(current);
139 simplex.addAll(expansion);
141 Collections.sort(simplex, comparator);
142 expansionAcceptance++;
144 log.debug("Expansion failed");
145 reflectionAcceptance++;
149 reflectionAcceptance++;
154 log.debug("Reflection was unsuccessful, aborting expansion, computing coordinate search");
156 functionExecutor.abort(expansion);
159 * Assume coordinate search to be unsuccessful, queue contraction step while computing.
162 functionExecutor.compute(simplex);
163 functionExecutor.waitFor(coordinateSearch);
165 if (accept(coordinateSearch, currentValue)) {
167 log.debug("Coordinate search successful, reseting simplex");
168 List<Point> toAbort = new LinkedList<Point>(simplex);
170 simplex.add(current);
171 for (Point p : pattern) {
172 simplex.add(current.add(p.mul(step)));
174 toAbort.removeAll(simplex);
175 functionExecutor.abort(toAbort);
176 simplexComputed = false;
177 coordinateAcceptance++;
180 log.debug("Coordinate search unsuccessful, halving step.");
187 log.debug("Ending optimization step with simplex " + simplex);
189 if (Thread.interrupted()) {
190 throw new InterruptedException();
193 } while (control.stepTaken(current, currentValue, simplex.get(0),
194 functionExecutor.getValue(simplex.get(0)), step));
196 } catch (InterruptedException e) {
197 log.info("Optimization was interrupted with InterruptedException");
200 log.info("Finishing optimization at point " + simplex.get(0) + " value = " +
201 functionExecutor.getValue(simplex.get(0)));
206 private void createReflection(List<Point> base, List<Point> reflection) {
207 Point current = base.get(0);
209 for (int i = 1; i < base.size(); i++) {
210 Point p = current.mul(2).sub(base.get(i));
215 private void createExpansion(List<Point> base, List<Point> expansion) {
216 Point current = base.get(0);
218 for (int i = 1; i < base.size(); i++) {
219 Point p = current.mul(3).sub(base.get(i).mul(2));
224 private void halveStep(List<Point> base) {
225 Point current = base.get(0);
226 for (int i = 1; i < base.size(); i++) {
227 Point p = base.get(i);
228 p = p.add(current).mul(0.5);
233 private void createCoordinateSearch(Point current, double step, List<Point> coordinateDirections) {
234 coordinateDirections.clear();
235 for (int i = 0; i < current.dim(); i++) {
236 Point p = new Point(current.dim());
238 coordinateDirections.add(current.add(p));
239 coordinateDirections.add(current.sub(p));
244 private boolean accept(List<Point> points, double currentValue) {
245 for (Point p : points) {
246 if (functionExecutor.getValue(p) < currentValue) {
256 public Point getOptimumPoint() {
257 if (simplex.size() == 0) {
258 throw new IllegalStateException("Optimization has not been called, simplex is empty");
260 return simplex.get(0);
264 public double getOptimumValue() {
265 return functionExecutor.getValue(getOptimumPoint());
269 public FunctionCache getFunctionCache() {
270 return functionExecutor;
274 public void setFunctionCache(FunctionCache functionCache) {
275 if (!(functionCache instanceof ParallelFunctionCache)) {
276 throw new IllegalArgumentException("Function cache needs to be a ParallelFunctionCache: " + functionCache);
278 this.functionExecutor = (ParallelFunctionCache) functionCache;
282 public String getStatistics() {
283 return "MultidirectionalSearchOptimizer[stepCount=" + stepCount +
284 ", reflectionAcceptance=" + reflectionAcceptance +
285 ", expansionAcceptance=" + expansionAcceptance +
286 ", coordinateAcceptance=" + coordinateAcceptance +
287 ", reductionFallback=" + reductionFallback;
291 public void resetStatistics() {
293 reflectionAcceptance = 0;
294 expansionAcceptance = 0;
295 coordinateAcceptance = 0;
296 reductionFallback = 0;