001 /*
002 * Java Genetic Algorithm Library (jenetics-1.5.0).
003 * Copyright (c) 2007-2013 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.util.Objects.requireNonNull;
023 import static org.jenetics.util.object.hashCodeOf;
024
025 import org.jenetics.util.RandomRegistry;
026
027
028 /**
029 * {@code StochasticUniversalSelector} is a method for selecting a
030 * population according to some given probability in a way that minimize chance
031 * fluctuations. It can be viewed as a type of roulette game where now we have
032 * P equally spaced points which we spin.
033 *
034 * <p><div align="center">
035 * <img src="doc-files/StochasticUniversalSelection.svg" width="400" />
036 * </p></div>
037 *
038 * The figure above shows how the stochastic-universal selection works; <i>n</i>
039 * is the number of individuals to select.
040 *
041 * @see <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Stochastic_universal_sampling">
042 * Wikipedia: Stochastic universal sampling
043 * </a>
044 *
045 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
046 * @since 1.0
047 * @version 1.0 — <em>$Date: 2013-12-08 $</em>
048 */
049 public class StochasticUniversalSelector<
050 G extends Gene<?, G>,
051 N extends Number & Comparable<? super N>
052 >
053 extends RouletteWheelSelector<G, N>
054 {
055
056 public StochasticUniversalSelector() {
057 }
058
059 /**
060 * This method sorts the population in descending order while calculating the
061 * selection probabilities. (The method {@link Population#sort()} is called
062 * by this method.)
063 */
064 @Override
065 public Population<G, N> select(
066 final Population<G, N> population,
067 final int count,
068 final Optimize opt
069 ) {
070 requireNonNull(population, "Population");
071 if (count < 0) {
072 throw new IllegalArgumentException(
073 "Selection count must be greater or equal then zero, but was " +
074 count
075 );
076 }
077
078 final Population<G, N> selection = new Population<>(count);
079 if (count == 0) {
080 return selection;
081 }
082
083 final double[] probabilities = probabilities(population, count, opt);
084 assert (population.size() == probabilities.length);
085
086 //Calculating the equally spaces random points.
087 final double delta = 1.0/count;
088 final double[] points = new double[count];
089 points[0] = RandomRegistry.getRandom().nextDouble()*delta;
090 for (int i = 1; i < count; ++i) {
091 points[i] = delta*i;
092 }
093
094 int j = 0;
095 double prop = 0;
096 for (int i = 0; i < count; ++i) {
097 while (points[i] > prop) {
098 prop += probabilities[j];
099 ++j;
100 }
101 selection.add(population.get(j));
102 }
103
104 return selection;
105 }
106
107 @Override
108 protected double[] probabilities(
109 final Population<G, N> population,
110 final int count
111 ) {
112 population.sort();
113 return super.probabilities(population, count);
114 }
115
116 @Override
117 public int hashCode() {
118 return hashCodeOf(getClass()).and(super.hashCode()).value();
119 }
120
121 @Override
122 public boolean equals(final Object obj) {
123 return obj == this ||
124 obj != null && obj.getClass() == getClass() && super.equals(obj);
125 }
126
127 @Override
128 public String toString() {
129 return getClass().getSimpleName();
130 }
131
132 }
133
134
135
136
137
|