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 java.util.Arrays;
021 import java.util.Comparator;
022
023 import org.apache.commons.math.FunctionEvaluationException;
024 import org.apache.commons.math.MathRuntimeException;
025 import org.apache.commons.math.analysis.DifferentiableMultivariateRealFunction;
026 import org.apache.commons.math.random.RandomVectorGenerator;
027
028 /**
029 * Special implementation of the {@link DifferentiableMultivariateRealOptimizer} interface adding
030 * multi-start features to an existing optimizer.
031 * <p>
032 * This class wraps a classical optimizer to use it several times in
033 * turn with different starting points in order to avoid being trapped
034 * into a local extremum when looking for a global one.
035 * </p>
036 * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $
037 * @since 2.0
038 */
039 public class MultiStartDifferentiableMultivariateRealOptimizer
040 implements DifferentiableMultivariateRealOptimizer {
041
042 /** Underlying classical optimizer. */
043 private final DifferentiableMultivariateRealOptimizer optimizer;
044
045 /** Maximal number of iterations allowed. */
046 private int maxIterations;
047
048 /** Number of iterations already performed for all starts. */
049 private int totalIterations;
050
051 /** Maximal number of evaluations allowed. */
052 private int maxEvaluations;
053
054 /** Number of evaluations already performed for all starts. */
055 private int totalEvaluations;
056
057 /** Number of gradient evaluations already performed for all starts. */
058 private int totalGradientEvaluations;
059
060 /** Number of starts to go. */
061 private int starts;
062
063 /** Random generator for multi-start. */
064 private RandomVectorGenerator generator;
065
066 /** Found optima. */
067 private RealPointValuePair[] optima;
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 vector generator to use for restarts
076 */
077 public MultiStartDifferentiableMultivariateRealOptimizer(final DifferentiableMultivariateRealOptimizer optimizer,
078 final int starts,
079 final RandomVectorGenerator generator) {
080 this.optimizer = optimizer;
081 this.totalIterations = 0;
082 this.totalEvaluations = 0;
083 this.totalGradientEvaluations = 0;
084 this.starts = starts;
085 this.generator = generator;
086 this.optima = null;
087 setMaxIterations(Integer.MAX_VALUE);
088 setMaxEvaluations(Integer.MAX_VALUE);
089 }
090
091 /** Get all the optima found during the last call to {@link
092 * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
093 * optimize}.
094 * <p>The optimizer stores all the optima found during a set of
095 * restarts. The {@link #optimize(DifferentiableMultivariateRealFunction,
096 * GoalType, double[]) optimize} method returns the best point only. This
097 * method returns all the points found at the end of each starts,
098 * including the best one already returned by the {@link
099 * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
100 * optimize} method.
101 * </p>
102 * <p>
103 * The returned array as one element for each start as specified
104 * in the constructor. It is ordered with the results from the
105 * runs that did converge first, sorted from best to worst
106 * objective value (i.e in ascending order if minimizing and in
107 * descending order if maximizing), followed by and null elements
108 * corresponding to the runs that did not converge. This means all
109 * elements will be null if the {@link #optimize(DifferentiableMultivariateRealFunction,
110 * GoalType, double[]) optimize} method did throw a {@link
111 * org.apache.commons.math.ConvergenceException ConvergenceException}).
112 * This also means that if the first element is non null, it is the best
113 * point found across all starts.</p>
114 * @return array containing the optima
115 * @exception IllegalStateException if {@link #optimize(DifferentiableMultivariateRealFunction,
116 * GoalType, double[]) optimize} has not been called
117 */
118 public RealPointValuePair[] getOptima() throws IllegalStateException {
119 if (optima == null) {
120 throw MathRuntimeException.createIllegalStateException("no optimum computed yet");
121 }
122 return optima.clone();
123 }
124
125 /** {@inheritDoc} */
126 public void setMaxIterations(int maxIterations) {
127 this.maxIterations = maxIterations;
128 }
129
130 /** {@inheritDoc} */
131 public int getMaxIterations() {
132 return maxIterations;
133 }
134
135 /** {@inheritDoc} */
136 public int getIterations() {
137 return totalIterations;
138 }
139
140 /** {@inheritDoc} */
141 public void setMaxEvaluations(int maxEvaluations) {
142 this.maxEvaluations = maxEvaluations;
143 }
144
145 /** {@inheritDoc} */
146 public int getMaxEvaluations() {
147 return maxEvaluations;
148 }
149
150 /** {@inheritDoc} */
151 public int getEvaluations() {
152 return totalEvaluations;
153 }
154
155 /** {@inheritDoc} */
156 public int getGradientEvaluations() {
157 return totalGradientEvaluations;
158 }
159
160 /** {@inheritDoc} */
161 public void setConvergenceChecker(RealConvergenceChecker checker) {
162 optimizer.setConvergenceChecker(checker);
163 }
164
165 /** {@inheritDoc} */
166 public RealConvergenceChecker getConvergenceChecker() {
167 return optimizer.getConvergenceChecker();
168 }
169
170 /** {@inheritDoc} */
171 public RealPointValuePair optimize(final DifferentiableMultivariateRealFunction f,
172 final GoalType goalType,
173 double[] startPoint)
174 throws FunctionEvaluationException, OptimizationException {
175
176 optima = new RealPointValuePair[starts];
177 totalIterations = 0;
178 totalEvaluations = 0;
179 totalGradientEvaluations = 0;
180
181 // multi-start loop
182 for (int i = 0; i < starts; ++i) {
183
184 try {
185 optimizer.setMaxIterations(maxIterations - totalIterations);
186 optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
187 optima[i] = optimizer.optimize(f, goalType,
188 (i == 0) ? startPoint : generator.nextVector());
189 } catch (FunctionEvaluationException fee) {
190 optima[i] = null;
191 } catch (OptimizationException oe) {
192 optima[i] = null;
193 }
194
195 totalIterations += optimizer.getIterations();
196 totalEvaluations += optimizer.getEvaluations();
197 totalGradientEvaluations += optimizer.getGradientEvaluations();
198
199 }
200
201 // sort the optima from best to worst, followed by null elements
202 Arrays.sort(optima, new Comparator<RealPointValuePair>() {
203 public int compare(final RealPointValuePair o1, final RealPointValuePair o2) {
204 if (o1 == null) {
205 return (o2 == null) ? 0 : +1;
206 } else if (o2 == null) {
207 return -1;
208 }
209 final double v1 = o1.getValue();
210 final double v2 = o2.getValue();
211 return (goalType == GoalType.MINIMIZE) ?
212 Double.compare(v1, v2) : Double.compare(v2, v1);
213 }
214 });
215
216 if (optima[0] == null) {
217 throw new OptimizationException(
218 "none of the {0} start points lead to convergence",
219 starts);
220 }
221
222 // return the found point given the best objective function value
223 return optima[0];
224
225 }
226
227 }