AbstractSimplex.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.direct;

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

  20. import org.apache.commons.math3.analysis.MultivariateFunction;
  21. import org.apache.commons.math3.exception.NotStrictlyPositiveException;
  22. import org.apache.commons.math3.exception.DimensionMismatchException;
  23. import org.apache.commons.math3.exception.ZeroException;
  24. import org.apache.commons.math3.exception.OutOfRangeException;
  25. import org.apache.commons.math3.exception.NullArgumentException;
  26. import org.apache.commons.math3.exception.MathIllegalArgumentException;
  27. import org.apache.commons.math3.exception.util.LocalizedFormats;
  28. import org.apache.commons.math3.optimization.PointValuePair;
  29. import org.apache.commons.math3.optimization.OptimizationData;

  30. /**
  31.  * This class implements the simplex concept.
  32.  * It is intended to be used in conjunction with {@link SimplexOptimizer}.
  33.  * <br/>
  34.  * The initial configuration of the simplex is set by the constructors
  35.  * {@link #AbstractSimplex(double[])} or {@link #AbstractSimplex(double[][])}.
  36.  * The other {@link #AbstractSimplex(int) constructor} will set all steps
  37.  * to 1, thus building a default configuration from a unit hypercube.
  38.  * <br/>
  39.  * Users <em>must</em> call the {@link #build(double[]) build} method in order
  40.  * to create the data structure that will be acted on by the other methods of
  41.  * this class.
  42.  *
  43.  * @see SimplexOptimizer
  44.  * @deprecated As of 3.1 (to be removed in 4.0).
  45.  * @since 3.0
  46.  */
  47. @Deprecated
  48. public abstract class AbstractSimplex implements OptimizationData {
  49.     /** Simplex. */
  50.     private PointValuePair[] simplex;
  51.     /** Start simplex configuration. */
  52.     private double[][] startConfiguration;
  53.     /** Simplex dimension (must be equal to {@code simplex.length - 1}). */
  54.     private final int dimension;

  55.     /**
  56.      * Build a unit hypercube simplex.
  57.      *
  58.      * @param n Dimension of the simplex.
  59.      */
  60.     protected AbstractSimplex(int n) {
  61.         this(n, 1d);
  62.     }

  63.     /**
  64.      * Build a hypercube simplex with the given side length.
  65.      *
  66.      * @param n Dimension of the simplex.
  67.      * @param sideLength Length of the sides of the hypercube.
  68.      */
  69.     protected AbstractSimplex(int n,
  70.                               double sideLength) {
  71.         this(createHypercubeSteps(n, sideLength));
  72.     }

  73.     /**
  74.      * The start configuration for simplex is built from a box parallel to
  75.      * the canonical axes of the space. The simplex is the subset of vertices
  76.      * of a box parallel to the canonical axes. It is built as the path followed
  77.      * while traveling from one vertex of the box to the diagonally opposite
  78.      * vertex moving only along the box edges. The first vertex of the box will
  79.      * be located at the start point of the optimization.
  80.      * As an example, in dimension 3 a simplex has 4 vertices. Setting the
  81.      * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
  82.      * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
  83.      * The first vertex would be set to the start point at (1, 1, 1) and the
  84.      * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
  85.      *
  86.      * @param steps Steps along the canonical axes representing box edges. They
  87.      * may be negative but not zero.
  88.      * @throws NullArgumentException if {@code steps} is {@code null}.
  89.      * @throws ZeroException if one of the steps is zero.
  90.      */
  91.     protected AbstractSimplex(final double[] steps) {
  92.         if (steps == null) {
  93.             throw new NullArgumentException();
  94.         }
  95.         if (steps.length == 0) {
  96.             throw new ZeroException();
  97.         }
  98.         dimension = steps.length;

  99.         // Only the relative position of the n final vertices with respect
  100.         // to the first one are stored.
  101.         startConfiguration = new double[dimension][dimension];
  102.         for (int i = 0; i < dimension; i++) {
  103.             final double[] vertexI = startConfiguration[i];
  104.             for (int j = 0; j < i + 1; j++) {
  105.                 if (steps[j] == 0) {
  106.                     throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX);
  107.                 }
  108.                 System.arraycopy(steps, 0, vertexI, 0, j + 1);
  109.             }
  110.         }
  111.     }

  112.     /**
  113.      * The real initial simplex will be set up by moving the reference
  114.      * simplex such that its first point is located at the start point of the
  115.      * optimization.
  116.      *
  117.      * @param referenceSimplex Reference simplex.
  118.      * @throws NotStrictlyPositiveException if the reference simplex does not
  119.      * contain at least one point.
  120.      * @throws DimensionMismatchException if there is a dimension mismatch
  121.      * in the reference simplex.
  122.      * @throws IllegalArgumentException if one of its vertices is duplicated.
  123.      */
  124.     protected AbstractSimplex(final double[][] referenceSimplex) {
  125.         if (referenceSimplex.length <= 0) {
  126.             throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT,
  127.                                                    referenceSimplex.length);
  128.         }
  129.         dimension = referenceSimplex.length - 1;

  130.         // Only the relative position of the n final vertices with respect
  131.         // to the first one are stored.
  132.         startConfiguration = new double[dimension][dimension];
  133.         final double[] ref0 = referenceSimplex[0];

  134.         // Loop over vertices.
  135.         for (int i = 0; i < referenceSimplex.length; i++) {
  136.             final double[] refI = referenceSimplex[i];

  137.             // Safety checks.
  138.             if (refI.length != dimension) {
  139.                 throw new DimensionMismatchException(refI.length, dimension);
  140.             }
  141.             for (int j = 0; j < i; j++) {
  142.                 final double[] refJ = referenceSimplex[j];
  143.                 boolean allEquals = true;
  144.                 for (int k = 0; k < dimension; k++) {
  145.                     if (refI[k] != refJ[k]) {
  146.                         allEquals = false;
  147.                         break;
  148.                     }
  149.                 }
  150.                 if (allEquals) {
  151.                     throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX,
  152.                                                            i, j);
  153.                 }
  154.             }

  155.             // Store vertex i position relative to vertex 0 position.
  156.             if (i > 0) {
  157.                 final double[] confI = startConfiguration[i - 1];
  158.                 for (int k = 0; k < dimension; k++) {
  159.                     confI[k] = refI[k] - ref0[k];
  160.                 }
  161.             }
  162.         }
  163.     }

  164.     /**
  165.      * Get simplex dimension.
  166.      *
  167.      * @return the dimension of the simplex.
  168.      */
  169.     public int getDimension() {
  170.         return dimension;
  171.     }

  172.     /**
  173.      * Get simplex size.
  174.      * After calling the {@link #build(double[]) build} method, this method will
  175.      * will be equivalent to {@code getDimension() + 1}.
  176.      *
  177.      * @return the size of the simplex.
  178.      */
  179.     public int getSize() {
  180.         return simplex.length;
  181.     }

  182.     /**
  183.      * Compute the next simplex of the algorithm.
  184.      *
  185.      * @param evaluationFunction Evaluation function.
  186.      * @param comparator Comparator to use to sort simplex vertices from best
  187.      * to worst.
  188.      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
  189.      * if the algorithm fails to converge.
  190.      */
  191.     public abstract void iterate(final MultivariateFunction evaluationFunction,
  192.                                  final Comparator<PointValuePair> comparator);

  193.     /**
  194.      * Build an initial simplex.
  195.      *
  196.      * @param startPoint First point of the simplex.
  197.      * @throws DimensionMismatchException if the start point does not match
  198.      * simplex dimension.
  199.      */
  200.     public void build(final double[] startPoint) {
  201.         if (dimension != startPoint.length) {
  202.             throw new DimensionMismatchException(dimension, startPoint.length);
  203.         }

  204.         // Set first vertex.
  205.         simplex = new PointValuePair[dimension + 1];
  206.         simplex[0] = new PointValuePair(startPoint, Double.NaN);

  207.         // Set remaining vertices.
  208.         for (int i = 0; i < dimension; i++) {
  209.             final double[] confI = startConfiguration[i];
  210.             final double[] vertexI = new double[dimension];
  211.             for (int k = 0; k < dimension; k++) {
  212.                 vertexI[k] = startPoint[k] + confI[k];
  213.             }
  214.             simplex[i + 1] = new PointValuePair(vertexI, Double.NaN);
  215.         }
  216.     }

  217.     /**
  218.      * Evaluate all the non-evaluated points of the simplex.
  219.      *
  220.      * @param evaluationFunction Evaluation function.
  221.      * @param comparator Comparator to use to sort simplex vertices from best to worst.
  222.      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
  223.      * if the maximal number of evaluations is exceeded.
  224.      */
  225.     public void evaluate(final MultivariateFunction evaluationFunction,
  226.                          final Comparator<PointValuePair> comparator) {
  227.         // Evaluate the objective function at all non-evaluated simplex points.
  228.         for (int i = 0; i < simplex.length; i++) {
  229.             final PointValuePair vertex = simplex[i];
  230.             final double[] point = vertex.getPointRef();
  231.             if (Double.isNaN(vertex.getValue())) {
  232.                 simplex[i] = new PointValuePair(point, evaluationFunction.value(point), false);
  233.             }
  234.         }

  235.         // Sort the simplex from best to worst.
  236.         Arrays.sort(simplex, comparator);
  237.     }

  238.     /**
  239.      * Replace the worst point of the simplex by a new point.
  240.      *
  241.      * @param pointValuePair Point to insert.
  242.      * @param comparator Comparator to use for sorting the simplex vertices
  243.      * from best to worst.
  244.      */
  245.     protected void replaceWorstPoint(PointValuePair pointValuePair,
  246.                                      final Comparator<PointValuePair> comparator) {
  247.         for (int i = 0; i < dimension; i++) {
  248.             if (comparator.compare(simplex[i], pointValuePair) > 0) {
  249.                 PointValuePair tmp = simplex[i];
  250.                 simplex[i] = pointValuePair;
  251.                 pointValuePair = tmp;
  252.             }
  253.         }
  254.         simplex[dimension] = pointValuePair;
  255.     }

  256.     /**
  257.      * Get the points of the simplex.
  258.      *
  259.      * @return all the simplex points.
  260.      */
  261.     public PointValuePair[] getPoints() {
  262.         final PointValuePair[] copy = new PointValuePair[simplex.length];
  263.         System.arraycopy(simplex, 0, copy, 0, simplex.length);
  264.         return copy;
  265.     }

  266.     /**
  267.      * Get the simplex point stored at the requested {@code index}.
  268.      *
  269.      * @param index Location.
  270.      * @return the point at location {@code index}.
  271.      */
  272.     public PointValuePair getPoint(int index) {
  273.         if (index < 0 ||
  274.             index >= simplex.length) {
  275.             throw new OutOfRangeException(index, 0, simplex.length - 1);
  276.         }
  277.         return simplex[index];
  278.     }

  279.     /**
  280.      * Store a new point at location {@code index}.
  281.      * Note that no deep-copy of {@code point} is performed.
  282.      *
  283.      * @param index Location.
  284.      * @param point New value.
  285.      */
  286.     protected void setPoint(int index, PointValuePair point) {
  287.         if (index < 0 ||
  288.             index >= simplex.length) {
  289.             throw new OutOfRangeException(index, 0, simplex.length - 1);
  290.         }
  291.         simplex[index] = point;
  292.     }

  293.     /**
  294.      * Replace all points.
  295.      * Note that no deep-copy of {@code points} is performed.
  296.      *
  297.      * @param points New Points.
  298.      */
  299.     protected void setPoints(PointValuePair[] points) {
  300.         if (points.length != simplex.length) {
  301.             throw new DimensionMismatchException(points.length, simplex.length);
  302.         }
  303.         simplex = points;
  304.     }

  305.     /**
  306.      * Create steps for a unit hypercube.
  307.      *
  308.      * @param n Dimension of the hypercube.
  309.      * @param sideLength Length of the sides of the hypercube.
  310.      * @return the steps.
  311.      */
  312.     private static double[] createHypercubeSteps(int n,
  313.                                                  double sideLength) {
  314.         final double[] steps = new double[n];
  315.         for (int i = 0; i < n; i++) {
  316.             steps[i] = sideLength;
  317.         }
  318.         return steps;
  319.     }
  320. }