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