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
018package org.apache.commons.math3.optim.univariate;
019
020import java.util.Arrays;
021import java.util.Comparator;
022import org.apache.commons.math3.exception.MathIllegalStateException;
023import org.apache.commons.math3.exception.NotStrictlyPositiveException;
024import org.apache.commons.math3.exception.util.LocalizedFormats;
025import org.apache.commons.math3.random.RandomGenerator;
026import org.apache.commons.math3.optim.MaxEval;
027import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
028import org.apache.commons.math3.optim.OptimizationData;
029
030/**
031 * Special implementation of the {@link UnivariateOptimizer} interface
032 * adding multi-start features to an existing optimizer.
033 * <br/>
034 * This class wraps an optimizer in order to use it several times in
035 * turn with different starting points (trying to avoid being trapped
036 * in a local extremum when looking for a global one).
037 *
038 * @since 3.0
039 */
040public class MultiStartUnivariateOptimizer
041    extends UnivariateOptimizer {
042    /** Underlying classical optimizer. */
043    private final UnivariateOptimizer optimizer;
044    /** Number of evaluations already performed for all starts. */
045    private int totalEvaluations;
046    /** Number of starts to go. */
047    private int starts;
048    /** Random generator for multi-start. */
049    private RandomGenerator generator;
050    /** Found optima. */
051    private UnivariatePointValuePair[] optima;
052    /** Optimization data. */
053    private OptimizationData[] optimData;
054    /**
055     * Location in {@link #optimData} where the updated maximum
056     * number of evaluations will be stored.
057     */
058    private int maxEvalIndex = -1;
059    /**
060     * Location in {@link #optimData} where the updated start value
061     * will be stored.
062     */
063    private int searchIntervalIndex = -1;
064
065    /**
066     * Create a multi-start optimizer from a single-start optimizer.
067     *
068     * @param optimizer Single-start optimizer to wrap.
069     * @param starts Number of starts to perform. If {@code starts == 1},
070     * the {@code optimize} methods will return the same solution as
071     * {@code optimizer} would.
072     * @param generator Random generator to use for restarts.
073     * @throws NotStrictlyPositiveException if {@code starts < 1}.
074     */
075    public MultiStartUnivariateOptimizer(final UnivariateOptimizer optimizer,
076                                         final int starts,
077                                         final RandomGenerator generator) {
078        super(optimizer.getConvergenceChecker());
079
080        if (starts < 1) {
081            throw new NotStrictlyPositiveException(starts);
082        }
083
084        this.optimizer = optimizer;
085        this.starts = starts;
086        this.generator = generator;
087    }
088
089    /** {@inheritDoc} */
090    @Override
091    public int getEvaluations() {
092        return totalEvaluations;
093    }
094
095    /**
096     * Gets all the optima found during the last call to {@code optimize}.
097     * The optimizer stores all the optima found during a set of
098     * restarts. The {@code optimize} method returns the best point only.
099     * This method returns all the points found at the end of each starts,
100     * including the best one already returned by the {@code optimize} method.
101     * <br/>
102     * The returned array as one element for each start as specified
103     * in the constructor. It is ordered with the results from the
104     * runs that did converge first, sorted from best to worst
105     * objective value (i.e in ascending order if minimizing and in
106     * descending order if maximizing), followed by {@code null} elements
107     * corresponding to the runs that did not converge. This means all
108     * elements will be {@code null} if the {@code optimize} method did throw
109     * an exception.
110     * This also means that if the first element is not {@code null}, it is
111     * the best point found across all starts.
112     *
113     * @return an array containing the optima.
114     * @throws MathIllegalStateException if {@link #optimize(OptimizationData[])
115     * optimize} has not been called.
116     */
117    public UnivariatePointValuePair[] getOptima() {
118        if (optima == null) {
119            throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
120        }
121        return optima.clone();
122    }
123
124    /**
125     * {@inheritDoc}
126     *
127     * @throws MathIllegalStateException if {@code optData} does not contain an
128     * instance of {@link MaxEval} or {@link SearchInterval}.
129     */
130    @Override
131    public UnivariatePointValuePair optimize(OptimizationData... optData) {
132        // Store arguments in order to pass them to the internal optimizer.
133       optimData = optData;
134        // Set up base class and perform computations.
135        return super.optimize(optData);
136    }
137
138    /** {@inheritDoc} */
139    @Override
140    protected UnivariatePointValuePair doOptimize() {
141        // Remove all instances of "MaxEval" and "SearchInterval" from the
142        // array that will be passed to the internal optimizer.
143        // The former is to enforce smaller numbers of allowed evaluations
144        // (according to how many have been used up already), and the latter
145        // to impose a different start value for each start.
146        for (int i = 0; i < optimData.length; i++) {
147            if (optimData[i] instanceof MaxEval) {
148                optimData[i] = null;
149                maxEvalIndex = i;
150                continue;
151            }
152            if (optimData[i] instanceof SearchInterval) {
153                optimData[i] = null;
154                searchIntervalIndex = i;
155                continue;
156            }
157        }
158        if (maxEvalIndex == -1) {
159            throw new MathIllegalStateException();
160        }
161        if (searchIntervalIndex == -1) {
162            throw new MathIllegalStateException();
163        }
164
165        RuntimeException lastException = null;
166        optima = new UnivariatePointValuePair[starts];
167        totalEvaluations = 0;
168
169        final int maxEval = getMaxEvaluations();
170        final double min = getMin();
171        final double max = getMax();
172        final double startValue = getStartValue();
173
174        // Multi-start loop.
175        for (int i = 0; i < starts; i++) {
176            // CHECKSTYLE: stop IllegalCatch
177            try {
178                // Decrease number of allowed evaluations.
179                optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
180                // New start value.
181                final double s = (i == 0) ?
182                    startValue :
183                    min + generator.nextDouble() * (max - min);
184                optimData[searchIntervalIndex] = new SearchInterval(min, max, s);
185                // Optimize.
186                optima[i] = optimizer.optimize(optimData);
187            } catch (RuntimeException mue) {
188                lastException = mue;
189                optima[i] = null;
190            }
191            // CHECKSTYLE: resume IllegalCatch
192
193            totalEvaluations += optimizer.getEvaluations();
194        }
195
196        sortPairs(getGoalType());
197
198        if (optima[0] == null) {
199            throw lastException; // Cannot be null if starts >= 1.
200        }
201
202        // Return the point with the best objective function value.
203        return optima[0];
204    }
205
206    /**
207     * Sort the optima from best to worst, followed by {@code null} elements.
208     *
209     * @param goal Goal type.
210     */
211    private void sortPairs(final GoalType goal) {
212        Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() {
213                /** {@inheritDoc} */
214                public int compare(final UnivariatePointValuePair o1,
215                                   final UnivariatePointValuePair o2) {
216                    if (o1 == null) {
217                        return (o2 == null) ? 0 : 1;
218                    } else if (o2 == null) {
219                        return -1;
220                    }
221                    final double v1 = o1.getValue();
222                    final double v2 = o2.getValue();
223                    return (goal == GoalType.MINIMIZE) ?
224                        Double.compare(v1, v2) : Double.compare(v2, v1);
225                }
226            });
227    }
228}