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.optimization.PointValuePair;
023 import org.apache.commons.math3.analysis.MultivariateFunction;
024
025 /**
026 * This class implements the Nelder-Mead simplex algorithm.
027 *
028 * @version $Id: NelderMeadSimplex.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 NelderMeadSimplex extends AbstractSimplex {
034 /** Default value for {@link #rho}: {@value}. */
035 private static final double DEFAULT_RHO = 1;
036 /** Default value for {@link #khi}: {@value}. */
037 private static final double DEFAULT_KHI = 2;
038 /** Default value for {@link #gamma}: {@value}. */
039 private static final double DEFAULT_GAMMA = 0.5;
040 /** Default value for {@link #sigma}: {@value}. */
041 private static final double DEFAULT_SIGMA = 0.5;
042 /** Reflection coefficient. */
043 private final double rho;
044 /** Expansion coefficient. */
045 private final double khi;
046 /** Contraction coefficient. */
047 private final double gamma;
048 /** Shrinkage coefficient. */
049 private final double sigma;
050
051 /**
052 * Build a Nelder-Mead simplex with default coefficients.
053 * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
054 * for both gamma and sigma.
055 *
056 * @param n Dimension of the simplex.
057 */
058 public NelderMeadSimplex(final int n) {
059 this(n, 1d);
060 }
061
062 /**
063 * Build a Nelder-Mead simplex with default coefficients.
064 * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
065 * for both gamma and sigma.
066 *
067 * @param n Dimension of the simplex.
068 * @param sideLength Length of the sides of the default (hypercube)
069 * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
070 */
071 public NelderMeadSimplex(final int n, double sideLength) {
072 this(n, sideLength,
073 DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
074 }
075
076 /**
077 * Build a Nelder-Mead simplex with specified coefficients.
078 *
079 * @param n Dimension of the simplex. See
080 * {@link AbstractSimplex#AbstractSimplex(int,double)}.
081 * @param sideLength Length of the sides of the default (hypercube)
082 * simplex. See {@link AbstractSimplex#AbstractSimplex(int,double)}.
083 * @param rho Reflection coefficient.
084 * @param khi Expansion coefficient.
085 * @param gamma Contraction coefficient.
086 * @param sigma Shrinkage coefficient.
087 */
088 public NelderMeadSimplex(final int n, double sideLength,
089 final double rho, final double khi,
090 final double gamma, final double sigma) {
091 super(n, sideLength);
092
093 this.rho = rho;
094 this.khi = khi;
095 this.gamma = gamma;
096 this.sigma = sigma;
097 }
098
099 /**
100 * Build a Nelder-Mead simplex with specified coefficients.
101 *
102 * @param n Dimension of the simplex. See
103 * {@link AbstractSimplex#AbstractSimplex(int)}.
104 * @param rho Reflection coefficient.
105 * @param khi Expansion coefficient.
106 * @param gamma Contraction coefficient.
107 * @param sigma Shrinkage coefficient.
108 */
109 public NelderMeadSimplex(final int n,
110 final double rho, final double khi,
111 final double gamma, final double sigma) {
112 this(n, 1d, rho, khi, gamma, sigma);
113 }
114
115 /**
116 * Build a Nelder-Mead simplex with default coefficients.
117 * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
118 * for both gamma and sigma.
119 *
120 * @param steps Steps along the canonical axes representing box edges.
121 * They may be negative but not zero. See
122 */
123 public NelderMeadSimplex(final double[] steps) {
124 this(steps, DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
125 }
126
127 /**
128 * Build a Nelder-Mead simplex with specified coefficients.
129 *
130 * @param steps Steps along the canonical axes representing box edges.
131 * They may be negative but not zero. See
132 * {@link AbstractSimplex#AbstractSimplex(double[])}.
133 * @param rho Reflection coefficient.
134 * @param khi Expansion coefficient.
135 * @param gamma Contraction coefficient.
136 * @param sigma Shrinkage coefficient.
137 * @throws IllegalArgumentException if one of the steps is zero.
138 */
139 public NelderMeadSimplex(final double[] steps,
140 final double rho, final double khi,
141 final double gamma, final double sigma) {
142 super(steps);
143
144 this.rho = rho;
145 this.khi = khi;
146 this.gamma = gamma;
147 this.sigma = sigma;
148 }
149
150 /**
151 * Build a Nelder-Mead simplex with default coefficients.
152 * The default coefficients are 1.0 for rho, 2.0 for khi and 0.5
153 * for both gamma and sigma.
154 *
155 * @param referenceSimplex Reference simplex. See
156 * {@link AbstractSimplex#AbstractSimplex(double[][])}.
157 */
158 public NelderMeadSimplex(final double[][] referenceSimplex) {
159 this(referenceSimplex, DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
160 }
161
162 /**
163 * Build a Nelder-Mead simplex with specified coefficients.
164 *
165 * @param referenceSimplex Reference simplex. See
166 * {@link AbstractSimplex#AbstractSimplex(double[][])}.
167 * @param rho Reflection coefficient.
168 * @param khi Expansion coefficient.
169 * @param gamma Contraction coefficient.
170 * @param sigma Shrinkage coefficient.
171 * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException
172 * if the reference simplex does not contain at least one point.
173 * @throws org.apache.commons.math3.exception.DimensionMismatchException
174 * if there is a dimension mismatch in the reference simplex.
175 */
176 public NelderMeadSimplex(final double[][] referenceSimplex,
177 final double rho, final double khi,
178 final double gamma, final double sigma) {
179 super(referenceSimplex);
180
181 this.rho = rho;
182 this.khi = khi;
183 this.gamma = gamma;
184 this.sigma = sigma;
185 }
186
187 /** {@inheritDoc} */
188 @Override
189 public void iterate(final MultivariateFunction evaluationFunction,
190 final Comparator<PointValuePair> comparator) {
191 // The simplex has n + 1 points if dimension is n.
192 final int n = getDimension();
193
194 // Interesting values.
195 final PointValuePair best = getPoint(0);
196 final PointValuePair secondBest = getPoint(n - 1);
197 final PointValuePair worst = getPoint(n);
198 final double[] xWorst = worst.getPointRef();
199
200 // Compute the centroid of the best vertices (dismissing the worst
201 // point at index n).
202 final double[] centroid = new double[n];
203 for (int i = 0; i < n; i++) {
204 final double[] x = getPoint(i).getPointRef();
205 for (int j = 0; j < n; j++) {
206 centroid[j] += x[j];
207 }
208 }
209 final double scaling = 1.0 / n;
210 for (int j = 0; j < n; j++) {
211 centroid[j] *= scaling;
212 }
213
214 // compute the reflection point
215 final double[] xR = new double[n];
216 for (int j = 0; j < n; j++) {
217 xR[j] = centroid[j] + rho * (centroid[j] - xWorst[j]);
218 }
219 final PointValuePair reflected
220 = new PointValuePair(xR, evaluationFunction.value(xR), false);
221
222 if (comparator.compare(best, reflected) <= 0 &&
223 comparator.compare(reflected, secondBest) < 0) {
224 // Accept the reflected point.
225 replaceWorstPoint(reflected, comparator);
226 } else if (comparator.compare(reflected, best) < 0) {
227 // Compute the expansion point.
228 final double[] xE = new double[n];
229 for (int j = 0; j < n; j++) {
230 xE[j] = centroid[j] + khi * (xR[j] - centroid[j]);
231 }
232 final PointValuePair expanded
233 = new PointValuePair(xE, evaluationFunction.value(xE), false);
234
235 if (comparator.compare(expanded, reflected) < 0) {
236 // Accept the expansion point.
237 replaceWorstPoint(expanded, comparator);
238 } else {
239 // Accept the reflected point.
240 replaceWorstPoint(reflected, comparator);
241 }
242 } else {
243 if (comparator.compare(reflected, worst) < 0) {
244 // Perform an outside contraction.
245 final double[] xC = new double[n];
246 for (int j = 0; j < n; j++) {
247 xC[j] = centroid[j] + gamma * (xR[j] - centroid[j]);
248 }
249 final PointValuePair outContracted
250 = new PointValuePair(xC, evaluationFunction.value(xC), false);
251 if (comparator.compare(outContracted, reflected) <= 0) {
252 // Accept the contraction point.
253 replaceWorstPoint(outContracted, comparator);
254 return;
255 }
256 } else {
257 // Perform an inside contraction.
258 final double[] xC = new double[n];
259 for (int j = 0; j < n; j++) {
260 xC[j] = centroid[j] - gamma * (centroid[j] - xWorst[j]);
261 }
262 final PointValuePair inContracted
263 = new PointValuePair(xC, evaluationFunction.value(xC), false);
264
265 if (comparator.compare(inContracted, worst) < 0) {
266 // Accept the contraction point.
267 replaceWorstPoint(inContracted, comparator);
268 return;
269 }
270 }
271
272 // Perform a shrink.
273 final double[] xSmallest = getPoint(0).getPointRef();
274 for (int i = 1; i <= n; i++) {
275 final double[] x = getPoint(i).getPoint();
276 for (int j = 0; j < n; j++) {
277 x[j] = xSmallest[j] + sigma * (x[j] - xSmallest[j]);
278 }
279 setPoint(i, new PointValuePair(x, Double.NaN, false));
280 }
281 evaluate(evaluationFunction, comparator);
282 }
283 }
284 }