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.optimization.univariate;
019
020import java.util.Arrays;
021import java.util.Comparator;
022
023import org.apache.commons.math3.analysis.UnivariateFunction;
024import org.apache.commons.math3.exception.MathIllegalStateException;
025import org.apache.commons.math3.exception.NotStrictlyPositiveException;
026import org.apache.commons.math3.exception.NullArgumentException;
027import org.apache.commons.math3.exception.util.LocalizedFormats;
028import org.apache.commons.math3.random.RandomGenerator;
029import org.apache.commons.math3.optimization.GoalType;
030import org.apache.commons.math3.optimization.ConvergenceChecker;
031
032/**
033 * Special implementation of the {@link UnivariateOptimizer} interface
034 * adding multi-start features to an existing optimizer.
035 *
036 * This class wraps a classical optimizer to use it several times in
037 * turn with different starting points in order to avoid being trapped
038 * into a local extremum when looking for a global one.
039 *
040 * @param <FUNC> Type of the objective function to be optimized.
041 *
042 * @version $Id: UnivariateMultiStartOptimizer.java 1422230 2012-12-15 12:11:13Z erans $
043 * @deprecated As of 3.1 (to be removed in 4.0).
044 * @since 3.0
045 */
046@Deprecated
047public class UnivariateMultiStartOptimizer<FUNC extends UnivariateFunction>
048    implements BaseUnivariateOptimizer<FUNC> {
049    /** Underlying classical optimizer. */
050    private final BaseUnivariateOptimizer<FUNC> optimizer;
051    /** Maximal number of evaluations allowed. */
052    private int maxEvaluations;
053    /** Number of evaluations already performed for all starts. */
054    private int totalEvaluations;
055    /** Number of starts to go. */
056    private int starts;
057    /** Random generator for multi-start. */
058    private RandomGenerator generator;
059    /** Found optima. */
060    private UnivariatePointValuePair[] optima;
061
062    /**
063     * Create a multi-start optimizer from a single-start optimizer.
064     *
065     * @param optimizer Single-start optimizer to wrap.
066     * @param starts Number of starts to perform. If {@code starts == 1},
067     * the {@code optimize} methods will return the same solution as
068     * {@code optimizer} would.
069     * @param generator Random generator to use for restarts.
070     * @throws NullArgumentException if {@code optimizer} or {@code generator}
071     * is {@code null}.
072     * @throws NotStrictlyPositiveException if {@code starts < 1}.
073     */
074    public UnivariateMultiStartOptimizer(final BaseUnivariateOptimizer<FUNC> optimizer,
075                                             final int starts,
076                                             final RandomGenerator generator) {
077        if (optimizer == null ||
078                generator == null) {
079                throw new NullArgumentException();
080        }
081        if (starts < 1) {
082            throw new NotStrictlyPositiveException(starts);
083        }
084
085        this.optimizer = optimizer;
086        this.starts = starts;
087        this.generator = generator;
088    }
089
090    /**
091     * {@inheritDoc}
092     */
093    public ConvergenceChecker<UnivariatePointValuePair> getConvergenceChecker() {
094        return optimizer.getConvergenceChecker();
095    }
096
097    /** {@inheritDoc} */
098    public int getMaxEvaluations() {
099        return maxEvaluations;
100    }
101
102    /** {@inheritDoc} */
103    public int getEvaluations() {
104        return totalEvaluations;
105    }
106
107    /**
108     * Get all the optima found during the last call to {@link
109     * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}.
110     * The optimizer stores all the optima found during a set of
111     * restarts. The {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
112     * method returns the best point only. This method returns all the points
113     * found at the end of each starts, including the best one already
114     * returned by the {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
115     * method.
116     * <br/>
117     * The returned array as one element for each start as specified
118     * in the constructor. It is ordered with the results from the
119     * runs that did converge first, sorted from best to worst
120     * objective value (i.e in ascending order if minimizing and in
121     * descending order if maximizing), followed by {@code null} elements
122     * corresponding to the runs that did not converge. This means all
123     * elements will be {@code null} if the {@link
124     * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
125     * method did throw an exception.
126     * This also means that if the first element is not {@code null}, it is
127     * the best point found across all starts.
128     *
129     * @return an array containing the optima.
130     * @throws MathIllegalStateException if {@link
131     * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
132     * has not been called.
133     */
134    public UnivariatePointValuePair[] getOptima() {
135        if (optima == null) {
136            throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
137        }
138        return optima.clone();
139    }
140
141    /** {@inheritDoc} */
142    public UnivariatePointValuePair optimize(int maxEval, final FUNC f,
143                                                 final GoalType goal,
144                                                 final double min, final double max) {
145        return optimize(maxEval, f, goal, min, max, min + 0.5 * (max - min));
146    }
147
148    /** {@inheritDoc} */
149    public UnivariatePointValuePair optimize(int maxEval, final FUNC f,
150                                                 final GoalType goal,
151                                                 final double min, final double max,
152                                                 final double startValue) {
153        RuntimeException lastException = null;
154        optima = new UnivariatePointValuePair[starts];
155        totalEvaluations = 0;
156
157        // Multi-start loop.
158        for (int i = 0; i < starts; ++i) {
159            // CHECKSTYLE: stop IllegalCatch
160            try {
161                final double s = (i == 0) ? startValue : min + generator.nextDouble() * (max - min);
162                optima[i] = optimizer.optimize(maxEval - totalEvaluations, f, goal, min, max, s);
163            } catch (RuntimeException mue) {
164                lastException = mue;
165                optima[i] = null;
166            }
167            // CHECKSTYLE: resume IllegalCatch
168
169            totalEvaluations += optimizer.getEvaluations();
170        }
171
172        sortPairs(goal);
173
174        if (optima[0] == null) {
175            throw lastException; // cannot be null if starts >=1
176        }
177
178        // Return the point with the best objective function value.
179        return optima[0];
180    }
181
182    /**
183     * Sort the optima from best to worst, followed by {@code null} elements.
184     *
185     * @param goal Goal type.
186     */
187    private void sortPairs(final GoalType goal) {
188        Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() {
189                public int compare(final UnivariatePointValuePair o1,
190                                   final UnivariatePointValuePair o2) {
191                    if (o1 == null) {
192                        return (o2 == null) ? 0 : 1;
193                    } else if (o2 == null) {
194                        return -1;
195                    }
196                    final double v1 = o1.getValue();
197                    final double v2 = o2.getValue();
198                    return (goal == GoalType.MINIMIZE) ?
199                        Double.compare(v1, v2) : Double.compare(v2, v1);
200                }
201            });
202    }
203}