001 /*
002 * Java Genetic Algorithm Library (jenetics-3.9.0).
003 * Copyright (c) 2007-2017 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * 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 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019 */
020 package org.jenetics;
021
022 import static java.lang.Math.abs;
023 import static java.lang.String.format;
024 import static java.util.Objects.requireNonNull;
025 import static org.jenetics.internal.math.arithmetic.pow;
026 import static org.jenetics.internal.math.base.ulpDistance;
027 import static org.jenetics.internal.util.IndexSorter.sort;
028
029 import java.util.Random;
030 import java.util.function.Function;
031
032 import org.jenetics.internal.math.DoubleAdder;
033 import org.jenetics.internal.util.array;
034
035 import org.jenetics.util.RandomRegistry;
036
037 /**
038 * Probability selectors are a variation of fitness proportional selectors and
039 * selects individuals from a given population based on it's selection
040 * probability <i>P(i)</i>.
041 * <p>
042 * <img src="doc-files/FitnessProportionalSelection.svg" width="400" alt="Selection">
043 * <p>
044 * Fitness proportional selection works as shown in the figure above. The
045 * runtime complexity of the implemented probability selectors is
046 * <i>O(n+</i>log<i>(n))</i> instead of <i>O(n<sup>2</sup>)</i> as for the naive
047 * approach: <i>A binary (index) search is performed on the summed probability
048 * array.</i>
049 *
050 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
051 * @since 1.0
052 * @version 3.2
053 */
054 public abstract class ProbabilitySelector<
055 G extends Gene<?, G>,
056 C extends Comparable<? super C>
057 >
058 implements Selector<G, C>
059 {
060 private static final int SERIAL_INDEX_THRESHOLD = 35;
061
062 private static final long MAX_ULP_DISTANCE = pow(10, 10);
063
064 private final boolean _sorted;
065 private final Function<double[], double[]> _reverter;
066
067
068 /**
069 * Create a new {@code ProbabilitySelector} with the given {@code sorting}
070 * flag. <em>This flag must set to {@code true} if the selector
071 * implementation is sorting the population in the
072 * {@link #probabilities(Population, int)} method.</em>
073 *
074 * @param sorted {@code true} if the implementation is sorting the
075 * population when calculating the selection probabilities,
076 * {@code false} otherwise.
077 */
078 protected ProbabilitySelector(final boolean sorted) {
079 _sorted = sorted;
080 _reverter = sorted ? array::revert : ProbabilitySelector::sortAndRevert;
081 }
082
083 /**
084 * Create a new selector with {@code sorted = false}.
085 */
086 protected ProbabilitySelector() {
087 this(false);
088 }
089
090 @Override
091 public Population<G, C> select(
092 final Population<G, C> population,
093 final int count,
094 final Optimize opt
095 ) {
096 requireNonNull(population, "Population");
097 requireNonNull(opt, "Optimization");
098 if (count < 0) {
099 throw new IllegalArgumentException(format(
100 "Selection count must be greater or equal then zero, but was %s.",
101 count
102 ));
103 }
104
105 final Population<G, C> selection = new Population<>(count);
106 if (count > 0 && !population.isEmpty()) {
107 final Population<G, C> pop = copy(population);
108
109 final double[] prob = probabilities(pop, count, opt);
110 assert pop.size() == prob.length
111 : "Population size and probability length are not equal.";
112
113 checkAndCorrect(prob);
114 assert sum2one(prob) : "Probabilities doesn't sum to one.";
115
116 incremental(prob);
117
118 final Random random = RandomRegistry.getRandom();
119 selection.fill(
120 () -> pop.get(indexOf(prob, random.nextDouble())),
121 count
122 );
123 }
124
125 return selection;
126 }
127
128 Population<G, C> copy(final Population<G, C> population) {
129 Population<G, C> pop = population;
130 if (_sorted) {
131 pop = population.copy();
132 pop.populationSort();
133 }
134
135 return pop;
136 }
137
138 /**
139 * This method takes the probabilities from the
140 * {@link #probabilities(Population, int)} method and inverts it if needed.
141 *
142 * @param population The population.
143 * @param count The number of phenotypes to select.
144 * @param opt Determines whether the individuals with higher fitness values
145 * or lower fitness values must be selected. This parameter
146 * determines whether the GA maximizes or minimizes the fitness
147 * function.
148 * @return Probability array.
149 */
150 protected final double[] probabilities(
151 final Population<G, C> population,
152 final int count,
153 final Optimize opt
154 ) {
155 return requireNonNull(opt) == Optimize.MINIMUM
156 ? _reverter.apply(probabilities(population, count))
157 : probabilities(population, count);
158 }
159
160 // Package private for testing.
161 static double[] sortAndRevert(final double[] array) {
162 final int[] indexes = sort(array);
163
164 // Copy the elements in reversed order.
165 final double[] result = new double[array.length];
166 for (int i = 0; i < result.length; ++i) {
167 result[indexes[result.length - 1 - i]] = array[indexes[i]];
168 }
169
170 return result;
171 }
172
173 /**
174 * <p>
175 * Return an Probability array, which corresponds to the given Population.
176 * The probability array and the population must have the same size. The
177 * population is not sorted. If a subclass needs a sorted population, the
178 * subclass is responsible to sort the population.
179 * </p>
180 * The implementer always assumes that higher fitness values are better. The
181 * base class inverts the probabilities, by reverting the returned
182 * probability array, if the GA is supposed to minimize the fitness function.
183 *
184 * @param population The <em>unsorted</em> population.
185 * @param count The number of phenotypes to select. <i>This parameter is not
186 * needed for most implementations.</i>
187 * @return Probability array. The returned probability array must have the
188 * length {@code population.size()} and <strong>must</strong> sum to
189 * one. The returned value is checked with
190 * {@code assert(Math.abs(math.sum(probabilities) - 1.0) < 0.0001)}
191 * in the base class.
192 */
193 protected abstract double[] probabilities(
194 final Population<G, C> population,
195 final int count
196 );
197
198 /**
199 * Checks if the given probability values are finite. If not, all values are
200 * set to the same probability.
201 *
202 * @param probabilities the probabilities to check.
203 */
204 private static void checkAndCorrect(final double[] probabilities) {
205 boolean ok = true;
206 for (int i = probabilities.length; --i >= 0 && ok;) {
207 ok = Double.isFinite(probabilities[i]);
208 }
209
210 if (!ok) {
211 final double value = 1.0/probabilities.length;
212 for (int i = probabilities.length; --i >= 0;) {
213 probabilities[i] = value;
214 }
215 }
216 }
217
218 /**
219 * Check if the given probabilities sum to one.
220 *
221 * @param probabilities the probabilities to check.
222 * @return {@code true} if the sum of the probabilities are within the error
223 * range, {@code false} otherwise.
224 */
225 static boolean sum2one(final double[] probabilities) {
226 final double sum = probabilities.length > 0
227 ? DoubleAdder.sum(probabilities)
228 : 1.0;
229 return abs(ulpDistance(sum, 1.0)) < MAX_ULP_DISTANCE;
230 }
231
232 static boolean eq(final double a, final double b) {
233 return abs(ulpDistance(a, b)) < MAX_ULP_DISTANCE;
234 }
235
236 static int indexOf(final double[] incr, final double v) {
237 return incr.length <= SERIAL_INDEX_THRESHOLD
238 ? indexOfSerial(incr, v)
239 : indexOfBinary(incr, v);
240 }
241
242 /**
243 * Perform a binary-search on the summed probability array.
244 */
245 static int indexOfBinary(final double[] incr, final double v) {
246 int imin = 0;
247 int imax = incr.length;
248 int index = -1;
249
250 while (imax > imin && index == -1) {
251 final int imid = (imin + imax) >>> 1;
252
253 if (imid == 0 || (incr[imid] >= v && incr[imid - 1] < v)) {
254 index = imid;
255 } else if (incr[imid] <= v) {
256 imin = imid + 1;
257 } else if (incr[imid] > v) {
258 imax = imid;
259 }
260 }
261
262 return index;
263 }
264
265 /**
266 * Perform a serial-search on the summed probability array.
267 */
268 static int indexOfSerial(final double[] incr, final double v) {
269 int index = -1;
270 for (int i = 0; i < incr.length && index == -1; ++i) {
271 if (incr[i] >= v) {
272 index = i;
273 }
274 }
275
276 return index;
277 }
278
279 /**
280 * In-place summation of the probability array.
281 */
282 static double[] incremental(final double[] values) {
283 final DoubleAdder adder = new DoubleAdder(values[0]);
284 for (int i = 1; i < values.length; ++i) {
285 values[i] = adder.add(values[i]).doubleValue();
286 }
287 return values;
288 }
289
290 }
|