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.optim.univariate;
019    
020    import java.util.Arrays;
021    import java.util.Comparator;
022    import org.apache.commons.math3.exception.MathIllegalStateException;
023    import org.apache.commons.math3.exception.NotStrictlyPositiveException;
024    import org.apache.commons.math3.exception.util.LocalizedFormats;
025    import org.apache.commons.math3.random.RandomGenerator;
026    import org.apache.commons.math3.optim.MaxEval;
027    import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
028    import org.apache.commons.math3.optim.OptimizationData;
029    
030    /**
031     * Special implementation of the {@link UnivariateOptimizer} interface
032     * adding multi-start features to an existing optimizer.
033     * <br/>
034     * This class wraps an optimizer in order to use it several times in
035     * turn with different starting points (trying to avoid being trapped
036     * in a local extremum when looking for a global one).
037     *
038     * @version $Id$
039     * @since 3.0
040     */
041    public class MultiStartUnivariateOptimizer
042        extends UnivariateOptimizer {
043        /** Underlying classical optimizer. */
044        private final UnivariateOptimizer optimizer;
045        /** Number of evaluations already performed for all starts. */
046        private int totalEvaluations;
047        /** Number of starts to go. */
048        private int starts;
049        /** Random generator for multi-start. */
050        private RandomGenerator generator;
051        /** Found optima. */
052        private UnivariatePointValuePair[] optima;
053        /** Optimization data. */
054        private OptimizationData[] optimData;
055        /**
056         * Location in {@link #optimData} where the updated maximum
057         * number of evaluations will be stored.
058         */
059        private int maxEvalIndex = -1;
060        /**
061         * Location in {@link #optimData} where the updated start value
062         * will be stored.
063         */
064        private int searchIntervalIndex = -1;
065    
066        /**
067         * Create a multi-start optimizer from a single-start optimizer.
068         *
069         * @param optimizer Single-start optimizer to wrap.
070         * @param starts Number of starts to perform. If {@code starts == 1},
071         * the {@code optimize} methods will return the same solution as
072         * {@code optimizer} would.
073         * @param generator Random generator to use for restarts.
074         * @throws NotStrictlyPositiveException if {@code starts < 1}.
075         */
076        public MultiStartUnivariateOptimizer(final UnivariateOptimizer optimizer,
077                                             final int starts,
078                                             final RandomGenerator generator) {
079            super(optimizer.getConvergenceChecker());
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        /** {@inheritDoc} */
091        @Override
092        public int getEvaluations() {
093            return totalEvaluations;
094        }
095    
096        /**
097         * Gets all the optima found during the last call to {@code optimize}.
098         * The optimizer stores all the optima found during a set of
099         * restarts. The {@code optimize} method returns the best point only.
100         * This method returns all the points found at the end of each starts,
101         * including the best one already returned by the {@code optimize} method.
102         * <br/>
103         * The returned array as one element for each start as specified
104         * in the constructor. It is ordered with the results from the
105         * runs that did converge first, sorted from best to worst
106         * objective value (i.e in ascending order if minimizing and in
107         * descending order if maximizing), followed by {@code null} elements
108         * corresponding to the runs that did not converge. This means all
109         * elements will be {@code null} if the {@code optimize} method did throw
110         * an exception.
111         * This also means that if the first element is not {@code null}, it is
112         * the best point found across all starts.
113         *
114         * @return an array containing the optima.
115         * @throws MathIllegalStateException if {@link #optimize(OptimizationData[])
116         * optimize} has not been called.
117         */
118        public UnivariatePointValuePair[] getOptima() {
119            if (optima == null) {
120                throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
121            }
122            return optima.clone();
123        }
124    
125        /**
126         * {@inheritDoc}
127         *
128         * @throws MathIllegalStateException if {@code optData} does not contain an
129         * instance of {@link MaxEval} or {@link SearchInterval}.
130         */
131        @Override
132        public UnivariatePointValuePair optimize(OptimizationData... optData) {
133            // Store arguments in order to pass them to the internal optimizer.
134           optimData = optData;
135            // Set up base class and perform computations.
136            return super.optimize(optData);
137        }
138    
139        /** {@inheritDoc} */
140        @Override
141        protected UnivariatePointValuePair doOptimize() {
142            // Remove all instances of "MaxEval" and "SearchInterval" from the
143            // array that will be passed to the internal optimizer.
144            // The former is to enforce smaller numbers of allowed evaluations
145            // (according to how many have been used up already), and the latter
146            // to impose a different start value for each start.
147            for (int i = 0; i < optimData.length; i++) {
148                if (optimData[i] instanceof MaxEval) {
149                    optimData[i] = null;
150                    maxEvalIndex = i;
151                    continue;
152                }
153                if (optimData[i] instanceof SearchInterval) {
154                    optimData[i] = null;
155                    searchIntervalIndex = i;
156                    continue;
157                }
158            }
159            if (maxEvalIndex == -1) {
160                throw new MathIllegalStateException();
161            }
162            if (searchIntervalIndex == -1) {
163                throw new MathIllegalStateException();
164            }
165    
166            RuntimeException lastException = null;
167            optima = new UnivariatePointValuePair[starts];
168            totalEvaluations = 0;
169    
170            final int maxEval = getMaxEvaluations();
171            final double min = getMin();
172            final double max = getMax();
173            final double startValue = getStartValue();
174    
175            // Multi-start loop.
176            for (int i = 0; i < starts; i++) {
177                // CHECKSTYLE: stop IllegalCatch
178                try {
179                    // Decrease number of allowed evaluations.
180                    optimData[maxEvalIndex] = new MaxEval(maxEval - totalEvaluations);
181                    // New start value.
182                    final double s = (i == 0) ?
183                        startValue :
184                        min + generator.nextDouble() * (max - min);
185                    optimData[searchIntervalIndex] = new SearchInterval(min, max, s);
186                    // Optimize.
187                    optima[i] = optimizer.optimize(optimData);
188                } catch (RuntimeException mue) {
189                    lastException = mue;
190                    optima[i] = null;
191                }
192                // CHECKSTYLE: resume IllegalCatch
193    
194                totalEvaluations += optimizer.getEvaluations();
195            }
196    
197            sortPairs(getGoalType());
198    
199            if (optima[0] == null) {
200                throw lastException; // Cannot be null if starts >= 1.
201            }
202    
203            // Return the point with the best objective function value.
204            return optima[0];
205        }
206    
207        /**
208         * Sort the optima from best to worst, followed by {@code null} elements.
209         *
210         * @param goal Goal type.
211         */
212        private void sortPairs(final GoalType goal) {
213            Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() {
214                    public int compare(final UnivariatePointValuePair o1,
215                                       final UnivariatePointValuePair o2) {
216                        if (o1 == null) {
217                            return (o2 == null) ? 0 : 1;
218                        } else if (o2 == null) {
219                            return -1;
220                        }
221                        final double v1 = o1.getValue();
222                        final double v2 = o2.getValue();
223                        return (goal == GoalType.MINIMIZE) ?
224                            Double.compare(v1, v2) : Double.compare(v2, v1);
225                    }
226                });
227        }
228    }