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.optimization.univariate;
19  
20  import java.util.Arrays;
21  import java.util.Comparator;
22  
23  import org.apache.commons.math3.analysis.UnivariateFunction;
24  import org.apache.commons.math3.exception.MathIllegalStateException;
25  import org.apache.commons.math3.exception.NotStrictlyPositiveException;
26  import org.apache.commons.math3.exception.NullArgumentException;
27  import org.apache.commons.math3.exception.util.LocalizedFormats;
28  import org.apache.commons.math3.random.RandomGenerator;
29  import org.apache.commons.math3.optimization.GoalType;
30  import org.apache.commons.math3.optimization.ConvergenceChecker;
31  
32  /**
33   * Special implementation of the {@link UnivariateOptimizer} interface
34   * adding multi-start features to an existing optimizer.
35   *
36   * This class wraps a classical optimizer to use it several times in
37   * turn with different starting points in order to avoid being trapped
38   * into a local extremum when looking for a global one.
39   *
40   * @param <FUNC> Type of the objective function to be optimized.
41   *
42   * @deprecated As of 3.1 (to be removed in 4.0).
43   * @since 3.0
44   */
45  @Deprecated
46  public class UnivariateMultiStartOptimizer<FUNC extends UnivariateFunction>
47      implements BaseUnivariateOptimizer<FUNC> {
48      /** Underlying classical optimizer. */
49      private final BaseUnivariateOptimizer<FUNC> optimizer;
50      /** Maximal number of evaluations allowed. */
51      private int maxEvaluations;
52      /** Number of evaluations already performed for all starts. */
53      private int totalEvaluations;
54      /** Number of starts to go. */
55      private int starts;
56      /** Random generator for multi-start. */
57      private RandomGenerator generator;
58      /** Found optima. */
59      private UnivariatePointValuePair[] optima;
60  
61      /**
62       * Create a multi-start optimizer from a single-start optimizer.
63       *
64       * @param optimizer Single-start optimizer to wrap.
65       * @param starts Number of starts to perform. If {@code starts == 1},
66       * the {@code optimize} methods will return the same solution as
67       * {@code optimizer} would.
68       * @param generator Random generator to use for restarts.
69       * @throws NullArgumentException if {@code optimizer} or {@code generator}
70       * is {@code null}.
71       * @throws NotStrictlyPositiveException if {@code starts < 1}.
72       */
73      public UnivariateMultiStartOptimizer(final BaseUnivariateOptimizer<FUNC> optimizer,
74                                               final int starts,
75                                               final RandomGenerator generator) {
76          if (optimizer == null ||
77                  generator == null) {
78                  throw new NullArgumentException();
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      /**
90       * {@inheritDoc}
91       */
92      public ConvergenceChecker<UnivariatePointValuePair> getConvergenceChecker() {
93          return optimizer.getConvergenceChecker();
94      }
95  
96      /** {@inheritDoc} */
97      public int getMaxEvaluations() {
98          return maxEvaluations;
99      }
100 
101     /** {@inheritDoc} */
102     public int getEvaluations() {
103         return totalEvaluations;
104     }
105 
106     /**
107      * Get all the optima found during the last call to {@link
108      * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}.
109      * The optimizer stores all the optima found during a set of
110      * restarts. The {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
111      * method returns the best point only. This method returns all the points
112      * found at the end of each starts, including the best one already
113      * returned by the {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
114      * method.
115      * <br/>
116      * The returned array as one element for each start as specified
117      * in the constructor. It is ordered with the results from the
118      * runs that did converge first, sorted from best to worst
119      * objective value (i.e in ascending order if minimizing and in
120      * descending order if maximizing), followed by {@code null} elements
121      * corresponding to the runs that did not converge. This means all
122      * elements will be {@code null} if the {@link
123      * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
124      * method did throw an exception.
125      * This also means that if the first element is not {@code null}, it is
126      * the best point found across all starts.
127      *
128      * @return an array containing the optima.
129      * @throws MathIllegalStateException if {@link
130      * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
131      * has not been called.
132      */
133     public UnivariatePointValuePair[] getOptima() {
134         if (optima == null) {
135             throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
136         }
137         return optima.clone();
138     }
139 
140     /** {@inheritDoc} */
141     public UnivariatePointValuePair optimize(int maxEval, final FUNC f,
142                                                  final GoalType goal,
143                                                  final double min, final double max) {
144         return optimize(maxEval, f, goal, min, max, min + 0.5 * (max - min));
145     }
146 
147     /** {@inheritDoc} */
148     public UnivariatePointValuePair optimize(int maxEval, final FUNC f,
149                                                  final GoalType goal,
150                                                  final double min, final double max,
151                                                  final double startValue) {
152         RuntimeException lastException = null;
153         optima = new UnivariatePointValuePair[starts];
154         totalEvaluations = 0;
155 
156         // Multi-start loop.
157         for (int i = 0; i < starts; ++i) {
158             // CHECKSTYLE: stop IllegalCatch
159             try {
160                 final double s = (i == 0) ? startValue : min + generator.nextDouble() * (max - min);
161                 optima[i] = optimizer.optimize(maxEval - totalEvaluations, f, goal, min, max, s);
162             } catch (RuntimeException mue) {
163                 lastException = mue;
164                 optima[i] = null;
165             }
166             // CHECKSTYLE: resume IllegalCatch
167 
168             totalEvaluations += optimizer.getEvaluations();
169         }
170 
171         sortPairs(goal);
172 
173         if (optima[0] == null) {
174             throw lastException; // cannot be null if starts >=1
175         }
176 
177         // Return the point with the best objective function value.
178         return optima[0];
179     }
180 
181     /**
182      * Sort the optima from best to worst, followed by {@code null} elements.
183      *
184      * @param goal Goal type.
185      */
186     private void sortPairs(final GoalType goal) {
187         Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() {
188                 public int compare(final UnivariatePointValuePair o1,
189                                    final UnivariatePointValuePair o2) {
190                     if (o1 == null) {
191                         return (o2 == null) ? 0 : 1;
192                     } else if (o2 == null) {
193                         return -1;
194                     }
195                     final double v1 = o1.getValue();
196                     final double v2 = o2.getValue();
197                     return (goal == GoalType.MINIMIZE) ?
198                         Double.compare(v1, v2) : Double.compare(v2, v1);
199                 }
200             });
201     }
202 }