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 package org.apache.commons.math3.optim;
018
019 import org.apache.commons.math3.exception.MathIllegalStateException;
020 import org.apache.commons.math3.exception.NotStrictlyPositiveException;
021 import org.apache.commons.math3.random.RandomVectorGenerator;
022
023 /**
024 * Base class multi-start optimizer for a multivariate function.
025 * <br/>
026 * This class wraps an optimizer in order to use it several times in
027 * turn with different starting points (trying to avoid being trapped
028 * in a local extremum when looking for a global one).
029 * <em>It is not a "user" class.</em>
030 *
031 * @param <PAIR> Type of the point/value pair returned by the optimization
032 * algorithm.
033 *
034 * @version $Id$
035 * @since 3.0
036 */
037 public abstract class BaseMultiStartMultivariateOptimizer<PAIR>
038 extends BaseMultivariateOptimizer<PAIR> {
039 /** Underlying classical optimizer. */
040 private final BaseMultivariateOptimizer<PAIR> optimizer;
041 /** Number of evaluations already performed for all starts. */
042 private int totalEvaluations;
043 /** Number of starts to go. */
044 private int starts;
045 /** Random generator for multi-start. */
046 private RandomVectorGenerator generator;
047 /** Optimization data. */
048 private OptimizationData[] optimData;
049 /**
050 * Location in {@link #optimData} where the updated maximum
051 * number of evaluations will be stored.
052 */
053 private int maxEvalIndex = -1;
054 /**
055 * Location in {@link #optimData} where the updated start value
056 * will be stored.
057 */
058 private int initialGuessIndex = -1;
059
060 /**
061 * Create a multi-start optimizer from a single-start optimizer.
062 *
063 * @param optimizer Single-start optimizer to wrap.
064 * @param starts Number of starts to perform. If {@code starts == 1},
065 * the {@link #optimize(OptimizationData[]) optimize} will return the
066 * same solution as the given {@code optimizer} would return.
067 * @param generator Random vector generator to use for restarts.
068 * @throws NotStrictlyPositiveException if {@code starts < 1}.
069 */
070 public BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<PAIR> optimizer,
071 final int starts,
072 final RandomVectorGenerator generator) {
073 super(optimizer.getConvergenceChecker());
074
075 if (starts < 1) {
076 throw new NotStrictlyPositiveException(starts);
077 }
078
079 this.optimizer = optimizer;
080 this.starts = starts;
081 this.generator = generator;
082 }
083
084 /** {@inheritDoc} */
085 @Override
086 public int getEvaluations() {
087 return totalEvaluations;
088 }
089
090 /**
091 * Gets all the optima found during the last call to {@code optimize}.
092 * The optimizer stores all the optima found during a set of
093 * restarts. The {@code optimize} method returns the best point only.
094 * This method returns all the points found at the end of each starts,
095 * including the best one already returned by the {@code optimize} method.
096 * <br/>
097 * The returned array as one element for each start as specified
098 * in the constructor. It is ordered with the results from the
099 * runs that did converge first, sorted from best to worst
100 * objective value (i.e in ascending order if minimizing and in
101 * descending order if maximizing), followed by {@code null} elements
102 * corresponding to the runs that did not converge. This means all
103 * elements will be {@code null} if the {@code optimize} method did throw
104 * an exception.
105 * This also means that if the first element is not {@code null}, it is
106 * the best point found across all starts.
107 * <br/>
108 * The behaviour is undefined if this method is called before
109 * {@code optimize}; it will likely throw {@code NullPointerException}.
110 *
111 * @return an array containing the optima sorted from best to worst.
112 */
113 public abstract PAIR[] getOptima();
114
115 /**
116 * {@inheritDoc}
117 *
118 * @throws MathIllegalStateException if {@code optData} does not contain an
119 * instance of {@link MaxEval} or {@link InitialGuess}.
120 */
121 @Override
122 public PAIR optimize(OptimizationData... optData) {
123 // Store arguments in order to pass them to the internal optimizer.
124 optimData = optData;
125 // Set up base class and perform computations.
126 return super.optimize(optData);
127 }
128
129 /** {@inheritDoc} */
130 @Override
131 protected PAIR doOptimize() {
132 // Remove all instances of "MaxEval" and "InitialGuess" from the
133 // array that will be passed to the internal optimizer.
134 // The former is to enforce smaller numbers of allowed evaluations
135 // (according to how many have been used up already), and the latter
136 // to impose a different start value for each start.
137 for (int i = 0; i < optimData.length; i++) {
138 if (optimData[i] instanceof MaxEval) {
139 optimData[i] = null;
140 maxEvalIndex = i;
141 }
142 if (optimData[i] instanceof InitialGuess) {
143 optimData[i] = null;
144 initialGuessIndex = i;
145 continue;
146 }
147 }
148 if (maxEvalIndex == -1) {
149 throw new MathIllegalStateException();
150 }
151 if (initialGuessIndex == -1) {
152 throw new MathIllegalStateException();
153 }
154
155 RuntimeException lastException = null;
156 totalEvaluations = 0;
157 clear();
158
159 final int maxEval = getMaxEvaluations();
160 final double[] min = getLowerBound(); // XXX Should be used to enforce bounds (see below).
161 final double[] max = getUpperBound(); // XXX Should be used to enforce bounds (see below).
162 final double[] startPoint = getStartPoint();
163
164 // Multi-start loop.
165 for (int i = 0; i < starts; i++) {
166 // CHECKSTYLE: stop IllegalCatch
167 try {
168 // Decrease number of allowed evaluations.
169 optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
170 // New start value.
171 final double[] s = (i == 0) ?
172 startPoint :
173 generator.nextVector(); // XXX This does not enforce bounds!
174 optimData[initialGuessIndex] = new InitialGuess(s);
175 // Optimize.
176 final PAIR result = optimizer.optimize(optimData);
177 store(result);
178 } catch (RuntimeException mue) {
179 lastException = mue;
180 }
181 // CHECKSTYLE: resume IllegalCatch
182
183 totalEvaluations += optimizer.getEvaluations();
184 }
185
186 final PAIR[] optima = getOptima();
187 if (optima.length == 0) {
188 // All runs failed.
189 throw lastException; // Cannot be null if starts >= 1.
190 }
191
192 // Return the best optimum.
193 return optima[0];
194 }
195
196 /**
197 * Method that will be called in order to store each found optimum.
198 *
199 * @param optimum Result of an optimization run.
200 */
201 protected abstract void store(PAIR optimum);
202 /**
203 * Method that will called in order to clear all stored optima.
204 */
205 protected abstract void clear();
206 }