001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018 package org.apache.commons.math.optimization;
019
020 import org.apache.commons.math.ConvergenceException;
021 import org.apache.commons.math.FunctionEvaluationException;
022 import org.apache.commons.math.MathRuntimeException;
023 import org.apache.commons.math.analysis.UnivariateRealFunction;
024 import org.apache.commons.math.random.RandomGenerator;
025
026 /**
027 * Special implementation of the {@link UnivariateRealOptimizer} interface adding
028 * multi-start features to an existing optimizer.
029 * <p>
030 * This class wraps a classical optimizer to use it several times in
031 * turn with different starting points in order to avoid being trapped
032 * into a local extremum when looking for a global one.
033 * </p>
034 * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $
035 * @since 2.0
036 */
037 public class MultiStartUnivariateRealOptimizer implements UnivariateRealOptimizer {
038
039 /** Serializable version identifier. */
040 private static final long serialVersionUID = 5983375963110961019L;
041
042 /** Underlying classical optimizer. */
043 private final UnivariateRealOptimizer optimizer;
044
045 /** Maximal number of iterations allowed. */
046 private int maxIterations;
047
048 /** Maximal number of evaluations allowed. */
049 private int maxEvaluations;
050
051 /** Number of iterations already performed for all starts. */
052 private int totalIterations;
053
054 /** Number of evaluations already performed for all starts. */
055 private int totalEvaluations;
056
057 /** Number of starts to go. */
058 private int starts;
059
060 /** Random generator for multi-start. */
061 private RandomGenerator generator;
062
063 /** Found optima. */
064 private double[] optima;
065
066 /** Found function values at optima. */
067 private double[] optimaValues;
068
069 /**
070 * Create a multi-start optimizer from a single-start optimizer
071 * @param optimizer single-start optimizer to wrap
072 * @param starts number of starts to perform (including the
073 * first one), multi-start is disabled if value is less than or
074 * equal to 1
075 * @param generator random generator to use for restarts
076 */
077 public MultiStartUnivariateRealOptimizer(final UnivariateRealOptimizer optimizer,
078 final int starts,
079 final RandomGenerator generator) {
080 this.optimizer = optimizer;
081 this.totalIterations = 0;
082 this.starts = starts;
083 this.generator = generator;
084 this.optima = null;
085 setMaximalIterationCount(Integer.MAX_VALUE);
086 setMaxEvaluations(Integer.MAX_VALUE);
087 }
088
089 /** {@inheritDoc} */
090 public double getFunctionValue() {
091 return optimizer.getFunctionValue();
092 }
093
094 /** {@inheritDoc} */
095 public double getResult() {
096 return optimizer.getResult();
097 }
098
099 /** {@inheritDoc} */
100 public double getAbsoluteAccuracy() {
101 return optimizer.getAbsoluteAccuracy();
102 }
103
104 /** {@inheritDoc} */
105 public int getIterationCount() {
106 return totalIterations;
107 }
108
109 /** {@inheritDoc} */
110 public int getMaximalIterationCount() {
111 return maxIterations;
112 }
113
114 /** {@inheritDoc} */
115 public int getMaxEvaluations() {
116 return maxEvaluations;
117 }
118
119 /** {@inheritDoc} */
120 public int getEvaluations() {
121 return totalEvaluations;
122 }
123
124 /** {@inheritDoc} */
125 public double getRelativeAccuracy() {
126 return optimizer.getRelativeAccuracy();
127 }
128
129 /** {@inheritDoc} */
130 public void resetAbsoluteAccuracy() {
131 optimizer.resetAbsoluteAccuracy();
132 }
133
134 /** {@inheritDoc} */
135 public void resetMaximalIterationCount() {
136 optimizer.resetMaximalIterationCount();
137 }
138
139 /** {@inheritDoc} */
140 public void resetRelativeAccuracy() {
141 optimizer.resetRelativeAccuracy();
142 }
143
144 /** {@inheritDoc} */
145 public void setAbsoluteAccuracy(double accuracy) {
146 optimizer.setAbsoluteAccuracy(accuracy);
147 }
148
149 /** {@inheritDoc} */
150 public void setMaximalIterationCount(int count) {
151 this.maxIterations = count;
152 }
153
154 /** {@inheritDoc} */
155 public void setMaxEvaluations(int maxEvaluations) {
156 this.maxEvaluations = maxEvaluations;
157 }
158
159 /** {@inheritDoc} */
160 public void setRelativeAccuracy(double accuracy) {
161 optimizer.setRelativeAccuracy(accuracy);
162 }
163
164 /** Get all the optima found during the last call to {@link
165 * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}.
166 * <p>The optimizer stores all the optima found during a set of
167 * restarts. The {@link #optimize(UnivariateRealFunction, GoalType,
168 * double, double) optimize} method returns the best point only. This
169 * method returns all the points found at the end of each starts,
170 * including the best one already returned by the {@link
171 * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}
172 * method.
173 * </p>
174 * <p>
175 * The returned array as one element for each start as specified
176 * in the constructor. It is ordered with the results from the
177 * runs that did converge first, sorted from best to worst
178 * objective value (i.e in ascending order if minimizing and in
179 * descending order if maximizing), followed by Double.NaN elements
180 * corresponding to the runs that did not converge. This means all
181 * elements will be NaN if the {@link #optimize(UnivariateRealFunction,
182 * GoalType, double, double) optimize} method did throw a {@link
183 * ConvergenceException ConvergenceException}). This also means that
184 * if the first element is not NaN, it is the best point found across
185 * all starts.</p>
186 * @return array containing the optima
187 * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction,
188 * GoalType, double, double) optimize} has not been called
189 * @see #getOptimaValues()
190 */
191 public double[] getOptima() throws IllegalStateException {
192 if (optima == null) {
193 throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
194 }
195 return optima.clone();
196 }
197
198 /** Get all the function values at optima found during the last call to {@link
199 * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}.
200 * <p>
201 * The returned array as one element for each start as specified
202 * in the constructor. It is ordered with the results from the
203 * runs that did converge first, sorted from best to worst
204 * objective value (i.e in ascending order if minimizing and in
205 * descending order if maximizing), followed by Double.NaN elements
206 * corresponding to the runs that did not converge. This means all
207 * elements will be NaN if the {@link #optimize(UnivariateRealFunction,
208 * GoalType, double, double) optimize} method did throw a {@link
209 * ConvergenceException ConvergenceException}). This also means that
210 * if the first element is not NaN, it is the best point found across
211 * all starts.</p>
212 * @return array containing the optima
213 * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction,
214 * GoalType, double, double) optimize} has not been called
215 * @see #getOptima()
216 */
217 public double[] getOptimaValues() throws IllegalStateException {
218 if (optimaValues == null) {
219 throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
220 }
221 return optimaValues.clone();
222 }
223
224 /** {@inheritDoc} */
225 public double optimize(final UnivariateRealFunction f, final GoalType goalType,
226 final double min, final double max)
227 throws ConvergenceException,
228 FunctionEvaluationException {
229
230 optima = new double[starts];
231 optimaValues = new double[starts];
232 totalIterations = 0;
233 totalEvaluations = 0;
234
235 // multi-start loop
236 for (int i = 0; i < starts; ++i) {
237
238 try {
239 optimizer.setMaximalIterationCount(maxIterations - totalIterations);
240 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
241 final double bound1 = (i == 0) ? min : min + generator.nextDouble() * (max - min);
242 final double bound2 = (i == 0) ? max : min + generator.nextDouble() * (max - min);
243 optima[i] = optimizer.optimize(f, goalType,
244 Math.min(bound1, bound2),
245 Math.max(bound1, bound2));
246 optimaValues[i] = optimizer.getFunctionValue();
247 } catch (FunctionEvaluationException fee) {
248 optima[i] = Double.NaN;
249 optimaValues[i] = Double.NaN;
250 } catch (ConvergenceException ce) {
251 optima[i] = Double.NaN;
252 optimaValues[i] = Double.NaN;
253 }
254
255 totalIterations += optimizer.getIterationCount();
256 totalEvaluations += optimizer.getEvaluations();
257
258 }
259
260 // sort the optima from best to worst, followed by NaN elements
261 int lastNaN = optima.length;
262 for (int i = 0; i < lastNaN; ++i) {
263 if (Double.isNaN(optima[i])) {
264 optima[i] = optima[--lastNaN];
265 optima[lastNaN + 1] = Double.NaN;
266 optimaValues[i] = optimaValues[--lastNaN];
267 optimaValues[lastNaN + 1] = Double.NaN;
268 }
269 }
270
271 double currX = optima[0];
272 double currY = optimaValues[0];
273 for (int j = 1; j < lastNaN; ++j) {
274 final double prevY = currY;
275 currX = optima[j];
276 currY = optimaValues[j];
277 if ((goalType == GoalType.MAXIMIZE) ^ (currY < prevY)) {
278 // the current element should be inserted closer to the beginning
279 int i = j - 1;
280 double mIX = optima[i];
281 double mIY = optimaValues[i];
282 while ((i >= 0) && ((goalType == GoalType.MAXIMIZE) ^ (currY < mIY))) {
283 optima[i + 1] = mIX;
284 optimaValues[i + 1] = mIY;
285 if (i-- != 0) {
286 mIX = optima[i];
287 mIY = optimaValues[i];
288 } else {
289 mIX = Double.NaN;
290 mIY = Double.NaN;
291 }
292 }
293 optima[i + 1] = currX;
294 optimaValues[i + 1] = currY;
295 currX = optima[j];
296 currY = optimaValues[j];
297 }
298 }
299
300 if (Double.isNaN(optima[0])) {
301 throw new OptimizationException(
302 "none of the {0} start points lead to convergence",
303 starts);
304 }
305
306 // return the found point given the best objective function value
307 return optima[0];
308
309 }
310
311 /** {@inheritDoc} */
312 public double optimize(final UnivariateRealFunction f, final GoalType goalType,
313 final double min, final double max, final double startValue)
314 throws ConvergenceException, FunctionEvaluationException {
315 return optimize(f, goalType, min, max);
316 }
317
318 }