limit.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-3.9.0).
003  * Copyright (c) 2007-2017 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@gmx.at)
019  */
020 package org.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 org.jenetics.internal.util.require;
033 
034 import org.jenetics.stat.DoubleMoments;
035 import org.jenetics.util.NanoClock;
036 
037 /**
038  * This class contains factory methods for creating predicates, which can be
039  * used for limiting the evolution stream. Some of the <em>limit</em> predicates
040  * have to maintain internal state for working properly. It is therefor
041  * recommended to create new instances for every stream and don't reuse it.
042  *
043  @see EvolutionStream#limit(Predicate)
044  *
045  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
046  @since 3.0
047  @version 3.7
048  */
049 public final class limit {
050     private limit() {require.noInstance();}
051 
052     /**
053      * Return a predicate, which will truncate the evolution stream after the
054      * given number of generations. The returned predicate behaves like a call
055      * of the {@link java.util.stream.Stream#limit(long)} and exists for
056      <i>completeness</i> reasons.
057      *
058      @since 3.1
059      *
060      @param generation the number of generations after the evolution stream is
061      *        truncated
062      @return a predicate which truncates the evolution stream after the given
063      *        number of generations
064      @throws java.lang.IllegalArgumentException if the given {@code generation}
065      *         is smaller than zero.
066      */
067     public static Predicate<Object> byFixedGeneration(final long generation) {
068         if (generation < 0) {
069             throw new IllegalArgumentException(format(
070                 "The number of generations must greater than one, but was %d",
071                 generation
072             ));
073         }
074 
075         return new Predicate<Object>() {
076             private final AtomicLong _current = new AtomicLong();
077             @Override
078             public boolean test(final Object o) {
079                 return _current.incrementAndGet() < generation;
080             }
081         };
082     }
083 
084     /**
085      * Return a predicate, which will truncate the evolution stream if no
086      * better phenotype could be found after the given number of
087      * {@code generations}.
088      *
089      <pre>{@code
090      * final Phenotype<DoubleGene, Double> result = engine.stream()
091      *      // Truncate the evolution stream after 5 "steady" generations.
092      *     .limit(bySteadyFitness(5))
093      *      // The evolution will stop after maximal 100 generations.
094      *     .limit(100)
095      *     .collect(toBestPhenotype());
096      * }</pre>
097      *
098      @param generations the number of <i>steady</i> generations
099      @param <C> the fitness type
100      @return a predicate which truncate the evolution stream if no better
101      *         phenotype could be found after a give number of
102      *         {@code generations}
103      @throws IllegalArgumentException if the generation is smaller than
104      *         one.
105      */
106     public static <C extends Comparable<? super C>>
107     Predicate<EvolutionResult<?, C>> bySteadyFitness(final int generations) {
108         return new SteadyFitnessLimit<>(generations);
109     }
110 
111     /**
112      * Return a predicate, which will truncate the evolution stream if the GA
113      * execution exceeds a given time duration. This predicate is (normally)
114      * used as safety net, for guaranteed stream truncation.
115      *
116      <pre>{@code
117      * final Phenotype<DoubleGene, Double> result = engine.stream()
118      *      // Truncate the evolution stream after 5 "steady" generations.
119      *     .limit(bySteadyFitness(5))
120      *      // The evolution will stop after maximal 500 ms.
121      *     .limit(byExecutionTime(Duration.ofMillis(500), Clock.systemUTC())
122      *     .collect(toBestPhenotype());
123      * }</pre>
124      *
125      @since 3.1
126      *
127      @param duration the duration after the evolution stream will be truncated
128      @param clock the clock used for measure the execution time
129      @return a predicate, which will truncate the evolution stream, based on
130      *         the exceeded execution time
131      @throws NullPointerException if one of the arguments is {@code null}
132      */
133     public static Predicate<Object>
134     byExecutionTime(final Duration duration, final Clock clock) {
135         return new ExecutionTimeLimit(duration, clock);
136     }
137 
138     /**
139      * Return a predicate, which will truncate the evolution stream if the GA
140      * execution exceeds a given time duration. This predicate is (normally)
141      * used as safety net, for guaranteed stream truncation.
142      *
143      <pre>{@code
144      * final Phenotype<DoubleGene, Double> result = engine.stream()
145      *      // Truncate the evolution stream after 5 "steady" generations.
146      *     .limit(bySteadyFitness(5))
147      *      // The evolution will stop after maximal 500 ms.
148      *     .limit(byExecutionTime(Duration.ofMillis(500))
149      *     .collect(toBestPhenotype());
150      * }</pre>
151      *
152      @since 3.1
153      *
154      @param duration the duration after the evolution stream will be truncated
155      @return a predicate, which will truncate the evolution stream, based on
156      *         the exceeded execution time
157      @throws NullPointerException if the evolution {@code duration} is
158      *         {@code null}
159      */
160     public static Predicate<Object>
161     byExecutionTime(final Duration duration) {
162         return byExecutionTime(duration, NanoClock.systemUTC());
163     }
164 
165     /**
166      * Return a predicate, which will truncated the evolution stream if the
167      * best fitness of the current population becomes less than the specified
168      * threshold and the objective is set to minimize the fitness. This
169      * predicate also stops the evolution if the best fitness in the current
170      * population becomes greater than the user-specified fitness threshold when
171      * the objective is to maximize the fitness.
172      *
173      <pre>{@code
174      * final Phenotype<DoubleGene, Double> result = engine.stream()
175      *      // Truncate the evolution stream if the best fitness is higher than
176      *      // the given threshold of '2.3'.
177      *     .limit(byFitnessThreshold(2.3))
178      *      // The evolution will stop after maximal 250 generations; guarantees
179      *      // the termination (truncation) of the evolution stream.
180      *     .limit(250)
181      *     .collect(toBestPhenotype());
182      * }</pre>
183      *
184      @since 3.1
185      *
186      @param threshold the desired threshold
187      @param <C> the fitness type
188      @return the predicate which truncates the evolution stream based on the
189      *         given {@code threshold}.
190      @throws NullPointerException if the given {@code threshold} is
191      *        {@code null}.
192      */
193     public static <C extends Comparable<? super C>>
194     Predicate<EvolutionResult<?, C>> byFitnessThreshold(final C threshold) {
195         return new FitnessThresholdLimit<>(threshold);
196     }
197 
198     /**
199      * Return a predicate, which will truncate the evolution stream if the
200      * fitness is converging. Two filters of different lengths are used to
201      * smooth the best fitness across the generations.
202      *
203      <pre>{@code
204      * final Phenotype<DoubleGene, Double> result = engine.stream()
205      *     .limit(byFitnessConvergence(5, 15, (s, l) -> {
206      *          final double div = max(abs(s.getMean()), abs(l.getMean()));
207      *          final eps = abs(s.getMean() - l.getMean())/(div <= 10E-20 ? 1.0 : div);
208      *          return esp >= 10E-5
209      *     }))
210      *     .collect(toBestPhenotype());
211      * }</pre>
212      *
213      * In the example above, the moving average of the short- and long filter
214      * is used for determining the fitness convergence.
215      *
216      <p>
217      <b>API note: </b><em>The returned predicate maintains mutable state.
218      * Using it in a parallel evolution streams needs external synchronization
219      * of the {@code test} method.</em>
220      *
221      @since 3.7
222      *
223      @param shortFilterSize the size of the short filter
224      @param longFilterSize the size of the long filter. The long filter size
225      *        also determines the minimum number of generations of the evolution
226      *        stream.
227      @param proceed the predicate which determines when the evolution stream
228      *        is truncated. The first parameter of the predicate contains the
229      *        double statistics of the short filter and the second parameter
230      *        contains the statistics of the long filter
231      @param <N> the fitness type
232      @return a new fitness convergence strategy
233      @throws NullPointerException if the {@code proceed} predicate is
234      *         {@code null}
235      */
236     public static <N extends Number & Comparable<? super N>>
237     Predicate<EvolutionResult<?, N>> byFitnessConvergence(
238         final int shortFilterSize,
239         final int longFilterSize,
240         final BiPredicate<DoubleMoments, DoubleMoments> proceed
241     ) {
242         return new FitnessConvergenceLimit<>(
243             shortFilterSize,
244             longFilterSize,
245             proceed
246         );
247     }
248 
249     /**
250      * Return a predicate, which will truncate the evolution stream if the
251      * fitness is converging. Two filters of different lengths are used to
252      * smooth the best fitness across the generations. When the smoothed best
253      * fitness from the long filter is less than a user-specified percentage
254      * away from the smoothed best fitness from the short filter, the fitness is
255      * deemed as converged and the evolution terminates.
256      *
257      <pre>{@code
258      * final Phenotype<DoubleGene, Double> result = engine.stream()
259      *     .limit(byFitnessConvergence(5, 15, 10E-4))
260      *     .collect(toBestPhenotype());
261      * }</pre>
262      *
263      * In the given example, the evolution stream stops, if the difference of the
264      * mean values of the long and short filter is less than 1%. The short
265      * filter calculates the mean of the best fitness values of the last 5
266      * generations. The long filter uses the best fitness values of the last 15
267      * generations.
268      *
269      <p>
270      <b>API note: </b><em>The returned predicate maintains mutable state.
271      * Using it in a parallel evolution streams needs external synchronization
272      * of the {@code test} method.</em>
273      *
274      @since 3.7
275      *
276      @param shortFilterSize the size of the short filter
277      @param longFilterSize the size of the long filter. The long filter size
278      *        also determines the minimum number of generations of the evolution
279      *        stream.
280      @param epsilon the maximal relative distance of the mean value between
281      *        the short and the long filter. The {@code epsilon} must within the
282      *        range of {@code [0..1]}.
283      @param <N> the fitness type
284      @return a new fitness convergence strategy
285      @throws IllegalArgumentException if {@code shortFilterSize < 1} ||
286      *         {@code longFilterSize < 2} ||
287      *         {@code shortFilterSize >= longFilterSize}
288      @throws IllegalArgumentException if {@code epsilon} is not in the range
289      *         of {@code [0..1]}
290      */
291     public static <N extends Number & Comparable<? super N>>
292     Predicate<EvolutionResult<?, N>> byFitnessConvergence(
293         final int shortFilterSize,
294         final int longFilterSize,
295         final double epsilon
296     ) {
297         if (epsilon < 0.0 || epsilon > 1.0) {
298             throw new IllegalArgumentException(format(
299                 "The given epsilon is not in the range [0, 1]: %f", epsilon
300             ));
301         }
302 
303         return new FitnessConvergenceLimit<>(
304             shortFilterSize,
305             longFilterSize,
306             (s, l-> eps(s.getMean(), l.getMean()) >= epsilon
307         );
308     }
309 
310     // Calculate the relative mean difference between short and long filter.
311     private static double eps(final double s, final double l) {
312         final double div = max(abs(s), abs(l));
313         return abs(s - l)/(div <= 10E-20 1.0 : div);
314     }
315 
316     /**
317      * A termination method that stops the evolution when the population is
318      * deemed as converged. The population is deemed as converged when the
319      * average fitness across the current population is less than a
320      * user-specified percentage away from the best fitness of the current
321      * population. This method takes a predicate with the <em>best</em> fitness
322      * and the population fitness moments and determine whether to proceed or
323      * not.
324      *
325      @since 3.9
326      *
327      @param proceed the predicate which determines when the evolution stream
328      *        is truncated. The first parameter of the predicate contains the
329      *        best fitness of the population and the second parameter contains
330      *        the statistics of population fitness values
331      @param <N> the fitness type
332      @return a new fitness convergence strategy
333      @throws NullPointerException if the {@code proceed} predicate is
334      *         {@code null}
335      */
336     public static <N extends Number & Comparable<? super N>>
337     Predicate<EvolutionResult<?, N>> byPopulationConvergence(
338         final BiPredicate<Double, DoubleMoments> proceed
339     ) {
340         return new PopulationConvergenceLimit<>(proceed);
341     }
342 
343     /**
344      * A termination method that stops the evolution when the population is
345      * deemed as converged. The population is deemed as converged when the
346      * average fitness across the current population is less than a
347      * user-specified percentage away from the best fitness of the current
348      * population.
349      *
350      @since 3.9
351      *
352      @param epsilon the maximal relative distance of the best fitness value of
353      *        the population and the mean value of the population fitness values.
354      @param <N> the fitness type
355      @return a new fitness convergence strategy
356      @throws IllegalArgumentException if {@code epsilon} is not in the range
357      *         of {@code [0..1]}
358      */
359     public static <N extends Number & Comparable<? super N>>
360     Predicate<EvolutionResult<?, N>>
361     byPopulationConvergence(final double epsilon) {
362         if (epsilon < 0.0 || epsilon > 1.0) {
363             throw new IllegalArgumentException(format(
364                 "The given epsilon is not in the range [0, 1]: %f", epsilon
365             ));
366         }
367 
368         return new PopulationConvergenceLimit<>((best, moments->
369             eps(best, moments.getMean()) >= epsilon
370         );
371     }
372 
373 
374 }