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