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