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