001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 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@gmail.com)
019 */
020package io.jenetics;
021
022import static java.lang.String.format;
023import static java.util.Objects.requireNonNull;
024
025import java.util.Comparator;
026import java.util.random.RandomGenerator;
027import java.util.stream.Stream;
028
029import io.jenetics.util.ISeq;
030import io.jenetics.util.MSeq;
031import io.jenetics.util.RandomRegistry;
032import io.jenetics.util.Seq;
033
034/**
035 * In tournament selection the best individual from a random sample of <i>s</i>
036 * individuals is chosen from the population <i>P<sub>g</sub></i>. The samples
037 * are drawn with replacement. An individual will win a tournament only if its
038 * fitness is greater than the fitness of the other <i>s-1</i>  competitors.
039 * Note that the worst individual never survives, and the best individual wins
040 * in all the tournaments it participates. The selection pressure can be varied
041 * by changing the tournament size <i>s</i> . For large values of <i>s</i>, weak
042 * individuals have less chance being selected.
043 *
044 * @see <a href="http://en.wikipedia.org/wiki/Tournament_selection">Tournament selection</a>
045 *
046 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
047 * @since 1.0
048 * @version 6.0
049 */
050public class TournamentSelector<
051        G extends Gene<?, G>,
052        C extends Comparable<? super C>
053>
054        implements Selector<G, C>
055{
056
057        private final Comparator<? super Phenotype<G, C>> _comparator;
058        private final int _sampleSize;
059
060        /**
061         * Create a tournament selector with the give {@code comparator} and
062         * sample size. The sample size must be greater than one.
063         *
064         * @since 6.0
065         *
066         * @param comparator the comparator use for comparing two individuals during
067         *        a tournament
068         * @param sampleSize the number of individuals involved in one tournament
069         * @throws IllegalArgumentException if the sample size is smaller than two
070         * @throws NullPointerException if the given {@code comparator} is
071         *         {@code null}
072         */
073        public TournamentSelector(
074                final Comparator<? super Phenotype<G, C>> comparator,
075                final int sampleSize
076        ) {
077                _comparator = requireNonNull(comparator);
078                if (sampleSize < 2) {
079                        throw new IllegalArgumentException(
080                                "Sample size must be greater than one, but was " + sampleSize
081                        );
082                }
083                _sampleSize = sampleSize;
084        }
085
086        /**
087         * Create a tournament selector with the give sample size. The sample size
088         * must be greater than one.
089         *
090         * @param sampleSize the number of individuals involved in one tournament
091         * @throws IllegalArgumentException if the sample size is smaller than two.
092         */
093        public TournamentSelector(final int sampleSize) {
094                this(Phenotype::compareTo, sampleSize);
095        }
096
097        /**
098         * Create a tournament selector with sample size two.
099         */
100        public TournamentSelector() {
101                this(Phenotype::compareTo,2);
102        }
103
104        /**
105         * Return the sample size of the tournament selector.
106         *
107         * @since 5.0
108         *
109         * @return the sample size of the tournament selector
110         */
111        public int sampleSize() {
112                return _sampleSize;
113        }
114
115        @Override
116        public ISeq<Phenotype<G, C>> select(
117                final Seq<Phenotype<G, C>> population,
118                final int count,
119                final Optimize opt
120        ) {
121                requireNonNull(population, "Population");
122                requireNonNull(opt, "Optimization");
123                if (count < 0) {
124                        throw new IllegalArgumentException(format(
125                                "Selection count must be greater or equal then zero, but was %s",
126                                count
127                        ));
128                }
129
130                final var random = RandomRegistry.random();
131                return population.isEmpty()
132                        ? ISeq.empty()
133                        : MSeq.<Phenotype<G, C>>ofLength(count)
134                                .fill(() -> select(population, opt, random))
135                                .toISeq();
136        }
137
138        private Phenotype<G, C> select(
139                final Seq<Phenotype<G, C>> population,
140                final Optimize opt,
141                final RandomGenerator random
142        ) {
143                final int N = population.size();
144
145                assert _sampleSize >= 2;
146                assert N >= 1;
147
148                final Comparator<? super Phenotype<G, C>> cmp = opt == Optimize.MAXIMUM
149                        ? _comparator
150                        : _comparator.reversed();
151
152                return Stream.generate(() -> population.get(random.nextInt(N)))
153                        .limit(_sampleSize)
154                        .max(cmp)
155                        .orElseThrow(AssertionError::new);
156        }
157
158        @Override
159        public String toString() {
160                return format("%s[s=%d]", getClass().getSimpleName(), _sampleSize);
161        }
162
163}