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 package org.apache.commons.math4.legacy.optim.nonlinear.scalar.noderiv;
18
19 import java.util.List;
20 import java.util.ArrayList;
21 import java.util.Comparator;
22 import java.util.function.UnaryOperator;
23 import java.util.function.DoublePredicate;
24
25 import org.apache.commons.math4.legacy.analysis.MultivariateFunction;
26 import org.apache.commons.math4.legacy.optim.PointValuePair;
27
28 /**
29 * <a href="https://scholarship.rice.edu/handle/1911/16304">Multi-directional</a> search method.
30 */
31 public class MultiDirectionalTransform
32 implements Simplex.TransformFactory {
33 /** Reflection coefficient. */
34 private static final double ALPHA = 1;
35 /** Default value for {@link #gamma}: {@value}. */
36 private static final double DEFAULT_GAMMA = 2;
37 /** Default value for {@link #sigma}: {@value}. */
38 private static final double DEFAULT_SIGMA = 0.5;
39 /** Expansion coefficient. */
40 private final double gamma;
41 /** Contraction coefficient. */
42 private final double sigma;
43
44 /**
45 * @param gamma Expansion coefficient.
46 * @param sigma Shrinkage coefficient.
47 */
48 public MultiDirectionalTransform(double gamma,
49 double sigma) {
50 if (gamma < 1) {
51 throw new IllegalArgumentException("gamma: " + gamma);
52 }
53 if (sigma < 0 ||
54 sigma > 1) {
55 throw new IllegalArgumentException("sigma: " + sigma);
56 }
57
58 this.gamma = gamma;
59 this.sigma = sigma;
60 }
61
62 /**
63 * Transform with default values.
64 */
65 public MultiDirectionalTransform() {
66 this(DEFAULT_GAMMA,
67 DEFAULT_SIGMA);
68 }
69
70 /** {@inheritDoc} */
71 @Override
72 public UnaryOperator<Simplex> create(final MultivariateFunction evaluationFunction,
73 final Comparator<PointValuePair> comparator,
74 final DoublePredicate sa) {
75 return original -> {
76 final PointValuePair best = original.get(0);
77
78 // Perform a reflection step.
79 final Simplex reflectedSimplex = transform(original,
80 ALPHA,
81 comparator,
82 evaluationFunction);
83 final PointValuePair reflectedBest = reflectedSimplex.get(0);
84
85 if (comparator.compare(reflectedBest, best) < 0) {
86 // Compute the expanded simplex.
87 final Simplex expandedSimplex = transform(original,
88 gamma,
89 comparator,
90 evaluationFunction);
91 final PointValuePair expandedBest = expandedSimplex.get(0);
92
93 if (comparator.compare(expandedBest, reflectedBest) <= 0 ||
94 (sa != null &&
95 sa.test(expandedBest.getValue() - reflectedBest.getValue()))) {
96 return expandedSimplex;
97 } else {
98 return reflectedSimplex;
99 }
100 } else {
101 // Compute the contracted simplex.
102 return original.shrink(sigma, evaluationFunction);
103 }
104 };
105 }
106
107 /**
108 * Computes and evaluates a new simplex.
109 *
110 * @param original Original simplex.
111 * @param coeff Linear coefficient.
112 * @param comp Fitness comparator.
113 * @param evalFunc Objective function.
114 * @return the transformed simplex.
115 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
116 * if the maximal number of evaluations is exceeded.
117 */
118 private Simplex transform(Simplex original,
119 double coeff,
120 Comparator<PointValuePair> comp,
121 MultivariateFunction evalFunc) {
122 // Transformed simplex is the result a linear transformation on all
123 // points except the first one.
124 final int replSize = original.getSize() - 1;
125 final List<PointValuePair> replacement = new ArrayList<>();
126 final double[] bestPoint = original.get(0).getPoint();
127 for (int i = 0; i < replSize; i++) {
128 replacement.add(Simplex.newPoint(bestPoint,
129 -coeff,
130 original.get(i + 1).getPoint(),
131 evalFunc));
132 }
133
134 return original.replaceLast(replacement).evaluate(evalFunc, comp);
135 }
136
137 /** {@inheritDoc} */
138 @Override
139 public String toString() {
140 return "Multidirectional [g=" + gamma +
141 " s=" + sigma + "]";
142 }
143 }