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