ProbabilitySelector.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-1.6.0).
003  * Copyright (c) 2007-2014 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.util.math.pow;
026 import static org.jenetics.util.math.statistics.sum;
027 import static org.jenetics.util.math.ulpDistance;
028 
029 import java.util.Random;
030 
031 import org.jenetics.util.Factory;
032 import org.jenetics.util.RandomRegistry;
033 
034 
035 /**
036  * Probability selectors are a variation of fitness proportional selectors and
037  * selects individuals from a given population based on it's selection
038  * probability <i>P(i)</i>.
039  <p><div align="center">
040  <img src="doc-files/FitnessProportionalSelection.svg" width="400" />
041  </p></div>
042  * Fitness proportional selection works as shown in the figure above. The
043  * runtime complexity of the implemented probability selectors is
044  <i>O(n+</i>log<i>(n))</i> instead of <i>O(n<sup>2</sup>)</i> as for the naive
045  * approach: <i>A binary (index) search is performed on the summed probability
046  * array.</i>
047  *
048  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
049  @since 1.0
050  @version 1.0 &mdash; <em>$Date: 2014-02-15 $</em>
051  */
052 public abstract class ProbabilitySelector<
053     extends Gene<?, G>,
054     extends Comparable<? super C>
055 >
056     implements Selector<G, C>
057 {
058     private static final long MAX_ULP_DISTANCE = pow(1010);
059 
060     protected ProbabilitySelector() {
061     }
062 
063     @Override
064     public Population<G, C> select(
065         final Population<G, C> population,
066         final int count,
067         final Optimize opt
068     ) {
069         requireNonNull(population, "Population");
070         requireNonNull(opt, "Optimization");
071         if (count < 0) {
072             throw new IllegalArgumentException(format(
073                 "Selection count must be greater or equal then zero, but was %s.",
074                 count
075             ));
076         }
077 
078         final Population<G, C> selection = new Population<>(count);
079 
080         if (count > 0) {
081             final double[] probabilities = probabilities(population, count, opt);
082             assert (population.size() == probabilities.length:
083                 "Population size and probability length are not equal.";
084             assert (sum2one(probabilities)) "Probabilities doesn't sum to one.";
085 
086             incremental(probabilities);
087             final Factory<Phenotype<G, C>> factory = factory(
088                 population, probabilities, RandomRegistry.getRandom()
089             );
090 
091             selection.fill(factory, count);
092             assert (count == selection.size());
093         }
094 
095         return selection;
096     }
097 
098     private static <
099         extends Gene<?, G>,
100         extends Comparable<? super C>
101     >
102     Factory<Phenotype<G, C>> factory(
103         final Population<G, C> population,
104         final double[] probabilities,
105         final Random random
106     ) {
107         return new Factory<Phenotype<G, C>>() {
108             @Override
109             public Phenotype<G, C> newInstance() {
110                 return select(population, probabilities, random);
111             }
112         };
113     }
114 
115     private static <
116         extends Gene<?, G>,
117         extends Comparable<? super C>
118     >
119     Phenotype<G, C> select(
120         final Population<G, C> population,
121         final double[] probabilities,
122         final Random random
123     ) {
124         final double value = random.nextDouble();
125         return population.get(indexOf(probabilities, value));
126     }
127 
128     /**
129      * This method takes the probabilities from the
130      {@link #probabilities(Population, int)} method and inverts it if needed.
131      *
132      @param population The population.
133      @param count The number of phenotypes to select.
134      @param opt Determines whether the individuals with higher fitness values
135      *        or lower fitness values must be selected. This parameter determines
136      *        whether the GA maximizes or minimizes the fitness function.
137      @return Probability array.
138      */
139     protected final double[] probabilities(
140         final Population<G, C> population,
141         final int count,
142         final Optimize opt
143     ) {
144         final double[] probabilities = probabilities(population, count);
145         if (opt == Optimize.MINIMUM) {
146             invert(probabilities);
147         }
148         return probabilities;
149     }
150 
151     private static void invert(final double[] probabilities) {
152         for (int i = 0; i < probabilities.length; ++i) {
153             probabilities[i1.0 - probabilities[i];
154         }
155     }
156 
157     /**
158      <p>
159      * Return an Probability array, which corresponds to the given Population.
160      * The probability array and the population must have the same size. The
161      * population is not sorted. If a subclass needs a sorted population, the
162      * subclass is responsible to sort the population.
163      </p>
164      * The implementor always assumes that higher fitness values are better. The
165      * base class inverts the probabilities ({@code p = 1.0 - p }) if the GA is
166      * supposed to minimize the fitness function.
167      *
168      @param population The <em>unsorted</em> population.
169      @param count The number of phenotypes to select. <i>This parameter is not
170      *         needed for most implementations.</i>
171      @return Probability array. The returned probability array must have the
172      *         length {@code population.size()} and <strong>must</strong> sum to
173      *         one. The returned value is checked with
174      *         {@code assert(Math.abs(math.sum(probabilities) - 1.0) < 0.0001)}
175      *         in the base class.
176      */
177     protected abstract double[] probabilities(
178         final Population<G, C> population,
179         final int count
180     );
181 
182     /**
183      * Check if the given probabilities sum to one.
184      *
185      @param probabilities the probabilities to check.
186      @return {@code true} if the sum of the probabilities are within the error
187      *          range, {@code false} otherwise.
188      */
189     static boolean sum2one(final double[] probabilities) {
190         final double sum = sum(probabilities);
191         return abs(ulpDistance(sum, 1.0)) < MAX_ULP_DISTANCE;
192     }
193 
194     /**
195      * Perform a binary-search on the summed probability array.
196      */
197     final static int indexOf(final double[] incremental, final double v) {
198         int imin = 0;
199         int imax = incremental.length;
200 
201         while (imax > imin) {
202             int imid = (imin + imax>>> 1;
203 
204             if (imid == 0) {
205                 return imid;
206             else if (incremental[imid>= v && incremental[imid - 1< v) {
207                 return imid;
208             else if (incremental[imid<= v) {
209                 imin = imid + 1;
210             else if (incremental[imid> v) {
211                 imax = imid;
212             }
213         }
214 
215         return incremental.length - 1;
216     }
217 
218     /**
219      * In-place summation of the probability array.
220      */
221     final static double[] incremental(final double[] values) {
222         for (int i = 1; i < values.length; ++i) {
223             values[i= values[i - 1+ values[i];
224         }
225         return values;
226     }
227 
228 }