001 /*
002 * Java Genetic Algorithm Library (jenetics-3.0.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.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.0 — <em>$Date: 2014-12-28 $</em>
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 Function<double[], double[]> _reverter;
065
066 /**
067 * Create a new {@code ProbabilitySelector} with the given {@code sorting}
068 * flag. <em>This flag must set to {@code true} if the selector
069 * implementation is sorting the population in the
070 * {@link #probabilities(Population, int)} method.</em>
071 *
072 * @param sorted {@code true} if the implementation is sorting the
073 * population when calculating the selection probabilities,
074 * {@code false} otherwise.
075 */
076 protected ProbabilitySelector(final boolean sorted) {
077 _reverter = sorted ? array::revert : ProbabilitySelector::sortAndRevert;
078 }
079
080 /**
081 * Create a new selector with {@code sorted = false}.
082 */
083 protected ProbabilitySelector() {
084 this(false);
085 }
086
087 @Override
088 public Population<G, C> select(
089 final Population<G, C> population,
090 final int count,
091 final Optimize opt
092 ) {
093 requireNonNull(population, "Population");
094 requireNonNull(opt, "Optimization");
095 if (count < 0) {
096 throw new IllegalArgumentException(format(
097 "Selection count must be greater or equal then zero, but was %s.",
098 count
099 ));
100 }
101
102 final Population<G, C> selection = new Population<>(count);
103
104 if (count > 0) {
105 final double[] prob = probabilities(population, count, opt);
106 assert (population.size() == prob.length) :
107 "Population size and probability length are not equal.";
108 assert (sum2one(prob)) : "Probabilities doesn't sum to one.";
109
110 incremental(prob);
111
112 final Random random = RandomRegistry.getRandom();
113 selection.fill(
114 () -> population.get(indexOf(prob, random.nextDouble())),
115 count
116 );
117 }
118
119 return selection;
120 }
121
122 /**
123 * This method takes the probabilities from the
124 * {@link #probabilities(Population, int)} method and inverts it if needed.
125 *
126 * @param population The population.
127 * @param count The number of phenotypes to select.
128 * @param opt Determines whether the individuals with higher fitness values
129 * or lower fitness values must be selected. This parameter
130 * determines whether the GA maximizes or minimizes the fitness
131 * function.
132 * @return Probability array.
133 */
134 protected final double[] probabilities(
135 final Population<G, C> population,
136 final int count,
137 final Optimize opt
138 ) {
139 return requireNonNull(opt) == Optimize.MINIMUM ?
140 _reverter.apply(probabilities(population, count)) :
141 probabilities(population, count);
142 }
143
144 // Package private for testing.
145 static double[] sortAndRevert(final double[] array) {
146 final int[] indexes = sort(array);
147
148 // Copy the elements in reversed order.
149 final double[] result = new double[array.length];
150 for (int i = 0; i < result.length; ++i) {
151 result[indexes[result.length - 1 - i]] = array[indexes[i]];
152 }
153
154 return result;
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 implementer 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 = DoubleAdder.sum(probabilities);
191 return abs(ulpDistance(sum, 1.0)) < MAX_ULP_DISTANCE;
192 }
193
194 static int indexOf(final double[] incr, final double v) {
195 return incr.length <= SERIAL_INDEX_THRESHOLD ?
196 indexOfSerial(incr, v) :
197 indexOfBinary(incr, v);
198 }
199
200 /**
201 * Perform a binary-search on the summed probability array.
202 */
203 static int indexOfBinary(final double[] incr, final double v) {
204 int imin = 0;
205 int imax = incr.length;
206 int index = -1;
207
208 while (imax > imin && index == -1) {
209 final int imid = (imin + imax) >>> 1;
210
211 if (imid == 0 || (incr[imid] >= v && incr[imid - 1] < v)) {
212 index = imid;
213 } else if (incr[imid] <= v) {
214 imin = imid + 1;
215 } else if (incr[imid] > v) {
216 imax = imid;
217 }
218 }
219
220 return index;
221 }
222
223 /**
224 * Perform a serial-search on the summed probability array.
225 */
226 static int indexOfSerial(final double[] incr, final double v) {
227 int index = -1;
228 for (int i = 0; i < incr.length && index == -1; ++i) {
229 if (incr[i] >= v) {
230 index = i;
231 }
232 }
233
234 return index;
235 }
236
237 /**
238 * In-place summation of the probability array.
239 */
240 static double[] incremental(final double[] values) {
241 for (int i = 1; i < values.length; ++i) {
242 values[i] = values[i - 1] + values[i];
243 }
244 return values;
245 }
246
247 }
|