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

   1 package net.sf.openrocket.optimization.general.onedim;
   2
   3 import net.sf.openrocket.logging.LogHelper;
   4 import net.sf.openrocket.optimization.general.FunctionCache;
   5 import net.sf.openrocket.optimization.general.FunctionOptimizer;
   6 import net.sf.openrocket.optimization.general.OptimizationController;
   7 import net.sf.openrocket.optimization.general.OptimizationException;
   8 import net.sf.openrocket.optimization.general.ParallelFunctionCache;
   9 import net.sf.openrocket.optimization.general.Point;
  10 import net.sf.openrocket.startup.Application;
  11 import net.sf.openrocket.util.MathUtil;
  12 import net.sf.openrocket.util.Statistics;
  13
  14 /**
  15  * An implementation of a one-dimensional golden section search method
  16  * (see e.g. Nonlinear programming, Bazaraa, Sherall, Shetty, 2nd edition, p. 270)
  17  * <p>
  18  * This implementation attempts to guess future evaluations and computes them in parallel
  19  * with the next point.
  20  * <p>
  21  * The optimization can be aborted by interrupting the current thread.
  22  */
  23 public class GoldenSectionSearchOptimizer implements FunctionOptimizer, Statistics {
  24         private static final LogHelper log = Application.getLogger();
  25
  26         private static final double ALPHA = (Math.sqrt(5) - 1) / 2.0;
  27
  28
  29         private ParallelFunctionCache functionExecutor;
  30
  31         private Point current = null;
  32
  33         private int guessSuccess = 0;
  34         private int guessFailure = 0;
  35
  36
  37         /**
  38          * Construct an optimizer with no function executor.
  39          */
  40         public GoldenSectionSearchOptimizer() {
  41                 // No-op
  42         }
  43
  44         /**
  45          * Construct an optimizer.
  46          *
  47          * @param functionExecutor      the function executor.
  48          */
  49         public GoldenSectionSearchOptimizer(ParallelFunctionCache functionExecutor) {
  50                 super();
  51                 this.functionExecutor = functionExecutor;
  52         }
  53
  54         @Override
  55         public void optimize(Point initial, OptimizationController control) throws OptimizationException {
  56
  57                 if (initial.dim() != 1) {
  58                         throw new IllegalArgumentException("Only single-dimensional optimization supported, dim=" +
  59                                         initial.dim());
  60                 }
  61
  62                 log.info("Starting golden section search for optimization");
  63
  64                 Point guessAC = null;
  65                 Point guessBD = null;
  66
  67                 try {
  68                         boolean guessedAC;
  69
  70                         Point previous = p(0);
  71                         double previousValue = Double.NaN;
  72                         current = previous;
  73                         double currentValue = Double.NaN;
  74
  75                         /*
  76                          * Initialize the points + computation.
  77                          */
  78                         Point a = p(0);
  79                         Point d = p(1.0);
  80                         Point b = section1(a, d);
  81                         Point c = section2(a, d);
  82
  83                         functionExecutor.compute(a);
  84                         functionExecutor.compute(d);
  85                         functionExecutor.compute(b);
  86                         functionExecutor.compute(c);
  87
  88                         // Wait for points a and d, which normally are already precomputed
  89                         functionExecutor.waitFor(a);
  90                         functionExecutor.waitFor(d);
  91
  92                         boolean continueOptimization = true;
  93                         while (continueOptimization) {
  94
  95                                 /*
  96                                  * Get values at A & D for guessing.
  97                                  * These are pre-calculated except during the first step.
  98                                  */
  99                                 double fa, fd;
 100                                 fa = functionExecutor.getValue(a);
 101                                 fd = functionExecutor.getValue(d);
 102
 103
 104                                 /*
 105                                  * Start calculating possible two next points.  The order of evaluation
 106                                  * is selected based on the function values at A and D.
 107                                  */
 108                                 guessAC = section1(a, c);
 109                                 guessBD = section2(b, d);
 110                                 System.err.println("Queueing " + guessAC + " and " + guessBD);
 111                                 if (Double.isNaN(fd) || fa < fd) {
 112                                         guessedAC = true;
 113                                         functionExecutor.compute(guessAC);
 114                                         functionExecutor.compute(guessBD);
 115                                 } else {
 116                                         guessedAC = false;
 117                                         functionExecutor.compute(guessBD);
 118                                         functionExecutor.compute(guessAC);
 119                                 }
 120
 121
 122                                 /*
 123                                  * Get values at B and C.
 124                                  */
 125                                 double fb, fc;
 126                                 functionExecutor.waitFor(b);
 127                                 functionExecutor.waitFor(c);
 128                                 fb = functionExecutor.getValue(b);
 129                                 fc = functionExecutor.getValue(c);
 130
 131                                 double min = MathUtil.min(fa, fb, fc, fd);
 132                                 if (Double.isNaN(min)) {
 133                                         throw new OptimizationException("Unable to compute initial function values");
 134                                 }
 135
 136
 137                                 /*
 138                                  * Update previous and current values for step control.
 139                                  */
 140                                 previousValue = currentValue;
 141                                 currentValue = min;
 142                                 previous = current;
 143                                 if (min == fa) {
 144                                         current = a;
 145                                 } else if (min == fb) {
 146                                         current = b;
 147                                 } else if (min == fc) {
 148                                         current = c;
 149                                 } else {
 150                                         current = d;
 151                                 }
 152
 153
 154                                 /*
 155                                  * Select next positions.  These are already being calculated in the background
 156                                  * as guessAC and guessBD.
 157                                  */
 158                                 if (min == fa || min == fb) {
 159                                         d = c;
 160                                         c = b;
 161                                         b = guessAC;
 162                                         functionExecutor.abort(guessBD);
 163                                         guessBD = null;
 164                                         log.debug("Selecting A-C region, a=" + a.get(0) + " c=" + c.get(0));
 165                                         if (guessedAC) {
 166                                                 guessSuccess++;
 167                                         } else {
 168                                                 guessFailure++;
 169                                         }
 170                                 } else {
 171                                         a = b;
 172                                         b = c;
 173                                         c = guessBD;
 174                                         functionExecutor.abort(guessAC);
 175                                         guessAC = null;
 176                                         log.debug("Selecting B-D region, b=" + b.get(0) + " d=" + d.get(0));
 177                                         if (!guessedAC) {
 178                                                 guessSuccess++;
 179                                         } else {
 180                                                 guessFailure++;
 181                                         }
 182                                 }
 183
 184
 185                                 /*
 186                                  * Check optimization control.
 187                                  */
 188                                 continueOptimization = control.stepTaken(previous, previousValue,
 189                                                 current, currentValue, c.get(0) - a.get(0));
 190
 191                                 if (Thread.interrupted()) {
 192                                         throw new InterruptedException();
 193                                 }
 194
 195                         }
 196
 197
 198                 } catch (InterruptedException e) {
 199                         log.info("Optimization was interrupted with InterruptedException");
 200                 }
 201
 202                 if (guessAC != null) {
 203                         System.err.println("Aborting " + guessAC);
 204                         functionExecutor.abort(guessAC);
 205                 }
 206                 if (guessBD != null) {
 207                         System.err.println("Aborting " + guessBD);
 208                         functionExecutor.abort(guessBD);
 209                 }
 210
 211
 212                 log.info("Finishing optimization at point " + getOptimumPoint() + " value " + getOptimumValue());
 213                 log.info("Optimization statistics: " + getStatistics());
 214         }
 215
 216
 217         private Point p(double v) {
 218                 return new Point(v);
 219         }
 220
 221
 222         private Point section1(Point a, Point b) {
 223                 double va = a.get(0);
 224                 double vb = b.get(0);
 225                 return p(va + (1 - ALPHA) * (vb - va));
 226         }
 227
 228         private Point section2(Point a, Point b) {
 229                 double va = a.get(0);
 230                 double vb = b.get(0);
 231                 return p(va + ALPHA * (vb - va));
 232         }
 233
 234
 235
 236         @Override
 237         public Point getOptimumPoint() {
 238                 return current;
 239         }
 240
 241
 242         @Override
 243         public double getOptimumValue() {
 244                 if (getOptimumPoint() == null) {
 245                         return Double.NaN;
 246                 }
 247                 return functionExecutor.getValue(getOptimumPoint());
 248         }
 249
 250         @Override
 251         public FunctionCache getFunctionCache() {
 252                 return functionExecutor;
 253         }
 254
 255         @Override
 256         public void setFunctionCache(FunctionCache functionCache) {
 257                 if (!(functionCache instanceof ParallelFunctionCache)) {
 258                         throw new IllegalArgumentException("Function cache needs to be a ParallelFunctionCache: " + functionCache);
 259                 }
 260                 this.functionExecutor = (ParallelFunctionCache) functionCache;
 261         }
 262
 263         @Override
 264         public String getStatistics() {
 265                 return String.format("Guess hit rate %d/%d = %.3f", guessSuccess, guessSuccess + guessFailure,
 266                                 ((double) guessSuccess) / (guessSuccess + guessFailure));
 267         }
 268
 269         @Override
 270         public void resetStatistics() {
 271                 guessSuccess = 0;
 272                 guessFailure = 0;
 273         }
 274
 275 }