TournamentSelector.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.lang.String.format;
023 import static java.util.Objects.requireNonNull;
024 import static org.jenetics.util.object.hashCodeOf;
025 
026 import java.util.Random;
027 
028 import org.jenetics.util.Factory;
029 import org.jenetics.util.RandomRegistry;
030 
031 /**
032  * In tournament selection the best individual from a random sample of <i>s</i>
033  * individuals is chosen from the population <i>P<sub>g</sub></i>. The samples
034  * are drawn with replacement. An individual will win a tournament only if its
035  * fitness is greater than the fitness of the other <i>s-1</i>  competitors.
036  * Note that the worst individual never survives, and the best individual wins
037  * in all the tournaments it participates. The selection pressure can be varied
038  * by changing the tournament size <i>s</i> . For large values of <i>s</i>, weak
039  * individuals have less chance being selected.
040  *
041  @see <a href="http://en.wikipedia.org/wiki/Tournament_selection">Tournament selection</a>
042  *
043  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
044  @since 1.0
045  @version 1.0 &mdash; <em>$Date: 2013-08-30 $</em>
046  */
047 public class TournamentSelector<
048     extends Gene<?, G>,
049     extends Comparable<? super C>
050 >
051     implements Selector<G, C>
052 {
053 
054     private final int _sampleSize;
055 
056     /**
057      * Create a tournament selector with the give sample size. The sample size
058      * must be greater than one.
059      *
060      @throws IllegalArgumentException if the sample size is smaller than two.
061      */
062     public TournamentSelector(final int sampleSize) {
063         if (sampleSize < 2) {
064             throw new IllegalArgumentException(
065                 "Sample size must be greater than one, but was " + sampleSize
066             );
067         }
068         _sampleSize = sampleSize;
069     }
070 
071     /**
072      * Create a tournament selector with sample size two.
073      */
074     public TournamentSelector() {
075         this(2);
076     }
077 
078     /**
079      @throws IllegalArgumentException if the sample size is greater than the
080      *         population size or {@code count} is greater the the population
081      *         size or the _sampleSize is greater the the population size.
082      @throws NullPointerException if the {@code population} is {@code null}.
083      */
084     @Override
085     public Population<G, C> select(
086         final Population<G, C> population,
087         final int count,
088         final Optimize opt
089     ) {
090         requireNonNull(population, "Population");
091         requireNonNull(opt, "Optimization");
092         if (count < 0) {
093             throw new IllegalArgumentException(format(
094                 "Selection count must be greater or equal then zero, but was %s",
095                 count
096             ));
097         }
098         if (count > population.size()) {
099             throw new IllegalArgumentException(format(
100                 "Selection size greater than population size: %s > %s",
101                 count, population.size()
102             ));
103         }
104         if (_sampleSize > population.size()) {
105             throw new IllegalArgumentException(format(
106                 "Tournament size is greater than the population size! %d > %d.",
107                  _sampleSize, population.size()
108             ));
109         }
110 
111         final Population<G, C> pop = new Population<>(count);
112         final Factory<Phenotype<G, C>> factory = factory(
113             population, opt, _sampleSize, RandomRegistry.getRandom()
114         );
115 
116         return pop.fill(factory, count);
117     }
118 
119     private static <
120         extends Gene<?, G>,
121         extends Comparable<? super C>
122     >
123     Factory<Phenotype<G, C>> factory(
124         final Population<G, C> population,
125         final Optimize opt,
126         final int sampleSize,
127         final Random random
128     ) {
129         return new Factory<Phenotype<G, C>>() {
130             @Override
131             public Phenotype<G, C> newInstance() {
132                 return select(population, opt, sampleSize, random);
133             }
134         };
135     }
136 
137     private static <
138         extends Gene<?, G>,
139         extends Comparable<? super C>
140     >
141     Phenotype<G, C> select(
142         final Population<G, C> population,
143         final Optimize opt,
144         final int sampleSize,
145         final Random random
146     ) {
147         final int N = population.size();
148         Phenotype<G, C> winner = population.get(random.nextInt(N));
149 
150         for (int j = 0; j < sampleSize; ++j) {
151             final Phenotype<G, C> selection = population.get(random.nextInt(N));
152             if (opt.compare(selection, winner0) {
153                 winner = selection;
154             }
155         }
156         assert (winner != null);
157 
158         return winner;
159     }
160 
161     @Override
162     public int hashCode() {
163         return hashCodeOf(getClass()).and(_sampleSize).value();
164     }
165 
166     @Override
167     public boolean equals(final Object obj) {
168         if (obj == this) {
169             return true;
170         }
171         if (obj == null || obj.getClass() != getClass()) {
172             return false;
173         }
174 
175         final TournamentSelector<?, ?> selector = (TournamentSelector<?, ?>)obj;
176         return _sampleSize == selector._sampleSize;
177     }
178 
179     public static <SG extends Gene<?, SG>, SC extends Comparable<SC>>
180     TournamentSelector<SG, SC> valueOf(final int sampleSize) {
181         return new TournamentSelector<>(sampleSize);
182     }
183 
184     public static <SG extends Gene<?, SG>, SC extends Comparable<SC>>
185     TournamentSelector<SG, SC> valueOf() {
186         return new TournamentSelector<>();
187     }
188 
189     @Override
190     public String toString() {
191         return format("%s[s=%d]", getClass().getSimpleName(), _sampleSize);
192     }
193 
194 }
195 
196 
197 
198