001 /*
002 * Java Genetic Algorithm Library (jenetics-8.0.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 */
020 package io.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.Duration;
027 import java.time.InstantSource;
028 import java.util.concurrent.atomic.AtomicLong;
029 import java.util.function.BiPredicate;
030 import java.util.function.Predicate;
031
032 import io.jenetics.NumericGene;
033 import io.jenetics.stat.DoubleMoments;
034 import io.jenetics.util.NanoClock;
035
036 /**
037 * This class contains factory methods for creating predicates, which can be
038 * used for limiting the evolution stream. Some of the <em>limit</em> predicates
039 * have to maintain internal state for working properly. It is therefore
040 * recommended creating new instances for every stream and don't reuse it.
041 *
042 * @see EvolutionStream#limit(Predicate)
043 *
044 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
045 * @since 3.0
046 * @version 3.7
047 */
048 public final class Limits {
049 private Limits() {}
050
051 /**
052 * Return a predicate which always return {@code true}.
053 *
054 * @since 4.1
055 *
056 * @return a predicate which always return {@code true}
057 */
058 public static Predicate<Object> infinite() {
059 return result -> true;
060 }
061
062 /**
063 * Return a predicate, which will truncate the evolution stream after the
064 * given number of generations. The returned predicate behaves like a call
065 * of the {@link java.util.stream.Stream#limit(long)} and exists for
066 * <i>completeness</i> reasons.
067 *
068 * @implNote
069 * This predicate is mainly there for completion reason and behaves exactly
070 * as the {@link java.util.stream.Stream#limit(long)} function, except for
071 * the number of evaluations performed by the resulting stream. The evaluation
072 * of the population is {@code max generations + 1}. This is because the
073 * limiting predicate works on the {@link EvolutionResult} object, which
074 * guarantees to contain an evaluated population. That means that the
075 * population must be evaluated at least once, even for a generation limit
076 * of zero. If this is an unacceptable performance penalty, better use the
077 * {@link java.util.stream.Stream#limit(long)} function instead.
078 *
079 * @since 3.1
080 *
081 * @param generation the number of generations after the evolution stream is
082 * truncated
083 * @return a predicate which truncates the evolution stream after the given
084 * number of generations
085 * @throws java.lang.IllegalArgumentException if the given {@code generation}
086 * is smaller than zero.
087 */
088 public static Predicate<Object> byFixedGeneration(final long generation) {
089 if (generation < 0) {
090 throw new IllegalArgumentException(format(
091 "The number of generations must greater or equal than zero, " +
092 "but was %d",
093 generation
094 ));
095 }
096
097 return new Predicate<>() {
098 private final AtomicLong _current = new AtomicLong();
099 @Override
100 public boolean test(final Object o) {
101 return _current.incrementAndGet() <= generation;
102 }
103 };
104 }
105
106 /**
107 * Return a predicate, which will truncate the evolution stream if no
108 * better phenotype could be found after the given number of
109 * {@code generations}.
110 *
111 * {@snippet lang="java":
112 * final Phenotype<DoubleGene, Double> result = engine.stream()
113 * // Truncate the evolution stream after 5 "steady" generations.
114 * .limit(bySteadyFitness(5))
115 * // The evolution will stop after maximal 100 generations.
116 * .limit(100)
117 * .collect(toBestPhenotype());
118 * }
119 *
120 * @param generations the number of <i>steady</i> generations
121 * @param <C> the fitness type
122 * @return a predicate which truncate the evolution stream if no better
123 * phenotype could be found after a give number of
124 * {@code generations}
125 * @throws IllegalArgumentException if the generation is smaller than
126 * one.
127 */
128 public static <C extends Comparable<? super C>>
129 Predicate<EvolutionResult<?, C>> bySteadyFitness(final int generations) {
130 return new SteadyFitnessLimit<>(generations);
131 }
132
133 /**
134 * Return a predicate, which will truncate the evolution stream if the GA
135 * execution exceeds a given time duration. This predicate is (normally)
136 * used as a safety net, for guaranteed stream truncation.
137 *
138 * {@snippet lang="java":
139 * final Phenotype<DoubleGene, Double> result = engine.stream()
140 * // Truncate the evolution stream after 5 "steady" generations.
141 * .limit(bySteadyFitness(5))
142 * // The evolution will stop after maximal 500 ms.
143 * .limit(byExecutionTime(Duration.ofMillis(500), Clock.systemUTC()))
144 * .collect(toBestPhenotype());
145 * }
146 *
147 * @since 3.1
148 *
149 * @param duration the duration after the evolution stream will be truncated
150 * @param clock the clock used for measure the execution time
151 * @return a predicate, which will truncate the evolution stream, based on
152 * the exceeded execution time
153 * @throws NullPointerException if one of the arguments is {@code null}
154 */
155 public static Predicate<Object>
156 byExecutionTime(final Duration duration, final InstantSource clock) {
157 return new ExecutionTimeLimit(duration, clock);
158 }
159
160 /**
161 * Return a predicate, which will truncate the evolution stream if the GA
162 * execution exceeds a given time duration. This predicate is (normally)
163 * used as a safety net, for guaranteed stream truncation.
164 *
165 * {@snippet lang="java":
166 * final Phenotype<DoubleGene, Double> result = engine.stream()
167 * // Truncate the evolution stream after 5 "steady" generations.
168 * .limit(bySteadyFitness(5))
169 * // The evolution will stop after maximal 500 ms.
170 * .limit(byExecutionTime(Duration.ofMillis(500)))
171 * .collect(toBestPhenotype());
172 * }
173 *
174 * @since 3.1
175 *
176 * @param duration the duration after the evolution stream will be truncated
177 * @return a predicate, which will truncate the evolution stream, based on
178 * the exceeded execution time
179 * @throws NullPointerException if the evolution {@code duration} is
180 * {@code null}
181 */
182 public static Predicate<Object>
183 byExecutionTime(final Duration duration) {
184 return byExecutionTime(duration, NanoClock.systemUTC());
185 }
186
187 /**
188 * Return a predicate, which will truncated the evolution stream if the
189 * best fitness of the current population becomes less than the specified
190 * threshold, and the objective is set to minimize the fitness. This
191 * predicate also stops the evolution if the best fitness in the current
192 * population becomes greater than the user-specified fitness threshold when
193 * the objective is to maximize the fitness.
194 *
195 * {@snippet lang="java":
196 * final Phenotype<DoubleGene, Double> result = engine.stream()
197 * // Truncate the evolution stream if the best fitness is higher than
198 * // the given threshold of '2.3'.
199 * .limit(byFitnessThreshold(2.3))
200 * // The evolution will stop after maximal 250 generations; guarantees
201 * // the termination (truncation) of the evolution stream.
202 * .limit(250)
203 * .collect(toBestPhenotype());
204 * }
205 *
206 * @since 3.1
207 *
208 * @param threshold the desired threshold
209 * @param <C> the fitness type
210 * @return the predicate which truncates the evolution stream based on the
211 * given {@code threshold}.
212 * @throws NullPointerException if the given {@code threshold} is
213 * {@code null}.
214 */
215 public static <C extends Comparable<? super C>>
216 Predicate<EvolutionResult<?, C>> byFitnessThreshold(final C threshold) {
217 return new FitnessThresholdLimit<>(threshold);
218 }
219
220 /**
221 * Return a predicate, which will truncate the evolution stream if the
222 * fitness is converging. Two filters of different lengths are used to
223 * smooth the best fitness across the generations.
224 *
225 * {@snippet lang="java":
226 * final Phenotype<DoubleGene, Double> result = engine.stream()
227 * .limit(byFitnessConvergence(5, 15, (s, l) -> {
228 * final double div = max(abs(s.getMean()), abs(l.getMean()));
229 * final var eps = abs(s.getMean() - l.getMean())/(div <= 10E-20 ? 1.0 : div);
230 * return eps >= 10E-5;
231 * }))
232 * .collect(toBestPhenotype());
233 * }
234 *
235 * In the example above, the moving average of the short- and long filter
236 * is used for determining the fitness convergence.
237 *
238 * @apiNote The returned predicate maintains a mutable state.
239 * Using it in a parallel evolution streams needs external synchronization
240 * of the {@code test} method.
241 *
242 * @since 3.7
243 *
244 * @param shortFilterSize the size of the short filter
245 * @param longFilterSize the size of the long filter. The long filter size
246 * also determines the minimum number of generations of the evolution
247 * stream.
248 * @param proceed the predicate which determines when the evolution stream
249 * is truncated. The first parameter of the predicate contains the
250 * double statistics of the short filter, and the second parameter
251 * contains the statistics of the long filter
252 * @param <N> the fitness type
253 * @return a new fitness convergence strategy
254 * @throws NullPointerException if the {@code proceed} predicate is
255 * {@code null}
256 */
257 public static <N extends Number & Comparable<? super N>>
258 Predicate<EvolutionResult<?, N>> byFitnessConvergence(
259 final int shortFilterSize,
260 final int longFilterSize,
261 final BiPredicate<DoubleMoments, DoubleMoments> proceed
262 ) {
263 return new FitnessConvergenceLimit<>(
264 shortFilterSize,
265 longFilterSize,
266 proceed
267 );
268 }
269
270 /**
271 * Return a predicate, which will truncate the evolution stream if the
272 * fitness is converging. Two filters of different lengths are used to
273 * smooth the best fitness across the generations. When the smoothed best
274 * fitness from the long filter is less than a user-specified percentage
275 * away from the smoothed best fitness from the short filter, the fitness is
276 * deemed as converged and the evolution terminates.
277 *
278 * {@snippet lang="java":
279 * final Phenotype<DoubleGene, Double> result = engine.stream()
280 * .limit(byFitnessConvergence(5, 15, 10E-4))
281 * .collect(toBestPhenotype());
282 * }
283 *
284 * In the given example, the evolution stream stops, if the difference of the
285 * mean values of the long and short filter is less than 1%. The short
286 * filter calculates the mean of the best fitness values of the last 5
287 * generations. The long filter uses the best fitness values of the last 15
288 * generations.
289 *
290 * @apiNote The returned predicate maintains a mutable state.
291 * Using it in a parallel evolution streams needs external synchronization
292 * of the {@code test} method.
293 *
294 * @since 3.7
295 *
296 * @param shortFilterSize the size of the short filter
297 * @param longFilterSize the size of the long filter. The long filter size
298 * also determines the minimum number of generations of the evolution
299 * stream.
300 * @param epsilon the maximal relative distance of the mean value between
301 * the short and the long filter. The {@code epsilon} must within the
302 * range of {@code [0..1]}.
303 * @param <N> the fitness type
304 * @return a new fitness convergence strategy
305 * @throws IllegalArgumentException if {@code shortFilterSize < 1} ||
306 * {@code longFilterSize < 2} ||
307 * {@code shortFilterSize >= longFilterSize}
308 * @throws IllegalArgumentException if {@code epsilon} is not in the range
309 * of {@code [0..1]}
310 */
311 public static <N extends Number & Comparable<? super N>>
312 Predicate<EvolutionResult<?, N>> byFitnessConvergence(
313 final int shortFilterSize,
314 final int longFilterSize,
315 final double epsilon
316 ) {
317 if (epsilon < 0.0 || epsilon > 1.0) {
318 throw new IllegalArgumentException(format(
319 "The given epsilon is not in the range [0, 1]: %f", epsilon
320 ));
321 }
322
323 return new FitnessConvergenceLimit<>(
324 shortFilterSize,
325 longFilterSize,
326 (s, l) -> eps(s.mean(), l.mean()) >= epsilon
327 );
328 }
329
330 // Calculate the relative mean difference between short and long filter.
331 private static double eps(final double s, final double l) {
332 final double div = max(abs(s), abs(l));
333 return abs(s - l)/(div <= 10E-20 ? 1.0 : div);
334 }
335
336 /**
337 * A termination method that stops the evolution when the population is
338 * deemed as converged. The population is deemed as converged when the
339 * average fitness across the current population is less than a
340 * user-specified percentage away from the best fitness of the current
341 * population. This method takes a predicate with the <em>best</em> fitness
342 * and the population fitness moments and determine whether to proceed or
343 * not.
344 *
345 * @since 3.9
346 *
347 * @param proceed the predicate which determines when the evolution stream
348 * is truncated. The first parameter of the predicate contains the
349 * best fitness of the population, and the second parameter contains
350 * the statistics of population fitness values
351 * @param <N> the fitness type
352 * @return a new fitness convergence strategy
353 * @throws NullPointerException if the {@code proceed} predicate is
354 * {@code null}
355 */
356 public static <N extends Number & Comparable<? super N>>
357 Predicate<EvolutionResult<?, N>> byPopulationConvergence(
358 final BiPredicate<Double, DoubleMoments> proceed
359 ) {
360 return new PopulationConvergenceLimit<>(proceed);
361 }
362
363 /**
364 * A termination method that stops the evolution when the population is
365 * deemed as converged. The population is deemed as converged when the
366 * average fitness across the current population is less than a
367 * user-specified percentage away from the best fitness of the current
368 * population.
369 *
370 * @since 3.9
371 *
372 * @param epsilon the maximal relative distance of the best fitness value of
373 * the population and the mean value of the population fitness values.
374 * @param <N> the fitness type
375 * @return a new fitness convergence strategy
376 * @throws IllegalArgumentException if {@code epsilon} is not in the range
377 * of {@code [0..1]}
378 */
379 public static <N extends Number & Comparable<? super N>>
380 Predicate<EvolutionResult<?, N>>
381 byPopulationConvergence(final double epsilon) {
382 if (epsilon < 0.0 || epsilon > 1.0) {
383 throw new IllegalArgumentException(format(
384 "The given epsilon is not in the range [0, 1]: %f", epsilon
385 ));
386 }
387
388 return new PopulationConvergenceLimit<>((best, moments) ->
389 eps(best, moments.mean()) >= epsilon
390 );
391 }
392
393 /**
394 * A termination method that stops the evolution when a user-specified
395 * percentage of the genes ({@code convergedGeneRage}) that make up a
396 * {@code Genotype} are deemed as converged. A gene is deemed as converged,
397 * if the {@code geneConvergence} {@code Predicate<DoubleMoments>} for this
398 * gene returns {@code true}.
399 *
400 * @since 4.0
401 * @see #byGeneConvergence(double, double)
402 *
403 * @param geneConvergence predicate, which defines when a gene is deemed as
404 * converged, by using the statistics of this gene over all genotypes
405 * of the population
406 * @param convergedGeneRate the percentage of genes which must be converged
407 * for truncating the evolution stream
408 * @param <G> the gene type
409 * @return a new gene convergence predicate
410 * @throws NullPointerException if the given gene convergence predicate is
411 * {@code null}
412 * @throws IllegalArgumentException if the {@code convergedGeneRate} is not
413 * within the range {@code [0, 1]}
414 */
415 public static <G extends NumericGene<?, G>> Predicate<EvolutionResult<G, ?>>
416 byGeneConvergence(
417 final Predicate<DoubleMoments> geneConvergence,
418 final double convergedGeneRate
419 ) {
420 return new GeneConvergenceLimit<>(geneConvergence, convergedGeneRate);
421 }
422
423 /**
424 * A termination method that stops the evolution when a user-specified
425 * percentage of the genes ({@code convergedGeneRage}) that make up a
426 * {@code Genotype} are deemed as converged. A gene is deemed as converged
427 * when the average value of that gene across all the genotypes in the
428 * current population is less than a user-specified percentage
429 * ({@code convergenceRate}) away from the maximum gene value across the
430 * genotypes.
431 * <p>
432 * This method is equivalent to the following code snippet:
433 * {@snippet lang="java":
434 * final Predicate<EvolutionResult<DoubleGene, ?>> limit =
435 * byGeneConvergence(
436 * stat -> stat.getMax()*convergenceRate <= stat.getMean(),
437 * convergedGeneRate
438 * );
439 * }
440 *
441 * @since 4.0
442 * @see #byGeneConvergence(Predicate, double)
443 *
444 * @param convergenceRate the relative distance of the average gene value
445 * to its maximum value
446 * @param convergedGeneRate the percentage of genes which must be converged
447 * for truncating the evolution stream
448 * @param <G> the gene type
449 * @return a new gene convergence predicate
450 * @throws IllegalArgumentException if the {@code convergedGeneRate} or
451 * {@code convergenceRate} are not within the range {@code [0, 1]}
452 */
453 public static <G extends NumericGene<?, G>> Predicate<EvolutionResult<G, ?>>
454 byGeneConvergence(
455 final double convergenceRate,
456 final double convergedGeneRate
457 ) {
458 return byGeneConvergence(
459 stat -> stat.max()*convergenceRate <= stat.mean(),
460 convergedGeneRate
461 );
462 }
463
464 }
|