001/*
002 * Java Genetic Algorithm Library (jenetics-7.1.0).
003 * Copyright (c) 2007-2022 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.Math.max;
023import static java.lang.Math.min;
024import static java.lang.String.format;
025import static java.util.Objects.requireNonNull;
026
027import io.jenetics.internal.util.Requires;
028import io.jenetics.util.ISeq;
029import io.jenetics.util.Seq;
030
031/**
032 * The {@code EliteSelector} copies a small proportion of the fittest candidates,
033 * without changes, into the next generation. This may have a dramatic impact on
034 * performance by ensuring that the GA doesn't waste time re-discovering
035 * previously refused partial solutions. Individuals that are preserved through
036 * elitism remain eligible for selection as parents of the next generation.
037 * Elitism is also related with memory: remember the best solution found so far.
038 * A problem with elitism is that it may causes the GA to converge to a local
039 * optimum, so pure elitism is a race to the nearest local optimum.
040 *
041 * <pre>{@code
042 * final Selector<DoubleGene, Double> selector = new EliteSelector<>(
043 *     // Number of best individuals preserved for next generation: elites
044 *     3,
045 *     // Selector used for selecting rest of population.
046 *     new RouletteWheelSelector<>()
047 * );
048 * }</pre>
049 *
050 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
051 * @version 5.0
052 * @since 4.0
053 */
054public class EliteSelector<
055        G extends Gene<?, G>,
056        C extends Comparable<? super C>
057>
058        implements Selector<G, C>
059{
060        private final TruncationSelector<G, C>
061        ELITE_SELECTOR = new TruncationSelector<>();
062
063        private final Selector<G, C> _nonEliteSelector;
064        private final int _eliteCount;
065
066        /**
067         * Create a new elite selector with the desired number of elites to be
068         * selected and the selector used for selecting the rest of the population.
069         *
070         * @param eliteCount the desired number of elite individual to be selected
071         * @param nonEliteSelector the selector used for selecting the rest of the
072         *        population
073         * @throws IllegalArgumentException if {@code eliteCount < 1}
074         * @throws NullPointerException if the {@code nonEliteSelector} is
075         *         {@code null}
076         */
077        public EliteSelector(
078                final int eliteCount,
079                final Selector<G, C> nonEliteSelector
080        ) {
081                _eliteCount = Requires.positive(eliteCount);
082                _nonEliteSelector = requireNonNull(nonEliteSelector);
083        }
084
085        /**
086         * Create a new elite selector with the desired number of elites to be
087         * selected. The selector for selecting the rest of the population is
088         * initialized with {@code TournamentSelector<>(3)}.
089         *
090         * @see TournamentSelector
091         *
092         * @param eliteCount the desired number of elite individual to be selected
093         * @throws IllegalArgumentException if {@code eliteCount < 1}
094         */
095        public EliteSelector(final int eliteCount) {
096                this(eliteCount, new TournamentSelector<>(3));
097        }
098
099        /**
100         * Create a new elite selector with selector used for selecting the rest of
101         * the population. The elite count is set to 1.
102         *
103         * @see TournamentSelector
104         *
105         * @param nonEliteSelector the selector used for selecting the rest of the
106         *        population
107         * @throws NullPointerException if the {@code nonEliteSelector} is
108         *         {@code null}
109         */
110        public EliteSelector(final Selector<G, C> nonEliteSelector) {
111                this(1, nonEliteSelector);
112        }
113
114        /**
115         * Create a new elite selector with elite count 1 and the selector for
116         * selecting the rest of the population is initialized with
117         * {@code TournamentSelector<>(3)}
118         */
119        public EliteSelector() {
120                this(1, new TournamentSelector<>(3));
121        }
122
123        @Override
124        public ISeq<Phenotype<G, C>> select(
125                final Seq<Phenotype<G, C>> population,
126                final int count,
127                final Optimize opt
128        ) {
129                if (count < 0) {
130                        throw new IllegalArgumentException(format(
131                                "Selection count must be greater or equal then zero, but was %s.",
132                                count
133                        ));
134                }
135
136                ISeq<Phenotype<G, C>> result;
137                if (population.isEmpty() || count <= 0) {
138                        result = ISeq.empty();
139                } else {
140                        final int ec = min(count, _eliteCount);
141                        result = ELITE_SELECTOR.select(population, ec, opt);
142                        result = result.append(
143                                _nonEliteSelector.select(population, max(0, count - ec), opt)
144                        );
145                }
146
147                return result;
148        }
149
150        @Override
151        public String toString() {
152                return format("EliteSelector[%d, %s]", _eliteCount, _nonEliteSelector);
153        }
154
155}