StochasticUniversalSelector.java
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 &mdash; <em>$Date: 2013-12-08 $</em>
048  */
049 public class StochasticUniversalSelector<
050     extends Gene<?, G>,
051     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