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