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