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 }
|