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.Arrays;
21  import java.util.Comparator;
22  
23  import org.apache.commons.math3.analysis.MultivariateFunction;
24  import org.apache.commons.math3.exception.NotStrictlyPositiveException;
25  import org.apache.commons.math3.exception.DimensionMismatchException;
26  import org.apache.commons.math3.exception.ZeroException;
27  import org.apache.commons.math3.exception.OutOfRangeException;
28  import org.apache.commons.math3.exception.NullArgumentException;
29  import org.apache.commons.math3.exception.MathIllegalArgumentException;
30  import org.apache.commons.math3.exception.util.LocalizedFormats;
31  import org.apache.commons.math3.optimization.PointValuePair;
32  import org.apache.commons.math3.optimization.OptimizationData;
33  
34  /**
35   * This class implements the simplex concept.
36   * It is intended to be used in conjunction with {@link SimplexOptimizer}.
37   * <br/>
38   * The initial configuration of the simplex is set by the constructors
39   * {@link #AbstractSimplex(double[])} or {@link #AbstractSimplex(double[][])}.
40   * The other {@link #AbstractSimplex(int) constructor} will set all steps
41   * to 1, thus building a default configuration from a unit hypercube.
42   * <br/>
43   * Users <em>must</em> call the {@link #build(double[]) build} method in order
44   * to create the data structure that will be acted on by the other methods of
45   * this class.
46   *
47   * @see SimplexOptimizer
48   * @deprecated As of 3.1 (to be removed in 4.0).
49   * @since 3.0
50   */
51  @Deprecated
52  public abstract class AbstractSimplex implements OptimizationData {
53      /** Simplex. */
54      private PointValuePair[] simplex;
55      /** Start simplex configuration. */
56      private double[][] startConfiguration;
57      /** Simplex dimension (must be equal to {@code simplex.length - 1}). */
58      private final int dimension;
59  
60      /**
61       * Build a unit hypercube simplex.
62       *
63       * @param n Dimension of the simplex.
64       */
65      protected AbstractSimplex(int n) {
66          this(n, 1d);
67      }
68  
69      /**
70       * Build a hypercube simplex with the given side length.
71       *
72       * @param n Dimension of the simplex.
73       * @param sideLength Length of the sides of the hypercube.
74       */
75      protected AbstractSimplex(int n,
76                                double sideLength) {
77          this(createHypercubeSteps(n, sideLength));
78      }
79  
80      /**
81       * The start configuration for simplex is built from a box parallel to
82       * the canonical axes of the space. The simplex is the subset of vertices
83       * of a box parallel to the canonical axes. It is built as the path followed
84       * while traveling from one vertex of the box to the diagonally opposite
85       * vertex moving only along the box edges. The first vertex of the box will
86       * be located at the start point of the optimization.
87       * As an example, in dimension 3 a simplex has 4 vertices. Setting the
88       * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
89       * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
90       * The first vertex would be set to the start point at (1, 1, 1) and the
91       * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
92       *
93       * @param steps Steps along the canonical axes representing box edges. They
94       * may be negative but not zero.
95       * @throws NullArgumentException if {@code steps} is {@code null}.
96       * @throws ZeroException if one of the steps is zero.
97       */
98      protected AbstractSimplex(final double[] steps) {
99          if (steps == null) {
100             throw new NullArgumentException();
101         }
102         if (steps.length == 0) {
103             throw new ZeroException();
104         }
105         dimension = steps.length;
106 
107         // Only the relative position of the n final vertices with respect
108         // to the first one are stored.
109         startConfiguration = new double[dimension][dimension];
110         for (int i = 0; i < dimension; i++) {
111             final double[] vertexI = startConfiguration[i];
112             for (int j = 0; j < i + 1; j++) {
113                 if (steps[j] == 0) {
114                     throw new ZeroException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX);
115                 }
116                 System.arraycopy(steps, 0, vertexI, 0, j + 1);
117             }
118         }
119     }
120 
121     /**
122      * The real initial simplex will be set up by moving the reference
123      * simplex such that its first point is located at the start point of the
124      * optimization.
125      *
126      * @param referenceSimplex Reference simplex.
127      * @throws NotStrictlyPositiveException if the reference simplex does not
128      * contain at least one point.
129      * @throws DimensionMismatchException if there is a dimension mismatch
130      * in the reference simplex.
131      * @throws IllegalArgumentException if one of its vertices is duplicated.
132      */
133     protected AbstractSimplex(final double[][] referenceSimplex) {
134         if (referenceSimplex.length <= 0) {
135             throw new NotStrictlyPositiveException(LocalizedFormats.SIMPLEX_NEED_ONE_POINT,
136                                                    referenceSimplex.length);
137         }
138         dimension = referenceSimplex.length - 1;
139 
140         // Only the relative position of the n final vertices with respect
141         // to the first one are stored.
142         startConfiguration = new double[dimension][dimension];
143         final double[] ref0 = referenceSimplex[0];
144 
145         // Loop over vertices.
146         for (int i = 0; i < referenceSimplex.length; i++) {
147             final double[] refI = referenceSimplex[i];
148 
149             // Safety checks.
150             if (refI.length != dimension) {
151                 throw new DimensionMismatchException(refI.length, dimension);
152             }
153             for (int j = 0; j < i; j++) {
154                 final double[] refJ = referenceSimplex[j];
155                 boolean allEquals = true;
156                 for (int k = 0; k < dimension; k++) {
157                     if (refI[k] != refJ[k]) {
158                         allEquals = false;
159                         break;
160                     }
161                 }
162                 if (allEquals) {
163                     throw new MathIllegalArgumentException(LocalizedFormats.EQUAL_VERTICES_IN_SIMPLEX,
164                                                            i, j);
165                 }
166             }
167 
168             // Store vertex i position relative to vertex 0 position.
169             if (i > 0) {
170                 final double[] confI = startConfiguration[i - 1];
171                 for (int k = 0; k < dimension; k++) {
172                     confI[k] = refI[k] - ref0[k];
173                 }
174             }
175         }
176     }
177 
178     /**
179      * Get simplex dimension.
180      *
181      * @return the dimension of the simplex.
182      */
183     public int getDimension() {
184         return dimension;
185     }
186 
187     /**
188      * Get simplex size.
189      * After calling the {@link #build(double[]) build} method, this method will
190      * will be equivalent to {@code getDimension() + 1}.
191      *
192      * @return the size of the simplex.
193      */
194     public int getSize() {
195         return simplex.length;
196     }
197 
198     /**
199      * Compute the next simplex of the algorithm.
200      *
201      * @param evaluationFunction Evaluation function.
202      * @param comparator Comparator to use to sort simplex vertices from best
203      * to worst.
204      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
205      * if the algorithm fails to converge.
206      */
207     public abstract void iterate(final MultivariateFunction evaluationFunction,
208                                  final Comparator<PointValuePair> comparator);
209 
210     /**
211      * Build an initial simplex.
212      *
213      * @param startPoint First point of the simplex.
214      * @throws DimensionMismatchException if the start point does not match
215      * simplex dimension.
216      */
217     public void build(final double[] startPoint) {
218         if (dimension != startPoint.length) {
219             throw new DimensionMismatchException(dimension, startPoint.length);
220         }
221 
222         // Set first vertex.
223         simplex = new PointValuePair[dimension + 1];
224         simplex[0] = new PointValuePair(startPoint, Double.NaN);
225 
226         // Set remaining vertices.
227         for (int i = 0; i < dimension; i++) {
228             final double[] confI = startConfiguration[i];
229             final double[] vertexI = new double[dimension];
230             for (int k = 0; k < dimension; k++) {
231                 vertexI[k] = startPoint[k] + confI[k];
232             }
233             simplex[i + 1] = new PointValuePair(vertexI, Double.NaN);
234         }
235     }
236 
237     /**
238      * Evaluate all the non-evaluated points of the simplex.
239      *
240      * @param evaluationFunction Evaluation function.
241      * @param comparator Comparator to use to sort simplex vertices from best to worst.
242      * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
243      * if the maximal number of evaluations is exceeded.
244      */
245     public void evaluate(final MultivariateFunction evaluationFunction,
246                          final Comparator<PointValuePair> comparator) {
247         // Evaluate the objective function at all non-evaluated simplex points.
248         for (int i = 0; i < simplex.length; i++) {
249             final PointValuePair vertex = simplex[i];
250             final double[] point = vertex.getPointRef();
251             if (Double.isNaN(vertex.getValue())) {
252                 simplex[i] = new PointValuePair(point, evaluationFunction.value(point), false);
253             }
254         }
255 
256         // Sort the simplex from best to worst.
257         Arrays.sort(simplex, comparator);
258     }
259 
260     /**
261      * Replace the worst point of the simplex by a new point.
262      *
263      * @param pointValuePair Point to insert.
264      * @param comparator Comparator to use for sorting the simplex vertices
265      * from best to worst.
266      */
267     protected void replaceWorstPoint(PointValuePair pointValuePair,
268                                      final Comparator<PointValuePair> comparator) {
269         for (int i = 0; i < dimension; i++) {
270             if (comparator.compare(simplex[i], pointValuePair) > 0) {
271                 PointValuePair tmp = simplex[i];
272                 simplex[i] = pointValuePair;
273                 pointValuePair = tmp;
274             }
275         }
276         simplex[dimension] = pointValuePair;
277     }
278 
279     /**
280      * Get the points of the simplex.
281      *
282      * @return all the simplex points.
283      */
284     public PointValuePair[] getPoints() {
285         final PointValuePair[] copy = new PointValuePair[simplex.length];
286         System.arraycopy(simplex, 0, copy, 0, simplex.length);
287         return copy;
288     }
289 
290     /**
291      * Get the simplex point stored at the requested {@code index}.
292      *
293      * @param index Location.
294      * @return the point at location {@code index}.
295      */
296     public PointValuePair getPoint(int index) {
297         if (index < 0 ||
298             index >= simplex.length) {
299             throw new OutOfRangeException(index, 0, simplex.length - 1);
300         }
301         return simplex[index];
302     }
303 
304     /**
305      * Store a new point at location {@code index}.
306      * Note that no deep-copy of {@code point} is performed.
307      *
308      * @param index Location.
309      * @param point New value.
310      */
311     protected void setPoint(int index, PointValuePair point) {
312         if (index < 0 ||
313             index >= simplex.length) {
314             throw new OutOfRangeException(index, 0, simplex.length - 1);
315         }
316         simplex[index] = point;
317     }
318 
319     /**
320      * Replace all points.
321      * Note that no deep-copy of {@code points} is performed.
322      *
323      * @param points New Points.
324      */
325     protected void setPoints(PointValuePair[] points) {
326         if (points.length != simplex.length) {
327             throw new DimensionMismatchException(points.length, simplex.length);
328         }
329         simplex = points;
330     }
331 
332     /**
333      * Create steps for a unit hypercube.
334      *
335      * @param n Dimension of the hypercube.
336      * @param sideLength Length of the sides of the hypercube.
337      * @return the steps.
338      */
339     private static double[] createHypercubeSteps(int n,
340                                                  double sideLength) {
341         final double[] steps = new double[n];
342         for (int i = 0; i < n; i++) {
343             steps[i] = sideLength;
344         }
345         return steps;
346     }
347 }