    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.Comparator;
    021
    022    import org.apache.commons.math3.analysis.MultivariateFunction;
    023    import org.apache.commons.math3.optimization.PointValuePair;
    024
    025    /**
    026     * This class implements the multi-directional direct search method.
    027     *
    028     * @version $Id: MultiDirectionalSimplex.java 1422230 2012-12-15 12:11:13Z erans $
    029     * @deprecated As of 3.1 (to be removed in 4.0).
    030     * @since 3.0
    031     */
    032    @Deprecated
    033    public class MultiDirectionalSimplex extends AbstractSimplex {
    034        /** Default value for {@link #khi}: {@value}. */
    035        private static final double DEFAULT_KHI = 2;
    036        /** Default value for {@link #gamma}: {@value}. */
    037        private static final double DEFAULT_GAMMA = 0.5;
    038        /** Expansion coefficient. */
    039        private final double khi;
    040        /** Contraction coefficient. */
    041        private final double gamma;
    042
    043        /**
    044         * Build a multi-directional simplex with default coefficients.
    045         * The default values are 2.0 for khi and 0.5 for gamma.
    046         *
    047         * @param n Dimension of the simplex.
    048         */
    049        public MultiDirectionalSimplex(final int n) {
    050            this(n, 1d);
    051        }
    052
    053        /**
    054         * Build a multi-directional simplex with default coefficients.
    055         * The default values are 2.0 for khi and 0.5 for gamma.
    056         *
    057         * @param n Dimension of the simplex.
    058         * @param sideLength Length of the sides of the default (hypercube)
    059         * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
    060         */
    061        public MultiDirectionalSimplex(final int n, double sideLength) {
    062            this(n, sideLength, DEFAULT_KHI, DEFAULT_GAMMA);
    063        }
    064
    065        /**
    066         * Build a multi-directional simplex with specified coefficients.
    067         *
    068         * @param n Dimension of the simplex. See
    069         * {@link AbstractSimplex#AbstractSimplex(int,double)}.
    070         * @param khi Expansion coefficient.
    071         * @param gamma Contraction coefficient.
    072         */
    073        public MultiDirectionalSimplex(final int n,
    074                                       final double khi, final double gamma) {
    075            this(n, 1d, khi, gamma);
    076        }
    077
    078        /**
    079         * Build a multi-directional simplex with specified coefficients.
    080         *
    081         * @param n Dimension of the simplex. See
    082         * {@link AbstractSimplex#AbstractSimplex(int,double)}.
    083         * @param sideLength Length of the sides of the default (hypercube)
    084         * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
    085         * @param khi Expansion coefficient.
    086         * @param gamma Contraction coefficient.
    087         */
    088        public MultiDirectionalSimplex(final int n, double sideLength,
    089                                       final double khi, final double gamma) {
    090            super(n, sideLength);
    091
    092            this.khi   = khi;
    093            this.gamma = gamma;
    094        }
    095
    096        /**
    097         * Build a multi-directional simplex with default coefficients.
    098         * The default values are 2.0 for khi and 0.5 for gamma.
    099         *
    100         * @param steps Steps along the canonical axes representing box edges.
    101         * They may be negative but not zero. See
    102         */
    103        public MultiDirectionalSimplex(final double[] steps) {
    104            this(steps, DEFAULT_KHI, DEFAULT_GAMMA);
    105        }
    106
    107        /**
    108         * Build a multi-directional simplex with specified coefficients.
    109         *
    110         * @param steps Steps along the canonical axes representing box edges.
    111         * They may be negative but not zero. See
    112         * {@link AbstractSimplex#AbstractSimplex(double[])}.
    113         * @param khi Expansion coefficient.
    114         * @param gamma Contraction coefficient.
    115         */
    116        public MultiDirectionalSimplex(final double[] steps,
    117                                       final double khi, final double gamma) {
    118            super(steps);
    119
    120            this.khi   = khi;
    121            this.gamma = gamma;
    122        }
    123
    124        /**
    125         * Build a multi-directional simplex with default coefficients.
    126         * The default values are 2.0 for khi and 0.5 for gamma.
    127         *
    128         * @param referenceSimplex Reference simplex. See
    129         * {@link AbstractSimplex#AbstractSimplex(double[][])}.
    130         */
    131        public MultiDirectionalSimplex(final double[][] referenceSimplex) {
    132            this(referenceSimplex, DEFAULT_KHI, DEFAULT_GAMMA);
    133        }
    134
    135        /**
    136         * Build a multi-directional simplex with specified coefficients.
    137         *
    138         * @param referenceSimplex Reference simplex. See
    139         * {@link AbstractSimplex#AbstractSimplex(double[][])}.
    140         * @param khi Expansion coefficient.
    141         * @param gamma Contraction coefficient.
    142         * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException
    143         * if the reference simplex does not contain at least one point.
    144         * @throws org.apache.commons.math3.exception.DimensionMismatchException
    145         * if there is a dimension mismatch in the reference simplex.
    146         */
    147        public MultiDirectionalSimplex(final double[][] referenceSimplex,
    148                                       final double khi, final double gamma) {
    149            super(referenceSimplex);
    150
    151            this.khi   = khi;
    152            this.gamma = gamma;
    153        }
    154
    155        /** {@inheritDoc} */
    156        @Override
    157        public void iterate(final MultivariateFunction evaluationFunction,
    158                            final Comparator<PointValuePair> comparator) {
    159            // Save the original simplex.
    160            final PointValuePair[] original = getPoints();
    161            final PointValuePair best = original[0];
    162
    163            // Perform a reflection step.
    164            final PointValuePair reflected = evaluateNewSimplex(evaluationFunction,
    165                                                                    original, 1, comparator);
    166            if (comparator.compare(reflected, best) < 0) {
    167                // Compute the expanded simplex.
    168                final PointValuePair[] reflectedSimplex = getPoints();
    169                final PointValuePair expanded = evaluateNewSimplex(evaluationFunction,
    170                                                                       original, khi, comparator);
    171                if (comparator.compare(reflected, expanded) <= 0) {
    172                    // Keep the reflected simplex.
    173                    setPoints(reflectedSimplex);
    174                }
    175                // Keep the expanded simplex.
    176                return;
    177            }
    178
    179            // Compute the contracted simplex.
    180            evaluateNewSimplex(evaluationFunction, original, gamma, comparator);
    181
    182        }
    183
    184        /**
    185         * Compute and evaluate a new simplex.
    186         *
    187         * @param evaluationFunction Evaluation function.
    188         * @param original Original simplex (to be preserved).
    189         * @param coeff Linear coefficient.
    190         * @param comparator Comparator to use to sort simplex vertices from best
    191         * to poorest.
    192         * @return the best point in the transformed simplex.
    193         * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
    194         * if the maximal number of evaluations is exceeded.
    195         */
    196        private PointValuePair evaluateNewSimplex(final MultivariateFunction evaluationFunction,
    197                                                      final PointValuePair[] original,
    198                                                      final double coeff,
    199                                                      final Comparator<PointValuePair> comparator) {
    200            final double[] xSmallest = original[0].getPointRef();
    201            // Perform a linear transformation on all the simplex points,
    202            // except the first one.
    203            setPoint(0, original[0]);
    204            final int dim = getDimension();
    205            for (int i = 1; i < getSize(); i++) {
    206                final double[] xOriginal = original[i].getPointRef();
    207                final double[] xTransformed = new double[dim];
    208                for (int j = 0; j < dim; j++) {
    209                    xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
    210                }
    211                setPoint(i, new PointValuePair(xTransformed, Double.NaN, false));
    212            }
    213
    214            // Evaluate the simplex.
    215            evaluate(evaluationFunction, comparator);
    216
    217            return getPoint(0);
    218        }
    219    }