    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.math.optimization;
    019
    020    import java.util.Arrays;
    021    import java.util.Comparator;
    022
    023    import org.apache.commons.math.FunctionEvaluationException;
    024    import org.apache.commons.math.MathRuntimeException;
    025    import org.apache.commons.math.analysis.DifferentiableMultivariateRealFunction;
    026    import org.apache.commons.math.exception.util.LocalizedFormats;
    027    import org.apache.commons.math.random.RandomVectorGenerator;
    028
    029    /**
    030     * Special implementation of the {@link DifferentiableMultivariateRealOptimizer} interface adding
    031     * multi-start features to an existing optimizer.
    032     * <p>
    033     * This class wraps a classical optimizer to use it several times in
    034     * turn with different starting points in order to avoid being trapped
    035     * into a local extremum when looking for a global one.
    036     * </p>
    037     * @version $Revision: 1073158 $ $Date: 2011-02-21 22:46:52 +0100 (lun. 21 f??vr. 2011) $
    038     * @since 2.0
    039     */
    040    public class MultiStartDifferentiableMultivariateRealOptimizer
    041        implements DifferentiableMultivariateRealOptimizer {
    042
    043        /** Underlying classical optimizer. */
    044        private final DifferentiableMultivariateRealOptimizer optimizer;
    045
    046        /** Maximal number of iterations allowed. */
    047        private int maxIterations;
    048
    049        /** Number of iterations already performed for all starts. */
    050        private int totalIterations;
    051
    052        /** Maximal number of evaluations allowed. */
    053        private int maxEvaluations;
    054
    055        /** Number of evaluations already performed for all starts. */
    056        private int totalEvaluations;
    057
    058        /** Number of gradient evaluations already performed for all starts. */
    059        private int totalGradientEvaluations;
    060
    061        /** Number of starts to go. */
    062        private int starts;
    063
    064        /** Random generator for multi-start. */
    065        private RandomVectorGenerator generator;
    066
    067        /** Found optima. */
    068        private RealPointValuePair[] optima;
    069
    070        /**
    071         * Create a multi-start optimizer from a single-start optimizer
    072         * @param optimizer single-start optimizer to wrap
    073         * @param starts number of starts to perform (including the
    074         * first one), multi-start is disabled if value is less than or
    075         * equal to 1
    076         * @param generator random vector generator to use for restarts
    077         */
    078        public MultiStartDifferentiableMultivariateRealOptimizer(final DifferentiableMultivariateRealOptimizer optimizer,
    079                                                                 final int starts,
    080                                                                 final RandomVectorGenerator generator) {
    081            this.optimizer                = optimizer;
    082            this.totalIterations          = 0;
    083            this.totalEvaluations         = 0;
    084            this.totalGradientEvaluations = 0;
    085            this.starts                   = starts;
    086            this.generator                = generator;
    087            this.optima                   = null;
    088            setMaxIterations(Integer.MAX_VALUE);
    089            setMaxEvaluations(Integer.MAX_VALUE);
    090        }
    091
    092        /** Get all the optima found during the last call to {@link
    093         * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
    094         * optimize}.
    095         * <p>The optimizer stores all the optima found during a set of
    096         * restarts. The {@link #optimize(DifferentiableMultivariateRealFunction,
    097         * GoalType, double[]) optimize} method returns the best point only. This
    098         * method returns all the points found at the end of each starts,
    099         * including the best one already returned by the {@link
    100         * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
    101         * optimize} method.
    102         * </p>
    103         * <p>
    104         * The returned array as one element for each start as specified
    105         * in the constructor. It is ordered with the results from the
    106         * runs that did converge first, sorted from best to worst
    107         * objective value (i.e in ascending order if minimizing and in
    108         * descending order if maximizing), followed by and null elements
    109         * corresponding to the runs that did not converge. This means all
    110         * elements will be null if the {@link #optimize(DifferentiableMultivariateRealFunction,
    111         * GoalType, double[]) optimize} method did throw a {@link
    112         * org.apache.commons.math.ConvergenceException ConvergenceException}).
    113         * This also means that if the first element is non null, it is the best
    114         * point found across all starts.</p>
    115         * @return array containing the optima
    116         * @exception IllegalStateException if {@link #optimize(DifferentiableMultivariateRealFunction,
    117         * GoalType, double[]) optimize} has not been called
    118         */
    119        public RealPointValuePair[] getOptima() throws IllegalStateException {
    120            if (optima == null) {
    121                throw MathRuntimeException.createIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
    122            }
    123            return optima.clone();
    124        }
    125
    126        /** {@inheritDoc} */
    127        public void setMaxIterations(int maxIterations) {
    128            this.maxIterations = maxIterations;
    129        }
    130
    131        /** {@inheritDoc} */
    132        public int getMaxIterations() {
    133            return maxIterations;
    134        }
    135
    136        /** {@inheritDoc} */
    137        public int getIterations() {
    138            return totalIterations;
    139        }
    140
    141        /** {@inheritDoc} */
    142        public void setMaxEvaluations(int maxEvaluations) {
    143            this.maxEvaluations = maxEvaluations;
    144        }
    145
    146        /** {@inheritDoc} */
    147        public int getMaxEvaluations() {
    148            return maxEvaluations;
    149        }
    150
    151        /** {@inheritDoc} */
    152        public int getEvaluations() {
    153            return totalEvaluations;
    154        }
    155
    156        /** {@inheritDoc} */
    157        public int getGradientEvaluations() {
    158            return totalGradientEvaluations;
    159        }
    160
    161        /** {@inheritDoc} */
    162        public void setConvergenceChecker(RealConvergenceChecker checker) {
    163            optimizer.setConvergenceChecker(checker);
    164        }
    165
    166        /** {@inheritDoc} */
    167        public RealConvergenceChecker getConvergenceChecker() {
    168            return optimizer.getConvergenceChecker();
    169        }
    170
    171        /** {@inheritDoc} */
    172        public RealPointValuePair optimize(final DifferentiableMultivariateRealFunction f,
    173                                             final GoalType goalType,
    174                                             double[] startPoint)
    175            throws FunctionEvaluationException, OptimizationException, FunctionEvaluationException {
    176
    177            optima                   = new RealPointValuePair[starts];
    178            totalIterations          = 0;
    179            totalEvaluations         = 0;
    180            totalGradientEvaluations = 0;
    181
    182            // multi-start loop
    183            for (int i = 0; i < starts; ++i) {
    184
    185                try {
    186                    optimizer.setMaxIterations(maxIterations - totalIterations);
    187                    optimizer.setMaxEvaluations(maxEvaluations - totalEvaluations);
    188                    optima[i] = optimizer.optimize(f, goalType,
    189                                                   (i == 0) ? startPoint : generator.nextVector());
    190                } catch (FunctionEvaluationException fee) {
    191                    optima[i] = null;
    192                } catch (OptimizationException oe) {
    193                    optima[i] = null;
    194                }
    195
    196                totalIterations          += optimizer.getIterations();
    197                totalEvaluations         += optimizer.getEvaluations();
    198                totalGradientEvaluations += optimizer.getGradientEvaluations();
    199
    200            }
    201
    202            // sort the optima from best to worst, followed by null elements
    203            Arrays.sort(optima, new Comparator<RealPointValuePair>() {
    204                public int compare(final RealPointValuePair o1, final RealPointValuePair o2) {
    205                    if (o1 == null) {
    206                        return (o2 == null) ? 0 : +1;
    207                    } else if (o2 == null) {
    208                        return -1;
    209                    }
    210                    final double v1 = o1.getValue();
    211                    final double v2 = o2.getValue();
    212                    return (goalType == GoalType.MINIMIZE) ?
    213                            Double.compare(v1, v2) : Double.compare(v2, v1);
    214                }
    215            });
    216
    217            if (optima[0] == null) {
    218                throw new OptimizationException(
    219                        LocalizedFormats.NO_CONVERGENCE_WITH_ANY_START_POINT,
    220                        starts);
    221            }
    222
    223            // return the found point given the best objective function value
    224            return optima[0];
    225
    226        }
    227
    228    }