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.ConvergenceException;
024    import org.apache.commons.math.FunctionEvaluationException;
025    import org.apache.commons.math.MathRuntimeException;
026    import org.apache.commons.math.analysis.MultivariateRealFunction;
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: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
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         * ConvergenceException ConvergenceException}). This also means that
108         * if the first element is non null, it is the best point found across
109         * 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("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 {
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                        "none of the {0} start points lead to convergence",
208                        starts);
209            }
210    
211            // return the found point given the best objective function value
212            return optima[0];
213    
214        }
215    
216    }