    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.univariate;
    019
    020    import java.util.Arrays;
    021    import java.util.Comparator;
    022
    023    import org.apache.commons.math3.analysis.UnivariateFunction;
    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.RandomGenerator;
    029    import org.apache.commons.math3.optimization.GoalType;
    030    import 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
    047    public 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    }