View Javadoc
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  
18  package org.apache.commons.math3.optimization.direct;
19  
20  import java.util.Comparator;
21  
22  import org.apache.commons.math3.analysis.MultivariateFunction;
23  import org.apache.commons.math3.optimization.PointValuePair;
24  
25  /**
26   * This class implements the multi-directional direct search method.
27   *
28   * @deprecated As of 3.1 (to be removed in 4.0).
29   * @since 3.0
30   */
31  @Deprecated
32  public class MultiDirectionalSimplex extends AbstractSimplex {
33      /** Default value for {@link #khi}: {@value}. */
34      private static final double DEFAULT_KHI = 2;
35      /** Default value for {@link #gamma}: {@value}. */
36      private static final double DEFAULT_GAMMA = 0.5;
37      /** Expansion coefficient. */
38      private final double khi;
39      /** Contraction coefficient. */
40      private final double gamma;
41  
42      /**
43       * Build a multi-directional simplex with default coefficients.
44       * The default values are 2.0 for khi and 0.5 for gamma.
45       *
46       * @param n Dimension of the simplex.
47       */
48      public MultiDirectionalSimplex(final int n) {
49          this(n, 1d);
50      }
51  
52      /**
53       * Build a multi-directional simplex with default coefficients.
54       * The default values are 2.0 for khi and 0.5 for gamma.
55       *
56       * @param n Dimension of the simplex.
57       * @param sideLength Length of the sides of the default (hypercube)
58       * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
59       */
60      public MultiDirectionalSimplex(final int n, double sideLength) {
61          this(n, sideLength, DEFAULT_KHI, DEFAULT_GAMMA);
62      }
63  
64      /**
65       * Build a multi-directional simplex with specified coefficients.
66       *
67       * @param n Dimension of the simplex. See
68       * {@link AbstractSimplex#AbstractSimplex(int,double)}.
69       * @param khi Expansion coefficient.
70       * @param gamma Contraction coefficient.
71       */
72      public MultiDirectionalSimplex(final int n,
73                                     final double khi, final double gamma) {
74          this(n, 1d, khi, gamma);
75      }
76  
77      /**
78       * Build a multi-directional simplex with specified coefficients.
79       *
80       * @param n Dimension of the simplex. See
81       * {@link AbstractSimplex#AbstractSimplex(int,double)}.
82       * @param sideLength Length of the sides of the default (hypercube)
83       * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
84       * @param khi Expansion coefficient.
85       * @param gamma Contraction coefficient.
86       */
87      public MultiDirectionalSimplex(final int n, double sideLength,
88                                     final double khi, final double gamma) {
89          super(n, sideLength);
90  
91          this.khi   = khi;
92          this.gamma = gamma;
93      }
94  
95      /**
96       * Build a multi-directional simplex with default coefficients.
97       * The default values are 2.0 for khi and 0.5 for gamma.
98       *
99       * @param steps Steps along the canonical axes representing box edges.
100      * They may be negative but not zero. See
101      */
102     public MultiDirectionalSimplex(final double[] steps) {
103         this(steps, DEFAULT_KHI, DEFAULT_GAMMA);
104     }
105 
106     /**
107      * Build a multi-directional simplex with specified coefficients.
108      *
109      * @param steps Steps along the canonical axes representing box edges.
110      * They may be negative but not zero. See
111      * {@link AbstractSimplex#AbstractSimplex(double[])}.
112      * @param khi Expansion coefficient.
113      * @param gamma Contraction coefficient.
114      */
115     public MultiDirectionalSimplex(final double[] steps,
116                                    final double khi, final double gamma) {
117         super(steps);
118 
119         this.khi   = khi;
120         this.gamma = gamma;
121     }
122 
123     /**
124      * Build a multi-directional simplex with default coefficients.
125      * The default values are 2.0 for khi and 0.5 for gamma.
126      *
127      * @param referenceSimplex Reference simplex. See
128      * {@link AbstractSimplex#AbstractSimplex(double[][])}.
129      */
130     public MultiDirectionalSimplex(final double[][] referenceSimplex) {
131         this(referenceSimplex, DEFAULT_KHI, DEFAULT_GAMMA);
132     }
133 
134     /**
135      * Build a multi-directional simplex with specified coefficients.
136      *
137      * @param referenceSimplex Reference simplex. See
138      * {@link AbstractSimplex#AbstractSimplex(double[][])}.
139      * @param khi Expansion coefficient.
140      * @param gamma Contraction coefficient.
141      * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException
142      * if the reference simplex does not contain at least one point.
143      * @throws org.apache.commons.math3.exception.DimensionMismatchException
144      * if there is a dimension mismatch in the reference simplex.
145      */
146     public MultiDirectionalSimplex(final double[][] referenceSimplex,
147                                    final double khi, final double gamma) {
148         super(referenceSimplex);
149 
150         this.khi   = khi;
151         this.gamma = gamma;
152     }
153 
154     /** {@inheritDoc} */
155     @Override
156     public void iterate(final MultivariateFunction evaluationFunction,
157                         final Comparator<PointValuePair> comparator) {
158         // Save the original simplex.
159         final PointValuePair[] original = getPoints();
160         final PointValuePair best = original[0];
161 
162         // Perform a reflection step.
163         final PointValuePair reflected = evaluateNewSimplex(evaluationFunction,
164                                                                 original, 1, comparator);
165         if (comparator.compare(reflected, best) < 0) {
166             // Compute the expanded simplex.
167             final PointValuePair[] reflectedSimplex = getPoints();
168             final PointValuePair expanded = evaluateNewSimplex(evaluationFunction,
169                                                                    original, khi, comparator);
170             if (comparator.compare(reflected, expanded) <= 0) {
171                 // Keep the reflected simplex.
172                 setPoints(reflectedSimplex);
173             }
174             // Keep the expanded simplex.
175             return;
176         }
177 
178         // Compute the contracted simplex.
179         evaluateNewSimplex(evaluationFunction, original, gamma, comparator);
180 
181     }
182 
183     /**
184      * Compute and evaluate a new simplex.
185      *
186      * @param evaluationFunction Evaluation function.
187      * @param original Original simplex (to be preserved).
188      * @param coeff Linear coefficient.
189      * @param comparator Comparator to use to sort simplex vertices from best
190      * to poorest.
191      * @return the best point in the transformed simplex.
192      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
193      * if the maximal number of evaluations is exceeded.
194      */
195     private PointValuePair evaluateNewSimplex(final MultivariateFunction evaluationFunction,
196                                                   final PointValuePair[] original,
197                                                   final double coeff,
198                                                   final Comparator<PointValuePair> comparator) {
199         final double[] xSmallest = original[0].getPointRef();
200         // Perform a linear transformation on all the simplex points,
201         // except the first one.
202         setPoint(0, original[0]);
203         final int dim = getDimension();
204         for (int i = 1; i < getSize(); i++) {
205             final double[] xOriginal = original[i].getPointRef();
206             final double[] xTransformed = new double[dim];
207             for (int j = 0; j < dim; j++) {
208                 xTransformed[j] = xSmallest[j] + coeff * (xSmallest[j] - xOriginal[j]);
209             }
210             setPoint(i, new PointValuePair(xTransformed, Double.NaN, false));
211         }
212 
213         // Evaluate the simplex.
214         evaluate(evaluationFunction, comparator);
215 
216         return getPoint(0);
217     }
218 }