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  
18  package org.apache.commons.math.optimization;
19  
20  import org.apache.commons.math.ConvergenceException;
21  import org.apache.commons.math.FunctionEvaluationException;
22  import org.apache.commons.math.MathRuntimeException;
23  import org.apache.commons.math.analysis.UnivariateRealFunction;
24  import org.apache.commons.math.random.RandomGenerator;
25  
26  /** 
27   * Special implementation of the {@link UnivariateRealOptimizer} interface adding
28   * multi-start features to an existing optimizer.
29   * <p>
30   * This class wraps a classical optimizer to use it several times in
31   * turn with different starting points in order to avoid being trapped
32   * into a local extremum when looking for a global one.
33   * </p>
34   * @version $Revision: 797786 $ $Date: 2009-07-25 12:13:55 -0400 (Sat, 25 Jul 2009) $
35   * @since 2.0
36   */
37  public class MultiStartUnivariateRealOptimizer implements UnivariateRealOptimizer {
38  
39      /** Serializable version identifier. */
40      private static final long serialVersionUID = 5983375963110961019L;
41  
42      /** Underlying classical optimizer. */
43      private final UnivariateRealOptimizer optimizer;
44  
45      /** Maximal number of iterations allowed. */
46      private int maxIterations;
47  
48      /** Maximal number of evaluations allowed. */
49      private int maxEvaluations;
50  
51      /** Number of iterations already performed for all starts. */
52      private int totalIterations;
53  
54      /** Number of evaluations already performed for all starts. */
55      private int totalEvaluations;
56  
57      /** Number of starts to go. */
58      private int starts;
59  
60      /** Random generator for multi-start. */
61      private RandomGenerator generator;
62  
63      /** Found optima. */
64      private double[] optima;
65  
66      /** Found function values at optima. */
67      private double[] optimaValues;
68  
69      /**
70       * Create a multi-start optimizer from a single-start optimizer
71       * @param optimizer single-start optimizer to wrap
72       * @param starts number of starts to perform (including the
73       * first one), multi-start is disabled if value is less than or
74       * equal to 1
75       * @param generator random generator to use for restarts
76       */
77      public MultiStartUnivariateRealOptimizer(final UnivariateRealOptimizer optimizer,
78                                               final int starts,
79                                               final RandomGenerator generator) {
80          this.optimizer        = optimizer;
81          this.totalIterations  = 0;
82          this.starts           = starts;
83          this.generator        = generator;
84          this.optima           = null;
85          setMaximalIterationCount(Integer.MAX_VALUE);
86          setMaxEvaluations(Integer.MAX_VALUE);
87      }
88  
89      /** {@inheritDoc} */
90      public double getFunctionValue() {
91          return optimizer.getFunctionValue();
92      }
93  
94      /** {@inheritDoc} */
95      public double getResult() {
96          return optimizer.getResult();
97      }
98  
99      /** {@inheritDoc} */
100     public double getAbsoluteAccuracy() {
101         return optimizer.getAbsoluteAccuracy();
102     }
103 
104     /** {@inheritDoc} */
105     public int getIterationCount() {
106         return totalIterations;
107     }
108 
109     /** {@inheritDoc} */
110     public int getMaximalIterationCount() {
111         return maxIterations;
112     }
113 
114     /** {@inheritDoc} */
115     public int getMaxEvaluations() {
116         return maxEvaluations;
117     }
118 
119     /** {@inheritDoc} */
120     public int getEvaluations() {
121         return totalEvaluations;
122     }
123 
124     /** {@inheritDoc} */
125     public double getRelativeAccuracy() {
126         return optimizer.getRelativeAccuracy();
127     }
128 
129     /** {@inheritDoc} */
130     public void resetAbsoluteAccuracy() {
131         optimizer.resetAbsoluteAccuracy();
132     }
133 
134     /** {@inheritDoc} */
135     public void resetMaximalIterationCount() {
136         optimizer.resetMaximalIterationCount();
137     }
138 
139     /** {@inheritDoc} */
140     public void resetRelativeAccuracy() {
141         optimizer.resetRelativeAccuracy();
142     }
143 
144     /** {@inheritDoc} */
145     public void setAbsoluteAccuracy(double accuracy) {
146         optimizer.setAbsoluteAccuracy(accuracy);
147     }
148 
149     /** {@inheritDoc} */
150     public void setMaximalIterationCount(int count) {
151         this.maxIterations = count;
152     }
153 
154     /** {@inheritDoc} */
155     public void setMaxEvaluations(int maxEvaluations) {
156         this.maxEvaluations = maxEvaluations;
157     }
158 
159     /** {@inheritDoc} */
160     public void setRelativeAccuracy(double accuracy) {
161         optimizer.setRelativeAccuracy(accuracy);
162     }
163 
164     /** Get all the optima found during the last call to {@link
165      * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}.
166      * <p>The optimizer stores all the optima found during a set of
167      * restarts. The {@link #optimize(UnivariateRealFunction, GoalType,
168      * double, double) optimize} method returns the best point only. This
169      * method returns all the points found at the end of each starts,
170      * including the best one already returned by the {@link
171      * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}
172      * method.
173      * </p>
174      * <p>
175      * The returned array as one element for each start as specified
176      * in the constructor. It is ordered with the results from the
177      * runs that did converge first, sorted from best to worst
178      * objective value (i.e in ascending order if minimizing and in
179      * descending order if maximizing), followed by Double.NaN elements
180      * corresponding to the runs that did not converge. This means all
181      * elements will be NaN if the {@link #optimize(UnivariateRealFunction,
182      * GoalType, double, double) optimize} method did throw a {@link
183      * ConvergenceException ConvergenceException}). This also means that
184      * if the first element is not NaN, it is the best point found across
185      * all starts.</p>
186      * @return array containing the optima
187      * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction,
188      * GoalType, double, double) optimize} has not been called
189      * @see #getOptimaValues()
190      */
191     public double[] getOptima() throws IllegalStateException {
192         if (optima == null) {
193             throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
194         }
195         return optima.clone();
196     }
197 
198     /** Get all the function values at optima found during the last call to {@link
199      * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}.
200      * <p>
201      * The returned array as one element for each start as specified
202      * in the constructor. It is ordered with the results from the
203      * runs that did converge first, sorted from best to worst
204      * objective value (i.e in ascending order if minimizing and in
205      * descending order if maximizing), followed by Double.NaN elements
206      * corresponding to the runs that did not converge. This means all
207      * elements will be NaN if the {@link #optimize(UnivariateRealFunction,
208      * GoalType, double, double) optimize} method did throw a {@link
209      * ConvergenceException ConvergenceException}). This also means that
210      * if the first element is not NaN, it is the best point found across
211      * all starts.</p>
212      * @return array containing the optima
213      * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction,
214      * GoalType, double, double) optimize} has not been called
215      * @see #getOptima()
216      */
217     public double[] getOptimaValues() throws IllegalStateException {
218         if (optimaValues == null) {
219             throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
220         }
221         return optimaValues.clone();
222     }
223 
224     /** {@inheritDoc} */
225     public double optimize(final UnivariateRealFunction f, final GoalType goalType,
226                            final double min, final double max)
227         throws ConvergenceException,
228             FunctionEvaluationException {
229 
230         optima           = new double[starts];
231         optimaValues     = new double[starts];
232         totalIterations  = 0;
233         totalEvaluations = 0;
234 
235         // multi-start loop
236         for (int i = 0; i < starts; ++i) {
237 
238             try {
239                 optimizer.setMaximalIterationCount(maxIterations - totalIterations);
240                 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
241                 final double bound1 = (i == 0) ? min : min + generator.nextDouble() * (max - min);
242                 final double bound2 = (i == 0) ? max : min + generator.nextDouble() * (max - min);
243                 optima[i]       = optimizer.optimize(f, goalType,
244                                                      Math.min(bound1, bound2),
245                                                      Math.max(bound1, bound2));
246                 optimaValues[i] = optimizer.getFunctionValue();
247             } catch (FunctionEvaluationException fee) {
248                 optima[i]       = Double.NaN;
249                 optimaValues[i] = Double.NaN;
250             } catch (ConvergenceException ce) {
251                 optima[i]       = Double.NaN;
252                 optimaValues[i] = Double.NaN;
253             }
254 
255             totalIterations  += optimizer.getIterationCount();
256             totalEvaluations += optimizer.getEvaluations();
257 
258         }
259 
260         // sort the optima from best to worst, followed by NaN elements
261         int lastNaN = optima.length;
262         for (int i = 0; i < lastNaN; ++i) {
263             if (Double.isNaN(optima[i])) {
264                 optima[i] = optima[--lastNaN];
265                 optima[lastNaN + 1] = Double.NaN;
266                 optimaValues[i] = optimaValues[--lastNaN];
267                 optimaValues[lastNaN + 1] = Double.NaN;
268             }
269         }
270 
271         double currX = optima[0];
272         double currY = optimaValues[0];
273         for (int j = 1; j < lastNaN; ++j) {
274             final double prevY = currY;
275             currX = optima[j];
276             currY = optimaValues[j];
277             if ((goalType == GoalType.MAXIMIZE) ^ (currY < prevY)) {
278                 // the current element should be inserted closer to the beginning
279                 int i = j - 1;
280                 double mIX = optima[i];
281                 double mIY = optimaValues[i];
282                 while ((i >= 0) && ((goalType == GoalType.MAXIMIZE) ^ (currY < mIY))) {
283                     optima[i + 1]       = mIX;
284                     optimaValues[i + 1] = mIY;
285                     if (i-- != 0) {
286                         mIX = optima[i];
287                         mIY = optimaValues[i];
288                     } else {
289                         mIX = Double.NaN;
290                         mIY = Double.NaN;
291                     }
292                 }
293                 optima[i + 1]       = currX;
294                 optimaValues[i + 1] = currY;
295                 currX = optima[j];
296                 currY = optimaValues[j];
297             }
298         }
299 
300         if (Double.isNaN(optima[0])) {
301             throw new OptimizationException(
302                     "none of the {0} start points lead to convergence",
303                     starts);
304         }
305 
306         // return the found point given the best objective function value
307         return optima[0];
308 
309     }
310 
311     /** {@inheritDoc} */
312     public double optimize(final UnivariateRealFunction f, final GoalType goalType,
313                            final double min, final double max, final double startValue)
314             throws ConvergenceException, FunctionEvaluationException {
315         return optimize(f, goalType, min, max);
316     }
317 
318 }