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.ParallelFunctionCache;
13 import net.sf.openrocket.optimization.general.Point;
14 import net.sf.openrocket.startup.Application;
15 import net.sf.openrocket.util.Statistics;
18 * A customized implementation of the parallel multidirectional search algorithm by Dennis and Torczon.
20 * This is a parallel pattern search optimization algorithm. The function evaluations are performed
21 * using an ExecutorService. By default a ThreadPoolExecutor is used that has as many thread defined
22 * as the system has processors.
24 public class MultidirectionalSearchOptimizer implements FunctionOptimizer, Statistics {
25 private static final LogHelper log = Application.getLogger();
27 private List<Point> simplex = new ArrayList<Point>();
29 private ParallelFunctionCache functionExecutor;
31 private boolean useExpansion = false;
33 private int stepCount = 0;
34 private int reflectionAcceptance = 0;
35 private int expansionAcceptance = 0;
36 private int coordinateAcceptance = 0;
37 private int reductionFallback = 0;
40 public MultidirectionalSearchOptimizer() {
44 public MultidirectionalSearchOptimizer(ParallelFunctionCache functionCache) {
45 this.functionExecutor = functionCache;
51 public void optimize(Point initial, OptimizationController control) {
52 FunctionCacheComparator comparator = new FunctionCacheComparator(functionExecutor);
54 final List<Point> pattern = SearchPattern.square(initial.dim());
55 log.info("Starting optimization at " + initial + " with pattern " + pattern);
59 boolean simplexComputed = false;
62 // Set up the current simplex
65 for (Point p : pattern) {
66 simplex.add(initial.add(p.mul(step)));
70 List<Point> reflection = new ArrayList<Point>(simplex.size());
71 List<Point> expansion = new ArrayList<Point>(simplex.size());
72 List<Point> coordinateSearch = new ArrayList<Point>(simplex.size());
77 log.debug("Starting optimization step with simplex " + simplex +
78 (simplexComputed ? "" : " (not computed)"));
81 if (!simplexComputed) {
82 // TODO: Could something be computed in parallel?
83 functionExecutor.compute(simplex);
84 functionExecutor.waitFor(simplex);
85 Collections.sort(simplex, comparator);
86 simplexComputed = true;
89 current = simplex.get(0);
90 currentValue = functionExecutor.getValue(current);
93 * Compute and queue the next points in likely order of usefulness.
94 * Expansion is unlikely as we're mainly dealing with bounded optimization.
96 createReflection(simplex, reflection);
97 createCoordinateSearch(current, step, coordinateSearch);
99 createExpansion(simplex, expansion);
101 functionExecutor.compute(reflection);
102 functionExecutor.compute(coordinateSearch);
104 functionExecutor.compute(expansion);
106 // Check reflection acceptance
107 log.debug("Computing reflection");
108 functionExecutor.waitFor(reflection);
110 if (accept(reflection, currentValue)) {
112 log.debug("Reflection was successful, aborting coordinate search, " +
113 (useExpansion ? "computing" : "skipping") + " expansion");
115 functionExecutor.abort(coordinateSearch);
118 simplex.add(current);
119 simplex.addAll(reflection);
120 Collections.sort(simplex, comparator);
125 * Assume expansion to be unsuccessful, queue next reflection while computing expansion.
127 createReflection(simplex, reflection);
129 functionExecutor.compute(reflection);
130 functionExecutor.waitFor(expansion);
132 if (accept(expansion, currentValue)) {
133 log.debug("Expansion was successful, aborting reflection");
134 functionExecutor.abort(reflection);
137 simplex.add(current);
138 simplex.addAll(expansion);
140 Collections.sort(simplex, comparator);
141 expansionAcceptance++;
143 log.debug("Expansion failed");
144 reflectionAcceptance++;
148 reflectionAcceptance++;
153 log.debug("Reflection was unsuccessful, aborting expansion, computing coordinate search");
155 functionExecutor.abort(expansion);
158 * Assume coordinate search to be unsuccessful, queue contraction step while computing.
161 functionExecutor.compute(simplex);
162 functionExecutor.waitFor(coordinateSearch);
164 if (accept(coordinateSearch, currentValue)) {
166 log.debug("Coordinate search successful, reseting simplex");
167 List<Point> toAbort = new LinkedList<Point>(simplex);
169 simplex.add(current);
170 for (Point p : pattern) {
171 simplex.add(current.add(p.mul(step)));
173 toAbort.removeAll(simplex);
174 functionExecutor.abort(toAbort);
175 simplexComputed = false;
176 coordinateAcceptance++;
179 log.debug("Coordinate search unsuccessful, halving step.");
186 log.debug("Ending optimization step with simplex " + simplex);
188 if (Thread.interrupted()) {
189 throw new InterruptedException();
192 } while (control.stepTaken(current, currentValue, simplex.get(0),
193 functionExecutor.getValue(simplex.get(0)), step));
195 } catch (InterruptedException e) {
196 log.info("Optimization was interrupted with InterruptedException");
199 log.info("Finishing optimization at point " + simplex.get(0) + " value = " +
200 functionExecutor.getValue(simplex.get(0)));
205 private void createReflection(List<Point> base, List<Point> reflection) {
206 Point current = base.get(0);
208 for (int i = 1; i < base.size(); i++) {
209 Point p = current.mul(2).sub(base.get(i));
214 private void createExpansion(List<Point> base, List<Point> expansion) {
215 Point current = base.get(0);
217 for (int i = 1; i < base.size(); i++) {
218 Point p = current.mul(3).sub(base.get(i).mul(2));
223 private void halveStep(List<Point> base) {
224 Point current = base.get(0);
225 for (int i = 1; i < base.size(); i++) {
226 Point p = base.get(i);
227 p = p.add(current).mul(0.5);
232 private void createCoordinateSearch(Point current, double step, List<Point> coordinateDirections) {
233 coordinateDirections.clear();
234 for (int i = 0; i < current.dim(); i++) {
235 Point p = new Point(current.dim());
237 coordinateDirections.add(current.add(p));
238 coordinateDirections.add(current.sub(p));
243 private boolean accept(List<Point> points, double currentValue) {
244 for (Point p : points) {
245 if (functionExecutor.getValue(p) < currentValue) {
255 public Point getOptimumPoint() {
256 if (simplex.size() == 0) {
257 throw new IllegalStateException("Optimization has not been called, simplex is empty");
259 return simplex.get(0);
263 public double getOptimumValue() {
264 return functionExecutor.getValue(getOptimumPoint());
268 public FunctionCache getFunctionCache() {
269 return functionExecutor;
273 public void setFunctionCache(FunctionCache functionCache) {
274 if (!(functionCache instanceof ParallelFunctionCache)) {
275 throw new IllegalArgumentException("Function cache needs to be a ParallelFunctionCache: " + functionCache);
277 this.functionExecutor = (ParallelFunctionCache) functionCache;
281 public String getStatistics() {
282 return "MultidirectionalSearchOptimizer[stepCount=" + stepCount +
283 ", reflectionAcceptance=" + reflectionAcceptance +
284 ", expansionAcceptance=" + expansionAcceptance +
285 ", coordinateAcceptance=" + coordinateAcceptance +
286 ", reductionFallback=" + reductionFallback;
290 public void resetStatistics() {
292 reflectionAcceptance = 0;
293 expansionAcceptance = 0;
294 coordinateAcceptance = 0;
295 reductionFallback = 0;