001 /*
002 * Java Genetic Algorithm Library (jenetics-3.9.0).
003 * Copyright (c) 2007-2017 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.engine;
021
022 import static java.lang.Math.abs;
023 import static java.lang.Math.max;
024 import static java.lang.String.format;
025
026 import java.time.Clock;
027 import java.time.Duration;
028 import java.util.concurrent.atomic.AtomicLong;
029 import java.util.function.BiPredicate;
030 import java.util.function.Predicate;
031
032 import org.jenetics.internal.util.require;
033
034 import org.jenetics.stat.DoubleMoments;
035 import org.jenetics.util.NanoClock;
036
037 /**
038 * This class contains factory methods for creating predicates, which can be
039 * used for limiting the evolution stream. Some of the <em>limit</em> predicates
040 * have to maintain internal state for working properly. It is therefor
041 * recommended to create new instances for every stream and don't reuse it.
042 *
043 * @see EvolutionStream#limit(Predicate)
044 *
045 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
046 * @since 3.0
047 * @version 3.7
048 */
049 public final class limit {
050 private limit() {require.noInstance();}
051
052 /**
053 * Return a predicate, which will truncate the evolution stream after the
054 * given number of generations. The returned predicate behaves like a call
055 * of the {@link java.util.stream.Stream#limit(long)} and exists for
056 * <i>completeness</i> reasons.
057 *
058 * @since 3.1
059 *
060 * @param generation the number of generations after the evolution stream is
061 * truncated
062 * @return a predicate which truncates the evolution stream after the given
063 * number of generations
064 * @throws java.lang.IllegalArgumentException if the given {@code generation}
065 * is smaller than zero.
066 */
067 public static Predicate<Object> byFixedGeneration(final long generation) {
068 if (generation < 0) {
069 throw new IllegalArgumentException(format(
070 "The number of generations must greater than one, but was %d",
071 generation
072 ));
073 }
074
075 return new Predicate<Object>() {
076 private final AtomicLong _current = new AtomicLong();
077 @Override
078 public boolean test(final Object o) {
079 return _current.incrementAndGet() < generation;
080 }
081 };
082 }
083
084 /**
085 * Return a predicate, which will truncate the evolution stream if no
086 * better phenotype could be found after the given number of
087 * {@code generations}.
088 *
089 * <pre>{@code
090 * final Phenotype<DoubleGene, Double> result = engine.stream()
091 * // Truncate the evolution stream after 5 "steady" generations.
092 * .limit(bySteadyFitness(5))
093 * // The evolution will stop after maximal 100 generations.
094 * .limit(100)
095 * .collect(toBestPhenotype());
096 * }</pre>
097 *
098 * @param generations the number of <i>steady</i> generations
099 * @param <C> the fitness type
100 * @return a predicate which truncate the evolution stream if no better
101 * phenotype could be found after a give number of
102 * {@code generations}
103 * @throws IllegalArgumentException if the generation is smaller than
104 * one.
105 */
106 public static <C extends Comparable<? super C>>
107 Predicate<EvolutionResult<?, C>> bySteadyFitness(final int generations) {
108 return new SteadyFitnessLimit<>(generations);
109 }
110
111 /**
112 * Return a predicate, which will truncate the evolution stream if the GA
113 * execution exceeds a given time duration. This predicate is (normally)
114 * used as safety net, for guaranteed stream truncation.
115 *
116 * <pre>{@code
117 * final Phenotype<DoubleGene, Double> result = engine.stream()
118 * // Truncate the evolution stream after 5 "steady" generations.
119 * .limit(bySteadyFitness(5))
120 * // The evolution will stop after maximal 500 ms.
121 * .limit(byExecutionTime(Duration.ofMillis(500), Clock.systemUTC())
122 * .collect(toBestPhenotype());
123 * }</pre>
124 *
125 * @since 3.1
126 *
127 * @param duration the duration after the evolution stream will be truncated
128 * @param clock the clock used for measure the execution time
129 * @return a predicate, which will truncate the evolution stream, based on
130 * the exceeded execution time
131 * @throws NullPointerException if one of the arguments is {@code null}
132 */
133 public static Predicate<Object>
134 byExecutionTime(final Duration duration, final Clock clock) {
135 return new ExecutionTimeLimit(duration, clock);
136 }
137
138 /**
139 * Return a predicate, which will truncate the evolution stream if the GA
140 * execution exceeds a given time duration. This predicate is (normally)
141 * used as safety net, for guaranteed stream truncation.
142 *
143 * <pre>{@code
144 * final Phenotype<DoubleGene, Double> result = engine.stream()
145 * // Truncate the evolution stream after 5 "steady" generations.
146 * .limit(bySteadyFitness(5))
147 * // The evolution will stop after maximal 500 ms.
148 * .limit(byExecutionTime(Duration.ofMillis(500))
149 * .collect(toBestPhenotype());
150 * }</pre>
151 *
152 * @since 3.1
153 *
154 * @param duration the duration after the evolution stream will be truncated
155 * @return a predicate, which will truncate the evolution stream, based on
156 * the exceeded execution time
157 * @throws NullPointerException if the evolution {@code duration} is
158 * {@code null}
159 */
160 public static Predicate<Object>
161 byExecutionTime(final Duration duration) {
162 return byExecutionTime(duration, NanoClock.systemUTC());
163 }
164
165 /**
166 * Return a predicate, which will truncated the evolution stream if the
167 * best fitness of the current population becomes less than the specified
168 * threshold and the objective is set to minimize the fitness. This
169 * predicate also stops the evolution if the best fitness in the current
170 * population becomes greater than the user-specified fitness threshold when
171 * the objective is to maximize the fitness.
172 *
173 * <pre>{@code
174 * final Phenotype<DoubleGene, Double> result = engine.stream()
175 * // Truncate the evolution stream if the best fitness is higher than
176 * // the given threshold of '2.3'.
177 * .limit(byFitnessThreshold(2.3))
178 * // The evolution will stop after maximal 250 generations; guarantees
179 * // the termination (truncation) of the evolution stream.
180 * .limit(250)
181 * .collect(toBestPhenotype());
182 * }</pre>
183 *
184 * @since 3.1
185 *
186 * @param threshold the desired threshold
187 * @param <C> the fitness type
188 * @return the predicate which truncates the evolution stream based on the
189 * given {@code threshold}.
190 * @throws NullPointerException if the given {@code threshold} is
191 * {@code null}.
192 */
193 public static <C extends Comparable<? super C>>
194 Predicate<EvolutionResult<?, C>> byFitnessThreshold(final C threshold) {
195 return new FitnessThresholdLimit<>(threshold);
196 }
197
198 /**
199 * Return a predicate, which will truncate the evolution stream if the
200 * fitness is converging. Two filters of different lengths are used to
201 * smooth the best fitness across the generations.
202 *
203 * <pre>{@code
204 * final Phenotype<DoubleGene, Double> result = engine.stream()
205 * .limit(byFitnessConvergence(5, 15, (s, l) -> {
206 * final double div = max(abs(s.getMean()), abs(l.getMean()));
207 * final eps = abs(s.getMean() - l.getMean())/(div <= 10E-20 ? 1.0 : div);
208 * return esp >= 10E-5
209 * }))
210 * .collect(toBestPhenotype());
211 * }</pre>
212 *
213 * In the example above, the moving average of the short- and long filter
214 * is used for determining the fitness convergence.
215 *
216 * <p>
217 * <b>API note: </b><em>The returned predicate maintains mutable state.
218 * Using it in a parallel evolution streams needs external synchronization
219 * of the {@code test} method.</em>
220 *
221 * @since 3.7
222 *
223 * @param shortFilterSize the size of the short filter
224 * @param longFilterSize the size of the long filter. The long filter size
225 * also determines the minimum number of generations of the evolution
226 * stream.
227 * @param proceed the predicate which determines when the evolution stream
228 * is truncated. The first parameter of the predicate contains the
229 * double statistics of the short filter and the second parameter
230 * contains the statistics of the long filter
231 * @param <N> the fitness type
232 * @return a new fitness convergence strategy
233 * @throws NullPointerException if the {@code proceed} predicate is
234 * {@code null}
235 */
236 public static <N extends Number & Comparable<? super N>>
237 Predicate<EvolutionResult<?, N>> byFitnessConvergence(
238 final int shortFilterSize,
239 final int longFilterSize,
240 final BiPredicate<DoubleMoments, DoubleMoments> proceed
241 ) {
242 return new FitnessConvergenceLimit<>(
243 shortFilterSize,
244 longFilterSize,
245 proceed
246 );
247 }
248
249 /**
250 * Return a predicate, which will truncate the evolution stream if the
251 * fitness is converging. Two filters of different lengths are used to
252 * smooth the best fitness across the generations. When the smoothed best
253 * fitness from the long filter is less than a user-specified percentage
254 * away from the smoothed best fitness from the short filter, the fitness is
255 * deemed as converged and the evolution terminates.
256 *
257 * <pre>{@code
258 * final Phenotype<DoubleGene, Double> result = engine.stream()
259 * .limit(byFitnessConvergence(5, 15, 10E-4))
260 * .collect(toBestPhenotype());
261 * }</pre>
262 *
263 * In the given example, the evolution stream stops, if the difference of the
264 * mean values of the long and short filter is less than 1%. The short
265 * filter calculates the mean of the best fitness values of the last 5
266 * generations. The long filter uses the best fitness values of the last 15
267 * generations.
268 *
269 * <p>
270 * <b>API note: </b><em>The returned predicate maintains mutable state.
271 * Using it in a parallel evolution streams needs external synchronization
272 * of the {@code test} method.</em>
273 *
274 * @since 3.7
275 *
276 * @param shortFilterSize the size of the short filter
277 * @param longFilterSize the size of the long filter. The long filter size
278 * also determines the minimum number of generations of the evolution
279 * stream.
280 * @param epsilon the maximal relative distance of the mean value between
281 * the short and the long filter. The {@code epsilon} must within the
282 * range of {@code [0..1]}.
283 * @param <N> the fitness type
284 * @return a new fitness convergence strategy
285 * @throws IllegalArgumentException if {@code shortFilterSize < 1} ||
286 * {@code longFilterSize < 2} ||
287 * {@code shortFilterSize >= longFilterSize}
288 * @throws IllegalArgumentException if {@code epsilon} is not in the range
289 * of {@code [0..1]}
290 */
291 public static <N extends Number & Comparable<? super N>>
292 Predicate<EvolutionResult<?, N>> byFitnessConvergence(
293 final int shortFilterSize,
294 final int longFilterSize,
295 final double epsilon
296 ) {
297 if (epsilon < 0.0 || epsilon > 1.0) {
298 throw new IllegalArgumentException(format(
299 "The given epsilon is not in the range [0, 1]: %f", epsilon
300 ));
301 }
302
303 return new FitnessConvergenceLimit<>(
304 shortFilterSize,
305 longFilterSize,
306 (s, l) -> eps(s.getMean(), l.getMean()) >= epsilon
307 );
308 }
309
310 // Calculate the relative mean difference between short and long filter.
311 private static double eps(final double s, final double l) {
312 final double div = max(abs(s), abs(l));
313 return abs(s - l)/(div <= 10E-20 ? 1.0 : div);
314 }
315
316 /**
317 * A termination method that stops the evolution when the population is
318 * deemed as converged. The population is deemed as converged when the
319 * average fitness across the current population is less than a
320 * user-specified percentage away from the best fitness of the current
321 * population. This method takes a predicate with the <em>best</em> fitness
322 * and the population fitness moments and determine whether to proceed or
323 * not.
324 *
325 * @since 3.9
326 *
327 * @param proceed the predicate which determines when the evolution stream
328 * is truncated. The first parameter of the predicate contains the
329 * best fitness of the population and the second parameter contains
330 * the statistics of population fitness values
331 * @param <N> the fitness type
332 * @return a new fitness convergence strategy
333 * @throws NullPointerException if the {@code proceed} predicate is
334 * {@code null}
335 */
336 public static <N extends Number & Comparable<? super N>>
337 Predicate<EvolutionResult<?, N>> byPopulationConvergence(
338 final BiPredicate<Double, DoubleMoments> proceed
339 ) {
340 return new PopulationConvergenceLimit<>(proceed);
341 }
342
343 /**
344 * A termination method that stops the evolution when the population is
345 * deemed as converged. The population is deemed as converged when the
346 * average fitness across the current population is less than a
347 * user-specified percentage away from the best fitness of the current
348 * population.
349 *
350 * @since 3.9
351 *
352 * @param epsilon the maximal relative distance of the best fitness value of
353 * the population and the mean value of the population fitness values.
354 * @param <N> the fitness type
355 * @return a new fitness convergence strategy
356 * @throws IllegalArgumentException if {@code epsilon} is not in the range
357 * of {@code [0..1]}
358 */
359 public static <N extends Number & Comparable<? super N>>
360 Predicate<EvolutionResult<?, N>>
361 byPopulationConvergence(final double epsilon) {
362 if (epsilon < 0.0 || epsilon > 1.0) {
363 throw new IllegalArgumentException(format(
364 "The given epsilon is not in the range [0, 1]: %f", epsilon
365 ));
366 }
367
368 return new PopulationConvergenceLimit<>((best, moments) ->
369 eps(best, moments.getMean()) >= epsilon
370 );
371 }
372
373
374 }
|