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