    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.math3.optimization.direct;
    019
    020    import java.util.Arrays;
    021    import java.util.Comparator;
    022
    023    import org.apache.commons.math3.analysis.MultivariateFunction;
    024    import org.apache.commons.math3.exception.NotStrictlyPositiveException;
    025    import org.apache.commons.math3.exception.DimensionMismatchException;
    026    import org.apache.commons.math3.exception.ZeroException;
    027    import org.apache.commons.math3.exception.OutOfRangeException;
    028    import org.apache.commons.math3.exception.NullArgumentException;
    029    import org.apache.commons.math3.exception.MathIllegalArgumentException;
    030    import org.apache.commons.math3.exception.util.LocalizedFormats;
    031    import org.apache.commons.math3.optimization.PointValuePair;
    032    import org.apache.commons.math3.optimization.OptimizationData;
    033
    034    /**
    035     * This class implements the simplex concept.
    036     * It is intended to be used in conjunction with {@link SimplexOptimizer}.
    037     * <br/>
    038     * The initial configuration of the simplex is set by the constructors
    039     * {@link #AbstractSimplex(double[])} or {@link #AbstractSimplex(double[][])}.
    040     * The other {@link #AbstractSimplex(int) constructor} will set all steps
    041     * to 1, thus building a default configuration from a unit hypercube.
    042     * <br/>
    043     * Users <em>must</em> call the {@link #build(double[]) build} method in order
    044     * to create the data structure that will be acted on by the other methods of
    045     * this class.
    046     *
    047     * @see SimplexOptimizer
    048     * @version $Id: AbstractSimplex.java 1422230 2012-12-15 12:11:13Z erans $
    049     * @deprecated As of 3.1 (to be removed in 4.0).
    050     * @since 3.0
    051     */
    052    @Deprecated
    053    public abstract class AbstractSimplex implements OptimizationData {
    054        /** Simplex. */
    055        private PointValuePair[] simplex;
    056        /** Start simplex configuration. */
    057        private double[][] startConfiguration;
    058        /** Simplex dimension (must be equal to {@code simplex.length - 1}). */
    059        private final int dimension;
    060
    061        /**
    062         * Build a unit hypercube simplex.
    063         *
    064         * @param n Dimension of the simplex.
    065         */
    066        protected AbstractSimplex(int n) {
    067            this(n, 1d);
    068        }
    069
    070        /**
    071         * Build a hypercube simplex with the given side length.
    072         *
    073         * @param n Dimension of the simplex.
    074         * @param sideLength Length of the sides of the hypercube.
    075         */
    076        protected AbstractSimplex(int n,
    077                                  double sideLength) {
    078            this(createHypercubeSteps(n, sideLength));
    079        }
    080
    081        /**
    082         * The start configuration for simplex is built from a box parallel to
    083         * the canonical axes of the space. The simplex is the subset of vertices
    084         * of a box parallel to the canonical axes. It is built as the path followed
    085         * while traveling from one vertex of the box to the diagonally opposite
    086         * vertex moving only along the box edges. The first vertex of the box will
    087         * be located at the start point of the optimization.
    088         * As an example, in dimension 3 a simplex has 4 vertices. Setting the
    089         * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
    090         * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
    091         * The first vertex would be set to the start point at (1, 1, 1) and the
    092         * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
    093         *
    094         * @param steps Steps along the canonical axes representing box edges. They
    095         * may be negative but not zero.
    096         * @throws NullArgumentException if {@code steps} is {@code null}.
    097         * @throws ZeroException if one of the steps is zero.
    098         */
    099        protected AbstractSimplex(final double[] steps) {
    100            if (steps == null) {
    101                throw new NullArgumentException();
    102            }
    103            if (steps.length == 0) {
    104                throw new ZeroException();
    105            }
    106            dimension = steps.length;
    107
    108            // Only the relative position of the n final vertices with respect
    109            // to the first one are stored.
    110            startConfiguration = new double[dimension][dimension];
    111            for (int i = 0; i < dimension; i++) {
    112                final double[] vertexI = startConfiguration[i];
    113                for (int j = 0; j < i + 1; j++) {
    114                    if (steps[j] == 0) {
    115                        throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX);
    116                    }
    117                    System.arraycopy(steps, 0, vertexI, 0, j + 1);
    118                }
    119            }
    120        }
    121
    122        /**
    123         * The real initial simplex will be set up by moving the reference
    124         * simplex such that its first point is located at the start point of the
    125         * optimization.
    126         *
    127         * @param referenceSimplex Reference simplex.
    128         * @throws NotStrictlyPositiveException if the reference simplex does not
    129         * contain at least one point.
    130         * @throws DimensionMismatchException if there is a dimension mismatch
    131         * in the reference simplex.
    132         * @throws IllegalArgumentException if one of its vertices is duplicated.
    133         */
    134        protected AbstractSimplex(final double[][] referenceSimplex) {
    135            if (referenceSimplex.length <= 0) {
    136                throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT,
    137                                                       referenceSimplex.length);
    138            }
    139            dimension = referenceSimplex.length - 1;
    140
    141            // Only the relative position of the n final vertices with respect
    142            // to the first one are stored.
    143            startConfiguration = new double[dimension][dimension];
    144            final double[] ref0 = referenceSimplex[0];
    145
    146            // Loop over vertices.
    147            for (int i = 0; i < referenceSimplex.length; i++) {
    148                final double[] refI = referenceSimplex[i];
    149
    150                // Safety checks.
    151                if (refI.length != dimension) {
    152                    throw new DimensionMismatchException(refI.length, dimension);
    153                }
    154                for (int j = 0; j < i; j++) {
    155                    final double[] refJ = referenceSimplex[j];
    156                    boolean allEquals = true;
    157                    for (int k = 0; k < dimension; k++) {
    158                        if (refI[k] != refJ[k]) {
    159                            allEquals = false;
    160                            break;
    161                        }
    162                    }
    163                    if (allEquals) {
    164                        throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX,
    165                                                               i, j);
    166                    }
    167                }
    168
    169                // Store vertex i position relative to vertex 0 position.
    170                if (i > 0) {
    171                    final double[] confI = startConfiguration[i - 1];
    172                    for (int k = 0; k < dimension; k++) {
    173                        confI[k] = refI[k] - ref0[k];
    174                    }
    175                }
    176            }
    177        }
    178
    179        /**
    180         * Get simplex dimension.
    181         *
    182         * @return the dimension of the simplex.
    183         */
    184        public int getDimension() {
    185            return dimension;
    186        }
    187
    188        /**
    189         * Get simplex size.
    190         * After calling the {@link #build(double[]) build} method, this method will
    191         * will be equivalent to {@code getDimension() + 1}.
    192         *
    193         * @return the size of the simplex.
    194         */
    195        public int getSize() {
    196            return simplex.length;
    197        }
    198
    199        /**
    200         * Compute the next simplex of the algorithm.
    201         *
    202         * @param evaluationFunction Evaluation function.
    203         * @param comparator Comparator to use to sort simplex vertices from best
    204         * to worst.
    205         * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
    206         * if the algorithm fails to converge.
    207         */
    208        public abstract void iterate(final MultivariateFunction evaluationFunction,
    209                                     final Comparator<PointValuePair> comparator);
    210
    211        /**
    212         * Build an initial simplex.
    213         *
    214         * @param startPoint First point of the simplex.
    215         * @throws DimensionMismatchException if the start point does not match
    216         * simplex dimension.
    217         */
    218        public void build(final double[] startPoint) {
    219            if (dimension != startPoint.length) {
    220                throw new DimensionMismatchException(dimension, startPoint.length);
    221            }
    222
    223            // Set first vertex.
    224            simplex = new PointValuePair[dimension + 1];
    225            simplex[0] = new PointValuePair(startPoint, Double.NaN);
    226
    227            // Set remaining vertices.
    228            for (int i = 0; i < dimension; i++) {
    229                final double[] confI = startConfiguration[i];
    230                final double[] vertexI = new double[dimension];
    231                for (int k = 0; k < dimension; k++) {
    232                    vertexI[k] = startPoint[k] + confI[k];
    233                }
    234                simplex[i + 1] = new PointValuePair(vertexI, Double.NaN);
    235            }
    236        }
    237
    238        /**
    239         * Evaluate all the non-evaluated points of the simplex.
    240         *
    241         * @param evaluationFunction Evaluation function.
    242         * @param comparator Comparator to use to sort simplex vertices from best to worst.
    243         * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
    244         * if the maximal number of evaluations is exceeded.
    245         */
    246        public void evaluate(final MultivariateFunction evaluationFunction,
    247                             final Comparator<PointValuePair> comparator) {
    248            // Evaluate the objective function at all non-evaluated simplex points.
    249            for (int i = 0; i < simplex.length; i++) {
    250                final PointValuePair vertex = simplex[i];
    251                final double[] point = vertex.getPointRef();
    252                if (Double.isNaN(vertex.getValue())) {
    253                    simplex[i] = new PointValuePair(point, evaluationFunction.value(point), false);
    254                }
    255            }
    256
    257            // Sort the simplex from best to worst.
    258            Arrays.sort(simplex, comparator);
    259        }
    260
    261        /**
    262         * Replace the worst point of the simplex by a new point.
    263         *
    264         * @param pointValuePair Point to insert.
    265         * @param comparator Comparator to use for sorting the simplex vertices
    266         * from best to worst.
    267         */
    268        protected void replaceWorstPoint(PointValuePair pointValuePair,
    269                                         final Comparator<PointValuePair> comparator) {
    270            for (int i = 0; i < dimension; i++) {
    271                if (comparator.compare(simplex[i], pointValuePair) > 0) {
    272                    PointValuePair tmp = simplex[i];
    273                    simplex[i] = pointValuePair;
    274                    pointValuePair = tmp;
    275                }
    276            }
    277            simplex[dimension] = pointValuePair;
    278        }
    279
    280        /**
    281         * Get the points of the simplex.
    282         *
    283         * @return all the simplex points.
    284         */
    285        public PointValuePair[] getPoints() {
    286            final PointValuePair[] copy = new PointValuePair[simplex.length];
    287            System.arraycopy(simplex, 0, copy, 0, simplex.length);
    288            return copy;
    289        }
    290
    291        /**
    292         * Get the simplex point stored at the requested {@code index}.
    293         *
    294         * @param index Location.
    295         * @return the point at location {@code index}.
    296         */
    297        public PointValuePair getPoint(int index) {
    298            if (index < 0 ||
    299                index >= simplex.length) {
    300                throw new OutOfRangeException(index, 0, simplex.length - 1);
    301            }
    302            return simplex[index];
    303        }
    304
    305        /**
    306         * Store a new point at location {@code index}.
    307         * Note that no deep-copy of {@code point} is performed.
    308         *
    309         * @param index Location.
    310         * @param point New value.
    311         */
    312        protected void setPoint(int index, PointValuePair point) {
    313            if (index < 0 ||
    314                index >= simplex.length) {
    315                throw new OutOfRangeException(index, 0, simplex.length - 1);
    316            }
    317            simplex[index] = point;
    318        }
    319
    320        /**
    321         * Replace all points.
    322         * Note that no deep-copy of {@code points} is performed.
    323         *
    324         * @param points New Points.
    325         */
    326        protected void setPoints(PointValuePair[] points) {
    327            if (points.length != simplex.length) {
    328                throw new DimensionMismatchException(points.length, simplex.length);
    329            }
    330            simplex = points;
    331        }
    332
    333        /**
    334         * Create steps for a unit hypercube.
    335         *
    336         * @param n Dimension of the hypercube.
    337         * @param sideLength Length of the sides of the hypercube.
    338         * @return the steps.
    339         */
    340        private static double[] createHypercubeSteps(int n,
    341                                                     double sideLength) {
    342            final double[] steps = new double[n];
    343            for (int i = 0; i < n; i++) {
    344                steps[i] = sideLength;
    345            }
    346            return steps;
    347        }
    348    }