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 — <em>$Date: 2014-02-15 $</em>
051 */
052 public abstract class ProbabilitySelector<
053 G extends Gene<?, G>,
054 C extends Comparable<? super C>
055 >
056 implements Selector<G, C>
057 {
058 private static final long MAX_ULP_DISTANCE = pow(10, 10);
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 G extends Gene<?, G>,
100 C 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 G extends Gene<?, G>,
117 C 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[i] = 1.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 }
|