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   * @version $Id: BaseMultiStartMultivariateOptimizer.java 1454746 2013-03-09 17:37:30Z luc $
36   * @since 3.0
37   */
38  public abstract class BaseMultiStartMultivariateOptimizer<PAIR>
39      extends BaseMultivariateOptimizer<PAIR> {
40      /** Underlying classical optimizer. */
41      private final BaseMultivariateOptimizer<PAIR> optimizer;
42      /** Number of evaluations already performed for all starts. */
43      private int totalEvaluations;
44      /** Number of starts to go. */
45      private int starts;
46      /** Random generator for multi-start. */
47      private RandomVectorGenerator generator;
48      /** Optimization data. */
49      private OptimizationData[] optimData;
50      /**
51       * Location in {@link #optimData} where the updated maximum
52       * number of evaluations will be stored.
53       */
54      private int maxEvalIndex = -1;
55      /**
56       * Location in {@link #optimData} where the updated start value
57       * will be stored.
58       */
59      private int initialGuessIndex = -1;
60  
61      /**
62       * Create a multi-start optimizer from a single-start optimizer.
63       * <p>
64       * Note that if there are bounds constraints (see {@link #getLowerBound()}
65       * and {@link #getUpperBound()}), then a simple rejection algorithm is used
66       * at each restart. This implies that the random vector generator should have
67       * a good probability to generate vectors in the bounded domain, otherwise the
68       * rejection algorithm will hit the {@link #getMaxEvaluations()} count without
69       * generating a proper restart point. Users must be take great care of the <a
70       * href="http://en.wikipedia.org/wiki/Curse_of_dimensionality">curse of dimensionality</a>.
71       * </p>
72       * @param optimizer Single-start optimizer to wrap.
73       * @param starts Number of starts to perform. If {@code starts == 1},
74       * the {@link #optimize(OptimizationData[]) optimize} will return the
75       * same solution as the given {@code optimizer} would return.
76       * @param generator Random vector generator to use for restarts.
77       * @throws NotStrictlyPositiveException if {@code starts < 1}.
78       */
79      public BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<PAIR> optimizer,
80                                                 final int starts,
81                                                 final RandomVectorGenerator generator) {
82          super(optimizer.getConvergenceChecker());
83  
84          if (starts < 1) {
85              throw new NotStrictlyPositiveException(starts);
86          }
87  
88          this.optimizer = optimizer;
89          this.starts = starts;
90          this.generator = generator;
91      }
92  
93      /** {@inheritDoc} */
94      @Override
95      public int getEvaluations() {
96          return totalEvaluations;
97      }
98  
99      /**
100      * Gets all the optima found during the last call to {@code optimize}.
101      * The optimizer stores all the optima found during a set of
102      * restarts. The {@code optimize} method returns the best point only.
103      * This method returns all the points found at the end of each starts,
104      * including the best one already returned by the {@code optimize} method.
105      * <br/>
106      * The returned array as one element for each start as specified
107      * in the constructor. It is ordered with the results from the
108      * runs that did converge first, sorted from best to worst
109      * objective value (i.e in ascending order if minimizing and in
110      * descending order if maximizing), followed by {@code null} elements
111      * corresponding to the runs that did not converge. This means all
112      * elements will be {@code null} if the {@code optimize} method did throw
113      * an exception.
114      * This also means that if the first element is not {@code null}, it is
115      * the best point found across all starts.
116      * <br/>
117      * The behaviour is undefined if this method is called before
118      * {@code optimize}; it will likely throw {@code NullPointerException}.
119      *
120      * @return an array containing the optima sorted from best to worst.
121      */
122     public abstract PAIR[] getOptima();
123 
124     /**
125      * {@inheritDoc}
126      *
127      * @throws MathIllegalStateException if {@code optData} does not contain an
128      * instance of {@link MaxEval} or {@link InitialGuess}.
129      */
130     @Override
131     public PAIR optimize(OptimizationData... optData) {
132         // Store arguments in order to pass them to the internal optimizer.
133        optimData = optData;
134         // Set up base class and perform computations.
135         return super.optimize(optData);
136     }
137 
138     /** {@inheritDoc} */
139     @Override
140     protected PAIR doOptimize() {
141         // Remove all instances of "MaxEval" and "InitialGuess" from the
142         // array that will be passed to the internal optimizer.
143         // The former is to enforce smaller numbers of allowed evaluations
144         // (according to how many have been used up already), and the latter
145         // to impose a different start value for each start.
146         for (int i = 0; i < optimData.length; i++) {
147             if (optimData[i] instanceof MaxEval) {
148                 optimData[i] = null;
149                 maxEvalIndex = i;
150             }
151             if (optimData[i] instanceof InitialGuess) {
152                 optimData[i] = null;
153                 initialGuessIndex = i;
154                 continue;
155             }
156         }
157         if (maxEvalIndex == -1) {
158             throw new MathIllegalStateException();
159         }
160         if (initialGuessIndex == -1) {
161             throw new MathIllegalStateException();
162         }
163 
164         RuntimeException lastException = null;
165         totalEvaluations = 0;
166         clear();
167 
168         final int maxEval = getMaxEvaluations();
169         final double[] min = getLowerBound();
170         final double[] max = getUpperBound();
171         final double[] startPoint = getStartPoint();
172 
173         // Multi-start loop.
174         for (int i = 0; i < starts; i++) {
175             // CHECKSTYLE: stop IllegalCatch
176             try {
177                 // Decrease number of allowed evaluations.
178                 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
179                 // New start value.
180                 double[] s = null;
181                 if (i == 0) {
182                     s = startPoint;
183                 } else {
184                     int attempts = 0;
185                     while (s == null) {
186                         if (attempts++ >= getMaxEvaluations()) {
187                             throw new TooManyEvaluationsException(getMaxEvaluations());
188                         }
189                         s = generator.nextVector();
190                         for (int k = 0; s != null && k < s.length; ++k) {
191                             if ((min != null && s[k] < min[k]) || (max != null && s[k] > max[k])) {
192                                 // reject the vector
193                                 s = null;
194                             }
195                         }
196                     }
197                 }
198                 optimData[initialGuessIndex] = new InitialGuess(s);
199                 // Optimize.
200                 final PAIR result = optimizer.optimize(optimData);
201                 store(result);
202             } catch (RuntimeException mue) {
203                 lastException = mue;
204             }
205             // CHECKSTYLE: resume IllegalCatch
206 
207             totalEvaluations += optimizer.getEvaluations();
208         }
209 
210         final PAIR[] optima = getOptima();
211         if (optima.length == 0) {
212             // All runs failed.
213             throw lastException; // Cannot be null if starts >= 1.
214         }
215 
216         // Return the best optimum.
217         return optima[0];
218     }
219 
220     /**
221      * Method that will be called in order to store each found optimum.
222      *
223      * @param optimum Result of an optimization run.
224      */
225     protected abstract void store(PAIR optimum);
226     /**
227      * Method that will called in order to clear all stored optima.
228      */
229     protected abstract void clear();
230 }