    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    package org.apache.commons.math3.optim;
    018
    019    import org.apache.commons.math3.exception.MathIllegalStateException;
    020    import org.apache.commons.math3.exception.NotStrictlyPositiveException;
    021    import org.apache.commons.math3.random.RandomVectorGenerator;
    022
    023    /**
    024     * Base class multi-start optimizer for a multivariate function.
    025     * <br/>
    026     * This class wraps an optimizer in order to use it several times in
    027     * turn with different starting points (trying to avoid being trapped
    028     * in a local extremum when looking for a global one).
    029     * <em>It is not a "user" class.</em>
    030     *
    031     * @param <PAIR> Type of the point/value pair returned by the optimization
    032     * algorithm.
    033     *
    034     * @version $Id$
    035     * @since 3.0
    036     */
    037    public abstract class BaseMultiStartMultivariateOptimizer<PAIR>
    038        extends BaseMultivariateOptimizer<PAIR> {
    039        /** Underlying classical optimizer. */
    040        private final BaseMultivariateOptimizer<PAIR> optimizer;
    041        /** Number of evaluations already performed for all starts. */
    042        private int totalEvaluations;
    043        /** Number of starts to go. */
    044        private int starts;
    045        /** Random generator for multi-start. */
    046        private RandomVectorGenerator generator;
    047        /** Optimization data. */
    048        private OptimizationData[] optimData;
    049        /**
    050         * Location in {@link #optimData} where the updated maximum
    051         * number of evaluations will be stored.
    052         */
    053        private int maxEvalIndex = -1;
    054        /**
    055         * Location in {@link #optimData} where the updated start value
    056         * will be stored.
    057         */
    058        private int initialGuessIndex = -1;
    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(OptimizationData[]) optimize} will return the
    066         * same solution as the given {@code optimizer} would return.
    067         * @param generator Random vector generator to use for restarts.
    068         * @throws NotStrictlyPositiveException if {@code starts < 1}.
    069         */
    070        public BaseMultiStartMultivariateOptimizer(final BaseMultivariateOptimizer<PAIR> optimizer,
    071                                                   final int starts,
    072                                                   final RandomVectorGenerator generator) {
    073            super(optimizer.getConvergenceChecker());
    074
    075            if (starts < 1) {
    076                throw new NotStrictlyPositiveException(starts);
    077            }
    078
    079            this.optimizer = optimizer;
    080            this.starts = starts;
    081            this.generator = generator;
    082        }
    083
    084        /** {@inheritDoc} */
    085        @Override
    086        public int getEvaluations() {
    087            return totalEvaluations;
    088        }
    089
    090        /**
    091         * Gets all the optima found during the last call to {@code optimize}.
    092         * The optimizer stores all the optima found during a set of
    093         * restarts. The {@code optimize} method returns the best point only.
    094         * This method returns all the points found at the end of each starts,
    095         * including the best one already returned by the {@code optimize} method.
    096         * <br/>
    097         * The returned array as one element for each start as specified
    098         * in the constructor. It is ordered with the results from the
    099         * runs that did converge first, sorted from best to worst
    100         * objective value (i.e in ascending order if minimizing and in
    101         * descending order if maximizing), followed by {@code null} elements
    102         * corresponding to the runs that did not converge. This means all
    103         * elements will be {@code null} if the {@code optimize} method did throw
    104         * an exception.
    105         * This also means that if the first element is not {@code null}, it is
    106         * the best point found across all starts.
    107         * <br/>
    108         * The behaviour is undefined if this method is called before
    109         * {@code optimize}; it will likely throw {@code NullPointerException}.
    110         *
    111         * @return an array containing the optima sorted from best to worst.
    112         */
    113        public abstract PAIR[] getOptima();
    114
    115        /**
    116         * {@inheritDoc}
    117         *
    118         * @throws MathIllegalStateException if {@code optData} does not contain an
    119         * instance of {@link MaxEval} or {@link InitialGuess}.
    120         */
    121        @Override
    122        public PAIR optimize(OptimizationData... optData) {
    123            // Store arguments in order to pass them to the internal optimizer.
    124           optimData = optData;
    125            // Set up base class and perform computations.
    126            return super.optimize(optData);
    127        }
    128
    129        /** {@inheritDoc} */
    130        @Override
    131        protected PAIR doOptimize() {
    132            // Remove all instances of "MaxEval" and "InitialGuess" from the
    133            // array that will be passed to the internal optimizer.
    134            // The former is to enforce smaller numbers of allowed evaluations
    135            // (according to how many have been used up already), and the latter
    136            // to impose a different start value for each start.
    137            for (int i = 0; i < optimData.length; i++) {
    138                if (optimData[i] instanceof MaxEval) {
    139                    optimData[i] = null;
    140                    maxEvalIndex = i;
    141                }
    142                if (optimData[i] instanceof InitialGuess) {
    143                    optimData[i] = null;
    144                    initialGuessIndex = i;
    145                    continue;
    146                }
    147            }
    148            if (maxEvalIndex == -1) {
    149                throw new MathIllegalStateException();
    150            }
    151            if (initialGuessIndex == -1) {
    152                throw new MathIllegalStateException();
    153            }
    154
    155            RuntimeException lastException = null;
    156            totalEvaluations = 0;
    157            clear();
    158
    159            final int maxEval = getMaxEvaluations();
    160            final double[] min = getLowerBound(); // XXX Should be used to enforce bounds (see below).
    161            final double[] max = getUpperBound(); // XXX Should be used to enforce bounds (see below).
    162            final double[] startPoint = getStartPoint();
    163
    164            // Multi-start loop.
    165            for (int i = 0; i < starts; i++) {
    166                // CHECKSTYLE: stop IllegalCatch
    167                try {
    168                    // Decrease number of allowed evaluations.
    169                    optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
    170                    // New start value.
    171                    final double[] s = (i == 0) ?
    172                        startPoint :
    173                        generator.nextVector(); // XXX This does not enforce bounds!
    174                    optimData[initialGuessIndex] = new InitialGuess(s);
    175                    // Optimize.
    176                    final PAIR result = optimizer.optimize(optimData);
    177                    store(result);
    178                } catch (RuntimeException mue) {
    179                    lastException = mue;
    180                }
    181                // CHECKSTYLE: resume IllegalCatch
    182
    183                totalEvaluations += optimizer.getEvaluations();
    184            }
    185
    186            final PAIR[] optima = getOptima();
    187            if (optima.length == 0) {
    188                // All runs failed.
    189                throw lastException; // Cannot be null if starts >= 1.
    190            }
    191
    192            // Return the best optimum.
    193            return optima[0];
    194        }
    195
    196        /**
    197         * Method that will be called in order to store each found optimum.
    198         *
    199         * @param optimum Result of an optimization run.
    200         */
    201        protected abstract void store(PAIR optimum);
    202        /**
    203         * Method that will called in order to clear all stored optima.
    204         */
    205        protected abstract void clear();
    206    }