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   * @since 3.0
39   */
40  public class MultiStartUnivariateOptimizer
41      extends UnivariateOptimizer {
42      /** Underlying classical optimizer. */
43      private final UnivariateOptimizer optimizer;
44      /** Number of evaluations already performed for all starts. */
45      private int totalEvaluations;
46      /** Number of starts to go. */
47      private int starts;
48      /** Random generator for multi-start. */
49      private RandomGenerator generator;
50      /** Found optima. */
51      private UnivariatePointValuePair[] optima;
52      /** Optimization data. */
53      private OptimizationData[] optimData;
54      /**
55       * Location in {@link #optimData} where the updated maximum
56       * number of evaluations will be stored.
57       */
58      private int maxEvalIndex = -1;
59      /**
60       * Location in {@link #optimData} where the updated start value
61       * will be stored.
62       */
63      private int searchIntervalIndex = -1;
64  
65      /**
66       * Create a multi-start optimizer from a single-start optimizer.
67       *
68       * @param optimizer Single-start optimizer to wrap.
69       * @param starts Number of starts to perform. If {@code starts == 1},
70       * the {@code optimize} methods will return the same solution as
71       * {@code optimizer} would.
72       * @param generator Random generator to use for restarts.
73       * @throws NotStrictlyPositiveException if {@code starts < 1}.
74       */
75      public MultiStartUnivariateOptimizer(final UnivariateOptimizer optimizer,
76                                           final int starts,
77                                           final RandomGenerator generator) {
78          super(optimizer.getConvergenceChecker());
79  
80          if (starts < 1) {
81              throw new NotStrictlyPositiveException(starts);
82          }
83  
84          this.optimizer = optimizer;
85          this.starts = starts;
86          this.generator = generator;
87      }
88  
89      /** {@inheritDoc} */
90      @Override
91      public int getEvaluations() {
92          return totalEvaluations;
93      }
94  
95      /**
96       * Gets all the optima found during the last call to {@code optimize}.
97       * The optimizer stores all the optima found during a set of
98       * restarts. The {@code optimize} method returns the best point only.
99       * This method returns all the points found at the end of each starts,
100      * including the best one already returned by the {@code optimize} method.
101      * <br/>
102      * The returned array as one element for each start as specified
103      * in the constructor. It is ordered with the results from the
104      * runs that did converge first, sorted from best to worst
105      * objective value (i.e in ascending order if minimizing and in
106      * descending order if maximizing), followed by {@code null} elements
107      * corresponding to the runs that did not converge. This means all
108      * elements will be {@code null} if the {@code optimize} method did throw
109      * an exception.
110      * This also means that if the first element is not {@code null}, it is
111      * the best point found across all starts.
112      *
113      * @return an array containing the optima.
114      * @throws MathIllegalStateException if {@link #optimize(OptimizationData[])
115      * optimize} has not been called.
116      */
117     public UnivariatePointValuePair[] getOptima() {
118         if (optima == null) {
119             throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
120         }
121         return optima.clone();
122     }
123 
124     /**
125      * {@inheritDoc}
126      *
127      * @throws MathIllegalStateException if {@code optData} does not contain an
128      * instance of {@link MaxEval} or {@link SearchInterval}.
129      */
130     @Override
131     public UnivariatePointValuePair 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 UnivariatePointValuePair doOptimize() {
141         // Remove all instances of "MaxEval" and "SearchInterval" 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                 continue;
151             }
152             if (optimData[i] instanceof SearchInterval) {
153                 optimData[i] = null;
154                 searchIntervalIndex = i;
155                 continue;
156             }
157         }
158         if (maxEvalIndex == -1) {
159             throw new MathIllegalStateException();
160         }
161         if (searchIntervalIndex == -1) {
162             throw new MathIllegalStateException();
163         }
164 
165         RuntimeException lastException = null;
166         optima = new UnivariatePointValuePair[starts];
167         totalEvaluations = 0;
168 
169         final int maxEval = getMaxEvaluations();
170         final double min = getMin();
171         final double max = getMax();
172         final double startValue = getStartValue();
173 
174         // Multi-start loop.
175         for (int i = 0; i < starts; i++) {
176             // CHECKSTYLE: stop IllegalCatch
177             try {
178                 // Decrease number of allowed evaluations.
179                 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
180                 // New start value.
181                 final double s = (i == 0) ?
182                     startValue :
183                     min + generator.nextDouble() * (max - min);
184                 optimData[searchIntervalIndex] = new SearchInterval(min, max, s);
185                 // Optimize.
186                 optima[i] = optimizer.optimize(optimData);
187             } catch (RuntimeException mue) {
188                 lastException = mue;
189                 optima[i] = null;
190             }
191             // CHECKSTYLE: resume IllegalCatch
192 
193             totalEvaluations += optimizer.getEvaluations();
194         }
195 
196         sortPairs(getGoalType());
197 
198         if (optima[0] == null) {
199             throw lastException; // Cannot be null if starts >= 1.
200         }
201 
202         // Return the point with the best objective function value.
203         return optima[0];
204     }
205 
206     /**
207      * Sort the optima from best to worst, followed by {@code null} elements.
208      *
209      * @param goal Goal type.
210      */
211     private void sortPairs(final GoalType goal) {
212         Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() {
213                 public int compare(final UnivariatePointValuePair o1,
214                                    final UnivariatePointValuePair o2) {
215                     if (o1 == null) {
216                         return (o2 == null) ? 0 : 1;
217                     } else if (o2 == null) {
218                         return -1;
219                     }
220                     final double v1 = o1.getValue();
221                     final double v2 = o2.getValue();
222                     return (goal == GoalType.MINIMIZE) ?
223                         Double.compare(v1, v2) : Double.compare(v2, v1);
224                 }
225             });
226     }
227 }