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