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.math3.optimization.univariate;
019
020 import java.util.Arrays;
021 import java.util.Comparator;
022
023 import org.apache.commons.math3.analysis.UnivariateFunction;
024 import org.apache.commons.math3.exception.MathIllegalStateException;
025 import org.apache.commons.math3.exception.NotStrictlyPositiveException;
026 import org.apache.commons.math3.exception.NullArgumentException;
027 import org.apache.commons.math3.exception.util.LocalizedFormats;
028 import org.apache.commons.math3.random.RandomGenerator;
029 import org.apache.commons.math3.optimization.GoalType;
030 import org.apache.commons.math3.optimization.ConvergenceChecker;
031
032 /**
033 * Special implementation of the {@link UnivariateOptimizer} interface
034 * adding multi-start features to an existing optimizer.
035 *
036 * This class wraps a classical optimizer to use it several times in
037 * turn with different starting points in order to avoid being trapped
038 * into a local extremum when looking for a global one.
039 *
040 * @param <FUNC> Type of the objective function to be optimized.
041 *
042 * @version $Id: UnivariateMultiStartOptimizer.java 1422230 2012-12-15 12:11:13Z erans $
043 * @deprecated As of 3.1 (to be removed in 4.0).
044 * @since 3.0
045 */
046 @Deprecated
047 public class UnivariateMultiStartOptimizer<FUNC extends UnivariateFunction>
048 implements BaseUnivariateOptimizer<FUNC> {
049 /** Underlying classical optimizer. */
050 private final BaseUnivariateOptimizer<FUNC> optimizer;
051 /** Maximal number of evaluations allowed. */
052 private int maxEvaluations;
053 /** Number of evaluations already performed for all starts. */
054 private int totalEvaluations;
055 /** Number of starts to go. */
056 private int starts;
057 /** Random generator for multi-start. */
058 private RandomGenerator generator;
059 /** Found optima. */
060 private UnivariatePointValuePair[] optima;
061
062 /**
063 * Create a multi-start optimizer from a single-start optimizer.
064 *
065 * @param optimizer Single-start optimizer to wrap.
066 * @param starts Number of starts to perform. If {@code starts == 1},
067 * the {@code optimize} methods will return the same solution as
068 * {@code optimizer} would.
069 * @param generator Random generator to use for restarts.
070 * @throws NullArgumentException if {@code optimizer} or {@code generator}
071 * is {@code null}.
072 * @throws NotStrictlyPositiveException if {@code starts < 1}.
073 */
074 public UnivariateMultiStartOptimizer(final BaseUnivariateOptimizer<FUNC> optimizer,
075 final int starts,
076 final RandomGenerator generator) {
077 if (optimizer == null ||
078 generator == null) {
079 throw new NullArgumentException();
080 }
081 if (starts < 1) {
082 throw new NotStrictlyPositiveException(starts);
083 }
084
085 this.optimizer = optimizer;
086 this.starts = starts;
087 this.generator = generator;
088 }
089
090 /**
091 * {@inheritDoc}
092 */
093 public ConvergenceChecker<UnivariatePointValuePair> getConvergenceChecker() {
094 return optimizer.getConvergenceChecker();
095 }
096
097 /** {@inheritDoc} */
098 public int getMaxEvaluations() {
099 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 }