git.gag.com Git - debian/openrocket/blob - src/net/sf/openrocket/optimization/general/multidim/MultidirectionalSearchOptimizer.java

   1 package net.sf.openrocket.optimization.general.multidim;
   2
   3 import java.util.ArrayList;
   4 import java.util.Collections;
   5 import java.util.LinkedList;
   6 import java.util.List;
   7
   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;
  17
  18 /**
  19  * A customized implementation of the parallel multidirectional search algorithm by Dennis and Torczon.
  20  * <p>
  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.
  24  */
  25 public class MultidirectionalSearchOptimizer implements FunctionOptimizer, Statistics {
  26         private static final LogHelper log = Application.getLogger();
  27
  28         private List<Point> simplex = new ArrayList<Point>();
  29
  30         private ParallelFunctionCache functionExecutor;
  31
  32         private boolean useExpansion = false;
  33
  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;
  39
  40
  41         public MultidirectionalSearchOptimizer() {
  42                 // No-op
  43         }
  44
  45         public MultidirectionalSearchOptimizer(ParallelFunctionCache functionCache) {
  46                 this.functionExecutor = functionCache;
  47         }
  48
  49
  50
  51         @Override
  52         public void optimize(Point initial, OptimizationController control) throws OptimizationException {
  53                 FunctionCacheComparator comparator = new FunctionCacheComparator(functionExecutor);
  54
  55                 final List<Point> pattern = SearchPattern.square(initial.dim());
  56                 log.info("Starting optimization at " + initial + " with pattern " + pattern);
  57
  58                 try {
  59
  60                         boolean simplexComputed = false;
  61                         double step = 0.5;
  62
  63                         // Set up the current simplex
  64                         simplex.clear();
  65                         simplex.add(initial);
  66                         for (Point p : pattern) {
  67                                 simplex.add(initial.add(p.mul(step)));
  68                         }
  69
  70                         // Normal iterations
  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());
  74                         Point current;
  75                         double currentValue;
  76                         do {
  77
  78                                 log.debug("Starting optimization step with simplex " + simplex +
  79                                                 (simplexComputed ? "" : " (not computed)"));
  80                                 stepCount++;
  81
  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;
  88                                 }
  89
  90                                 current = simplex.get(0);
  91                                 currentValue = functionExecutor.getValue(current);
  92
  93                                 /*
  94                                  * Compute and queue the next points in likely order of usefulness.
  95                                  * Expansion is unlikely as we're mainly dealing with bounded optimization.
  96                                  */
  97                                 createReflection(simplex, reflection);
  98                                 createCoordinateSearch(current, step, coordinateSearch);
  99                                 if (useExpansion)
 100                                         createExpansion(simplex, expansion);
 101
 102                                 functionExecutor.compute(reflection);
 103                                 functionExecutor.compute(coordinateSearch);
 104                                 if (useExpansion)
 105                                         functionExecutor.compute(expansion);
 106
 107                                 // Check reflection acceptance
 108                                 log.debug("Computing reflection");
 109                                 functionExecutor.waitFor(reflection);
 110
 111                                 if (accept(reflection, currentValue)) {
 112
 113                                         log.debug("Reflection was successful, aborting coordinate search, " +
 114                                                         (useExpansion ? "computing" : "skipping") + " expansion");
 115
 116                                         functionExecutor.abort(coordinateSearch);
 117
 118                                         simplex.clear();
 119                                         simplex.add(current);
 120                                         simplex.addAll(reflection);
 121                                         Collections.sort(simplex, comparator);
 122
 123                                         if (useExpansion) {
 124
 125                                                 /*
 126                                                  * Assume expansion to be unsuccessful, queue next reflection while computing expansion.
 127                                                  */
 128                                                 createReflection(simplex, reflection);
 129
 130                                                 functionExecutor.compute(reflection);
 131                                                 functionExecutor.waitFor(expansion);
 132
 133                                                 if (accept(expansion, currentValue)) {
 134                                                         log.debug("Expansion was successful, aborting reflection");
 135                                                         functionExecutor.abort(reflection);
 136
 137                                                         simplex.clear();
 138                                                         simplex.add(current);
 139                                                         simplex.addAll(expansion);
 140                                                         step *= 2;
 141                                                         Collections.sort(simplex, comparator);
 142                                                         expansionAcceptance++;
 143                                                 } else {
 144                                                         log.debug("Expansion failed");
 145                                                         reflectionAcceptance++;
 146                                                 }
 147
 148                                         } else {
 149                                                 reflectionAcceptance++;
 150                                         }
 151
 152                                 } else {
 153
 154                                         log.debug("Reflection was unsuccessful, aborting expansion, computing coordinate search");
 155
 156                                         functionExecutor.abort(expansion);
 157
 158                                         /*
 159                                          * Assume coordinate search to be unsuccessful, queue contraction step while computing.
 160                                          */
 161                                         halveStep(simplex);
 162                                         functionExecutor.compute(simplex);
 163                                         functionExecutor.waitFor(coordinateSearch);
 164
 165                                         if (accept(coordinateSearch, currentValue)) {
 166
 167                                                 log.debug("Coordinate search successful, reseting simplex");
 168                                                 List<Point> toAbort = new LinkedList<Point>(simplex);
 169                                                 simplex.clear();
 170                                                 simplex.add(current);
 171                                                 for (Point p : pattern) {
 172                                                         simplex.add(current.add(p.mul(step)));
 173                                                 }
 174                                                 toAbort.removeAll(simplex);
 175                                                 functionExecutor.abort(toAbort);
 176                                                 simplexComputed = false;
 177                                                 coordinateAcceptance++;
 178
 179                                         } else {
 180                                                 log.debug("Coordinate search unsuccessful, halving step.");
 181                                                 step /= 2;
 182                                                 reductionFallback++;
 183                                         }
 184
 185                                 }
 186
 187                                 log.debug("Ending optimization step with simplex " + simplex);
 188
 189                                 if (Thread.interrupted()) {
 190                                         throw new InterruptedException();
 191                                 }
 192
 193                         } while (control.stepTaken(current, currentValue, simplex.get(0),
 194                                         functionExecutor.getValue(simplex.get(0)), step));
 195
 196                 } catch (InterruptedException e) {
 197                         log.info("Optimization was interrupted with InterruptedException");
 198                 }
 199
 200                 log.info("Finishing optimization at point " + simplex.get(0) + " value = " +
 201                                 functionExecutor.getValue(simplex.get(0)));
 202         }
 203
 204
 205
 206         private void createReflection(List<Point> base, List<Point> reflection) {
 207                 Point current = base.get(0);
 208                 reflection.clear();
 209                 for (int i = 1; i < base.size(); i++) {
 210                         Point p = current.mul(2).sub(base.get(i));
 211                         reflection.add(p);
 212                 }
 213         }
 214
 215         private void createExpansion(List<Point> base, List<Point> expansion) {
 216                 Point current = base.get(0);
 217                 expansion.clear();
 218                 for (int i = 1; i < base.size(); i++) {
 219                         Point p = current.mul(3).sub(base.get(i).mul(2));
 220                         expansion.add(p);
 221                 }
 222         }
 223
 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);
 229                         base.set(i, p);
 230                 }
 231         }
 232
 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());
 237                         p = p.set(i, step);
 238                         coordinateDirections.add(current.add(p));
 239                         coordinateDirections.add(current.sub(p));
 240                 }
 241         }
 242
 243
 244         private boolean accept(List<Point> points, double currentValue) {
 245                 for (Point p : points) {
 246                         if (functionExecutor.getValue(p) < currentValue) {
 247                                 return true;
 248                         }
 249                 }
 250                 return false;
 251         }
 252
 253
 254
 255         @Override
 256         public Point getOptimumPoint() {
 257                 if (simplex.size() == 0) {
 258                         throw new IllegalStateException("Optimization has not been called, simplex is empty");
 259                 }
 260                 return simplex.get(0);
 261         }
 262
 263         @Override
 264         public double getOptimumValue() {
 265                 return functionExecutor.getValue(getOptimumPoint());
 266         }
 267
 268         @Override
 269         public FunctionCache getFunctionCache() {
 270                 return functionExecutor;
 271         }
 272
 273         @Override
 274         public void setFunctionCache(FunctionCache functionCache) {
 275                 if (!(functionCache instanceof ParallelFunctionCache)) {
 276                         throw new IllegalArgumentException("Function cache needs to be a ParallelFunctionCache: " + functionCache);
 277                 }
 278                 this.functionExecutor = (ParallelFunctionCache) functionCache;
 279         }
 280
 281         @Override
 282         public String getStatistics() {
 283                 return "MultidirectionalSearchOptimizer[stepCount=" + stepCount +
 284                                 ", reflectionAcceptance=" + reflectionAcceptance +
 285                                 ", expansionAcceptance=" + expansionAcceptance +
 286                                 ", coordinateAcceptance=" + coordinateAcceptance +
 287                                 ", reductionFallback=" + reductionFallback;
 288         }
 289
 290         @Override
 291         public void resetStatistics() {
 292                 stepCount = 0;
 293                 reflectionAcceptance = 0;
 294                 expansionAcceptance = 0;
 295                 coordinateAcceptance = 0;
 296                 reductionFallback = 0;
 297         }
 298
 299 }