| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package org.apache.commons.math4.legacy.optim.nonlinear.scalar.noderiv; |
| |
| import java.util.List; |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Comparator; |
| import java.util.Collections; |
| import java.util.function.UnaryOperator; |
| import java.util.function.DoublePredicate; |
| |
| import org.apache.commons.math4.legacy.analysis.MultivariateFunction; |
| import org.apache.commons.math4.legacy.exception.DimensionMismatchException; |
| import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException; |
| import org.apache.commons.math4.legacy.exception.NotStrictlyPositiveException; |
| import org.apache.commons.math4.legacy.exception.ZeroException; |
| import org.apache.commons.math4.legacy.exception.util.LocalizedFormats; |
| import org.apache.commons.math4.legacy.optim.OptimizationData; |
| import org.apache.commons.math4.legacy.optim.PointValuePair; |
| |
| /** |
| * Represents a <a href="https://en.wikipedia.org/wiki/Simplex">simplex</a>. |
| * |
| * @see SimplexOptimizer |
| */ |
| public final class Simplex implements OptimizationData { |
| /** Coordinates. */ |
| private final List<PointValuePair> points; |
| |
| /** |
| * Builds from a given set of coordinates. |
| * |
| * @param referenceSimplex Reference simplex. |
| * @throws NotStrictlyPositiveException if the reference simplex does not |
| * contain at least one point. |
| * @throws DimensionMismatchException if there is a dimension mismatch |
| * in the reference simplex. |
| * @throws IllegalArgumentException if one of its vertices is duplicated. |
| */ |
| private Simplex(double[][] referenceSimplex) { |
| if (referenceSimplex.length <= 0) { |
| throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT, |
| referenceSimplex.length); |
| } |
| final int len = referenceSimplex.length; |
| points = new ArrayList<>(len); |
| |
| final int dim = len - 1; |
| |
| // Loop over vertices. |
| for (int i = 0; i < len; i++) { |
| final double[] refI = referenceSimplex[i]; |
| |
| // Safety checks. |
| if (refI.length != dim) { |
| throw new DimensionMismatchException(refI.length, dim); |
| } |
| for (int j = 1; j < i; j++) { |
| final double[] refJ = referenceSimplex[j]; |
| boolean allEquals = true; |
| for (int k = 0; k < dim; k++) { |
| if (refI[k] != refJ[k]) { |
| allEquals = false; |
| break; |
| } |
| } |
| if (allEquals) { |
| throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX, |
| i, j); |
| } |
| } |
| |
| points.add(new PointValuePair(refI, Double.NaN)); |
| } |
| } |
| |
| /** |
| * Builds from an existing simplex. |
| * |
| * @param points Simplex data. Reference will be stored in the newly |
| * constructed instance. |
| */ |
| private Simplex(List<PointValuePair> points) { |
| this.points = points; |
| } |
| |
| /** |
| * Builds from a given set of coordinates. |
| * |
| * @param simplex Simplex coordinates. |
| * @return a new instance. |
| * @throws NotStrictlyPositiveException if the reference simplex does not |
| * contain at least one point. |
| * @throws DimensionMismatchException if there is a dimension mismatch |
| * in the reference simplex. |
| * @throws IllegalArgumentException if one of its vertices is duplicated. |
| */ |
| public static Simplex of(double[][] simplex) { |
| return new Simplex(simplex); |
| } |
| |
| /** |
| * Builds simplex with the given side length. |
| * |
| * @param dim Space dimensions. |
| * @param sideLength Length of the sides of the hypercube. |
| * @return a new instance. |
| */ |
| public static Simplex equalSidesAlongAxes(int dim, |
| double sideLength) { |
| final double[] steps = new double[dim]; |
| Arrays.fill(steps, sideLength); |
| return alongAxes(steps); |
| } |
| |
| /** |
| * The start configuration for simplex is built from a box parallel to |
| * the canonical axes of the space. The simplex is the subset of vertices |
| * of a box parallel to the canonical axes. It is built as the path followed |
| * while traveling from one vertex of the box to the diagonally opposite |
| * vertex moving only along the box edges. The first vertex of the box will |
| * be located at the origin of the coordinate system. |
| * |
| * To be used for simplex-based optimization, the simplex must be |
| * {@link #translate(double[]) translated} so that its first vertex will be |
| * the {@link org.apache.commons.math4.legacy.optim.InitialGuess initial guess}. |
| * |
| * For example, in dimension 3 a simplex has 4 vertices. Setting the |
| * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the |
| * initial simplex would be: |
| * <ol> |
| * <li>(1, 1, 1),</li> |
| * <li>(2, 1, 1),</li> |
| * <li>(2, 11, 1),</li> |
| * <li>(2, 11, 3).</li> |
| * </ol> |
| * |
| * @param steps Steps along the canonical axes representing box edges. |
| * They may be negative but not zero. |
| * @throws ZeroException if one of the steps is zero. |
| * @return a new instance. |
| */ |
| public static Simplex alongAxes(double[] steps) { |
| if (steps.length == 0) { |
| throw new ZeroException(); |
| } |
| final int dim = steps.length; |
| final int len = dim + 1; |
| |
| // Only the relative position of the n final vertices with respect |
| // to the first one are stored. |
| final double[][] simplex = new double[len][dim]; |
| for (int i = 1; i < len; i++) { // First point is the origin (zero). |
| final double[] vertexI = simplex[i]; |
| for (int j = 0; j < i; j++) { |
| if (steps[j] == 0) { |
| throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX); |
| } |
| System.arraycopy(steps, 0, vertexI, 0, j + 1); |
| } |
| } |
| |
| return new Simplex(simplex); |
| } |
| |
| /** |
| * Returns the space dimension. |
| * |
| * @return the dimension of the simplex. |
| */ |
| public int getDimension() { |
| return points.size() - 1; |
| } |
| |
| /** |
| * Returns the number of vertices. |
| * |
| * @return the size of the simplex. |
| */ |
| public int getSize() { |
| return points.size(); |
| } |
| |
| /** |
| * Evaluates the (non-evaluated) simplex points and returns a new instance |
| * with vertices sorted from best to worst. |
| * |
| * @param function Evaluation function. |
| * @param comparator Comparator for sorting vertices, from best to worst. |
| * @return a new instance in which the vertices are sorted according to |
| * the given {@code comparator}. |
| */ |
| public Simplex evaluate(MultivariateFunction function, |
| Comparator<PointValuePair> comparator) { |
| final List<PointValuePair> newPoints = new ArrayList<>(points.size()); |
| for (PointValuePair pv : points) { |
| final double[] coord = pv.getPoint(); |
| final double value = Double.isNaN(pv.getValue()) ? |
| function.value(coord) : |
| pv.getValue(); |
| |
| newPoints.add(new PointValuePair(coord, value, false)); |
| } |
| |
| Collections.sort(newPoints, comparator); |
| return new Simplex(newPoints); |
| } |
| |
| /** |
| * Retrieves a copy of the simplex point stored at {@code index}. |
| * |
| * @param index Location. |
| * @return the point at location {@code index}. |
| */ |
| public PointValuePair get(int index) { |
| final PointValuePair p = points.get(index); |
| return new PointValuePair(p.getPoint(), p.getValue()); |
| } |
| |
| /** |
| * Creates a (deep) copy of the simplex points. |
| * |
| * @return the points. |
| */ |
| public List<PointValuePair> asList() { |
| return asList(0, points.size()); |
| } |
| |
| /** |
| * Generator of simplex transform. |
| * |
| * @see MultiDirectionalTransform |
| * @see NelderMeadTransform |
| * @see HedarFukushimaTransform |
| */ |
| public interface TransformFactory extends OptimizationData { |
| /** |
| * Creates a simplex transformation. |
| * |
| * @param evaluationFunction Evaluation function. |
| * @param comparator Vertex fitness comparator. |
| * @param saAcceptance Simulated annealing acceptance test. |
| * @return the simplex transform operator. |
| */ |
| UnaryOperator<Simplex> create(MultivariateFunction evaluationFunction, |
| Comparator<PointValuePair> comparator, |
| DoublePredicate saAcceptance); |
| } |
| |
| /** |
| * Creates a (deep) copy of the simplex points within slots |
| * {@code from} (included) and {@code to} (excluded). |
| * |
| * @param from Index of the first point to retrieve. |
| * @param to One past the index of the last point to retrieve. |
| * @return the points. |
| * @throws IllegalArgumentException if {@code from} and {@code to} are |
| * not within the {@code [0, n + 1]} interval (where {@code n} is the |
| * space dimension) or {@code from > to}. |
| */ |
| /* package private */ List<PointValuePair> asList(int from, |
| int to) { |
| if (from < 0 || |
| to > points.size() || |
| from > to) { |
| throw new IllegalArgumentException("Index"); |
| } |
| |
| final int len = to - from; |
| final List<PointValuePair> copy = new ArrayList<>(len); |
| for (int i = from; i < to; i++) { |
| copy.add(get(i)); |
| } |
| |
| return copy; |
| } |
| |
| /** |
| * Utility for evaluating a point with coordinates \( a_i + s (b_i - a_i) \). |
| * |
| * @param a Cartesian coordinates. |
| * @param s Scaling factor. |
| * @param b Cartesian coordinates. |
| * @param function Evaluation function. |
| * @return a new point. |
| */ |
| /* package private */ static PointValuePair newPoint(double[] a, |
| double s, |
| double[] b, |
| MultivariateFunction function) { |
| final int dim = a.length; |
| final double[] r = new double[dim]; |
| for (int i = 0; i < dim; i++) { |
| final double m = a[i]; |
| r[i] = m + s * (b[i] - m); |
| } |
| |
| return new PointValuePair(r, function.value(r), false); |
| } |
| |
| /** |
| * Utility for the "shrinking" a simplex: All the points will be |
| * transformed except the one at index 0. |
| * |
| * @param sigma Shrink factor. |
| * @param function Evaluation function. |
| * @return a new instance. |
| */ |
| /* package private */ Simplex shrink(double sigma, |
| MultivariateFunction function) { |
| final int replSize = getSize() - 1; |
| final List<PointValuePair> replacement = new ArrayList<>(); |
| final double[] bestPoint = get(0).getPoint(); |
| for (int i = 0; i < replSize; i++) { |
| replacement.add(Simplex.newPoint(bestPoint, |
| sigma, |
| get(i + 1).getPoint(), |
| function)); |
| } |
| |
| return replaceLast(replacement); |
| } |
| |
| /** |
| * Translates the simplex such that the first point's new coordinates |
| * will be at the given {@code point}. |
| * |
| * @param point Coordinates of the new simplex's first point. |
| * @return the translated points. |
| * @throws DimensionMismatchException if the dimensions do not match. |
| */ |
| /* package private */ Simplex translate(double[] point) { |
| final int dim = point.length; |
| if (getDimension() != dim) { |
| throw new DimensionMismatchException(getDimension(), dim); |
| } |
| final int len = points.size(); |
| final double[][] coordinates = new double[len][dim]; |
| final double[] current0 = points.get(0).getPoint(); // Current first point. |
| |
| // Set new vertices. |
| for (int i = 0; i < len; i++) { |
| final double[] currentI = points.get(i).getPoint(); |
| |
| final double[] newI = coordinates[i]; |
| for (int k = 0; k < dim; k++) { |
| newI[k] = point[k] + currentI[k] - current0[k]; |
| } |
| } |
| |
| return new Simplex(coordinates); |
| } |
| |
| /** |
| * Creates a new simplex where the given {@code point} replaces the one at the |
| * last position. |
| * Caveat: No check is done that the resulting set of points forms is a simplex. |
| * |
| * @param point Point. |
| * @return a new instance. |
| */ |
| /* package private */ Simplex replaceLast(PointValuePair point) { |
| final List<PointValuePair> newPoints = asList(0, getDimension()); // Deep copy. |
| newPoints.add(new PointValuePair(point.getPoint(), // Deep copy. |
| point.getValue(), |
| false)); |
| |
| return new Simplex(newPoints); |
| } |
| |
| /** |
| * Replace the last points of the simplex with the points from the given |
| * {@code replacement} list. |
| * Caveat: No check is done that the resulting set of points is a simplex. |
| * |
| * @param replacement List of points that will replace the last points of |
| * the {@code simplex}. |
| * @return a new instance. |
| */ |
| /* package private */ Simplex replaceLast(List<PointValuePair> replacement) { |
| final int nPoints = replacement.size(); |
| final int from = points.size() - nPoints; |
| final List<PointValuePair> newPoints = asList(0, from); // Deep copy. |
| |
| |
| for (int i = 0; i < nPoints; i++) { |
| final PointValuePair p = replacement.get(i); |
| newPoints.add(new PointValuePair(p.getPoint(), // Deep copy. |
| p.getValue(), |
| false)); |
| } |
| |
| return new Simplex(newPoints); |
| } |
| |
| /** |
| * @param list List of simplex points. |
| * @return the centroid of the points in the given {@code list}. |
| */ |
| /* package private */ static double[] centroid(List<PointValuePair> list) { |
| final double[] centroid = list.get(0).getPoint(); |
| |
| final int nPoints = list.size(); |
| final int dim = centroid.length; |
| for (int i = 1; i < nPoints; i++) { |
| final double[] p = list.get(i).getPoint(); |
| for (int k = 0; k < dim; k++) { |
| centroid[k] += p[k]; |
| } |
| } |
| |
| for (int k = 0; k < dim; k++) { |
| centroid[k] /= nPoints; |
| } |
| |
| return centroid; |
| } |
| } |