Limits.java
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 }