    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    }