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 1422230 2012-12-15 12:11:13Z erans $
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 }