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                                 System.err.println("stepsize = " + step);
 115                                 System.err.println("Simplex    = " + simplex);
 116                                 System.err.println("Reflection = " + reflection);
 117                                 log.debug("Computing reflection");
 118                                 functionExecutor.waitFor(reflection);
 119
 120                                 if (accept(reflection, currentValue)) {
 121
 122                                         log.debug("Reflection was successful, aborting coordinate search, " +
 123                                                         (useExpansion ? "computing" : "skipping") + " expansion");
 124
 125                                         if (useCoordinateSearch)
 126                                                 functionExecutor.abort(coordinateSearch);
 127
 128                                         simplex.clear();
 129                                         simplex.add(current);
 130                                         simplex.addAll(reflection);
 131                                         Collections.sort(simplex, comparator);
 132
 133                                         if (useExpansion) {
 134
 135                                                 /*
 136                                                  * Assume expansion to be unsuccessful, queue next reflection while computing expansion.
 137                                                  */
 138                                                 createReflection(simplex, reflection);
 139
 140                                                 functionExecutor.compute(reflection);
 141                                                 functionExecutor.waitFor(expansion);
 142
 143                                                 if (accept(expansion, currentValue)) {
 144                                                         log.debug("Expansion was successful, aborting reflection");
 145                                                         functionExecutor.abort(reflection);
 146
 147                                                         simplex.clear();
 148                                                         simplex.add(current);
 149                                                         simplex.addAll(expansion);
 150                                                         step *= 2;
 151                                                         Collections.sort(simplex, comparator);
 152                                                         expansionAcceptance++;
 153                                                 } else {
 154                                                         log.debug("Expansion failed");
 155                                                         reflectionAcceptance++;
 156                                                 }
 157
 158                                         } else {
 159                                                 reflectionAcceptance++;
 160                                         }
 161
 162                                 } else {
 163
 164                                         log.debug("Reflection was unsuccessful, aborting expansion, computing coordinate search");
 165
 166                                         functionExecutor.abort(expansion);
 167
 168                                         /*
 169                                          * Assume coordinate search to be unsuccessful, queue contraction step while computing.
 170                                          */
 171                                         halveStep(simplex);
 172                                         functionExecutor.compute(simplex);
 173
 174                                         if (useCoordinateSearch) {
 175                                                 functionExecutor.waitFor(coordinateSearch);
 176
 177                                                 if (accept(coordinateSearch, currentValue)) {
 178
 179                                                         log.debug("Coordinate search successful, reseting simplex");
 180                                                         List<Point> toAbort = new LinkedList<Point>(simplex);
 181                                                         simplex.clear();
 182                                                         simplex.add(current);
 183                                                         for (Point p : pattern) {
 184                                                                 simplex.add(current.add(p.mul(step)));
 185                                                         }
 186                                                         toAbort.removeAll(simplex);
 187                                                         functionExecutor.abort(toAbort);
 188                                                         simplexComputed = false;
 189                                                         coordinateAcceptance++;
 190
 191                                                 } else {
 192                                                         log.debug("Coordinate search unsuccessful, halving step.");
 193                                                         step /= 2;
 194                                                         simplexComputed = false;
 195                                                         reductionFallback++;
 196                                                 }
 197                                         } else {
 198                                                 log.debug("Coordinate search not used, halving step.");
 199                                                 step /= 2;
 200                                                 simplexComputed = false;
 201                                                 reductionFallback++;
 202                                         }
 203
 204                                 }
 205
 206                                 log.debug("Ending optimization step with simplex " + simplex);
 207
 208                                 continueOptimization = control.stepTaken(current, currentValue, simplex.get(0),
 209                                                 functionExecutor.getValue(simplex.get(0)), step);
 210
 211                                 if (Thread.interrupted()) {
 212                                         throw new InterruptedException();
 213                                 }
 214
 215                         }
 216
 217                 } catch (InterruptedException e) {
 218                         log.info("Optimization was interrupted with InterruptedException");
 219                 }
 220
 221                 log.info("Finishing optimization at point " + simplex.get(0) + " value = " +
 222                                 functionExecutor.getValue(simplex.get(0)));
 223                 log.info("Optimization statistics: " + getStatistics());
 224         }
 225
 226
 227
 228         private void createReflection(List<Point> base, List<Point> reflection) {
 229                 Point current = base.get(0);
 230                 reflection.clear();
 231
 232                 /*  new = - (old - current) + current = 2*current - old  */
 233                 for (int i = 1; i < base.size(); i++) {
 234                         Point p = base.get(i);
 235                         p = current.mul(2).sub(p);
 236                         reflection.add(p);
 237                 }
 238         }
 239
 240         private void createExpansion(List<Point> base, List<Point> expansion) {
 241                 Point current = base.get(0);
 242                 expansion.clear();
 243                 for (int i = 1; i < base.size(); i++) {
 244                         Point p = current.mul(3).sub(base.get(i).mul(2));
 245                         expansion.add(p);
 246                 }
 247         }
 248
 249         private void halveStep(List<Point> base) {
 250                 Point current = base.get(0);
 251                 for (int i = 1; i < base.size(); i++) {
 252                         Point p = base.get(i);
 253
 254                         /* new = (old - current)*0.5 + current = old*0.5 + current*0.5 = (old + current)*0.5 */
 255
 256                         p = p.add(current).mul(0.5);
 257                         base.set(i, p);
 258                 }
 259         }
 260
 261         private void createCoordinateSearch(Point current, double step, List<Point> coordinateDirections) {
 262                 coordinateDirections.clear();
 263                 for (int i = 0; i < current.dim(); i++) {
 264                         Point p = new Point(current.dim());
 265                         p = p.set(i, step);
 266                         coordinateDirections.add(current.add(p));
 267                         coordinateDirections.add(current.sub(p));
 268                 }
 269         }
 270
 271
 272         private boolean accept(List<Point> points, double currentValue) {
 273                 for (Point p : points) {
 274                         if (functionExecutor.getValue(p) < currentValue) {
 275                                 return true;
 276                         }
 277                 }
 278                 return false;
 279         }
 280
 281
 282
 283         @Override
 284         public Point getOptimumPoint() {
 285                 if (simplex.size() == 0) {
 286                         throw new IllegalStateException("Optimization has not been called, simplex is empty");
 287                 }
 288                 return simplex.get(0);
 289         }
 290
 291         @Override
 292         public double getOptimumValue() {
 293                 return functionExecutor.getValue(getOptimumPoint());
 294         }
 295
 296         @Override
 297         public FunctionCache getFunctionCache() {
 298                 return functionExecutor;
 299         }
 300
 301         @Override
 302         public void setFunctionCache(FunctionCache functionCache) {
 303                 if (!(functionCache instanceof ParallelFunctionCache)) {
 304                         throw new IllegalArgumentException("Function cache needs to be a ParallelFunctionCache: " + functionCache);
 305                 }
 306                 this.functionExecutor = (ParallelFunctionCache) functionCache;
 307         }
 308
 309         @Override
 310         public String getStatistics() {
 311                 return "MultidirectionalSearchOptimizer[stepCount=" + stepCount +
 312                                 ", reflectionAcceptance=" + reflectionAcceptance +
 313                                 ", expansionAcceptance=" + expansionAcceptance +
 314                                 ", coordinateAcceptance=" + coordinateAcceptance +
 315                                 ", reductionFallback=" + reductionFallback;
 316         }
 317
 318         @Override
 319         public void resetStatistics() {
 320                 stepCount = 0;
 321                 reflectionAcceptance = 0;
 322                 expansionAcceptance = 0;
 323                 coordinateAcceptance = 0;
 324                 reductionFallback = 0;
 325         }
 326
 327 }