ProbabilitySelector.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-3.7.0).
003  * Copyright (c) 2007-2016 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     extends Gene<?, G>,
056     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(1010);
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 > && !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 - - 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 >= && 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 == || (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 }