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   * @version $Id: AbstractSimplex.java 1422230 2012-12-15 12:11:13Z erans $
49   * @deprecated As of 3.1 (to be removed in 4.0).
50   * @since 3.0
51   */
52  @Deprecated
53  public abstract class AbstractSimplex implements OptimizationData {
54      /** Simplex. */
55      private PointValuePair[] simplex;
56      /** Start simplex configuration. */
57      private double[][] startConfiguration;
58      /** Simplex dimension (must be equal to {@code simplex.length - 1}). */
59      private final int dimension;
60  
61      /**
62       * Build a unit hypercube simplex.
63       *
64       * @param n Dimension of the simplex.
65       */
66      protected AbstractSimplex(int n) {
67          this(n, 1d);
68      }
69  
70      /**
71       * Build a hypercube simplex with the given side length.
72       *
73       * @param n Dimension of the simplex.
74       * @param sideLength Length of the sides of the hypercube.
75       */
76      protected AbstractSimplex(int n,
77                                double sideLength) {
78          this(createHypercubeSteps(n, sideLength));
79      }
80  
81      /**
82       * The start configuration for simplex is built from a box parallel to
83       * the canonical axes of the space. The simplex is the subset of vertices
84       * of a box parallel to the canonical axes. It is built as the path followed
85       * while traveling from one vertex of the box to the diagonally opposite
86       * vertex moving only along the box edges. The first vertex of the box will
87       * be located at the start point of the optimization.
88       * As an example, in dimension 3 a simplex has 4 vertices. Setting the
89       * steps to (1, 10, 2) and the start point to (1, 1, 1) would imply the
90       * start simplex would be: { (1, 1, 1), (2, 1, 1), (2, 11, 1), (2, 11, 3) }.
91       * The first vertex would be set to the start point at (1, 1, 1) and the
92       * last vertex would be set to the diagonally opposite vertex at (2, 11, 3).
93       *
94       * @param steps Steps along the canonical axes representing box edges. They
95       * may be negative but not zero.
96       * @throws NullArgumentException if {@code steps} is {@code null}.
97       * @throws ZeroException if one of the steps is zero.
98       */
99      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 }