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;
019
020 import java.util.Arrays;
021 import java.util.Comparator;
022
023 import org.apache.commons.math3.analysis.MultivariateFunction;
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.RandomVectorGenerator;
029
030 /**
031 * Base class for all implementations of a multi-start optimizer.
032 *
033 * This interface is mainly intended to enforce the internal coherence of
034 * Commons-Math. Users of the API are advised to base their code on
035 * {@link MultivariateMultiStartOptimizer} or on
036 * {@link DifferentiableMultivariateMultiStartOptimizer}.
037 *
038 * @param <FUNC> Type of the objective function to be optimized.
039 *
040 * @version $Id: BaseMultivariateMultiStartOptimizer.java 1422230 2012-12-15 12:11:13Z erans $
041 * @deprecated As of 3.1 (to be removed in 4.0).
042 * @since 3.0
043 */
044 @Deprecated
045 public class BaseMultivariateMultiStartOptimizer<FUNC extends MultivariateFunction>
046 implements BaseMultivariateOptimizer<FUNC> {
047 /** Underlying classical optimizer. */
048 private final BaseMultivariateOptimizer<FUNC> optimizer;
049 /** Maximal number of evaluations allowed. */
050 private int maxEvaluations;
051 /** Number of evaluations already performed for all starts. */
052 private int totalEvaluations;
053 /** Number of starts to go. */
054 private int starts;
055 /** Random generator for multi-start. */
056 private RandomVectorGenerator generator;
057 /** Found optima. */
058 private PointValuePair[] optima;
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(int,MultivariateFunction,GoalType,double[])
066 * optimize} will return the same solution as {@code optimizer} would.
067 * @param generator Random vector generator to use for restarts.
068 * @throws NullArgumentException if {@code optimizer} or {@code generator}
069 * is {@code null}.
070 * @throws NotStrictlyPositiveException if {@code starts < 1}.
071 */
072 protected BaseMultivariateMultiStartOptimizer(final BaseMultivariateOptimizer<FUNC> optimizer,
073 final int starts,
074 final RandomVectorGenerator generator) {
075 if (optimizer == null ||
076 generator == null) {
077 throw new NullArgumentException();
078 }
079 if (starts < 1) {
080 throw new NotStrictlyPositiveException(starts);
081 }
082
083 this.optimizer = optimizer;
084 this.starts = starts;
085 this.generator = generator;
086 }
087
088 /**
089 * Get all the optima found during the last call to {@link
090 * #optimize(int,MultivariateFunction,GoalType,double[]) optimize}.
091 * The optimizer stores all the optima found during a set of
092 * restarts. The {@link #optimize(int,MultivariateFunction,GoalType,double[])
093 * optimize} method returns the best point only. This method
094 * returns all the points found at the end of each starts,
095 * including the best one already returned by the {@link
096 * #optimize(int,MultivariateFunction,GoalType,double[]) optimize} method.
097 * <br/>
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(int,MultivariateFunction,GoalType,double[])
105 * optimize} method did throw an exception.
106 * This also means that if the first element is not {@code null}, it
107 * is the best point found across all starts.
108 *
109 * @return an array containing the optima.
110 * @throws MathIllegalStateException if {@link
111 * #optimize(int,MultivariateFunction,GoalType,double[]) optimize}
112 * has not been called.
113 */
114 public PointValuePair[] getOptima() {
115 if (optima == null) {
116 throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
117 }
118 return optima.clone();
119 }
120
121 /** {@inheritDoc} */
122 public int getMaxEvaluations() {
123 return maxEvaluations;
124 }
125
126 /** {@inheritDoc} */
127 public int getEvaluations() {
128 return totalEvaluations;
129 }
130
131 /** {@inheritDoc} */
132 public ConvergenceChecker<PointValuePair> getConvergenceChecker() {
133 return optimizer.getConvergenceChecker();
134 }
135
136 /**
137 * {@inheritDoc}
138 */
139 public PointValuePair optimize(int maxEval, final FUNC f,
140 final GoalType goal,
141 double[] startPoint) {
142 maxEvaluations = maxEval;
143 RuntimeException lastException = null;
144 optima = new PointValuePair[starts];
145 totalEvaluations = 0;
146
147 // Multi-start loop.
148 for (int i = 0; i < starts; ++i) {
149 // CHECKSTYLE: stop IllegalCatch
150 try {
151 optima[i] = optimizer.optimize(maxEval - totalEvaluations, f, goal,
152 i == 0 ? startPoint : generator.nextVector());
153 } catch (RuntimeException mue) {
154 lastException = mue;
155 optima[i] = null;
156 }
157 // CHECKSTYLE: resume IllegalCatch
158
159 totalEvaluations += optimizer.getEvaluations();
160 }
161
162 sortPairs(goal);
163
164 if (optima[0] == null) {
165 throw lastException; // cannot be null if starts >=1
166 }
167
168 // Return the found point given the best objective function value.
169 return optima[0];
170 }
171
172 /**
173 * Sort the optima from best to worst, followed by {@code null} elements.
174 *
175 * @param goal Goal type.
176 */
177 private void sortPairs(final GoalType goal) {
178 Arrays.sort(optima, new Comparator<PointValuePair>() {
179 public int compare(final PointValuePair o1,
180 final PointValuePair o2) {
181 if (o1 == null) {
182 return (o2 == null) ? 0 : 1;
183 } else if (o2 == null) {
184 return -1;
185 }
186 final double v1 = o1.getValue();
187 final double v2 = o2.getValue();
188 return (goal == GoalType.MINIMIZE) ?
189 Double.compare(v1, v2) : Double.compare(v2, v1);
190 }
191 });
192 }
193 }