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