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