View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math3.optim;
18  
19  import org.apache.commons.math3.exception.MathIllegalStateException;
20  import org.apache.commons.math3.exception.NotStrictlyPositiveException;
21  import org.apache.commons.math3.exception.TooManyEvaluationsException;
22  import org.apache.commons.math3.random.RandomVectorGenerator;
23  
24  /**
25   * Base class multi-start optimizer for a multivariate function.
26   * <br/>
27   * This class wraps an optimizer in order to use it several times in
28   * turn with different starting points (trying to avoid being trapped
29   * in a local extremum when looking for a global one).
30   * <em>It is not a "user" class.</em>
31   *
32   * @param <PAIR> Type of the point/value pair returned by the optimization
33   * algorithm.
34   *
35   * @since 3.0
36   */
37  public abstract class BaseMultiStartMultivariateOptimizer<PAIR>
38      extends BaseMultivariateOptimizer<PAIR> {
39      /** Underlying classical optimizer. */
40      private final BaseMultivariateOptimizer<PAIR> optimizer;
41      /** Number of evaluations already performed for all starts. */
42      private int totalEvaluations;
43      /** Number of starts to go. */
44      private int starts;
45      /** Random generator for multi-start. */
46      private RandomVectorGenerator generator;
47      /** Optimization data. */
48      private OptimizationData[] optimData;
49      /**
50       * Location in {@link #optimData} where the updated maximum
51       * number of evaluations will be stored.
52       */
53      private int maxEvalIndex = -1;
54      /**
55       * Location in {@link #optimData} where the updated start value
56       * will be stored.
57       */
58      private int initialGuessIndex = -1;
59  
60      /**
61       * Create a multi-start optimizer from a single-start optimizer.
62       * <p>
63       * Note that if there are bounds constraints (see {@link #getLowerBound()}
64       * and {@link #getUpperBound()}), then a simple rejection algorithm is used
65       * at each restart. This implies that the random vector generator should have
66       * a good probability to generate vectors in the bounded domain, otherwise the
67       * rejection algorithm will hit the {@link #getMaxEvaluations()} count without
68       * generating a proper restart point. Users must be take great care of the <a
69       * href="http://en.wikipedia.org/wiki/Curse_of_dimensionality">curse of dimensionality</a>.
70       * </p>
71       * @param optimizer Single-start optimizer to wrap.
72       * @param starts Number of starts to perform. If {@code starts == 1},
73       * the {@link #optimize(OptimizationData[]) optimize} will return the
74       * same solution as the given {@code optimizer} would return.
75       * @param generator Random vector generator to use for restarts.
76       * @throws NotStrictlyPositiveException if {@code starts < 1}.
77       */
78      public BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<PAIR> optimizer,
79                                                 final int starts,
80                                                 final RandomVectorGenerator generator) {
81          super(optimizer.getConvergenceChecker());
82  
83          if (starts < 1) {
84              throw new NotStrictlyPositiveException(starts);
85          }
86  
87          this.optimizer = optimizer;
88          this.starts = starts;
89          this.generator = generator;
90      }
91  
92      /** {@inheritDoc} */
93      @Override
94      public int getEvaluations() {
95          return totalEvaluations;
96      }
97  
98      /**
99       * Gets all the optima found during the last call to {@code optimize}.
100      * The optimizer stores all the optima found during a set of
101      * restarts. The {@code optimize} method returns the best point only.
102      * This method returns all the points found at the end of each starts,
103      * including the best one already returned by the {@code optimize} method.
104      * <br/>
105      * The returned array as one element for each start as specified
106      * in the constructor. It is ordered with the results from the
107      * runs that did converge first, sorted from best to worst
108      * objective value (i.e in ascending order if minimizing and in
109      * descending order if maximizing), followed by {@code null} elements
110      * corresponding to the runs that did not converge. This means all
111      * elements will be {@code null} if the {@code optimize} method did throw
112      * an exception.
113      * This also means that if the first element is not {@code null}, it is
114      * the best point found across all starts.
115      * <br/>
116      * The behaviour is undefined if this method is called before
117      * {@code optimize}; it will likely throw {@code NullPointerException}.
118      *
119      * @return an array containing the optima sorted from best to worst.
120      */
121     public abstract PAIR[] getOptima();
122 
123     /**
124      * {@inheritDoc}
125      *
126      * @throws MathIllegalStateException if {@code optData} does not contain an
127      * instance of {@link MaxEval} or {@link InitialGuess}.
128      */
129     @Override
130     public PAIR optimize(OptimizationData... optData) {
131         // Store arguments in order to pass them to the internal optimizer.
132        optimData = optData;
133         // Set up base class and perform computations.
134         return super.optimize(optData);
135     }
136 
137     /** {@inheritDoc} */
138     @Override
139     protected PAIR doOptimize() {
140         // Remove all instances of "MaxEval" and "InitialGuess" from the
141         // array that will be passed to the internal optimizer.
142         // The former is to enforce smaller numbers of allowed evaluations
143         // (according to how many have been used up already), and the latter
144         // to impose a different start value for each start.
145         for (int i = 0; i < optimData.length; i++) {
146             if (optimData[i] instanceof MaxEval) {
147                 optimData[i] = null;
148                 maxEvalIndex = i;
149             }
150             if (optimData[i] instanceof InitialGuess) {
151                 optimData[i] = null;
152                 initialGuessIndex = i;
153                 continue;
154             }
155         }
156         if (maxEvalIndex == -1) {
157             throw new MathIllegalStateException();
158         }
159         if (initialGuessIndex == -1) {
160             throw new MathIllegalStateException();
161         }
162 
163         RuntimeException lastException = null;
164         totalEvaluations = 0;
165         clear();
166 
167         final int maxEval = getMaxEvaluations();
168         final double[] min = getLowerBound();
169         final double[] max = getUpperBound();
170         final double[] startPoint = getStartPoint();
171 
172         // Multi-start loop.
173         for (int i = 0; i < starts; i++) {
174             // CHECKSTYLE: stop IllegalCatch
175             try {
176                 // Decrease number of allowed evaluations.
177                 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
178                 // New start value.
179                 double[] s = null;
180                 if (i == 0) {
181                     s = startPoint;
182                 } else {
183                     int attempts = 0;
184                     while (s == null) {
185                         if (attempts++ >= getMaxEvaluations()) {
186                             throw new TooManyEvaluationsException(getMaxEvaluations());
187                         }
188                         s = generator.nextVector();
189                         for (int k = 0; s != null && k < s.length; ++k) {
190                             if ((min != null && s[k] < min[k]) || (max != null && s[k] > max[k])) {
191                                 // reject the vector
192                                 s = null;
193                             }
194                         }
195                     }
196                 }
197                 optimData[initialGuessIndex] = new InitialGuess(s);
198                 // Optimize.
199                 final PAIR result = optimizer.optimize(optimData);
200                 store(result);
201             } catch (RuntimeException mue) {
202                 lastException = mue;
203             }
204             // CHECKSTYLE: resume IllegalCatch
205 
206             totalEvaluations += optimizer.getEvaluations();
207         }
208 
209         final PAIR[] optima = getOptima();
210         if (optima.length == 0) {
211             // All runs failed.
212             throw lastException; // Cannot be null if starts >= 1.
213         }
214 
215         // Return the best optimum.
216         return optima[0];
217     }
218 
219     /**
220      * Method that will be called in order to store each found optimum.
221      *
222      * @param optimum Result of an optimization run.
223      */
224     protected abstract void store(PAIR optimum);
225     /**
226      * Method that will called in order to clear all stored optima.
227      */
228     protected abstract void clear();
229 }