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