git.gag.com Git - debian/openrocket/blob - core/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                                                         simplexComputed = false;
 192                                                         reductionFallback++;
 193                                                 }
 194                                         } else {
 195                                                 log.debug("Coordinate search not used, halving step.");
 196                                                 step /= 2;
 197                                                 simplexComputed = false;
 198                                                 reductionFallback++;
 199                                         }
 200
 201                                 }
 202
 203                                 log.debug("Ending optimization step with simplex " + simplex);
 204
 205                                 continueOptimization = control.stepTaken(current, currentValue, simplex.get(0),
 206                                                 functionExecutor.getValue(simplex.get(0)), step);
 207
 208                                 if (Thread.interrupted()) {
 209                                         throw new InterruptedException();
 210                                 }
 211
 212                         }
 213
 214                 } catch (InterruptedException e) {
 215                         log.info("Optimization was interrupted with InterruptedException");
 216                 }
 217
 218                 log.info("Finishing optimization at point " + simplex.get(0) + " value = " +
 219                                 functionExecutor.getValue(simplex.get(0)));
 220                 log.info("Optimization statistics: " + getStatistics());
 221         }
 222
 223
 224
 225         private void createReflection(List<Point> base, List<Point> reflection) {
 226                 Point current = base.get(0);
 227                 reflection.clear();
 228
 229                 /*  new = - (old - current) + current = 2*current - old  */
 230                 for (int i = 1; i < base.size(); i++) {
 231                         Point p = base.get(i);
 232                         p = current.mul(2).sub(p);
 233                         reflection.add(p);
 234                 }
 235         }
 236
 237         private void createExpansion(List<Point> base, List<Point> expansion) {
 238                 Point current = base.get(0);
 239                 expansion.clear();
 240                 for (int i = 1; i < base.size(); i++) {
 241                         Point p = current.mul(3).sub(base.get(i).mul(2));
 242                         expansion.add(p);
 243                 }
 244         }
 245
 246         private void halveStep(List<Point> base) {
 247                 Point current = base.get(0);
 248                 for (int i = 1; i < base.size(); i++) {
 249                         Point p = base.get(i);
 250
 251                         /* new = (old - current)*0.5 + current = old*0.5 + current*0.5 = (old + current)*0.5 */
 252
 253                         p = p.add(current).mul(0.5);
 254                         base.set(i, p);
 255                 }
 256         }
 257
 258         private void createCoordinateSearch(Point current, double step, List<Point> coordinateDirections) {
 259                 coordinateDirections.clear();
 260                 for (int i = 0; i < current.dim(); i++) {
 261                         Point p = new Point(current.dim());
 262                         p = p.set(i, step);
 263                         coordinateDirections.add(current.add(p));
 264                         coordinateDirections.add(current.sub(p));
 265                 }
 266         }
 267
 268
 269         private boolean accept(List<Point> points, double currentValue) {
 270                 for (Point p : points) {
 271                         if (functionExecutor.getValue(p) < currentValue) {
 272                                 return true;
 273                         }
 274                 }
 275                 return false;
 276         }
 277
 278
 279
 280         @Override
 281         public Point getOptimumPoint() {
 282                 if (simplex.size() == 0) {
 283                         throw new IllegalStateException("Optimization has not been called, simplex is empty");
 284                 }
 285                 return simplex.get(0);
 286         }
 287
 288         @Override
 289         public double getOptimumValue() {
 290                 return functionExecutor.getValue(getOptimumPoint());
 291         }
 292
 293         @Override
 294         public FunctionCache getFunctionCache() {
 295                 return functionExecutor;
 296         }
 297
 298         @Override
 299         public void setFunctionCache(FunctionCache functionCache) {
 300                 if (!(functionCache instanceof ParallelFunctionCache)) {
 301                         throw new IllegalArgumentException("Function cache needs to be a ParallelFunctionCache: " + functionCache);
 302                 }
 303                 this.functionExecutor = (ParallelFunctionCache) functionCache;
 304         }
 305
 306         @Override
 307         public String getStatistics() {
 308                 return "MultidirectionalSearchOptimizer[stepCount=" + stepCount +
 309                                 ", reflectionAcceptance=" + reflectionAcceptance +
 310                                 ", expansionAcceptance=" + expansionAcceptance +
 311                                 ", coordinateAcceptance=" + coordinateAcceptance +
 312                                 ", reductionFallback=" + reductionFallback;
 313         }
 314
 315         @Override
 316         public void resetStatistics() {
 317                 stepCount = 0;
 318                 reflectionAcceptance = 0;
 319                 expansionAcceptance = 0;
 320                 coordinateAcceptance = 0;
 321                 reductionFallback = 0;
 322         }
 323
 324 }