UnivariateMultiStartOptimizer.java

  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. package org.apache.commons.math3.optimization.univariate;

  18. import java.util.Arrays;
  19. import java.util.Comparator;

  20. import org.apache.commons.math3.analysis.UnivariateFunction;
  21. import org.apache.commons.math3.exception.MathIllegalStateException;
  22. import org.apache.commons.math3.exception.NotStrictlyPositiveException;
  23. import org.apache.commons.math3.exception.NullArgumentException;
  24. import org.apache.commons.math3.exception.util.LocalizedFormats;
  25. import org.apache.commons.math3.random.RandomGenerator;
  26. import org.apache.commons.math3.optimization.GoalType;
  27. import org.apache.commons.math3.optimization.ConvergenceChecker;

  28. /**
  29.  * Special implementation of the {@link UnivariateOptimizer} interface
  30.  * adding multi-start features to an existing optimizer.
  31.  *
  32.  * This class wraps a classical optimizer to use it several times in
  33.  * turn with different starting points in order to avoid being trapped
  34.  * into a local extremum when looking for a global one.
  35.  *
  36.  * @param <FUNC> Type of the objective function to be optimized.
  37.  *
  38.  * @deprecated As of 3.1 (to be removed in 4.0).
  39.  * @since 3.0
  40.  */
  41. @Deprecated
  42. public class UnivariateMultiStartOptimizer<FUNC extends UnivariateFunction>
  43.     implements BaseUnivariateOptimizer<FUNC> {
  44.     /** Underlying classical optimizer. */
  45.     private final BaseUnivariateOptimizer<FUNC> optimizer;
  46.     /** Maximal number of evaluations allowed. */
  47.     private int maxEvaluations;
  48.     /** Number of evaluations already performed for all starts. */
  49.     private int totalEvaluations;
  50.     /** Number of starts to go. */
  51.     private int starts;
  52.     /** Random generator for multi-start. */
  53.     private RandomGenerator generator;
  54.     /** Found optima. */
  55.     private UnivariatePointValuePair[] optima;

  56.     /**
  57.      * Create a multi-start optimizer from a single-start optimizer.
  58.      *
  59.      * @param optimizer Single-start optimizer to wrap.
  60.      * @param starts Number of starts to perform. If {@code starts == 1},
  61.      * the {@code optimize} methods will return the same solution as
  62.      * {@code optimizer} would.
  63.      * @param generator Random generator to use for restarts.
  64.      * @throws NullArgumentException if {@code optimizer} or {@code generator}
  65.      * is {@code null}.
  66.      * @throws NotStrictlyPositiveException if {@code starts < 1}.
  67.      */
  68.     public UnivariateMultiStartOptimizer(final BaseUnivariateOptimizer<FUNC> optimizer,
  69.                                              final int starts,
  70.                                              final RandomGenerator generator) {
  71.         if (optimizer == null ||
  72.                 generator == null) {
  73.                 throw new NullArgumentException();
  74.         }
  75.         if (starts < 1) {
  76.             throw new NotStrictlyPositiveException(starts);
  77.         }

  78.         this.optimizer = optimizer;
  79.         this.starts = starts;
  80.         this.generator = generator;
  81.     }

  82.     /**
  83.      * {@inheritDoc}
  84.      */
  85.     public ConvergenceChecker<UnivariatePointValuePair> getConvergenceChecker() {
  86.         return optimizer.getConvergenceChecker();
  87.     }

  88.     /** {@inheritDoc} */
  89.     public int getMaxEvaluations() {
  90.         return maxEvaluations;
  91.     }

  92.     /** {@inheritDoc} */
  93.     public int getEvaluations() {
  94.         return totalEvaluations;
  95.     }

  96.     /**
  97.      * Get all the optima found during the last call to {@link
  98.      * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}.
  99.      * The optimizer stores all the optima found during a set of
  100.      * restarts. The {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
  101.      * method returns the best point only. This method returns all the points
  102.      * found at the end of each starts, including the best one already
  103.      * returned by the {@link #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
  104.      * method.
  105.      * <br/>
  106.      * The returned array as one element for each start as specified
  107.      * in the constructor. It is ordered with the results from the
  108.      * runs that did converge first, sorted from best to worst
  109.      * objective value (i.e in ascending order if minimizing and in
  110.      * descending order if maximizing), followed by {@code null} elements
  111.      * corresponding to the runs that did not converge. This means all
  112.      * elements will be {@code null} if the {@link
  113.      * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
  114.      * method did throw an exception.
  115.      * This also means that if the first element is not {@code null}, it is
  116.      * the best point found across all starts.
  117.      *
  118.      * @return an array containing the optima.
  119.      * @throws MathIllegalStateException if {@link
  120.      * #optimize(int,UnivariateFunction,GoalType,double,double) optimize}
  121.      * has not been called.
  122.      */
  123.     public UnivariatePointValuePair[] getOptima() {
  124.         if (optima == null) {
  125.             throw new MathIllegalStateException(LocalizedFormats.NO_OPTIMUM_COMPUTED_YET);
  126.         }
  127.         return optima.clone();
  128.     }

  129.     /** {@inheritDoc} */
  130.     public UnivariatePointValuePair optimize(int maxEval, final FUNC f,
  131.                                                  final GoalType goal,
  132.                                                  final double min, final double max) {
  133.         return optimize(maxEval, f, goal, min, max, min + 0.5 * (max - min));
  134.     }

  135.     /** {@inheritDoc} */
  136.     public UnivariatePointValuePair optimize(int maxEval, final FUNC f,
  137.                                                  final GoalType goal,
  138.                                                  final double min, final double max,
  139.                                                  final double startValue) {
  140.         RuntimeException lastException = null;
  141.         optima = new UnivariatePointValuePair[starts];
  142.         totalEvaluations = 0;

  143.         // Multi-start loop.
  144.         for (int i = 0; i < starts; ++i) {
  145.             // CHECKSTYLE: stop IllegalCatch
  146.             try {
  147.                 final double s = (i == 0) ? startValue : min + generator.nextDouble() * (max - min);
  148.                 optima[i] = optimizer.optimize(maxEval - totalEvaluations, f, goal, min, max, s);
  149.             } catch (RuntimeException mue) {
  150.                 lastException = mue;
  151.                 optima[i] = null;
  152.             }
  153.             // CHECKSTYLE: resume IllegalCatch

  154.             totalEvaluations += optimizer.getEvaluations();
  155.         }

  156.         sortPairs(goal);

  157.         if (optima[0] == null) {
  158.             throw lastException; // cannot be null if starts >=1
  159.         }

  160.         // Return the point with the best objective function value.
  161.         return optima[0];
  162.     }

  163.     /**
  164.      * Sort the optima from best to worst, followed by {@code null} elements.
  165.      *
  166.      * @param goal Goal type.
  167.      */
  168.     private void sortPairs(final GoalType goal) {
  169.         Arrays.sort(optima, new Comparator<UnivariatePointValuePair>() {
  170.                 public int compare(final UnivariatePointValuePair o1,
  171.                                    final UnivariatePointValuePair o2) {
  172.                     if (o1 == null) {
  173.                         return (o2 == null) ? 0 : 1;
  174.                     } else if (o2 == null) {
  175.                         return -1;
  176.                     }
  177.                     final double v1 = o1.getValue();
  178.                     final double v2 = o2.getValue();
  179.                     return (goal == GoalType.MINIMIZE) ?
  180.                         Double.compare(v1, v2) : Double.compare(v2, v1);
  181.                 }
  182.             });
  183.     }
  184. }