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.math3.optim.univariate;
19  
20  import java.util.Arrays;
21  import java.util.Comparator;
22  import org.apache.commons.math3.exception.MathIllegalStateException;
23  import org.apache.commons.math3.exception.NotStrictlyPositiveException;
24  import org.apache.commons.math3.exception.util.LocalizedFormats;
25  import org.apache.commons.math3.random.RandomGenerator;
26  import org.apache.commons.math3.optim.MaxEval;
27  import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
28  import org.apache.commons.math3.optim.OptimizationData;
29  
30  /**
31   * Special implementation of the {@link UnivariateOptimizer} interface
32   * adding multi-start features to an existing optimizer.
33   * <br/>
34   * This class wraps an optimizer in order to use it several times in
35   * turn with different starting points (trying to avoid being trapped
36   * in a local extremum when looking for a global one).
37   *
38   * @version $Id: MultiStartUnivariateOptimizer.java 1435539 2013-01-19 13:27:24Z tn $
39   * @since 3.0
40   */
41  public class MultiStartUnivariateOptimizer
42      extends UnivariateOptimizer {
43      /** Underlying classical optimizer. */
44      private final UnivariateOptimizer optimizer;
45      /** Number of evaluations already performed for all starts. */
46      private int totalEvaluations;
47      /** Number of starts to go. */
48      private int starts;
49      /** Random generator for multi-start. */
50      private RandomGenerator generator;
51      /** Found optima. */
52      private UnivariatePointValuePair[] optima;
53      /** Optimization data. */
54      private OptimizationData[] optimData;
55      /**
56       * Location in {@link #optimData} where the updated maximum
57       * number of evaluations will be stored.
58       */
59      private int maxEvalIndex = -1;
60      /**
61       * Location in {@link #optimData} where the updated start value
62       * will be stored.
63       */
64      private int searchIntervalIndex = -1;
65  
66      /**
67       * Create a multi-start optimizer from a single-start optimizer.
68       *
69       * @param optimizer Single-start optimizer to wrap.
70       * @param starts Number of starts to perform. If {@code starts == 1},
71       * the {@code optimize} methods will return the same solution as
72       * {@code optimizer} would.
73       * @param generator Random generator to use for restarts.
74       * @throws NotStrictlyPositiveException if {@code starts < 1}.
75       */
76      public MultiStartUnivariateOptimizer(final UnivariateOptimizer optimizer,
77                                           final int starts,
78                                           final RandomGenerator generator) {
79          super(optimizer.getConvergenceChecker());
80  
81          if (starts < 1) {
82              throw new NotStrictlyPositiveException(starts);
83          }
84  
85          this.optimizer = optimizer;
86          this.starts = starts;
87          this.generator = generator;
88      }
89  
90      /** {@inheritDoc} */
91      @Override
92      public int getEvaluations() {
93          return totalEvaluations;
94      }
95  
96      /**
97       * Gets all the optima found during the last call to {@code optimize}.
98       * The optimizer stores all the optima found during a set of
99       * restarts. The {@code optimize} method returns the best point only.
100      * This method returns all the points found at the end of each starts,
101      * including the best one already returned by the {@code optimize} method.
102      * <br/>
103      * The returned array as one element for each start as specified
104      * in the constructor. It is ordered with the results from the
105      * runs that did converge first, sorted from best to worst
106      * objective value (i.e in ascending order if minimizing and in
107      * descending order if maximizing), followed by {@code null} elements
108      * corresponding to the runs that did not converge. This means all
109      * elements will be {@code null} if the {@code optimize} method did throw
110      * an exception.
111      * This also means that if the first element is not {@code null}, it is
112      * the best point found across all starts.
113      *
114      * @return an array containing the optima.
115      * @throws MathIllegalStateException if {@link #optimize(OptimizationData[])
116      * optimize} has not been called.
117      */
118     public UnivariatePointValuePair[] getOptima() {
119         if (optima == null) {
120             throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
121         }
122         return optima.clone();
123     }
124 
125     /**
126      * {@inheritDoc}
127      *
128      * @throws MathIllegalStateException if {@code optData} does not contain an
129      * instance of {@link MaxEval} or {@link SearchInterval}.
130      */
131     @Override
132     public UnivariatePointValuePair optimize(OptimizationData... optData) {
133         // Store arguments in order to pass them to the internal optimizer.
134        optimData = optData;
135         // Set up base class and perform computations.
136         return super.optimize(optData);
137     }
138 
139     /** {@inheritDoc} */
140     @Override
141     protected UnivariatePointValuePair doOptimize() {
142         // Remove all instances of "MaxEval" and "SearchInterval" from the
143         // array that will be passed to the internal optimizer.
144         // The former is to enforce smaller numbers of allowed evaluations
145         // (according to how many have been used up already), and the latter
146         // to impose a different start value for each start.
147         for (int i = 0; i < optimData.length; i++) {
148             if (optimData[i] instanceof MaxEval) {
149                 optimData[i] = null;
150                 maxEvalIndex = i;
151                 continue;
152             }
153             if (optimData[i] instanceof SearchInterval) {
154                 optimData[i] = null;
155                 searchIntervalIndex = i;
156                 continue;
157             }
158         }
159         if (maxEvalIndex == -1) {
160             throw new MathIllegalStateException();
161         }
162         if (searchIntervalIndex == -1) {
163             throw new MathIllegalStateException();
164         }
165 
166         RuntimeException lastException = null;
167         optima = new UnivariatePointValuePair[starts];
168         totalEvaluations = 0;
169 
170         final int maxEval = getMaxEvaluations();
171         final double min = getMin();
172         final double max = getMax();
173         final double startValue = getStartValue();
174 
175         // Multi-start loop.
176         for (int i = 0; i < starts; i++) {
177             // CHECKSTYLE: stop IllegalCatch
178             try {
179                 // Decrease number of allowed evaluations.
180                 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
181                 // New start value.
182                 final double s = (i == 0) ?
183                     startValue :
184                     min + generator.nextDouble() * (max - min);
185                 optimData[searchIntervalIndex] = new SearchInterval(min, max, s);
186                 // Optimize.
187                 optima[i] = optimizer.optimize(optimData);
188             } catch (RuntimeException mue) {
189                 lastException = mue;
190                 optima[i] = null;
191             }
192             // CHECKSTYLE: resume IllegalCatch
193 
194             totalEvaluations += optimizer.getEvaluations();
195         }
196 
197         sortPairs(getGoalType());
198 
199         if (optima[0] == null) {
200             throw lastException; // Cannot be null if starts >= 1.
201         }
202 
203         // Return the point with the best objective function value.
204         return optima[0];
205     }
206 
207     /**
208      * Sort the optima from best to worst, followed by {@code null} elements.
209      *
210      * @param goal Goal type.
211      */
212     private void sortPairs(final GoalType goal) {
213         Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() {
214                 public int compare(final UnivariatePointValuePair o1,
215                                    final UnivariatePointValuePair o2) {
216                     if (o1 == null) {
217                         return (o2 == null) ? 0 : 1;
218                     } else if (o2 == null) {
219                         return -1;
220                     }
221                     final double v1 = o1.getValue();
222                     final double v2 = o2.getValue();
223                     return (goal == GoalType.MINIMIZE) ?
224                         Double.compare(v1, v2) : Double.compare(v2, v1);
225                 }
226             });
227     }
228 }