1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package org.hipparchus.optim.nonlinear.scalar.noderiv;
23
24 import java.util.Comparator;
25
26 import org.hipparchus.analysis.MultivariateFunction;
27 import org.hipparchus.optim.PointValuePair;
28
29
30
31
32
33 public class NelderMeadSimplex extends AbstractSimplex {
34
35 private static final double DEFAULT_RHO = 1;
36
37 private static final double DEFAULT_KHI = 2;
38
39 private static final double DEFAULT_GAMMA = 0.5;
40
41 private static final double DEFAULT_SIGMA = 0.5;
42
43 private final double rho;
44
45 private final double khi;
46
47 private final double gamma;
48
49 private final double sigma;
50
51
52
53
54
55
56
57
58 public NelderMeadSimplex(final int n) {
59 this(n, 1d);
60 }
61
62
63
64
65
66
67
68
69
70
71 public NelderMeadSimplex(final int n, double sideLength) {
72 this(n, sideLength,
73 DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
74 }
75
76
77
78
79
80
81
82
83
84
85
86
87
88 public NelderMeadSimplex(final int n, double sideLength,
89 final double rho, final double khi,
90 final double gamma, final double sigma) {
91 super(n, sideLength);
92
93 this.rho = rho;
94 this.khi = khi;
95 this.gamma = gamma;
96 this.sigma = sigma;
97 }
98
99
100
101
102
103
104
105
106
107
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
117
118
119
120
121
122
123 public NelderMeadSimplex(final double[] steps) {
124 this(steps, DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
125 }
126
127
128
129
130
131
132
133
134
135
136
137
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
152
153
154
155
156
157
158 public NelderMeadSimplex(final double[][] referenceSimplex) {
159 this(referenceSimplex, DEFAULT_RHO, DEFAULT_KHI, DEFAULT_GAMMA, DEFAULT_SIGMA);
160 }
161
162
163
164
165
166
167
168
169
170
171
172
173
174
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
188 @Override
189 public void iterate(final MultivariateFunction evaluationFunction,
190 final Comparator<PointValuePair> comparator) {
191
192 final int n = getDimension();
193
194
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
201
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
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
225 replaceWorstPoint(reflected, comparator);
226 } else if (comparator.compare(reflected, best) < 0) {
227
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
237 replaceWorstPoint(expanded, comparator);
238 } else {
239
240 replaceWorstPoint(reflected, comparator);
241 }
242 } else {
243 if (comparator.compare(reflected, worst) < 0) {
244
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
253 replaceWorstPoint(outContracted, comparator);
254 return;
255 }
256 } else {
257
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
267 replaceWorstPoint(inContracted, comparator);
268 return;
269 }
270 }
271
272
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 }