EvolutionResult.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-4.0.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@gmail.com)
019  */
020 package io.jenetics.engine;
021 
022 import static java.util.Objects.requireNonNull;
023 
024 import java.io.Serializable;
025 import java.util.HashSet;
026 import java.util.Objects;
027 import java.util.Set;
028 import java.util.function.Function;
029 import java.util.function.UnaryOperator;
030 import java.util.stream.Collector;
031 import java.util.stream.Stream;
032 
033 import io.jenetics.Gene;
034 import io.jenetics.Genotype;
035 import io.jenetics.Optimize;
036 import io.jenetics.Phenotype;
037 import io.jenetics.internal.util.Lazy;
038 import io.jenetics.stat.MinMax;
039 import io.jenetics.util.Factory;
040 import io.jenetics.util.ISeq;
041 import io.jenetics.util.Seq;
042 
043 /**
044  * Represents a state of the GA after an evolution step. It also represents the
045  * final state of an evolution process and can be created with an appropriate
046  * collector:
047  <pre>{@code
048  * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
049  * final EvolutionResult<EnumGene<Point>, Double> result = Engine.builder(tsm)
050  *     .optimize(Optimize.MINIMUM).build()
051  *     .stream()
052  *     .limit(100)
053  *     .collect(EvolutionResult.toBestEvolutionResult());
054  * }</pre>
055  *
056  @see EvolutionStart
057  @see Engine
058  *
059  @param <G> the gene type
060  @param <C> the fitness type
061  *
062  @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
063  @since 3.0
064  @version 4.0
065  */
066 public final class EvolutionResult<
067     extends Gene<?, G>,
068     extends Comparable<? super C>
069 >
070     implements Comparable<EvolutionResult<G, C>>, Serializable
071 {
072     private static final long serialVersionUID = 1L;
073 
074     private final Optimize _optimize;
075     private final ISeq<Phenotype<G, C>> _population;
076     private final long _generation;
077     private final long _totalGenerations;
078 
079     private final EvolutionDurations _durations;
080     private final int _killCount;
081     private final int _invalidCount;
082     private final int _alterCount;
083 
084     private final Lazy<Phenotype<G, C>> _best;
085     private final Lazy<Phenotype<G, C>> _worst;
086 
087     private EvolutionResult(
088         final Optimize optimize,
089         final ISeq<Phenotype<G, C>> population,
090         final long generation,
091         final long totalGenerations,
092         final EvolutionDurations durations,
093         final int killCount,
094         final int invalidCount,
095         final int alterCount
096     ) {
097         _optimize = requireNonNull(optimize);
098         _population = requireNonNull(population);
099         _generation = generation;
100         _totalGenerations = totalGenerations;
101         _durations = requireNonNull(durations);
102         _killCount = killCount;
103         _invalidCount = invalidCount;
104         _alterCount = alterCount;
105 
106         _best = Lazy.of(() -> _population.stream()
107             .max(_optimize.ascending())
108             .orElse(null)
109         );
110 
111         _worst = Lazy.of(() -> _population.stream()
112             .min(_optimize.ascending())
113             .orElse(null)
114         );
115     }
116 
117     /**
118      * Return the optimization strategy used.
119      *
120      @return the optimization strategy used
121      */
122     public Optimize getOptimize() {
123         return _optimize;
124     }
125 
126     /**
127      * Return the population after the evolution step.
128      *
129      @return the population after the evolution step
130      */
131     public ISeq<Phenotype<G, C>> getPopulation() {
132         return _population;
133     }
134 
135     /**
136      * Return the current list of genotypes of this evolution result.
137      *
138      @since 3.9
139      *
140      @return the list of genotypes of this evolution result.
141      */
142     public ISeq<Genotype<G>> getGenotypes() {
143         return _population.stream()
144             .map(Phenotype::getGenotype)
145             .collect(ISeq.toISeq());
146     }
147 
148     /**
149      * The current generation.
150      *
151      @return the current generation
152      */
153     public long getGeneration() {
154         return _generation;
155     }
156 
157     /**
158      * Return the generation count evaluated so far.
159      *
160      @return the total number of generations evaluated so far
161      */
162     public long getTotalGenerations() {
163         return _totalGenerations;
164     }
165 
166     /**
167      * Return the timing (meta) information of the evolution step.
168      *
169      @return the timing (meta) information of the evolution step
170      */
171     public EvolutionDurations getDurations() {
172         return _durations;
173     }
174 
175     /**
176      * Return the number of killed individuals.
177      *
178      @return the number of killed individuals
179      */
180     public int getKillCount() {
181         return _killCount;
182     }
183 
184     /**
185      * Return the number of invalid individuals.
186      *
187      @return the number of invalid individuals
188      */
189     public int getInvalidCount() {
190         return _invalidCount;
191     }
192 
193     /**
194      * The number of altered individuals.
195      *
196      @return the number of altered individuals
197      */
198     public int getAlterCount() {
199         return _alterCount;
200     }
201 
202     /**
203      * Return the best {@code Phenotype} of the result population.
204      *
205      @return the best {@code Phenotype} of the result population
206      */
207     public Phenotype<G, C> getBestPhenotype() {
208         return _best.get();
209     }
210 
211     /**
212      * Return the worst {@code Phenotype} of the result population.
213      *
214      @return the worst {@code Phenotype} of the result population
215      */
216     public Phenotype<G, C> getWorstPhenotype() {
217         return _worst.get();
218     }
219 
220     /**
221      * Return the best population fitness.
222      *
223      @return The best population fitness.
224      */
225     public C getBestFitness() {
226         return _best.get() != null ? _best.get().getFitness() null;
227     }
228 
229     /**
230      * Return the worst population fitness.
231      *
232      @return The worst population fitness.
233      */
234     public C getWorstFitness() {
235         return _worst.get() != null ? _worst.get().getFitness() null;
236     }
237 
238     /**
239      * Return the next evolution start object with the current population and
240      * the incremented generation.
241      *
242      @return the next evolution start object
243      */
244     EvolutionStart<G, C> next() {
245         return EvolutionStart.of(_population, _generation + 1);
246     }
247 
248     /**
249      * Compare {@code this} evolution result with another one, according the
250      * populations best individual.
251      *
252      @param other the other evolution result to compare
253      @return  a negative integer, zero, or a positive integer as this result
254      *          is less than, equal to, or greater than the specified result.
255      */
256     @Override
257     public int compareTo(final EvolutionResult<G, C> other) {
258         return _optimize.compare(_best.get(), other._best.get());
259     }
260 
261     private EvolutionResult<G, C> withTotalGenerations(final long total) {
262         return of(
263             _optimize,
264             _population,
265             _generation,
266             total,
267             _durations,
268             _killCount,
269             _invalidCount,
270             _alterCount
271         );
272     }
273 
274     @Override
275     public int hashCode() {
276         int hash = 17;
277         hash += 31*Objects.hashCode(_optimize17;
278         hash += 31*Objects.hashCode(_population17;
279         hash += 31*Objects.hashCode(_generation17;
280         hash += 31*Objects.hashCode(_totalGenerations17;
281         hash += 31*Objects.hashCode(_durations17;
282         hash += 31*Objects.hashCode(_killCount17;
283         hash += 31*Objects.hashCode(_invalidCount17;
284         hash += 31*Objects.hashCode(_alterCount17;
285         hash += 31*Objects.hashCode(getBestFitness()) 17;
286         return hash;
287     }
288 
289     @Override
290     public boolean equals(final Object obj) {
291         return obj instanceof EvolutionResult<?, ?> &&
292             Objects.equals(_optimize,
293                 ((EvolutionResult<?, ?>)obj)._optimize&&
294             Objects.equals(_population,
295                 ((EvolutionResult<?, ?>)obj)._population&&
296             Objects.equals(_generation,
297                 ((EvolutionResult<?, ?>)obj)._generation&&
298             Objects.equals(_totalGenerations,
299                 ((EvolutionResult<?, ?>)obj)._totalGenerations&&
300             Objects.equals(_durations,
301                 ((EvolutionResult<?, ?>)obj)._durations&&
302             Objects.equals(_killCount,
303                 ((EvolutionResult<?, ?>)obj)._killCount&&
304             Objects.equals(_invalidCount,
305                 ((EvolutionResult<?, ?>)obj)._invalidCount&&
306             Objects.equals(_alterCount,
307                 ((EvolutionResult<?, ?>)obj)._alterCount&&
308             Objects.equals(getBestFitness(),
309                 ((EvolutionResult<?, ?>)obj).getBestFitness());
310     }
311 
312 
313     /* *************************************************************************
314      *  Some static collector/factory methods.
315      * ************************************************************************/
316 
317     /**
318      * Return a collector which collects the best result of an evolution stream.
319      *
320      <pre>{@code
321      * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
322      * final EvolutionResult<EnumGene<Point>, Double> result = Engine.builder(tsm)
323      *     .optimize(Optimize.MINIMUM).build()
324      *     .stream()
325      *     .limit(100)
326      *     .collect(EvolutionResult.toBestEvolutionResult());
327      * }</pre>
328      *
329      * If the collected {@link EvolutionStream} is empty, the collector returns
330      <b>{@code null}</b>.
331      *
332      @param <G> the gene type
333      @param <C> the fitness type
334      @return a collector which collects the best result of an evolution stream
335      */
336     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
337     Collector<EvolutionResult<G, C>, ?, EvolutionResult<G, C>>
338     toBestEvolutionResult() {
339         return Collector.of(
340             MinMax::<EvolutionResult<G, C>>of,
341             MinMax::accept,
342             MinMax::combine,
343             mm -> mm.getMax() != null
344                 ? mm.getMax().withTotalGenerations(mm.getCount())
345                 null
346         );
347     }
348 
349     /**
350      * Return a collector which collects the best phenotype of an evolution
351      * stream.
352      *
353      <pre>{@code
354      * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
355      * final Phenotype<EnumGene<Point>, Double> result = Engine.builder(tsm)
356      *     .optimize(Optimize.MINIMUM).build()
357      *     .stream()
358      *     .limit(100)
359      *     .collect(EvolutionResult.toBestPhenotype());
360      * }</pre>
361      *
362      * If the collected {@link EvolutionStream} is empty, the collector returns
363      <b>{@code null}</b>.
364      *
365      @param <G> the gene type
366      @param <C> the fitness type
367      @return a collector which collects the best phenotype of an evolution
368      *         stream
369      */
370     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
371     Collector<EvolutionResult<G, C>, ?, Phenotype<G, C>>
372     toBestPhenotype() {
373         return Collector.of(
374             MinMax::<EvolutionResult<G, C>>of,
375             MinMax::accept,
376             MinMax::combine,
377             mm -> mm.getMax() != null
378                 ? mm.getMax().getBestPhenotype()
379                 null
380         );
381     }
382 
383     /**
384      * Return a collector which collects the best genotype of an evolution
385      * stream.
386      *
387      <pre>{@code
388      * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
389      * final Genotype<EnumGene<Point>> result = Engine.builder(tsm)
390      *     .optimize(Optimize.MINIMUM).build()
391      *     .stream()
392      *     .limit(100)
393      *     .collect(EvolutionResult.toBestGenotype());
394      * }</pre>
395      *
396      * If the collected {@link EvolutionStream} is empty, the collector returns
397      <b>{@code null}</b>.
398      *
399      @param <G> the gene type
400      @param <C> the fitness type
401      @return a collector which collects the best genotype of an evolution
402      *         stream
403      */
404     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
405     Collector<EvolutionResult<G, C>, ?, Genotype<G>>
406     toBestGenotype() {
407         return Collector.of(
408             MinMax::<EvolutionResult<G, C>>of,
409             MinMax::accept,
410             MinMax::combine,
411             mm -> mm.getMax() != null
412                 ? mm.getMax().getBestPhenotype() != null
413                     ? mm.getMax().getBestPhenotype().getGenotype()
414                     null
415                 null
416         );
417     }
418 
419     /**
420      * Return a collector which collects the best <em>result</em> (in the native
421      * problem space).
422      *
423      <pre>{@code
424      * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
425      * final ISeq<Point> route = Engine.builder(tsm)
426      *     .optimize(Optimize.MINIMUM).build()
427      *     .stream()
428      *     .limit(100)
429      *     .collect(EvolutionResult.toBestResult(tsm.codec().decoder()));
430      * }</pre>
431      *
432      * If the collected {@link EvolutionStream} is empty, the collector returns
433      <b>{@code null}</b>.
434      *
435      @since 3.6
436      *
437      @param decoder the decoder which converts the {@code Genotype} into the
438      *        result of the problem space.
439      @param <T> the <em>native</em> problem result type
440      @param <G> the gene type
441      @param <C> the fitness result type
442      @return a collector which collects the best result of an evolution stream
443      @throws NullPointerException if the given {@code decoder} is {@code null}
444      */
445     public static <G extends Gene<?, G>, C extends Comparable<? super C>, T>
446     Collector<EvolutionResult<G, C>, ?, T>
447     toBestResult(final Function<Genotype<G>, T> decoder) {
448         requireNonNull(decoder);
449 
450         return Collector.of(
451             MinMax::<EvolutionResult<G, C>>of,
452             MinMax::accept,
453             MinMax::combine,
454             mm -> mm.getMax() != null
455                 ? mm.getMax().getBestPhenotype() != null
456                     ? decoder.apply(mm.getMax().getBestPhenotype().getGenotype())
457                     null
458                 null
459         );
460     }
461 
462     /**
463      * Return a collector which collects the best <em>result</em> (in the native
464      * problem space).
465      *
466      <pre>{@code
467      * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
468      * final ISeq<Point> route = Engine.builder(tsm)
469      *     .optimize(Optimize.MINIMUM).build()
470      *     .stream()
471      *     .limit(100)
472      *     .collect(EvolutionResult.toBestResult(tsm.codec()));
473      * }</pre>
474      *
475      * If the collected {@link EvolutionStream} is empty, the collector returns
476      <b>{@code null}</b>.
477      *
478      @since 3.6
479      *
480      @param codec the problem decoder
481      @param <T> the <em>native</em> problem result type
482      @param <G> the gene type
483      @param <C> the fitness result type
484      @return a collector which collects the best result of an evolution stream
485      @throws NullPointerException if the given {@code codec} is {@code null}
486      */
487     public static <G extends Gene<?, G>, C extends Comparable<? super C>, T>
488     Collector<EvolutionResult<G, C>, ?, T>
489     toBestResult(final Codec<T, G> codec) {
490         return toBestResult(codec.decoder());
491     }
492 
493     /**
494      * Return a mapping function, which removes duplicate individuals from the
495      * population and replaces it with newly created one by the given genotype
496      * {@code factory}.
497      *
498      <pre>{@code
499      * final Problem<Double, DoubleGene, Integer> problem = ...;
500      * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
501      *     .mapping(EvolutionResult.toUniquePopulation(problem.codec().encoding(), 100))
502      *     .build();
503      * final Genotype<DoubleGene> best = engine.stream()
504      *     .limit(100);
505      *     .collect(EvolutionResult.toBestGenotype());
506      * }</pre>
507      *
508      @since 4.0
509      @see Engine.Builder#mapping(Function)
510      *
511      @param factory the genotype factory which create new individuals
512      @param maxRetries the maximal number of genotype creation tries
513      @param <G> the gene type
514      @param <C> the fitness function result type
515      @return  a mapping function, which removes duplicate individuals from the
516      *          population
517      @throws NullPointerException if the given genotype {@code factory} is
518      *         {@code null}
519      */
520     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
521     UnaryOperator<EvolutionResult<G, C>>
522     toUniquePopulation(final Factory<Genotype<G>> factory, final int maxRetries) {
523         requireNonNull(false);
524 
525         return result -> {
526             final Seq<Phenotype<G, C>> population = result.getPopulation();
527             final Seq<Genotype<G>> genotypes = result.getGenotypes();
528             final Set<Genotype<G>> elements = new HashSet<>(genotypes.asList());
529 
530             EvolutionResult<G, C> uniques = result;
531             if (elements.size() < population.size()) {
532                 int retries = 0;
533                 while (elements.size() < population.size() && retries < maxRetries) {
534                     if (!elements.add(factory.newInstance())) {
535                         ++retries;
536                     }
537                 }
538 
539                 uniques = result.with(
540                     Stream.concat(elements.stream(), genotypes.stream())
541                         .limit(population.size())
542                         .map(gt -> population.get(0).newInstance(
543                             factory.newInstance(), result.getGeneration()))
544                         .collect(ISeq.toISeq())
545                 );
546             }
547 
548             return uniques;
549         };
550     }
551 
552     EvolutionResult<G, C> with(final ISeq<Phenotype<G, C>> population) {
553         return EvolutionResult.of(
554             getOptimize(),
555             population,
556             getGeneration(),
557             getTotalGenerations(),
558             getDurations(),
559             getKillCount(),
560             getInvalidCount(),
561             getAlterCount()
562         );
563     }
564 
565     /**
566      * Return a mapping function, which removes duplicate individuals from the
567      * population and replaces it with newly created one by the given genotype
568      * {@code factory}.
569      *
570      <pre>{@code
571      * final Problem<Double, DoubleGene, Integer> problem = ...;
572      * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
573      *     .mapping(EvolutionResult.toUniquePopulation(problem.codec().encoding()))
574      *     .build();
575      * final Genotype<DoubleGene> best = engine.stream()
576      *     .limit(100);
577      *     .collect(EvolutionResult.toBestGenotype());
578      * }</pre>
579      *
580      @since 4.0
581      @see Engine.Builder#mapping(Function)
582      *
583      @param factory the genotype factory which create new individuals
584      @param <G> the gene type
585      @param <C> the fitness function result type
586      @return  a mapping function, which removes duplicate individuals from the
587      *          population
588      @throws NullPointerException if the given genotype {@code factory} is
589      *         {@code null}
590      */
591     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
592     UnaryOperator<EvolutionResult<G, C>>
593     toUniquePopulation(final Factory<Genotype<G>> factory) {
594         return toUniquePopulation(factory, 100);
595     }
596 
597     /**
598      * Return a mapping function, which removes duplicate individuals from the
599      * population and replaces it with newly created one by the existing
600      * genotype factory.
601      *
602      <pre>{@code
603      * final Problem<Double, DoubleGene, Integer> problem = ...;
604      * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
605      *     .mapping(EvolutionResult.toUniquePopulation(10))
606      *     .build();
607      * final Genotype<DoubleGene> best = engine.stream()
608      *     .limit(100);
609      *     .collect(EvolutionResult.toBestGenotype(5));
610      * }</pre>
611      *
612      @since 4.0
613      @see Engine.Builder#mapping(Function)
614      *
615      @param maxRetries the maximal number of genotype creation tries
616      @param <G> the gene type
617      @param <C> the fitness function result type
618      @return  a mapping function, which removes duplicate individuals from the
619      *          population
620      @throws NullPointerException if the given genotype {@code factory} is
621      *         {@code null}
622      */
623     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
624     UnaryOperator<EvolutionResult<G, C>> toUniquePopulation(final int maxRetries) {
625         return result -> {
626             final Factory<Genotype<G>> factory = result
627                 .getPopulation().get(0)
628                 .getGenotype();
629 
630             final UnaryOperator<EvolutionResult<G, C>> unifier =
631                 toUniquePopulation(factory, maxRetries);
632 
633             return unifier.apply(result);
634         };
635     }
636 
637     /**
638      * Return a mapping function, which removes duplicate individuals from the
639      * population and replaces it with newly created one by the existing
640      * genotype factory.
641      *
642      <pre>{@code
643      * final Problem<Double, DoubleGene, Integer> problem = ...;
644      * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
645      *     .mapping(EvolutionResult.toUniquePopulation())
646      *     .build();
647      * final Genotype<DoubleGene> best = engine.stream()
648      *     .limit(100);
649      *     .collect(EvolutionResult.toBestGenotype());
650      * }</pre>
651      *
652      @since 4.0
653      @see Engine.Builder#mapping(Function)
654      *
655      @param <G> the gene type
656      @param <C> the fitness function result type
657      @return  a mapping function, which removes duplicate individuals from the
658      *          population
659      @throws NullPointerException if the given genotype {@code factory} is
660      *         {@code null}
661      */
662     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
663     UnaryOperator<EvolutionResult<G, C>> toUniquePopulation() {
664         return result -> {
665             final Factory<Genotype<G>> factory = result
666                 .getPopulation().get(0)
667                 .getGenotype();
668 
669             final UnaryOperator<EvolutionResult<G, C>> unifier =
670                 toUniquePopulation(factory);
671 
672             return unifier.apply(result);
673         };
674     }
675 
676     /**
677      * Return an new {@code EvolutionResult} object with the given values.
678      *
679      @param optimize the optimization strategy used
680      @param population the population after the evolution step
681      @param generation the current generation
682      @param totalGenerations the overall number of generations
683      @param durations the timing (meta) information
684      @param killCount the number of individuals which has been killed
685      @param invalidCount the number of individuals which has been removed as
686      *        invalid
687      @param alterCount the number of individuals which has been altered
688      @param <G> the gene type
689      @param <C> the fitness type
690      @return an new evolution result object
691      @throws java.lang.NullPointerException if one of the parameters is
692      *         {@code null}
693      */
694     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
695     EvolutionResult<G, C> of(
696         final Optimize optimize,
697         final ISeq<Phenotype<G, C>> population,
698         final long generation,
699         final long totalGenerations,
700         final EvolutionDurations durations,
701         final int killCount,
702         final int invalidCount,
703         final int alterCount
704     ) {
705         return new EvolutionResult<>(
706             optimize,
707             population,
708             generation,
709             totalGenerations,
710             durations,
711             killCount,
712             invalidCount,
713             alterCount
714         );
715     }
716 
717     /**
718      * Return an new {@code EvolutionResult} object with the given values.
719      *
720      @param optimize the optimization strategy used
721      @param population the population after the evolution step
722      @param generation the current generation
723      @param durations the timing (meta) information
724      @param killCount the number of individuals which has been killed
725      @param invalidCount the number of individuals which has been removed as
726      *        invalid
727      @param alterCount the number of individuals which has been altered
728      @param <G> the gene type
729      @param <C> the fitness type
730      @return an new evolution result object
731      @throws java.lang.NullPointerException if one of the parameters is
732      *         {@code null}
733      */
734     public static <G extends Gene<?, G>, C extends Comparable<? super C>>
735     EvolutionResult<G, C> of(
736         final Optimize optimize,
737         final ISeq<Phenotype<G, C>> population,
738         final long generation,
739         final EvolutionDurations durations,
740         final int killCount,
741         final int invalidCount,
742         final int alterCount
743     ) {
744         return new EvolutionResult<>(
745             optimize,
746             population,
747             generation,
748             generation,
749             durations,
750             killCount,
751             invalidCount,
752             alterCount
753         );
754     }
755 
756 }