source: src/main/java/agents/org/apache/commons/math/optimization/MultiStartUnivariateRealOptimizer.java

Last change on this file was 1, checked in by Wouter Pasman, 7 years ago

Initial import : Genius 9.0.0
File size: 12.0 KB
Line 
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
18package agents.org.apache.commons.math.optimization;
19
20import agents.org.apache.commons.math.ConvergenceException;
21import agents.org.apache.commons.math.FunctionEvaluationException;
22import agents.org.apache.commons.math.MathRuntimeException;
23import agents.org.apache.commons.math.analysis.UnivariateRealFunction;
24import agents.org.apache.commons.math.exception.util.LocalizedFormats;
25import agents.org.apache.commons.math.random.RandomGenerator;
26import agents.org.apache.commons.math.util.FastMath;
27
28/**
29 * Special implementation of the {@link UnivariateRealOptimizer} interface adding
30 * multi-start features to an existing optimizer.
31 * <p>
32 * This class wraps a classical optimizer to use it several times in
33 * turn with different starting points in order to avoid being trapped
34 * into a local extremum when looking for a global one.
35 * </p>
36 * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $
37 * @since 2.0
38 */
39public class MultiStartUnivariateRealOptimizer implements UnivariateRealOptimizer {
40
41 /** Serializable version identifier. */
42 private static final long serialVersionUID = 5983375963110961019L;
43
44 /** Underlying classical optimizer. */
45 private final UnivariateRealOptimizer optimizer;
46
47 /** Maximal number of iterations allowed. */
48 private int maxIterations;
49
50 /** Maximal number of evaluations allowed. */
51 private int maxEvaluations;
52
53 /** Number of iterations already performed for all starts. */
54 private int totalIterations;
55
56 /** Number of evaluations already performed for all starts. */
57 private int totalEvaluations;
58
59 /** Number of starts to go. */
60 private int starts;
61
62 /** Random generator for multi-start. */
63 private RandomGenerator generator;
64
65 /** Found optima. */
66 private double[] optima;
67
68 /** Found function values at optima. */
69 private double[] optimaValues;
70
71 /**
72 * Create a multi-start optimizer from a single-start optimizer
73 * @param optimizer single-start optimizer to wrap
74 * @param starts number of starts to perform (including the
75 * first one), multi-start is disabled if value is less than or
76 * equal to 1
77 * @param generator random generator to use for restarts
78 */
79 public MultiStartUnivariateRealOptimizer(final UnivariateRealOptimizer optimizer,
80 final int starts,
81 final RandomGenerator generator) {
82 this.optimizer = optimizer;
83 this.totalIterations = 0;
84 this.starts = starts;
85 this.generator = generator;
86 this.optima = null;
87 setMaximalIterationCount(Integer.MAX_VALUE);
88 setMaxEvaluations(Integer.MAX_VALUE);
89 }
90
91 /** {@inheritDoc} */
92 public double getFunctionValue() {
93 return optimaValues[0];
94 }
95
96 /** {@inheritDoc} */
97 public double getResult() {
98 return optima[0];
99 }
100
101 /** {@inheritDoc} */
102 public double getAbsoluteAccuracy() {
103 return optimizer.getAbsoluteAccuracy();
104 }
105
106 /** {@inheritDoc} */
107 public int getIterationCount() {
108 return totalIterations;
109 }
110
111 /** {@inheritDoc} */
112 public int getMaximalIterationCount() {
113 return maxIterations;
114 }
115
116 /** {@inheritDoc} */
117 public int getMaxEvaluations() {
118 return maxEvaluations;
119 }
120
121 /** {@inheritDoc} */
122 public int getEvaluations() {
123 return totalEvaluations;
124 }
125
126 /** {@inheritDoc} */
127 public double getRelativeAccuracy() {
128 return optimizer.getRelativeAccuracy();
129 }
130
131 /** {@inheritDoc} */
132 public void resetAbsoluteAccuracy() {
133 optimizer.resetAbsoluteAccuracy();
134 }
135
136 /** {@inheritDoc} */
137 public void resetMaximalIterationCount() {
138 optimizer.resetMaximalIterationCount();
139 }
140
141 /** {@inheritDoc} */
142 public void resetRelativeAccuracy() {
143 optimizer.resetRelativeAccuracy();
144 }
145
146 /** {@inheritDoc} */
147 public void setAbsoluteAccuracy(double accuracy) {
148 optimizer.setAbsoluteAccuracy(accuracy);
149 }
150
151 /** {@inheritDoc} */
152 public void setMaximalIterationCount(int count) {
153 this.maxIterations = count;
154 }
155
156 /** {@inheritDoc} */
157 public void setMaxEvaluations(int maxEvaluations) {
158 this.maxEvaluations = maxEvaluations;
159 }
160
161 /** {@inheritDoc} */
162 public void setRelativeAccuracy(double accuracy) {
163 optimizer.setRelativeAccuracy(accuracy);
164 }
165
166 /** Get all the optima found during the last call to {@link
167 * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}.
168 * <p>The optimizer stores all the optima found during a set of
169 * restarts. The {@link #optimize(UnivariateRealFunction, GoalType,
170 * double, double) optimize} method returns the best point only. This
171 * method returns all the points found at the end of each starts,
172 * including the best one already returned by the {@link
173 * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}
174 * method.
175 * </p>
176 * <p>
177 * The returned array as one element for each start as specified
178 * in the constructor. It is ordered with the results from the
179 * runs that did converge first, sorted from best to worst
180 * objective value (i.e in ascending order if minimizing and in
181 * descending order if maximizing), followed by Double.NaN elements
182 * corresponding to the runs that did not converge. This means all
183 * elements will be NaN if the {@link #optimize(UnivariateRealFunction,
184 * GoalType, double, double) optimize} method did throw a {@link
185 * ConvergenceException ConvergenceException}). This also means that
186 * if the first element is not NaN, it is the best point found across
187 * all starts.</p>
188 * @return array containing the optima
189 * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction,
190 * GoalType, double, double) optimize} has not been called
191 * @see #getOptimaValues()
192 */
193 public double[] getOptima() throws IllegalStateException {
194 if (optima == null) {
195 throw MathRuntimeException.createIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
196 }
197 return optima.clone();
198 }
199
200 /** Get all the function values at optima found during the last call to {@link
201 * #optimize(UnivariateRealFunction, GoalType, double, double) optimize}.
202 * <p>
203 * The returned array as one element for each start as specified
204 * in the constructor. It is ordered with the results from the
205 * runs that did converge first, sorted from best to worst
206 * objective value (i.e in ascending order if minimizing and in
207 * descending order if maximizing), followed by Double.NaN elements
208 * corresponding to the runs that did not converge. This means all
209 * elements will be NaN if the {@link #optimize(UnivariateRealFunction,
210 * GoalType, double, double) optimize} method did throw a {@link
211 * ConvergenceException ConvergenceException}). This also means that
212 * if the first element is not NaN, it is the best point found across
213 * all starts.</p>
214 * @return array containing the optima
215 * @exception IllegalStateException if {@link #optimize(UnivariateRealFunction,
216 * GoalType, double, double) optimize} has not been called
217 * @see #getOptima()
218 */
219 public double[] getOptimaValues() throws IllegalStateException {
220 if (optimaValues == null) {
221 throw MathRuntimeException.createIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
222 }
223 return optimaValues.clone();
224 }
225
226 /** {@inheritDoc} */
227 public double optimize(final UnivariateRealFunction f, final GoalType goalType,
228 final double min, final double max)
229 throws ConvergenceException, FunctionEvaluationException {
230
231 optima = new double[starts];
232 optimaValues = new double[starts];
233 totalIterations = 0;
234 totalEvaluations = 0;
235
236 // multi-start loop
237 for (int i = 0; i < starts; ++i) {
238
239 try {
240 optimizer.setMaximalIterationCount(maxIterations - totalIterations);
241 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
242 final double bound1 = (i == 0) ? min : min + generator.nextDouble() * (max - min);
243 final double bound2 = (i == 0) ? max : min + generator.nextDouble() * (max - min);
244 optima[i] = optimizer.optimize(f, goalType,
245 FastMath.min(bound1, bound2),
246 FastMath.max(bound1, bound2));
247 optimaValues[i] = optimizer.getFunctionValue();
248 } catch (FunctionEvaluationException fee) {
249 optima[i] = Double.NaN;
250 optimaValues[i] = Double.NaN;
251 } catch (ConvergenceException ce) {
252 optima[i] = Double.NaN;
253 optimaValues[i] = Double.NaN;
254 }
255
256 totalIterations += optimizer.getIterationCount();
257 totalEvaluations += optimizer.getEvaluations();
258
259 }
260
261 // sort the optima from best to worst, followed by NaN elements
262 int lastNaN = optima.length;
263 for (int i = 0; i < lastNaN; ++i) {
264 if (Double.isNaN(optima[i])) {
265 optima[i] = optima[--lastNaN];
266 optima[lastNaN + 1] = Double.NaN;
267 optimaValues[i] = optimaValues[--lastNaN];
268 optimaValues[lastNaN + 1] = Double.NaN;
269 }
270 }
271
272 double currX = optima[0];
273 double currY = optimaValues[0];
274 for (int j = 1; j < lastNaN; ++j) {
275 final double prevY = currY;
276 currX = optima[j];
277 currY = optimaValues[j];
278 if ((goalType == GoalType.MAXIMIZE) ^ (currY < prevY)) {
279 // the current element should be inserted closer to the beginning
280 int i = j - 1;
281 double mIX = optima[i];
282 double mIY = optimaValues[i];
283 while ((i >= 0) && ((goalType == GoalType.MAXIMIZE) ^ (currY < mIY))) {
284 optima[i + 1] = mIX;
285 optimaValues[i + 1] = mIY;
286 if (i-- != 0) {
287 mIX = optima[i];
288 mIY = optimaValues[i];
289 } else {
290 mIX = Double.NaN;
291 mIY = Double.NaN;
292 }
293 }
294 optima[i + 1] = currX;
295 optimaValues[i + 1] = currY;
296 currX = optima[j];
297 currY = optimaValues[j];
298 }
299 }
300
301 if (Double.isNaN(optima[0])) {
302 throw new OptimizationException(
303 LocalizedFormats.NO_CONVERGENCE_WITH_ANY_START_POINT,
304 starts);
305 }
306
307 // return the found point given the best objective function value
308 return optima[0];
309
310 }
311
312 /** {@inheritDoc} */
313 public double optimize(final UnivariateRealFunction f, final GoalType goalType,
314 final double min, final double max, final double startValue)
315 throws ConvergenceException, FunctionEvaluationException {
316 return optimize(f, goalType, min, max);
317 }
318}
Note: See TracBrowser for help on using the repository browser.