Home | History | Annotate | Download | only in optimization 
      1 /*
      2  * Licensed to the Apache Software Foundation (ASF) under one or more
      3  * contributor license agreements.  See the NOTICE file distributed with
      4  * this work for additional information regarding copyright ownership.
      5  * The ASF licenses this file to You under the Apache License, Version 2.0
      6  * (the "License"); you may not use this file except in compliance with
      7  * the License.  You may obtain a copy of the License at
      8  *
      9  *      http://www.apache.org/licenses/LICENSE-2.0
     10  *
     11  * Unless required by applicable law or agreed to in writing, software
     12  * distributed under the License is distributed on an "AS IS" BASIS,
     13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14  * See the License for the specific language governing permissions and
     15  * limitations under the License.
     16  */
     17 
     18 package org.apache.commons.math.optimization;
     19 
     20 import java.util.Arrays;
     21 import java.util.Comparator;
     22 
     23 import org.apache.commons.math.FunctionEvaluationException;
     24 import org.apache.commons.math.MathRuntimeException;
     25 import org.apache.commons.math.analysis.DifferentiableMultivariateRealFunction;
     26 import org.apache.commons.math.exception.util.LocalizedFormats;
     27 import org.apache.commons.math.random.RandomVectorGenerator;
     28 
     29 /**
     30  * Special implementation of the {@link DifferentiableMultivariateRealOptimizer} interface adding
     31  * multi-start features to an existing optimizer.
     32  * <p>
     33  * This class wraps a classical optimizer to use it several times in
     34  * turn with different starting points in order to avoid being trapped
     35  * into a local extremum when looking for a global one.
     36  * </p>
     37  * @version $Revision: 1073158 $ $Date: 2011-02-21 22:46:52 +0100 (lun. 21 fvr. 2011) $
     38  * @since 2.0
     39  */
     40 public class MultiStartDifferentiableMultivariateRealOptimizer
     41     implements DifferentiableMultivariateRealOptimizer {
     42 
     43     /** Underlying classical optimizer. */
     44     private final DifferentiableMultivariateRealOptimizer optimizer;
     45 
     46     /** Maximal number of iterations allowed. */
     47     private int maxIterations;
     48 
     49     /** Number of iterations already performed for all starts. */
     50     private int totalIterations;
     51 
     52     /** Maximal number of evaluations allowed. */
     53     private int maxEvaluations;
     54 
     55     /** Number of evaluations already performed for all starts. */
     56     private int totalEvaluations;
     57 
     58     /** Number of gradient evaluations already performed for all starts. */
     59     private int totalGradientEvaluations;
     60 
     61     /** Number of starts to go. */
     62     private int starts;
     63 
     64     /** Random generator for multi-start. */
     65     private RandomVectorGenerator generator;
     66 
     67     /** Found optima. */
     68     private RealPointValuePair[] optima;
     69 
     70     /**
     71      * Create a multi-start optimizer from a single-start optimizer
     72      * @param optimizer single-start optimizer to wrap
     73      * @param starts number of starts to perform (including the
     74      * first one), multi-start is disabled if value is less than or
     75      * equal to 1
     76      * @param generator random vector generator to use for restarts
     77      */
     78     public MultiStartDifferentiableMultivariateRealOptimizer(final DifferentiableMultivariateRealOptimizer optimizer,
     79                                                              final int starts,
     80                                                              final RandomVectorGenerator generator) {
     81         this.optimizer                = optimizer;
     82         this.totalIterations          = 0;
     83         this.totalEvaluations         = 0;
     84         this.totalGradientEvaluations = 0;
     85         this.starts                   = starts;
     86         this.generator                = generator;
     87         this.optima                   = null;
     88         setMaxIterations(Integer.MAX_VALUE);
     89         setMaxEvaluations(Integer.MAX_VALUE);
     90     }
     91 
     92     /** Get all the optima found during the last call to {@link
     93      * #optimize(DifferentiableMultivariateRealFunction, GoalType, double[])
     94      * optimize}.
     95      * <p>The optimizer stores all the optima found during a set of
     96      * restarts. The {@link #optimize(DifferentiableMultivariateRealFunction,
     97      * GoalType, double[]) optimize} method returns the best point only. This
     98      * method returns all the points found at the end of each starts,
     99      * 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 }
    229