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 java.util.Arrays;
21  import java.util.Comparator;
22  
23  import org.apache.commons.math.ConvergenceException;
24  import org.apache.commons.math.FunctionEvaluationException;
25  import org.apache.commons.math.MathRuntimeException;
26  import org.apache.commons.math.analysis.MultivariateRealFunction;
27  import org.apache.commons.math.random.RandomVectorGenerator;
28  
29  /** 
30   * Special implementation of the {@link MultivariateRealOptimizer} interface adding
31   * multi-start features to an existing optimizer.
32   * <p>
33   * This class wraps a classical optimizer to use it several times in
34   * turn with different starting points in order to avoid being trapped
35   * into a local extremum when looking for a global one.
36   * </p>
37   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
38   * @since 2.0
39   */
40  public class MultiStartMultivariateRealOptimizer
41      implements MultivariateRealOptimizer {
42  
43      /** Underlying classical optimizer. */
44      private final MultivariateRealOptimizer optimizer;
45  
46      /** Maximal number of iterations allowed. */
47      private int maxIterations;
48  
49      /** Maximal number of evaluations allowed. */
50      private int maxEvaluations;
51  
52      /** Number of iterations already performed for all starts. */
53      private int totalIterations;
54  
55      /** Number of evaluations already performed for all starts. */
56      private int totalEvaluations;
57  
58      /** Number of starts to go. */
59      private int starts;
60  
61      /** Random generator for multi-start. */
62      private RandomVectorGenerator generator;
63  
64      /** Found optima. */
65      private RealPointValuePair[] optima;
66  
67      /**
68       * Create a multi-start optimizer from a single-start optimizer
69       * @param optimizer single-start optimizer to wrap
70       * @param starts number of starts to perform (including the
71       * first one), multi-start is disabled if value is less than or
72       * equal to 1
73       * @param generator random vector generator to use for restarts
74       */
75      public MultiStartMultivariateRealOptimizer(final MultivariateRealOptimizer optimizer,
76                                                 final int starts,
77                                                 final RandomVectorGenerator generator) {
78          this.optimizer        = optimizer;
79          this.totalIterations  = 0;
80          this.totalEvaluations = 0;
81          this.starts           = starts;
82          this.generator        = generator;
83          this.optima           = null;
84          setMaxIterations(Integer.MAX_VALUE);
85          setMaxEvaluations(Integer.MAX_VALUE);
86      }
87  
88      /** Get all the optima found during the last call to {@link
89       * #optimize(MultivariateRealFunction, GoalType, double[]) optimize}.
90       * <p>The optimizer stores all the optima found during a set of
91       * restarts. The {@link #optimize(MultivariateRealFunction, GoalType,
92       * double[]) optimize} method returns the best point only. This
93       * method returns all the points found at the end of each starts,
94       * including the best one already returned by the {@link
95       * #optimize(MultivariateRealFunction, GoalType, double[]) optimize}
96       * method.
97       * </p>
98       * <p>
99       * The returned array as one element for each start as specified
100      * in the constructor. It is ordered with the results from the
101      * runs that did converge first, sorted from best to worst
102      * objective value (i.e in ascending order if minimizing and in
103      * descending order if maximizing), followed by and null elements
104      * corresponding to the runs that did not converge. This means all
105      * elements will be null if the {@link #optimize(MultivariateRealFunction,
106      * GoalType, double[]) optimize} method did throw a {@link
107      * ConvergenceException ConvergenceException}). This also means that
108      * if the first element is non null, it is the best point found across
109      * all starts.</p>
110      * @return array containing the optima
111      * @exception IllegalStateException if {@link #optimize(MultivariateRealFunction,
112      * GoalType, double[]) optimize} has not been called
113      */
114     public RealPointValuePair[] getOptima() throws IllegalStateException {
115         if (optima == null) {
116             throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
117         }
118         return optima.clone();
119     }
120 
121     /** {@inheritDoc} */
122     public void setMaxIterations(int maxIterations) {
123         this.maxIterations = maxIterations;
124     }
125 
126     /** {@inheritDoc} */
127     public int getMaxIterations() {
128         return maxIterations;
129     }
130 
131     /** {@inheritDoc} */
132     public void setMaxEvaluations(int maxEvaluations) {
133         this.maxEvaluations = maxEvaluations;
134     }
135 
136     /** {@inheritDoc} */
137     public int getMaxEvaluations() {
138         return maxEvaluations;
139     }
140 
141     /** {@inheritDoc} */
142     public int getIterations() {
143         return totalIterations;
144     }
145 
146     /** {@inheritDoc} */
147     public int getEvaluations() {
148         return totalEvaluations;
149     }
150 
151     /** {@inheritDoc} */
152     public void setConvergenceChecker(RealConvergenceChecker checker) {
153         optimizer.setConvergenceChecker(checker);
154     }
155 
156     /** {@inheritDoc} */
157     public RealConvergenceChecker getConvergenceChecker() {
158         return optimizer.getConvergenceChecker();
159     }
160 
161     /** {@inheritDoc} */
162     public RealPointValuePair optimize(final MultivariateRealFunction f,
163                                          final GoalType goalType,
164                                          double[] startPoint)
165         throws FunctionEvaluationException, OptimizationException {
166 
167         optima           = new RealPointValuePair[starts];
168         totalIterations  = 0;
169         totalEvaluations = 0;
170 
171         // multi-start loop
172         for (int i = 0; i < starts; ++i) {
173 
174             try {
175                 optimizer.setMaxIterations(maxIterations - totalIterations);
176                 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
177                 optima[i] = optimizer.optimize(f, goalType,
178                                                (i == 0) ? startPoint : generator.nextVector());
179             } catch (FunctionEvaluationException fee) {
180                 optima[i] = null;
181             } catch (OptimizationException oe) {
182                 optima[i] = null;
183             }
184 
185             totalIterations  += optimizer.getIterations();
186             totalEvaluations += optimizer.getEvaluations();
187 
188         }
189 
190         // sort the optima from best to worst, followed by null elements
191         Arrays.sort(optima, new Comparator<RealPointValuePair>() {
192             public int compare(final RealPointValuePair o1, final RealPointValuePair o2) {
193                 if (o1 == null) {
194                     return (o2 == null) ? 0 : +1;
195                 } else if (o2 == null) {
196                     return -1;
197                 }
198                 final double v1 = o1.getValue();
199                 final double v2 = o2.getValue();
200                 return (goalType == GoalType.MINIMIZE) ?
201                         Double.compare(v1, v2) : Double.compare(v2, v1);
202             }
203         });
204 
205         if (optima[0] == null) {
206             throw new OptimizationException(
207                     "none of the {0} start points lead to convergence",
208                     starts);
209         }
210 
211         // return the found point given the best objective function value
212         return optima[0];
213 
214     }
215 
216 }